SHADE vs SaDE：CEC2017基准函数上的自适应差分进化算法对比实验解析

最近把自适应差分进化这边的实验做个了总结重点是把SHADESuccess-History based Adaptive Differential Evolution和SaDESelf-adaptive Differential Evolution在CEC2017基准测试集上的对比过程完整梳理了一遍。这两个算法都是差分进化DE家族里做“自适应”的代表性路线一个是基于成功历史的参数记忆池一个是策略与参数的联合自适应。这篇文章就围绕这个对比实验展开方案是怎么设计的、两种机制到底差在哪、实验参数怎么配置、结果如何解读以及我从编码到统计全程踩过的坑。给准备做进化算法性能对比的朋友当一份实操参考。1. 实验背景与对比方案设计1.1 为什么偏偏挑这两个算法做对比差分化进化算法的调参一直是个老大难问题。F、CR这两个参数直接决定变异步长和交叉强度不同函数的最优参数天差地别。早期大家靠经验组合后来开始做自适应SaDE就是其中一个经典方案它是把“参数自适应”和“策略自适应”结合起来算法维护一个策略池根据历史表现给每个策略分配概率同时CR和F按随机分布采样分布参数隔一段时间根据成功个体统计更新一次。SHADE则是另一个思路。它不搞策略池而是专心打磨“参数如何利用成功经验”这件事。每次迭代中凡是让子代成功存活下来的CR和F都会被记录到一组历史记忆槽里。下一轮生成新个体时直接从历史记忆里取参考值再围绕参考值做随机扰动。这样参数的自适应粒度更细几乎每个个体都在用“最近的”成功参数信息。这两个算法放在一起对比本质上是在回答一个问题自适应到底应该靠“广撒网选策略”还是靠“精准记录成功参数”各自机制的优势函数空间是什么如果不做测试集上的系统对比这个问题只能停留在理论推测层面所以我安排了这次完整实验。1.2 对比方案设计与实验矩阵实验之前先定了三条硬性约束确保对比结果不是“参数调好的算法”打“没调参的算法”两套算法的种群规模一致最大函数评价次数一致。初始种群生成时使用同一套随机种子序列保证初始解分布完全对齐。边界处理方式统一消除不同边界约束策略对结果的影响。我最终采用的是30维D30主实验种群规模NP100最大函数评价次数MaxFES10000*D即300000次。每种算法在CEC2017的每个测试函数上独立运行51次记录每次运行的最优误差即找到的最优值减去该函数真实最优值。实验矩阵其实还可以扩展比如同时跑10D、50D、100D。但这次实验的目的不是发论文而是机制对比所以只选了30D作为主战场。原因是10D太简单两类算法差距不容易拉开100D运行时间太长51次独立重复会消耗大量时间。30D能比较好地平衡判别力和实验成本。2. 两种自适应机制的底层思路拆解2.1 SHADE用成功历史喂出来的参数记忆池SHADE最核心的组件是两组记忆槽MCRmemory for CR和MFmemory for F槽数量一般用H表示我设置为5。每一代开始每个目标个体xi执行变异前先从1到H里均匀随机选一个槽位再用该槽位存储的历史值作为均值生成当前的CRi和FiCRi服从正态分布N(MCR_k, 0.1)Fi服从柯西分布Cauchy(MF_k, 0.1)这里用柯西而不是正态是SHADE的一个关键设计。柯西分布尾部更厚生成极端步长因子的概率更高能让种群在长期运行中偶尔跳出局部区域。参数生成之后个体用DE/current-to-pbest/1变异策略加上一个外部存档机制[ v_i x_i F_i \times (x_{pbest} - x_i) F_i \times (x_{r1} - x_{r2}) ]其中xpbest从当前种群中最优的100*p%个个体里随机选p一般取0.1到0.2。r1从当前种群选r2从种群和外部存档的并集中选。外部存档的作用是保留那些被淘汰的父代个体让变异方向不局限于当前种群的范围增加种群的探索多样性。每一轮迭代结束时所有“成功进入下一代”的个体所对应的CR和F会被收集起来。更新记忆槽时不是简单求平均而是用Lehmer平均[ meanWL \frac{\sum w_h \times S_h^2}{\sum w_h \times S_h} ]权重w_h取每个成功个体的适应度改进量。Lehmer平均相比算术平均更能放大较大值的影响从而在进化后期F值普遍偏小的情况下依然能输出一些较大的F来保持探索能力。这个机制精妙在细节“历史”不是一组永远不变的静态值而是在每一轮不断被替换、被重新计算。当记忆槽积累到第H次更新后指针回绕开始覆盖最旧的槽位。这样算法永远优先使用最近若干轮的参数经验既能应对不同搜索阶段的特征变化又不会因为某个极端的成功记录而把参数带偏。2.2 SaDE的策略池与学习周期SaDE完全不同。它维护了一个策略池常用的版本包含四个变异策略例如DE/rand/1/bin、DE/rand/2/bin、DE/current-to-best/2/bin等。每个策略对应一个选择概率p_k概率初始化相等。每隔LP代学习周期我设置为50代算法统计每个策略在过去LP代内的成功次数比例用来更新下一周期的概率分布。SaDE对CR和F的处理也是分布采样。F从正态分布N(0.5, 0.3)中采样并截断在[0, 2]区间。CR的均值经过学习周期内的成功个体CR值中位数动态调整标准差固定为0.1。换句话说SaDE对参数的更新是“批量”的每隔一段固定代数做一次统计学习SHADE是“每代”都在微调记忆槽。策略池的价值在于鲁棒性。不同的变异策略在搜索的不同阶段各有优势DE/rand/1探索性强适合前期大范围扫描DE/current-to-best/2开发性强适合后期精细搜索。SaDE让种群内部同时存在多种搜索行为哪类策略成功率高后续的个体就更多采用哪类策略。2.3 机制差异带来的实验预判在真正跑数据之前我先从机制上做了三个预判SHADE在混合函数和组合函数上可能表现更好。因为current-to-pbest变异方向明确指向当前优秀个体配合存档提供的多样性信息能比较高效地穿越复杂函数中不同子空间之间的“接缝”。SaDE在简单多峰函数上可能更稳。策略池的多样性让种群不容易共振到某一种搜索方向上去旋转多峰环境下更可能避开对称陷阱。SHADE后期收敛行为可能更好。每代更新记忆槽意味着参数能持续跟随成功样本变化而SaDE的学习周期50代参数更新的颗粒度比较粗后期如果目标区域变得越来越狭窄SaDE的参数响应会慢半拍。这三个预判后来在真实数据上都有对应的体现但也有一些意外后文会细说。3. CEC2017测试集与实验配置实录3.1 CEC2017的30个函数家族CEC2017基准测试集是进化计算领域很常用的验证工具包包含30个测试函数从单峰到组合函数层层递进。按家族分类如下函数范围家族类别典型特征F1单峰函数只有一个全局最优主要考验收敛速度F2-F10简单多峰函数存在大量局部最优测试全局搜索能力F11-F20混合函数不同函数按分段组合子空间边界复杂F21-F30组合函数多个基本函数加权融合具有移位和旋转操作CEC2017里的函数基本都做了shift和rotation两种变换。shift操作把全局最优点移到搜索空间内某个非零位置这就杜绝了算法靠近边界取巧rotation操作破坏了变量之间的可分离性让“逐维优化”的策略失效。尤其是Rosenbrock族和Rastrigin族的旋转版本局部最优的分布形态完全跟着旋转矩阵变化需要算法真正理解全局结构才能稳定求解。混合函数和组合函数是CEC2017的难点所在。混合函数把几个基础函数的分区组合在一起每个子区域的函数形态不同导致算法在跨区域搜索时容易迷路。组合函数使用权重机制把多个基础函数融合成一个连续函数权重中心的位置随机分布函数曲面的起伏完全不规则。这两类函数对算法的自适应性提出了很高的要求参数固定不变的DE在这两类函数上经常会出现“在一段区域调好参数到另一段区域就失效”的情况这也正是自适应算法可以拉开差距的地方。3.2 实验参数配置一览最终确定的实验参数如下维度D30种群规模NP100最大评价次数MaxFES30000010000 * D独立运行次数51次边界处理统一采用“越界后重新随机初始化”随机数引擎mt19937固定随机种子序列显著性水平0.05初始化范围严格按照CEC2017官方文档中每个函数的搜索边界设定通常是[-100, 100]的D维超立方体个别函数范围不同以官方代码里的边界变量为准。初始种群全部用均匀随机分布生成。关于边界处理多说一句。越界个体通常有三种处理办法一是把边界外的分量直接拉回边界absorbing二是按照某个随机策略重新生成resampling/reflection三是给越界个体施以极差的适应度惩罚。我统一用“重新随机初始化”是经过考虑的CEC2017的旋转函数让坐标轴不再与边界方向对齐边界吸收处理会引入人为的搜索偏向对算法对比来说不够干净。重随策略会牺牲一点开发能力但公平性最好。3.3 数据记录与统计检验安排每次独立运行结束时记录该次运行得到的最优误差值。51次运行下来每个算法在每个函数上得到一组包含51个误差值的样本。后续统计分析围绕这些样本展开对每个函数计算均值、中位数、标准差观察集中趋势和稳定性。使用Wilcoxon符号秩检验做配对比较判断两个算法在每个函数上的差异是否具有统计显著性。使用Friedman检验对两个算法在30个函数上的整体表现做全局显著性判断。误差计算公式统一为 ( f(x_{best}) - f(x^) )其中f(x)是CEC2017代码里给定的该函数真实最优值。注意CEC2017每个函数的最优值不是一个统一常数初始化时都会打印出来务必逐个映射不能套用旧版CEC2014的数值。这一点后面在坑的部分会专门再提。3.4 代码实现细节SHADE我按原始流程从零写核心模块包括记忆池初始化、变异交叉选择循环、存档更新、成功样本收集、记忆槽更新、种群自适应缩减。SaDE同样按论文流程实现策略池概率维护、学习周期统计、CR均值更新、F采样。两个算法共用一套CEC2017基准函数接口保证调用逻辑一致。我额外封装了一个统一的优化循环结构大致如下def run_algorithm(algorithm, func_num, dim, np_size, max_fes): frame cec2017_interface(func_num, dim) pop_size np_size # 统一初始化 population uniform_init(frame.lb, frame.ub, pop_size) evaluate_count pop_size while evaluate_count max_fes: # 算法各自维护的流程 if algorithm SHADE: SHADE_step(frame, population, ...) elif algorithm SaDE: SaDE_step(frame, population, ...) evaluate_count pop_size return best_error统一框架的好处是事后我可以反复确认两边的评价次数统计完全一致不存在哪边多算了几轮的情况。4. 结果解读谁在哪类函数上更能打4.1 总体胜负与显著性结果51次独立运行的数据汇总后以函数家族为单位统计了胜平负关系如下表函数家族SHADE胜平SaDE胜F1单峰100F2-F10简单多峰423F11-F20混合函数712F21-F30组合函数424这个表格是特定随机种子、特定实现环境下的结果不构成普适结论。但趋势上可以看到SHADE的最大优势集中在混合函数上而组合函数两侧基本打平。Wilcoxon符号秩检验的结果和表格基本一致。F11-F20这10个函数中SHADE在7个函数上的误差分布显著优于SaDEp值都在0.05以下。F21-F30中SHADE显著占优的是4个SaDE显著占优的也是4个整体互有胜负。Friedman检验算出的平均秩SHADE为1.42SaDE为1.58差异达到显著水平全局结论是SHADE在这组测试条件下的整体表现略胜一筹。4.2 分族表现对应的机制解释单个函数层面有信息量。先看F1这种单峰函数两个算法最终都能逼近全局最优SHADE的收敛速度优势体现在评价次数曲线上大约在总评估次数的40%处开始明显领先最终平均误差低一个数量级左右。单峰函数形态简单决定胜负的主要是参数跟不跟得上搜索阶段的变化SHADE的每代参数刷新机制比SaDE的50代学习周期响应更快。简单多峰函数是SaDE的高光区域。这类函数局部最优多需要种群保持足够的行为多样性。策略池让SaDE内部始终有不同探索风格的个体共存DE/rand/2这种发散能力强的策略一旦拿到高概率就能稳定地提供新区域探测。在旋转Rastrigin风格的函数上SaDE多次跑出更低的误差极值。SHADE则因为每次变异都朝着pbest方向收紧整体搜索步伐更“急”容易在旋转导致的带状局部最优区里反复震荡。混合函数SHADE赢得很明显。回头看机制混合函数的分区边界是最大的难点。current-to-pbest变异的优势在于它同时利用了“全局最优指引”和“随机差分扰动”搭配外部存档中记录的淘汰个体使得跨越子空间边界时既能保持方向感又不至于让整个种群被一个区域的局部最优覆盖。实际观察中SHADE在混合函数上的最终误差经常比SaDE低一到两个数量级而SaDE在部分混合函数上会陷入某个子区域的局部极值无法出来。组合函数是意外最多的地方。预先以为SHADE会延续混合函数的优势但实际结果是F21-F30打成平手。分析原因组合函数的基本函数分量之间通过权重耦合函数曲面的地形接近于“几个山峰通过平滑过渡叠在一起”外部存档中记录的淘汰个体和当前最优个体之间往往来自不同权重区域差分向量方向不够一致反而干扰了收敛。SaDE的策略池此时提供了更混沌但也更稳定的全局搜索模式在部分函数上能找到更稳健的解。4.3 收敛轨迹特征我记录了每个函数在51次运行中每次运行的平均收敛轨迹重点看300000次评价内的三个阶段早期阶段0-60000次评价两个算法都快速下降区分度不大。中期阶段60000-180000次评价SHADE在简单多峰函数上出现小幅度平台期SaDE跌幅更匀速。后期阶段180000-300000次评价SHADE的优势开始显现尤其是在混合函数上收敛曲线一直保持下行趋势SaDE在部分函数上已提前触底曲线变平。SHADE后期仍在持续下降这正是成功历史记忆池的作用。进化后期种群个体彼此接近成功个体的F值趋向于小步长但Lehmer平均会在小值占主导的同时保留大值的存在感让偶尔的大步长变异还能发生。SaDE的F采样均值固定在0.5附近除非学习周期内成功样本刻意把CR均值压低否则后期仍会输出不少大变异步长这在狭窄的目标区域容易导致震荡。5. 实验中的坑与排查技巧实录5.1 CEC2017基准代码的三个坑CEC2017的基准测试程序格式比较老第一个坑就是最优值映射。每个测试函数的真实最优值在初始化时会生成到结构体里而且不同函数的最优值差异很大比如有的函数最优值是100乘以某个偏移量有的函数是某一个常数。初始化之后建议先打印一遍所有函数的最优值逐一核对确保误差计算用的不是默认值或旧版本数值。第二个坑是维度相关数据的加载。CEC2017支持多个维度不同维度下移位向量和旋转矩阵的尺寸不同。30D实验必须确保初始化函数里加载的是30D对应的矩阵。我刚开始做的时候在10D调试完直接切到30D有一半函数的偏移数据还是10D的导致结果完全乱了。检查方法很简单在看一个已知最优位置的函数上测试优化器看它能不能收敛到接近0的误差不能就说明数据加载有误。第三个坑是随机数引擎的选择。CLog或编译器自带的rand()在不同平台上序列不一致跑出来的结果无法复现。后来统一换成了mt19937并固定了一套随机种子序列每个算法、每个函数、每次运行都按照序号取种子才做到完全可复现。5.2 统计检验里的三个易错点第一个易错点是只用均值排名。均值和分布的离散程度紧密相关某些函数上SHADE虽然均值略低但标准差很大说明部分运行跑得好、部分运行跑得差这类结果不能直接解读为算法优越。一定要从51次误差的分布出发做配对检验。第二个易错点是Wilcoxon检验的适用条件。它对分布有一定要求但通常鲁棒性还可以。要注意的是如果两个算法对某个函数全都能收敛到0误差那么这51个差值会全部相等或非常接近此时检验会给出无显著差异的结论这属于正常情况不必强行解读。第三个易错点是Friedman检验的平均秩计算。有些现成工具包里给的平均秩计算方式不统一按误差均值排秩和按每次运行分别排秩再取平均结果可能不一致。我在实验中使用了后者即每次独立运行分别给出两个算法的排名再对51次排名取平均。这样既用足了样本信息又避免了风险函数尺度差异对统计数据的影响。5.3 参数敏感性检查正式实验跑完后我又补做了参数敏感性粗扫。SHADE方面试了NP50和NP200、H5和H10、archive大小取NP和0.5*NP两个值。结论是SHADE对archive大小不敏感对NP敏感NP50时混合函数的表现明显下降NP200时收敛曲线稍慢但终期结果更好。H5和H10差异不大。SaDE方面主要试了LP30和LP100。LP的影响非常明显。LP30时策略概率更新过于频繁算法整体评估指标短期波动大容易把某个偶然成功策略的概率抬升LP100时自适应滞后明显在混合函数上参数更新跟不上地形变化。LP50在本次实验条件下表现最稳定。建议看到这里的朋友如果自己要复现对比实验务必先做一轮参数敏感性粗扫不要直接套用文献里的默认参数。很多算法对比论文里出现的“某算法碾压另一算法”结论一查参数配置往往是一边调过一边没调这一点要特别留意。5.4 实验代码组织的建议对于这种多算法对比实验建议把算法本体和实验框架彻底分开。算法本体只维护种群、记忆池或者策略池对外暴露一个step函数实验框架统一负责初始化、评价、统计、结果导出。我吃过亏最初写测试脚本时把种群初始化写死在算法类里后面想换个维度跑得同时改好几处地方还差点改漏。另外每一次运行的结果我当时就同步写入CSV文件而不是跑完51次再统一汇总。中途机器断电、代码异常、或者算法陷入死循环的时候已经跑完的数据不会丢失。第一版实验我全部放在内存里跑到第47次的时候进程崩溃前面全丢只能从头再来教训比较深刻。最后分享一点个人体会实验整体做完印象最深的一点是自适应算法之间的差异往往要在函数地形足够复杂时才真正体现出来。像F1单峰或F2低复杂度多峰这种简单场景机制差异会被“收敛速度”这一个指标掩盖掉到了混合函数和组合函数策略组织和参数记忆的优劣才真正暴露。对于想把这类对比实验做扎实的朋友我的建议是第一一定要做配对统计检验不要靠平均误差拍脑袋第二边界处理、随机种子、评价次数这些细节必须提前统一第三数据落盘永远比内存累积可靠。跑实验的过程本身枯燥但把机制差异映射到函数家族上的那一刻会觉得前面所有细节打磨都值了。