★ FEATURED ARTICLE CEC2024 的排名表出来以后优化算法圈子里的讨论热度一直没降。这次大家反复提到的名字很长叫 mLSHADE-RL。乍一看像是一连串字母的堆叠拆开其实很清晰m 表示多操作器集成LSHADE 是自适应差分进化家族的现代版本RL 也不是强化学习的那个 RL而是 Restart重启和 Local Search局部搜索的组合。简单说这套算法是在 LSHADE 的骨架上加了多策略并存、退化重启和局部精化三套机制在 CEC2024 单目标实数优化竞赛里拿到了第一梯队的名次。如果你平时做数值优化、调机器学习模型的超参数、做工程里的黑箱参数标定或者单纯对进化算法怎么在竞赛里脱颖而出感兴趣这篇都值得看完。我会从算法家族谱系讲起把多算子在做什么、重启为什么有用、局部搜索怎么接进全局搜索讲清楚最后再说说我实际移植和复现这类算法时的经验。1. 先把这个名字拆明白从 DE 到 LSHADE 的演进逻辑1.1 差分进化算法骨架为什么能活这么多年mLSHADE-RL 属于差分进化DE家族。DE 的思路非常朴素先在解空间里随机撒一群候选解每个个体代表一个可行解然后用“当前位置加上另外两个个体的差值”来产生扰动生成试验解接着对比父代和子代谁更好保留好的。经典的变异公式是 DE/rand/1也就是从种群中随便抽三个不同个体用其中两个的差来扰动第三个的缩放版本v x_r1 F × (x_r2 − x_r3)这里 F 是缩放因子控制扰动的强度。生成 v 之后再和某个个体做交叉把部分维度混进来形成试验解 u最后用贪心选择决定是否替换父代。这套机制强就强在它几乎不需要目标函数的梯度信息也不要求函数有解析形式所以特别适合黑箱优化。但原始的 DE 有一个大问题F 和交叉概率 CR 对齐两个参数在不同问题或不同阶段差距悬殊。有的阶段需要探索新区域F 要大有的阶段需要细调F 要小。固定参数极容易不稳定。1.2 SHADE 的贡献给参数装一个“历史记忆”后来提出的 SHADE 解决了这个问题。它的核心思想是参数不应该我们猜而应该从历史成功经验里去采样。具体的做法是维护一个档案memory存着若干组历史成功的 F 和 CR。每一代产生新个体时从档案里随机选一组参数加一点小扰动然后用这组参数去做变异交叉。等这一代的个体生成并完成选择之后把确实让子代变好的 F 和 CR 重新放回档案覆盖掉旧记录。这样参数就变成了一个随问题地形自动调节的循环。遇到平坦区域时档案里成功参数自然会倾向更大的扰动幅度遇到狭窄的峡谷地形时成功参数会变小。你不用一遍遍去调参算法自己会学着适应。1.3 LSHADE 的 L种群规模也开始动态变化SHADE 再进一步就是 LSHADE多出来的这个 L 是指线性种群缩减Linear Population Size Reduction。进化算法前期需要大种群来铺开探索后期其实不需要那么多个体在同一个盆地附近挤来挤去。LSHADE 的做法非常粗暴也极其有效种群规模从初始值 Nmax 按线性关系一路降到最小值 Nmin。假设最大评估次数是 FES那么每一代结束之后按当前已用评估次数占的比例去缩减种群把较差的个体直接淘汰把剩下的评估资源留给更优的个体做精细化搜索。这一步看上去简单效果却非常明显。同样预算下后期种群变小等于其他个体留下更多评估次数在最后阶段能把精度推得更高。这也是 LSHADE 家族在多个竞赛年份里稳定拿好名次的重要原因之一。1.4 mLSHADE-RL 到底加了什么弄清楚 LSHADE 之后mLSHADE-RL 的名字就容易理解了它在原先 LSHADE 框架之上又做了三个改造。第一个是 mmulti-operator多操作器。原来的 LSHADE 虽然 F 和 CR 能自适应但变异策略通常只有一种主要是 current-to-pbest/1。这个策略在多数地形下表现不错可一旦遇到极其复杂的组合地形单策略的劣势就会暴露。m 表示同时维护一个策略池里面放着几种不同倾向的变异策略算法根据实时效果去动态分配选择概率。第二个是 RRestart重启。进化算法最常见的悲剧是前期太早收敛种群缩成一个点后来再怎么变异都跳不出局部最优。重启就是检测到这种病态之后干脆把大部分个体重新随机初始化让种群重新获得多样性。第三个是 LLocal Search局部搜索。进化算法的强项是全局扫描弱项是后期精修。局部搜索机制会在预算接近上限时把一部分评估次数留给最优个体周边的一个小局部极小化模型把最后一点精度挖出来。三件事各自不复杂但要把它们协调进同一个框架里在竞赛规则下拿到稳定成绩牵扯的细节比从名字看起来多得多。2. 多操作器集成的真正意义单一优势打不赢所有地形2.1 每种变异策略都有“舒适区”很多刚开始用进化算法的人会陷入一个误区觉得变异策略越激进越好或者认为 current-to-pbest 在所有问题上都优于 rand/1。实际上每种策略在某一类地形上有明显优势换一个函数族就可能水土不服。拿最常见的两种说DE/rand/1 的探索性强因为扰动来源完全是随机的三个个体不依赖当前最优碰到多峰函数时不容易被某个局部最优带偏但是到了后期它完全不会朝着有希望的区域靠拢精度提升很慢。current-to-pbest/1 则相反它让每个个体都朝当前种群的前 p 个优秀个体方向变异收敛速度很快可遇到欺骗性比较强的函数容易被错误的“优秀个体”引到坑里。工程上碰到的黑箱问题不会告诉你它属于哪一类地形。如果只选一种策略等于提前赌地形类型。算对了是运气算错了就得吞下早熟或者收敛过慢的结果。2.2 策略池怎么搭平衡探索、开发和局部逼近mLSHADE-RL 的做法是备好几个策略具体组合根据竞赛论文描述一般会包含探索型、开发型、均衡型三个方向的代表。我按常见套路给一个参考搭配current-to-pbest/1基础开发型保证快速向有希望的个体靠拢。rand/1纯探索型防止所有个体挤在同一盆地。current-to-rand/1无交叉才做旋转不变变体适合处理某些坐标轴相关混合函数。这几种策略的 F 和 CR 可以共享同一套 SHADE 历史记忆机制也可以分开维护各自的历史。分开维护的好处是策略本身没有混淆参数采样过程中看不出问题代价是内存占用稍高但一般也就几十个浮点数完全可接受。2.3 在线选择概率不能靠“感觉”分配策略池里放了三个策略不等于每代平均采样。选谁不选谁要靠实时反馈来定。多数现代实现采用基于成功率的奖励更新机制每个策略统计自己在过去窗口中贡献了多少个能够成功替换父代的个体根据这个贡献比例用类似 softmax 的方式更新下一轮被选中的概率。细节上有几个常见坑奖励窗口太短更新频率过快策略概率会震荡算法会变得神经质。奖励窗口太长策略概率反应迟钝早期表现差但后期可能有用的策略会被过早淘汰。只统计成功率不统计成功率大小会把“小幅微调成功”当成和“大跨度跳变成功”同等重要的奖励。一个更稳的经验是奖励值用成功次数和提升幅度的乘积或者至少把提升比例分档计分而不是 0/1 二值。我在自己实现多算子框架时最初就是只统计替换次数结果某个策略总是以非常小的幅度成功替换导致概率持续上升最后变成一个“温水策略”整体收敛速度反而被拖慢。2.4 集成带来的代价监控变量变多调试也变得更难多操作器不是免费的。每个策略都有自己的参数状态、成功统计、概率权重算法的有效超参数从两三个变成七八个。不过大部分参数不用手动调像学习率和窗口长度这类可以设成相对安全的默认值。真正要注意的是策略池之间的调度不是一味增加策略就好。我也见过一些实现把七八种策略堆进池子里结果多数策略在多数时间段概率趋近于零纯属浪费评估预算。好的策略池贵精不贵多三个倾向互补的策略通常就足够。这个道理和工程里做多模型集成很像集成收益来自成员之间的相关性两个几乎一模一样的模型集成不如一个模型加一个简单的随机搜索器。3. 重启机制算法退化时干脆推倒重来3.1 进化算法最怕的不是收敛慢而是“伪早熟”大部分差分进化变体早期探索能力都不错真正容易出问题的地方是中期。如果种群多样性下降得太快个体全部集中在一个局部最优周围后续再怎么变异都相当于在这个局部区域做小范围抖动。这种情况下你很难通过调参救回来因为多样性已经没了。这个概念叫早熟收敛。但我在实际调试中很容易把“早熟”和“正常收敛”搞混。一个个体确实有可能正在一个很好的盆地里精确度还在缓慢爬升你乱判定为早熟然后大量重新初始化反而把这个好盆地丢了。所以关键是设计一套可靠的触发条件而不是简单看某个指标低就触发。3.2 触发条件怎么定多样性和停滞信号结合比较通用的方案是同时盯两类指标。一类是种群空间分布的多样性指标。最简单的是把所有个体两两距离求平均或者统计前 p 个最优个体之间的平均成对距离再除以当前搜索空间的直径。当这个比值掉到一个阈值以下比如小于 10 的负几次方数量级就判定多样性过低。另一类是停滞信号。记录最优个体在过去 K 代里更新了多少次。如果连续十几代甚至几十代都没有一个像样的改进说明当前区域的推进力已经接近耗尽。在 mLSHADE-RL 一类的现代实现里更常见的做法是结合多个指标做表决多样性确实低了同时最强个体的改进幅度也趋近于零这才触发重启。如果只看多样性低就重启很容易误伤正常收敛。3.3 重启不是“全部重来”而是“带着记忆重来”一个常见且错误的重启实现把整个种群重新随机撒一遍唯一保住的是全局最优个体。这个方案虽然简单却会把已经学到的有效搜索区域信息全部丢掉。更好的处理方式是分两类个体处理最优个体及其少量副本完全保留继续在原位置做精细搜索。其余个体并非在整个搜索空间完全均匀随机而是有一部分在全局均匀随机另一部分在最优个体周边按一定半径做高斯扰动重新生成。这样做的好处是如果当前最优解已经处在一个较好的局部区域重启之后还能有一部分个体在这个区域附近细挖同时又有足够的全局探索力去寻找未知的更好盆地。这种“全局洒点加局部撒点”的组合在经验上远胜于纯粹全部重新均匀初始化。3.4 重启次数控制和预算分配重启也不是无限次越好。每次重启需要重新采样、重新收敛这个过程本身消耗评估预算。如果预算已经消耗了 80% 再来一次全局重启后续个体几乎没有时间重新寻找新盆地再收敛可能还不如待在原局部最优继续搜索。竞赛类算法一般会在预算前端、中端各设一个重启窗口后端基本不重启只做局部搜索。我在自己的实验里也有类似结论重启发生在预算前 40% 通常收益明显发生在预算后 40% 风险远大于收益。道理很简单前中期重振多样性还能把剩下的预算花在刀刃上后期重来等于拱手放弃已经积累的信息。4. 局部搜索全局算法不擅长把解“磨光”4.1 进化算法的精度天花板黑箱优化里一个很普遍的观察是以群体为基础的进化算法在全局搜索方面表现惊人但在局部精化方面不行。原因是进化算法的变异步长再小也受限于种群中个体之间的差分距离。当所有个体都聚集在一个极小区域内差分向量本身的幅度就变得非常小变异扰动可能还不如浮点误差大。另一个问题是评估预算的分配方式。进化算法要把预算分给所有个体即使到了后期种群规模已经缩小单个个体分到的评估次数还是远不如专门做个局部优化器。这就像用大扫帚扫操场覆盖面很大但扫不干净每个角落局部搜索就是换成小刷子专门对付最后那点灰尘。4.2 局部搜索通常用什么模型竞赛级别的局部搜索才不会老老实实做一维一维的坐标扫描那样效率太低。常见做法是在当前最优解附近执行一个简化的局部优化过程比如单纯形法Nelder-Mead利用反射、扩张、收缩操作逼近局部极小。坐标循环搜索沿着每个维度轴逐步缩小步长适合维度不高的情况。伪造梯度下降用差分代替梯度做近似的下降方向。其中 Nelder-Mead 是很多人最早会想到的因为它实现简单、不依赖梯度。不过要注意单纯形法在高维问题上容易退化维度超过 30 之后效果明显变差。高维场景反而更常见的是用小步长的坐标循环加自适应步长衰减。mLSHADE-RL 这类算法里的局部搜索不会在每一代都启用而是设置一个触发时机通常是预算使用比例达到某个阈值之后每隔一定评估次数就做一轮局部搜索。每一轮局部搜索占用的评估次数也有上限比如预算的 5% 到 10%。4.3 局部搜索和重启机制的协调这一块是实际实现中最容易乱的地方因为重启和局部搜索的需求相反重启要把个体散开局部搜索要把个体聚拢。如果调度不好前脚刚把种群散开后脚就被局部搜索又拉回同一个点。我见过一个比较稳的协调策略把整个优化过程按评估预算分成两段前一段以全局探索和多算子调度为主只在多样性极低但又有理由相信还没收敛时做重启后一段禁止重启只允许局部搜索集中精力把当前最优解磨到极致。两段之间可以有一个相对短的缓冲区域视情况决定是否做最后一次小范围重启。竞赛里很多函数的最终精度就是从这种后段局部搜索里挤出来的。尤其对于单峰函数和复合函数全局算法跑到后期提升幅度很慢一次设计得当的 Nelder-Mead 或者坐标循环可能直接在最优点位数上带来一到两个数量级的提升。4.4 局部搜索的停止条件别设太紧做局部搜索时常见问题是把收敛阈值设得太严导致局部搜索占用大量评估次数。实际上局部搜索的停止条件应该跟整体预算挂钩连续多轮局部搜索改善幅度低于某个相对值就立刻收手把评估次数还给主算法。可以这么设局部搜索每轮最多用 M 次评估连续 T 次没有产生超过相对提升阈值 δ 的改进就停止。δ 通常用“当前最优值 × 1e-6 左右”做基准不要用绝对数值因为不同函数量级差异太大绝对阈值会失效。具体到实现时我记得最容易踩的坑是局部搜索只记录了目标函数值下降的步数却没有检查它是否真的更新了全局最优。搜索过程可能在一个小范围里空转了很长时间最优解并没有改进。所以每次局部搜索结束以后一定要判断“有没有让全局最优跳升”和“消耗的相对预算比”这两个值再决定下一轮要不要继续做。5. CEC2024 的测试环境为什么这个组合能赢5.1 竞赛规则决定了算法的设计取向CEC2024 的单目标实数优化竞赛题目沿用了这个系列一贯的思路一组包含了单峰、多峰、混合、复合等不同地形特征的函数维度从低到高分布。参赛算法的每次运行有一个固定的最大评估次数预算通常是 D 维度的某个常数倍数。最终排名看算法在所有测试函数上的平均表现排名。这个规则非常贴近真实工程预算有限目标函数未知必须在有限评估次数内找到尽量好的解。这就让只在一个函数族上强劲、但在另一个函数族上崩盘的“偏科型”算法很难拿到好总名次。mLSHADE-RL 能赢恰恰因为它的三套机制覆盖了三个不同阶段的失败模式多算子覆盖地形多样性重检索防止早期失败局部搜索为后期精度兜底。5.2 前中后三阶段的“接力”设计把整个优化过程比作一支接力队第一棒是多算子。不同策略在初期轮番上阵快速识别出哪些地形特征占主导把参数适应到合适的方向把有效搜索区域铺满整个解空间。第二棒是重启加动态种群缩减。如果第一个阶段出现了早熟重启机制会咬住不放及时把种群从局部最优里拔出来。正常收敛时种群规模线性下降把评估预算集中给领先个体。第三棒是局部搜索。最后阶段几乎不再期待找到新盆地只求在已有最优解附近做精修把误差压到最低。这三个机制单独拎出来任何一个都不算新发明。但在 CEC2024 的函数组上它们组成的整体非常稳健。竞赛测试函数里既有平滑的单峰函数也有严重旋转偏移的复合函数还有混合了多个子结构的混合函数单纯靠一种策略或者一种机制很难全照顾到。5.3 排名看的不是“峰值能力”是“稳健下限”竞赛评估通常要看多次独立运行结果再用均值、方差或者中位数来排名。这就意味着一个算法不能指望某次运行运气爆棚拿到最好成绩必须保证绝大多数运行都表现稳定。多算子在这里的价值很隐蔽策略池的存在降低了对地形先验的敏感性。无论这个函数内部结构偏旋转还是偏可分离池中至少有一个策略大概率能匹配上。配合在线概率更新算法很快就把选择倾向转移到有效策略上。重启的意义也类似。它保证的是“下限”即使前期走歪了中期还有机会纠正不至于一次性崩盘。局部搜索则是“上限”在正确收敛的前提下尽力冲高。下限保底、上限冲刺的组合正是很多工程问题里真正需要的。5.4 和 LSHADE 相比改进了什么如果和经典 LSHADE 对比差异很清晰。经典的 current-to-pbest 单一策略在多数基准函数上表现不错但在某些复合函数的子结构交界处容易失衡有的维度还在大范围探索有的维度已经收敛到头而单一策略无法兼顾。mLSHADE-RL 把这种失衡问题拆给多个策略去各司其职再用重启做二次保险。经典 LSHADE 后期精度不足的问题则由局部搜索补上。整体来看它不是颠覆性的新算法而是把已知手段以不错的工程水平封装进了同一个框架。竞赛里这种“稳中求进”的改良路线往往比空有一个惊艳想法但稳定性差的算法更有优势。6. 移植到自己的项目里的工程体会6.1 复现与改造步骤建议我对 S 组建议如果你也想在自己的优化任务里参考 mLSHADE-RL 的思路不必一上来就完整复刻所有机制可以按下面的顺序渐进式引入。先实现一个基础版 LSHADE。确认你已经具备参数历史记忆机制和线性种群缩减这两项是整个框架的地基。用标准测试函数跑一轮确保结果跟已发表数据量级一致。连 LSHADE 都还没跑稳就往上加模块出了 bug 根本定位不到是哪个机制的问题。再引入多算子池。给当前算法加第二个变异策略设计一套简单的窗口统计机制观察两个策略的概率变化是否合理在一个明确偏好开发的问题上开发型策略概率是否自然占优确认之后再加第三个策略。然后加重启机制。把多样性指标计算出来加日志观察未加重启的正常收敛过程中指标大致落在什么范围。把这个范围作为重启阈值的重要参考。很多论文给的阈值范围如果不结合你自己算法的实际曲线去校准基本不可直接用。最后加局部搜索。先在低维问题比如 10 维以下验证局部搜索是否真的能稳定提升精度再往高维扩展。局部搜索一个结束就要记录一次全局最优的跳变情况避免空转。6.2 最容易踩的四个坑参数记忆和策略池共享还是分离的问题。方案 A 是共享一套 F/CR 历史记忆实现简单策略之间的差异被削弱方案 B 是各策略维护各的历史效果更好但调试更麻烦。如果有余力上方案 B优先做方案 B。人说到底策略不同本质上是搜索行为不同硬凑一套参数历史会拖后腿。重启阈值的滞后性问题。多样性指标不是瞬时的种群中个体之间的距离变化是连续的。这个设计容易造成阈值触发滞后等你发现多样性太低时可能已经晚了。解决方式是把预警阈值和触发阈值分开预警阈值触发后先做局部保底操作比如暂停种群缩减观察几代如果指标进一步恶化才真正触发重启。我给这个问题浪费过不少时间建议新手直接照着做两个阈值。局部搜索的频率和具现化。局部搜索做得太频繁会把多算子拓展出来的多样性全部抵消太稀疏又起不到后段精修作用。建议先用总预算的 10% 到 20% 作为局部搜索的预算上限赛季初始设置偏保守10% 左右再按实际效果去调参。可视化监控的手段差距。不要只看目标函数值曲线。目标函数值是一条极度平滑的曲线看不出内部机制对不对。建议把每个策略的选择概率、种群多样性指标、重启触发次数、局部搜索成功次数这些内部状态全部以日志方式输出画在同一张时间轴图上。我能快速定位算法问题几乎都是靠这套内部状态监控而不是盯目标值曲线。6.3 真实问题里不要盲目“高仿”最后必须提醒一句竞赛排名算法搬到真实工程场景并不总是“即插即用”。竞赛里函数是固定的维度、预算都是明确指定的算法可以做针对性的调优。真实工程里评估预算往往更紧张而且函数噪声可能很大。此时多算子带来的稳定性提升依然有效但重启机制就要格外小心噪声环境下多样性指标和停滞信号都不稳定很容易误触发重启把原本正常的收敛进程打断。我的做法是在带噪声的真实问题上先把重启触发阈值调到很保守甚至前期完全不启用只靠着多算子和局部搜索的增量去优化。等观测到多次运行的一致行为之后再决定要不要放开重启。这类大型算法的真正价值并不是让你原封不动抄下来跑一个自己的测评基准而是提供一套“预算受限时怎么安排搜索行为”的成熟策略。理解每套机制解决什么问题、在什么阶段该发力、和前后阶段怎么衔接才是比拿到一份源码更重要的收获。
阅读完成 · 觉得有帮助？
