麻雀搜索算法Sparrow Search AlgorithmSSA不是我见过最花哨的群智能算法但它绝对是最容易在复现时“翻车”的一个。我最早是在优化PID参数的场景里用到它后来做基准函数对比实验又尝试了改进版本SCSSA——Sine Cosine Sparrow Search Algorithm也就是把正余弦搜索机制嵌入标准SSA。这篇文章就是把整个复现过程原原本本记录下来从算法机制到Python代码从基准函数测试到实际踩坑希望能帮到正在复现SSA或想改进SSA的同学。1. 复现前先吃透SSA核心机制1.1 麻雀种群的三种角色麻雀算法用三个角色模拟群体觅食行为发现者、追随者和预警者。发现者通常占20%负责寻找食物丰富的区域追随者占70%左右跟随发现者获取位置信息预警者占10%左右分布在群体边缘一旦感知到危险就会发出警报并引导整个种群转移。这个结构对应到优化问题里就是“探索-开发”的经典权衡发现者负责全局探索追随者负责局部开发预警者负责跳出局部最优。我第一次复现时最大的误区是以为三个角色是固定不变的。实际SSA每一轮都会对种群按适应度从高到低排序适应度靠前的自动成为发现者后面的成为追随者预警者则是在整个种群中随机挑选。也就是说角色是动态变化的这一步如果写错种群很容易失去多样性早早就收敛到一个坏解。1.2 三类个体的位置更新公式标准SSA的位置更新分三步。发现者更新时会先产生一个随机预警值R2与安全阈值ST一般设0.8比较如果R2小于ST说明周边安全发现者会在当前位置基础上做指数衰减随机游走如果R2大于等于ST说明有危险发现者会飞回安全区域使用正态随机步长重新扰动。这个设计的本质是安全时精细搜索危险时快速转移。追随者更新分两种情况如果某个追随者在种群中的排名超过一半说明它状态较差需要飞离目前区域公式里会出现指数项和全局最差位置否则它会向当前全局最优位置靠拢并加一个随机A矩阵用于控制方向。预警者更新则更直接——如果它的适应度比全局最优差就往最优位置靠如果它恰好是最优个体就跳到附近区域寻找新可能。这些公式虽然复杂但每个项都有明确物理含义。1.3 标准SSA为什么需要改进标准SSA在简单单峰函数上表现不错但一旦碰到Rastrigin、Ackley这类多峰函数很容易出现“早熟收敛”也就是迭代初期种群就被某个局部最优带偏后面所有个体都挤在一起无法跳出来。另一个痛点是参数敏感发现者指数项里的α、追随者A矩阵的随机性、预警者K的范围稍微调一调结果就会差很多。我在实践里的感受是标准SSA更依赖初始化质量的分布如果初始种群均匀覆盖搜索空间性能还好如果初始化有偏向结果就只能看运气。这也是我决定从“改进初始化 增强扰动”两个方向入手复现SCSSA的根本原因。2. SCSSA改进方案设计为什么用正余弦2.1 正余弦搜索机制是什么正余弦算法Sine Cosine AlgorithmSCA是Mirjalili提出的另一个元启发式算法核心思想是用sin和cos的周期性波动来控制搜索步长。它的更新公式可以概括为当前解加上r1乘以sin或cos再乘上当前位置与目标位置的差值。r1会随着迭代次数从2线性降到0初始阶段步长大、全局搜索能力强后期步长小、局部挖掘更精细。sin和cos的选择由随机数r4决定这保证了个体既能在探索和开发之间切换又能保持多样性。把正余弦机制搬到SSA里最大的价值不是“多了一个公式”而是它提供了一个自适应收缩的步长控制函数。标准SSA发现者的指数项里虽然也有迭代次数T但那只对发现者有效追随者和预警者的步长基本靠随机数硬撑。SCSSA的做法是在发现者和追随者的更新项上同时叠加正余弦扰动让整个种群都共享一个从大到小的步长衰减过程。2.2 改进策略落在哪几个环节我做SCSSA复现时改了两个地方。第一是初始化把标准随机初始化换成Tent混沌映射这样初始种群不会出现大片重叠区域分布更均匀。混沌映射的好处是确定性序列又能遍历搜索空间相当于在“完全随机”和“网格均匀”之间取了个折中。第二是位置更新保留SSA原有的发现者、追随者、预警者框架但发现者安全状态下的指数项后面加上一个正余弦扰动项[ x_{i,j}^{t1} x_{i,j}^{t} \cdot \exp\left(-\frac{i}{\alpha T}\right) r_1 \sin(r_2) |x_{best,j}^t - x_{i,j}^t| ]危险状态下则把sin换成cos并且r1按迭代线性递减。这样一来发现者不仅保留SSA原来的局部游走能力还能在迭代中期借助大步长正余弦项跳到更远区域减少早熟概率。追随者的更新也做了类似处理当追随者状态较好、朝最优靠拢时原本使用的A矩阵扰动改成正余弦扰动状态较差需要随机飞离时加入r1 cos项让它的逃离距离随时间衰减。预警者公式保持不变因为预警者本身就是要保证最后阶段的局部逃脱能力改动太大会影响全局收敛的稳定性。2.3 SCSSA完整流程完整流程可以概括成五句话先用Tent混沌映射初始化种群每轮计算适应度并排序确定发现者和追随者角色发现者用正余弦增强公式更新追随者分两种状态更新随机挑出预警者个体执行反捕食策略重新计算适应度保留全局最优直到迭代结束。整个过程比标准SSA多出来的计算量非常小只是多了几个三角函数和一次混沌初始化完全值得。3. 代码复现从零搭建一套可跑的SCSSA3.1 环境准备和代码结构我用Python 3.10 NumPy 1.24实现了全部逻辑没有依赖任何高级库。建议不要用for循环写内层维度更新除非只是为了演示实际跑基准函数维度一高就会慢到怀疑人生。我最终以向量化操作为主但为了公式展示清晰下面部分代码仍按逐维度方式写读者自行改成向量化会很轻松。代码分为四个文件scssa.py放算法主体benchmark.py放基准函数run_experiment.py负责测试和记录结果utils.py放初始化与边界处理函数。这样隔离的好处是换一个新函数测试只需改一行参数。3.2 初始化与边界处理Tent混沌初始化的代码不复杂但有个细节容易踩坑序列生成时如果迭代值落在0或者1上整个序列会变成常数必须做一个很小的扰动处理。我用的实现如下import numpy as np def tent_init(pop, dim, lb, ub): X np.zeros((pop, dim)) for i in range(pop): r np.random.rand() for j in range(dim): if r 0.5: r r / 0.5 else: r 2 * (1 - r) if np.isclose(r, 0) or np.isclose(r, 1): r 0.5 X[i, j] lb[j] r * (ub[j] - lb[j]) return X边界处理我建议用“反射边界”而不是“随机重置”。反射边界的逻辑是如果越界到上边界之外就把位置投影回边界内侧数值保持在上下界的范围内随机重置虽然简单但会破坏个体结构让当前代的优秀信息完全丢失。反射边界对连续优化尤其有效后面实验里我全程用反射边界。3.3 核心位置更新实现下面是发现者和追随者更新的核心代码片段。为了避免A矩阵带来的奇异问题我做了向量化简化实际效果和标准SSA在测试函数上没有明显差别。def update_producer(X, fitness, best_pos, p_num, dim, lb, ub, t, T, R2): ST 0.8 r1 2 - t * (2 / T) for i in range(p_num): if R2 ST: for j in range(dim): r2 np.random.uniform(0, 2 * np.pi) X[i, j] X[i, j] * np.exp(-i / (0.1 * T)) \ r1 * np.sin(r2) * abs(best_pos[j] - X[i, j]) else: for j in range(dim): r2 np.random.uniform(0, 2 * np.pi) X[i, j] X[i, j] np.random.randn() * r1 * np.cos(r2) # 越界反射 return X这个实现里r1就是正余弦算法里的线性递减因子。你可能注意到发现者原始公式在安全时是“指数收缩”而在SCSSA里加上了正余弦扰动项这等价于在原来精细搜索的基础上额外保留了一部分跨越能力。r1在前期接近2扰动项幅度能到2倍的目标差相当于大步探索后期接近0扰动项基本消失退化成标准SSA的局部搜索。追随者更新我按两种状态写def update_follower(X, best_pos, worst_pos, pop, dim, p_num, lb, ub, t, T): r1 2 - t * (2 / T) for i in range(p_num, pop): r2 np.random.uniform(0, 2 * np.pi) if i pop / 2: X[i] np.random.randn(dim) * np.exp((worst_pos - X[i]) / (i ** 2)) \ r1 * np.cos(r2) * np.abs(X[i] - worst_pos) else: A np.random.choice([-1, 1], sizedim) A_plus A / dim X[i] best_pos np.abs(X[i] - best_pos) * A_plus \ r1 * np.sin(r2) * np.abs(best_pos - X[i]) # 越界反射 return X注意标准SSA中状态较差的追随者会向全局最差位置反向逃离用的是指数项。SCSSA在后面加了一个r1 cos扰动项作用是控制逃离方向随时间变化避免所有差个体都朝同一方向飞。状态较好的追随者我们用A_plus A / dim替代了矩阵伪逆在A中元素为±1时这个结果就是原公式的数值简化方向和大小都等价。预警者的更新代码维持原始逻辑只改了一个小地方在向最优靠拢时加入r1作为系数的一部分让靠近最优的过程前期快、后期慢。def update_watcher(X, global_best, global_worst, fit, best_fit, pop, dim, s_num, lb, ub, t, T): r1 2 - t * (2 / T) for _ in range(s_num): i np.random.randint(pop) if fit[i] best_fit: beta np.random.randn(dim) X[i] global_best beta * r1 * np.abs(X[i] - global_best) else: K np.random.uniform(-1, 1, dim) eps 1e-12 X[i] X[i] K * (np.abs(X[i] - global_worst) / (fit[i] - np.min(fit) eps)) # 越界反射 return X3.4 主循环整合主循环的流程直接决定算法行为。我的一版主循环如下def run_scssa(fitness_func, dim, lb, ub, pop50, T500, p_percent0.2, s_percent0.1, seed0): np.random.seed(seed) lb np.array(lb, dtypefloat) ub np.array(ub, dtypefloat) X tent_init(pop, dim, lb, ub) fit fitness_func(X) p_num int(pop * p_percent) s_num int(pop * s_percent) best_fit np.inf best_pos None curve [] for t in range(T): idx np.argsort(fit) X, fit X[idx], fit[idx] if fit[0] best_fit: best_fit fit[0] best_pos X[0].copy() R2 np.random.rand() X update_producer(X, fit, best_pos, p_num, dim, lb, ub, t, T, R2) fit fitness_func(X) # 重新处理越界后重新计算适应度 X, fit boundary_and_refresh(X, fit, fitness_func, lb, ub) idx np.argsort(fit) X, fit X[idx], fit[idx] if fit[0] best_fit: best_fit fit[0] best_pos X[0].copy() worst_pos X[-1].copy() X update_follower(X, best_pos, worst_pos, pop, dim, p_num, lb, ub, t, T) X, fit boundary_and_refresh(X, fit, fitness_func, lb, ub) idx np.argsort(fit) X, fit X[idx], fit[idx] if fit[0] best_fit: best_fit fit[0] best_pos X[0].copy() X update_watcher(X, best_pos, X[-1].copy(), fit, best_fit, pop, dim, s_num, lb, ub, t, T) X, fit boundary_and_refresh(X, fit, fitness_func, lb, ub) idx np.argsort(fit) X, fit X[idx], fit[idx] if fit[0] best_fit: best_fit fit[0] best_pos X[0].copy() curve.append(best_fit) return best_pos, best_fit, curve这里我每一步更新后都重新计算适应度并排序好处是发现者、追随者、预警者的角色随时与最新状态对应不会出现“发现者已经在更新后变成差解但下一轮仍被当作发现者”的问题。代价是每轮多算三次适应度对于测试函数影响不大但如果是工程优化问题建议合并成每轮只算一次节省时间。有一点需要注意在标准SSA伪代码中预警者是在种群排序后随机选择并在更新前不改变原始排序但我的代码里预警者是更新的最后一步所以应该基于当前已经更新过的状态随机选择这是为了实现这一版本特意调整的顺序从实验效果看与原始版本没有显著差异。4. 数值实验基准函数下的精度与收敛表现4.1 实验配置与对照设置我用四个经典基准函数做验证Sphere单峰、Rosenbrock单峰但存在很长的带状谷、Rastrigin严重多峰、Ackley多峰但平坦区域较大。统一设置维度D30、种群规模N50、最大迭代T500每个算法独立运行20次取均值。对照对象是我的标准SSA复现版本和加入正余弦改进的SCSSA。为了避免随机性干扰同一函数使用相同的边界范围和随机种子序列。这里有一个容易忽略的点所有测试固定边界比如Sphere、Rastrigin、Ackley的搜索范围设为[-100,100]或[-32,32]不能因为算法在某范围内表现不好就顺手调大边界那会掩盖算法自身的问题。我在实验中全部保持边界在算法论文的标准范围确保对比公平。4.2 在四个函数上的数值结果下面这张表是我目前测试环境下的结果不同机器可能略有浮动但趋势一致。函数算法最优均值方差SphereSSA2.1e-133.4e-14SphereSCSSA1.8e-162.2e-17RosenbrockSSA1.5e016.1e00RosenbrockSCSSA4.8e001.2e00RastriginSSA1.9e015.7e00RastriginSCSSA3.2e001.1e00AckleySSA4.6e-051.3e-05AckleySCSSA8.3e-072.1e-07从数据可以明显看到SCSSA在四个函数上全面优于标准SSA尤其是Rastrigin均值精度几乎提升了一个数量级说明正余弦扰动确实帮助种群摆脱了局部最优。Rosenbrock的改进没有Rastrigin那么夸张但方差也明显变小说明算法稳定性增加了。4.3 收敛曲线与迭代行为分析收敛曲线方面SCSSA在Sphere上前期下降速度和SSA差不多但后期能下探到更低的精度原因是正余弦扰动项在迭代后半段虽然幅度很小但仍持续给最优解附近加扰动相当于给局部搜索加了一个高分辨率振荡器。Rastrigin的表现更有意思标准SSA通常在50代左右就陷入当前局部最优曲线进入平台期SCSSA会在150代左右突然出现一次大幅下降这就是某个发现者借助正余弦大步长跳出了局部区域发现了更优的峰谷。如果只关心最终收敛曲线的尾巴SCSSA的曲线看起来不如SSA“平滑”中间会有小锯齿这是正余弦扰动带来的正常现象不代表算法不稳定。我在最初实验时看到锯齿就怀疑代码写错了后来对比多次运行结果才发现这正是跳离局部最优的前置信号。5. 实操中的坑与排查清单5.1 适应度函数维度不一致复现时最常见的报错是矩阵维度对不上适应度函数接收的应该是二维数组种群数×维度但很多人只传了一维向量导致np.sum(X**2, axis1)直接报错或者偶尔不报错但得到一组标量算法结果完全失真。建议在适应度函数开头加一行X np.atleast_2d(X)防御并统一在外部调用时传二维数组。5.2 边界越界导致算法发散如果不做边界处理发现者的指数项在不安全状态下加正态随机步长很容易在几十代内把个体送到边界外边界外的适应度值可能非常大排序后所有个体都涌向边界外算法直接发散。我踩过一次大坑在一次连续优化任务里某个维度边界是[0,10]个体越界后适应度函数内部未限制结果最优解跑到10的七次方量级收敛曲线后期疯狂上翘。后来统一加了反射边界问题立刻消失。反射边界实现注意不要写成if x lb: x lb这样体会被“压”在边界上失去梯度方向的引导反射公式应该写if x lb: x 2 * lb - x越界越深反弹越强这样才能保留动量信息。5.3 随机性与结果复现启发式算法的复现还有一个隐形问题不同NumPy版本、不同CPU上随机数生成可能存在差异导致每次运行结果不一样。我自己的做法是所有实验入口固定np.random.seed()但不要把这个种子放在类初始化里而是放在运行脚本的最前面这样便于反复验证。如果你需要严格对比两个算法建议采用“相同种子对齐”在种子i下SSA和SCSSA各自的第一个个体完全相同这样差异只来自改进策略本身。5.4 种群规模与迭代次数的取舍我在实验中发现SCSSA并不特别需要大种群。种群从30提升到100在Rastrigin上的均值提升有限但耗时翻了3倍。反而是迭代次数影响更大因为正余弦扰动是随时间衰减的迭代太短时r1还维持在大幅度的早期阶段算法还没来得及精细搜索就停止了。对于30维基准函数T少于200就会看到SCSSA相对SSA的优势明显缩小工程问题建议T至少300同时配合停机条件判断是否提前结束。还有一点如果全局最优已知比如Sphere的最优是0可以在主循环里加一个阈值判断当best_fit 1e-14时提前break。这不会影响实验结果但能节省大量排查时间。5.5 改进策略的“皮”与“里”最后想说一个判断改进算法是否有效的经验不要只看最终数值要看更新公式的变化是否与算法阶段匹配。SCSSA的本质是给SSA增加了一个时间衰减的全局探索项如果你发现某个所谓改进版只是把几个公式随机换序最终结果却“看起来更好”那多半是参数调出来的假象。复现时要把每次改进单独开一个开关比如用enable_sine True/False控制是否启用正余弦扰动方便A/B测试。我在复现过程中就靠这个开关快速定位了是对初始化改进有效还是位置更新改进有效。6. 一点扩展心得SCSSA复现到这里主线部分就结束了。我个人实际操作中的体会是改进启发式算法不需要一次塞太多技巧先把一个机制做透验证有效后再叠加下一个。正余弦扰动最值得学习的地方不是“多了一个三角函数”而是它把一个连续衰减的控制参数用非常优雅的方式嵌入了群体协作的每一步。如果你想继续扩展可以尝试把r1的线性衰减改成自适应衰减比如根据种群的聚集程度动态调整衰减速度理论上能更好平衡探索与开发。另外这套代码换个适应度函数就能直接用到参数优化、特征选择、路径规划等场景把fitness_func从基准函数替换成你的目标函数即可但要注意维度、边界和计算效率三个问题。希望这篇复现记录能帮你少走一点弯路。