章猛，邹德旋，徐福强，罗鸿赟
(江苏师范大学电气工程及自动化学院，江苏 徐州 221116)
差分进化算法（Differential Evolution，DE）在1997年Storn和Price发表的文章[1]中正式提出，是一种基于群体的进化算法。它借助种群个体之间的差分信息来影响个体的进化方向，并通过贪婪选择的方式将适应度更优的个体保留，经过不断的进化得到最优解。但在面对复杂的全局优化问题时，DE 算法容易出现收敛精度低、陷入局部最优等问题。针对这些问题，国内外的学者提出来许多的改进方案，以提高DE算法的优化性能。
从变异策略的研究来看，文献[2]中提出一种“Top-bottom”策略：根据适应度进行排序，将种群的前75%个体和后75%个体构成档案库，从中选择个体构成差分向量以一定的概率来维持种群多样性，将大部分个体导向潜在的更有希望的区域；
文献[3]提出一种新的变异策略DE/Alopex/1，根据适应度值计算两个个体相关性和特殊参数“温度”，进一步来计算不同的移动方向的概率，引导个体向优质区域移动。文献[4]提出DE/neighbor/1 策略，以N 个个体构成的邻域内选择最优个体作为基向量，从剩余个体随机选择个体构成差分向量，平衡DE的全局探索和局部开发能力。
从控制参数调整方面来看，文献[5]使用正态分布随机数和柯西分布随机数来进行控制参数的自适应调整，并使用权重莱默均值的方式来控制均值，提高“精英”信息对参数更新的作用。文献[6]提出新的参数AF 代表种群的分散程度，根据分散程度判断控制参数F和CR是在原来的程度上增加或减少，配合不同的变异策略平衡全局探索和局部开发。
从引入优良机制方面来看，文献[7]使用了外部存档的方法，可以选择该外部存档中的一些高质量解决方案作为候选解决方案。文献[8]中设计局部搜索半径，在最优个体附近搜索四个节点运用牛顿三次插值进行局部搜索，提高算法收敛性能。
基于以上学者的研究，本文提出多种群协同进化的差分进化算法（Multi-population Coevolution Differential Dvolution，MCDE）。本算法提出双序法进行种群划分：同时使用适应度值排序和距离系数排序将种群分为三个子种群：优秀种群、次优种群和普通种群；
针对不同种群的特点，使用不同的变异策略和控制参数；
同时针对普通种群采用概率判定的方式确定个体的变异策略来加快收敛速度。为了验证本文算法的性能，采用CEC2017[9]标准测试函数进行仿真实验，结果证明本算法与其他算法相比性能更好。
1.1 种群初始化
初始化阶段主要是确定各种初始参数：种群数量NP、变量维度D、可行域、变异因子F、交叉因子CR；
以及使用均匀随机数的方式产生初代种群，具体公式如下：
其中，xi,j表示第i个粒子的第j维；
i=1,2,…,NP，j=1,2,…,D。rand()表示[0,1]内的均匀随机数。xmax，xmin表示可行域的最大值和最小值。
1.2 变异
变异部分主要是通过差分向量和基向量进行加权求和得到下一代个体，从而实现个体变异。常见的变异策略如下：
1.3 交叉
1.4 选择
通过贪婪选择的方式在实验个体与父代个体之间选出更优秀的个体做为子代个体。具体公式如下：
2.1 基于适应度值和欧氏距离的种群划分
在本文使用双序法将种群划分为优秀种群X1、次优种群X2、普通种群X3。首先将种群个体按照适应度函数值进行排序得到种群Y1，然后按照公式⑻计算每个个体与最优个体的距离系数di，并按距离排序得到种群Y2：
di代表第i个粒子与全局最优粒子之间的距离系数，di越小，该粒子离最优粒子越近。
本文基于二八法则[10]，将种群Y1和种群Y2的前20%提出来构成种群Y3和种群Y4。若个体xi在Y3内却不在Y4内，则其属于种群X2。以种群Y2剩余个体内离全局最优粒子最近的粒子为边界，距离更近的粒子划入种群X1，距离较远的粒子划入种群X3。同时种群X1内的个体数量上限为0.5*NP。
采用该划分方式将由公式⑴得到的50 个个体放置函数的等值线图中具体分类如图1 所示，其中三角形代表种群X1，圆代表种群X3，五角星代表种群X2。
图1 子种群分布图
2.2 种群的策略选取
对于种群X1的个体来说，它们存在于以xbest为圆心的圆形区域内，适合使用搜索能力强且搜索精度高的变异策略。因此选用DE/current-to-best/1 策略，其中K=0.1。种群X2的个体所处位置是全局最优个体的候选位置，选取的是DE/rand/1 策略，有利于快速筛选确定全局最优位置。
本文根据在ESCDE[11]中提出DE/rand assemble/1策略得到思路提出了一种变异策略称作DE/rand*3/1如式⑼所示：
根据种群X3的特点，个体的适应度值差且与xbest的距离不理想。因此通过调整基向量的方式来促使个体向更优的个体学习。采用概率判定法来决定变异策略的选择来保证种群多样性。具体的策略选择如下：
其中，参数W是根据sigmoid 函数提出，一种新的参数，表达式如下：
其中，T=30·(g/G-0.5)，g为当前迭代次数，G为最大迭代次数。当种群X2的种群数量未超过种群数量的1%时，认为已经找到了全局最优解的位置，此时，若g/G＜1/2，则T=30·g/G,以加强局部探索能力。
2.3 参数自适应机制
在DE算法中变异率F决定变异个体的移动步长，交叉率CR决定实验个体从变异个体继承基因的概率。固定的控制参数不能适应各种问题，还容易影响优化进度。因此本文采用自适应的方式获得种群X1控制参数，公式如下：
由上式可获得在[µF-0.1,µF+0.1]和[µCR-0.1,µCR+0.1]内的正态分布随机数，参数µF和µCR按式⒁和式⒂进行更新。
其中，Fmax=0.9，Fmin=0.2;，CRmax=0.9，CRmin=0.5。由此可得种群X1在其范围内同时兼具很强的局部探索能力和全局探索能力。种群X2和种群X3要保持种群多样性，因此，参数F选择[0,1]内的均匀随机数，参数CR的选取如下：
2.4 MCDE算法流程图
MCDE算法的流程图如图2所示。
图2 MCDE算法流程图
3.1 测试函数
为了评估本文所提出的MCDE 算法，将在CEC2017 测试函数集的30 个测试函数上进行仿真实验。其中中F1～F3 为单峰函数，F4～F10 为多峰函数，F11～F20为混合函数，F21～F30为复合函数。
3.2 参数设置
另外选择四种近年优秀的算法MDE[7]、DE-BMS[12]、DE/Alopex/1[3]、HSDE[13]与MCDE 算法相对比。各算法在30 维的情况下，NP=100、G=3000；
在100 维时，NP=200、G=5000。各算法的参数设置遵循原文献。为了避免随机因素对算法的影响，每个算法独立运行30 次。实验环境为：处理器Intel(R) Core(TM) i5-8265U CPU@ 1.60GHz 1.80 GHz，RAM 12GB，Win10 64位操作系统，MATLAB R2019a。
3.3 仿真实验结果
表1 和表2 表示MCDE 算法和其他比较算法在低维（D=30）和高维（D=100）时的平均值和方差比较，其中最好的数据结果以加粗字体表示。
表1 MCDE与其他算法结果对比（D=30）
图3～图8 是低维时函数F1，F10，F21 和高维时函数F5，F20，F22的收敛曲线图。
3.4 算法收敛精度分析
表1 是各算法在30 维时的实验数据对比结果，从表中数据可已看出，在平均值指标方面，MCDE算法在30 个测试函数中取得了20 个第一和四个第二的成绩，其余测试函数除F22 和F30 以外都与比较算法中得到的最优结果相差不大，说明MCDE 算法具有很强的收敛精度。从方差值指标来看，MCDE 算法取得了六个第一、七个第二，在算法稳定性上也有一定的保障。综上所述，MCDE 算法在低维（D=30）的情况下，在单峰函数，多峰函数和复合函数上较其他算法有明显的优势，在混合函数上也能取得较好的表现。
表2 是各算法在100 维情况下的平均值，方差的数据对比结果，从平均值指标上来看，MCDE 算法在F2、F5、F7、F8、F10、F16、F17、F20、F21、F22、F23、F24、F26、F29 等14 个测试函数上的收敛精度优于其他比较算法，且在其他测试函数上的优化结果与比较算法的最优结果接近。综和表1 和表2 来看，无论是在低维（D=30）还是在高维（D=100）的情况下，MCDE 算法较其他对比算法，均具有明显的优势，这说明MCDE算法的种群划分方法、概率判定机制及变异策略能够有效的提高算法的寻优能力和收敛精度。
3.5 算法收敛曲线分析
图3～图8表示的是各算法在不同的测试函数上的收敛曲线图，图3～图5是低维的情况下的函数收敛图。从图3 中可以看出，MCDE 算法在函数F1 上的收敛速度略慢于MDE算法，比其他算法均快，并且和MDE算法同时得到全局最优值。从图4 和图5 中可以看出MCDE 算法在函数F10 和F21 上的收敛速度不是最快的，但却是最稳的，精度最高的，尽管收敛速度出现波动，但没有陷入局部最优值，这也表明了本文的双序法种群划分的效果。图6～图8是高维的情况下的函数收敛图。从图8 可以看出MCDE 算法在函数F22 上收敛速度存在一个剧烈变化的过程，但没有陷入局部最优，收敛精度是所有算法中最高的。从图6、图7 可以看出，MCDE 算法在函数F5 和函数F20 上能以最快的速度得到最好的结果，且全程收敛曲线平缓，未陷入局部最优。
图3 F1函数测试结果（D=30）
图4 F10函数测试结果（D=30）
图5 F21函数测试结果（D=30）
图6 F5函数测试结果（D=100）
图7 F20函数测试结果（D=100）
图8 F22函数测试结果（D=100）
本文提出来一种多种群协作的差分进化算法（MCDE），首先提出双序法，同时使用距离系数排序和适应度排序，将全局最优粒子的侯选位置划分出来；
同时根据不同子种群的特点来选择合适的变异策略，并对普通种群选用概率判定法选择变异策略更好的平衡全局探索能力和局部搜索能力，避免陷入局部最优。通过MCDE 算法和近年来先进算法在CEC2017测试函数集上的实验结果看，无论是在低维还是在高维情况下，MCDE 算法的收敛精度和收敛能力整体上优于其他比较算法，且在进化过程中没有发生陷入局部最优的情况。但也存在收敛速度波动较大的缺点，接下来将针对该问题进行深入研究。综上所述，MCDE算法是一种有效可靠的全局优化算法。