基于自适应缩放比例因子的差分进化算法

沈佳杰，江 红，王 肃

（华东师范大学 信息科学技术学院，上海200241）

0 引 言

差分进化算 法 （differential evolution，DE）是 由D.Storn和K.Price在1995年共同提出的一个在连续空间内启发式搜索的随机算法［1，2］。由于其优良的可扩展性和通用性，已经广泛应用到各个领域。但是标准的差分进化算法依然存在很多问题，如早熟和对于在高维多峰函数条件下难以找到全局最优值等等。对于这一些问题已提出了很多新的解决办法，如增加新的算子、混合算法等等，对于差分进化算法存在的问题和对于问题相应的改进可以参考文献 ［3，4］。

本文针对差分进化算法在高维函数上易早熟和难以找到全局最优值的问题，提出一个基于自适应缩放比例因子改进的差分进化算法，通过理论推导和实验证明了改进的基于自适应缩放比例因子差分进化算法可以有效地减少算法在高维多峰环境下的迭代步骤数以及更好的找到目标问题的全局最优值。

1 标准差分进化算法

1.1 差分进化算法简介

差分进化算法是基于群体智能的进化算法，其主要的操作有变异操作、交叉操作和选择操作，通过这3种不同操作，标准的差分进化算法［1，2］可以高效地找出函数的最优值，其主要定义如下：

个体种群由N个独立的个体组成，记为

式中：N——种群数。

每一个个体是一个D维向量，记为

式中：D——问题维数。

类似于遗传算法，需要通过差分进化算法中的变异、交叉和选择操作对种群进行变换，从而找出最优值点。

1.1.1 变异操作

变异操作的主要作用是对于不同个体进行差分变换，从而产生新的变异个体。变异公式如下

新的变异个体Vi由3个不同的个体通过式 （3）计算而得。

1.1.2 交叉操作

交叉操作的主要作用是生成的实验个体与原个体进行交叉操作，从而生成新的变异个体。交叉操作如下

式中：rand（0，1）为 ［0，1］之间随机数，CR 为交叉概率其取值在 ［0，1］之间，rnbr（i）是指第i个个体的向量标号。

如式 （4）所示，交叉操作的本质是将变异个体与原个体在各个维度向量上以一定的概率进行交叉，生成新的实验个体ui。

1.1.3 选择操作

选择操作的主要作用是在个体进入下一步迭代时，在现在个体和实验个体中选择一个适应度较高的个体生成下一代的种群。选择操作如式 （5）所示

如式 （5）所示，当改进实验个体的适应度大于原来个体适应度值，则采用改进后的实验个体，其它情况下采用原来个体。

1.2 标准差分算法步骤

标准差分算法步骤如下：

步骤1 初始化种群X0进入差分进化算法，确定CR，将迭代步数t设为1，同时设定最大迭代步数tmax。

步骤2 调用变异操作。通过式 （3），计算所有个体的变异个体。

步骤3 调用交叉操作。通过式 （4），生成所有个体的实验个体。

步骤4 调用选择操作。通过式 （5），判断生成的实验个体是否比现存个体的适应度高，如果适应度高于现存个体，则让实验个体替当前个体；否则，保留，生成下一代。

步骤5 判断是否已经达到最优值或迭代步骤数是已经超过最大迭代步骤数，如果是，转向步骤6；否则转向步骤2。

步骤6 输出最优值点。

1.3 对标准差分算法的改进

从标准差分进化算法可以看出，标准的CR是一定的，极易造成差分进化算法的早熟，所以部分文献针对于这个问题提出改进CR的计算方法［5，6］。文献 ［5］中将CR的计算方法改为

式中：g——当前算法的步骤数，G——算法整体的迭代步骤上限，CRmin——变异值的最小值，CRmax——变异值的最大值。

其最大的优点是在算法开始时，尽量关注全局范围的变异情况，而在算法接近于收敛的时候，更加关注局部的收敛情况，形成二次变异差分进化算法。

除此之外，许多文献还对标准差分进化算法进行了其它方面的改进，如对差分进化算法交叉和变异操作的改进［7，8］，对编码进行优化改进［9］、对个体进行排序以提高算法效率［10］、利用信息论中熵的概念提高算法效率［11］，以及对多目标问题使用差分进化算法的求解，如使用不同的理论对 进化算法进行改进［12，13］、 进化算法综述［14，15］和对多目标差分算法收敛性的讨论［16］。

2 改进的差分进化算法

2.1 假设和定义

本文中改进的差分进化算法的假设和定义如下：

假设1：个体适应度为正数，其随着个体对于环境适应能力的增强而变大，即需要将问题归一为正数最大值问题。

假设2：多峰函数是连续的且最优值点存在且可以被找到。

假设3：多峰函数每一维变量是独立的影响函数的取值。

定义1 整个种群适应度的方差称为适应度方差，记为

式中：fi——当前个体的适应度，favg——平均适应度，N——种群数。δ2的值越大，说明种群越分散，对于随机搜索越有利；反之，δ2的值越小，说明种群越集中。

定义2 种群整体集中程度反比于种群的方差，称为早熟比例基数，记为

式中：f——一个比例系数。

定义3 个体的适应度相对于最大适应度和最小适应度归一化的值，称为归一化适应度，记为

定义4 早熟比例基数与归一化适应度的乘积称为个体的健康值，记为Hi＝Fsimi＊Kbase（10）

当个体的健康值大于某个阈值，则此个体称为优势个体；当个体的健康值小于该阈值，此个体称为劣势个体。

根据以上定义，对于不同个体的改进，Ki计算公式如下

式中：a——一个系数，rand（0，1）为 （0，1）之间的随机数，Kmin为在健康度较低条件下的K的低维比例因子，Kmax为在健康度较高条件下的K的高维比例因子。

定义5 对于函数极值点的第i极值点中第j维存在一个领域，使得在对于每一个个体的进行一次小于比例因子Kminij的变异、交叉和选择后，落在整个领域外的实验个体的适应度值小于原来个体的值，领域叫做Kminij步长最极值领域。在极值点比例系数中最小的比例系数称为这极值点的最小比例系数，记为Kmini，所有极值点最小比例系数Kmini的最小值称为最小比例系数，记为Kmin。

2.2 改进差分进化算法的步骤

本文中改进的差分进化算法的算法步骤如下：

步骤1 初始化种群X0进入差分进化算法，确定CR，将迭代步数T设为1，同时设定最大迭代步数Tmax。

步骤2 根据式 （7）和式 （8），以及现在的迭代步数T和适应度，计算δ2、比例基值Kbase。

步骤3 根据式 （9）、式 （10）确定本个体的健康值Hi，根据式 （11）计算当前个体的Ki。

步骤4 根据式 （3）调用变异操作，计算变异个体。

步骤5 根据式 （4）和CR进行交叉操作，计算得到实验个体。

步骤6 根据式 （5），调用选择操作生成下一代个体，检查是否所有的个体都完成了迭代。如果还有个体未完成迭代，回到步骤3。

步骤7 判断是否已经达到最优值或迭代步骤数已经超过最大迭代步骤数，如果是转向步骤8，否则转向步骤2。

步骤8 输出最优值点。

2.3 算法性质及其定理证明

本文中改进的差分进化算法的性质及其定理证明如下：

定理1 当所有的个体每一维分量都落在极值而不是最优值的Kminij步长最极值领域，且算法的比例系数值小于对应的最小比例系数值，即K＜Kmin时，则标准差分进化算法无法找到最优值点。

证明：假设原先个体为的个体编号是r0，而随机选中的个体的编号为r1、r2和r3，所以对于t＋1步实验个体有以下组成

其中K≤Kmin，xr0j表示r0的第j维的分量，xr1j表示r1的第j维的分量、xr2j表示r2的第j维的分量、xr3j表示r3的第j维的分量。

对于式 （13），由于实验个体中的分量相较于上一步的个体分量没有发生变化，所以只需要讨论式 （12）。对于t＋1步的迭代，对于每一个个体的每一维变量有以下两种可能：

（1）下一步迭代时跳出r1的最极值领域内

由于所有的个体每一维都在极值而不是最值的Kminij步长最极值领域内且差分进化算法的比例系数小于最小比例系数 （即K＜Kmin），所以这一维变量的改变必然导致个体适应度值的变小。又因为多峰函数每一维变量是独立的影响函数，所以产生的实验个体必然小于原个体的适应度值，在选择步骤中必然会选择原个体，而不是变异个体。

（2）下一步依然在r1的最极值领域内

由于所有的个体的每一维分量都在极值而不是最优值的Kminij步长最极值领域，所以迭代后的个体也一定不在最优值的Kminij步长最极值领域内，因此不会达到最优值。

综上所述，原命题成立。

推论1 当多维函数的维数和函数极值点足够多时，传统的差分进化算法很难找到全局最优值点。

证明：随着函数维数和局部极值点的增多，陷入局部极值点的概率将增大，所以随着函数维数和局部极值点增多其越难找到全局最优值点。

定理1与推论1说明了标准的差分进化算法在多峰函数条件下，如果比例系数值选择过小，则较容易发生早熟现象，即过早进入找到局部最优值的搜索而忽略了全局的最优值点，而如果比例因子取得太大的话，又会因为其迭代跨度太大，不利于最优值点的局部搜索。

定理2 如果高维比例因子足够大，在迭代步骤数足够多的情况下，改进差分进化算法可以找到最优值。

证明：由于迭代步骤足够多，那么当陷入局部极值的个体必然有n步迭代进入式 （11）中高维部分，又因为高维的步长足够长，所以必然存在个体高维的迭代可以跳出局部极值。而与此同时在最优值周围的个体，由于迭代步骤足够多，必然存在个体通过式 （11）的低维搜索找到最优值。

所以改进差分进化算法可以在迭代步骤数足够多的情况下找到最优值。

3 实 验

本实验是在MATLAB2010b环境下进行测试，本文选择表1所示的5个函数作为本实验的测试函数，其中测试函数1～5的性质各不相同：函数1、函数4和函数5是多峰函数，函数2和函数3为单峰函数。在实验中分别对于低维数据 （2，2，2，3，3）和高维数据 （2，15，10，10，15）各自独立进行10次实验，分别对10次试验迭代次数的最大值、最小值和平均值进行统计。

表1 模拟使用的测试函数

为了减少CR对于实验结果的影响，实验中采用规定CR为常数的方法。表2是在低维 （2，2，2，3，3）情况下标准差分进化算法和改进后的差分进化算法迭代步骤数的对比，表3是在高维 （2，15，10，10，15）情况下标准差分进化算法和改进后的差分进化算法迭代步骤数的对比。

其中SDE代表标准差分进化算法，IDE代表本文中的差分进化算法。

由表2可知，改进差分进化算法相较于传统差分进化算法没有明显的改进，在某些函数上，甚至有时性能还低于标准的差分进化算法，其主要原因是改进的差分进化算法为了提高对于全局最优值的查找能力，进行了不必要的高维搜索。由表3可知，随着测试函数维度的增加，在多维函数4和函数5中改进差分进化算法其达标时的迭代次数相较传统的差分进化算法明显减少，甚至在函数4中，在交叉概率CR为0.2的情况下，有1000次无法迭代出结果的情况，而改进的差分进化算法依然可以在最多343步下找到函数的达标值点，这符合推论1和定理2。

图1 显示了迭代结束时传统差分进化算法和改进差分进化算法在算法终止时，高维和低维不同环境下，对于5个实验中的测试函数的平均最小值。

表2 对于第一组维数 （2，2，2，3，3）其优化结果前后迭代步数比较

表3 对于第一组维数 （2，15，10，10，15）其优化结果前后迭代步数比较

图1 低维和高维条件下，差分算法平均最小值的比较

从图1（a）中可以看出，低维的条件下，改进差分进化算法与传统方法找到函数最小值相似，图1（b）高维条件下，改进后的差分进化算法的平均最小值小于或等于标准的差分进化算法，尤其是在多维函数4中其平均值相差较大。

4 结束语

本文中通过对于标准差分进化算法引入自适应的比例因子，提出了一个基于自适应比例算子的改进的差分进化算法，通过实验分析和理论推导证明改进的差分进化算法较传统差分进化算法在高维多峰函数环境下，可以有效地提高算法对于全局最优值点的查找能力以及减少差分进化算法的迭代步骤数，但是由于本文中对于改进的差分进化算法的实验数量有限，是否可以找出一个即可以不依赖于函数先验知识的通用比例因子的计算方法，依然是值得研究的问题。

［1］Storn R，Price K.Differential Evolution－a simple and efficient heuristic for global optimization over continuous spaces ［J］.Journal of Global Optimization，1997，11 （4）：341－359.

［2］Storn R，Price K.Minimizing the real functions of the ICEC’96contest by differential evolution ［C］／／Proceedings of IEEE International Conference on Evolutionary Computation，1996.

［3］LIU Bo，WANG Ling，JIN Yihui.Advances in differential evolution ［J］.Control and Decision，2007，22 （7）：721－729（in Chinese）.［刘波，王凌，金以慧.差分进化算法的研究进展 ［J］.控制与决策，2007，22 （7）：721－729.］

［4］YANG Qiwen，CAI Liang，XUE Yuncan.A survey of differential evolution algorithms ［J］.Pattern Recognition and Artificial Intelligence，2008，21 （4）：506－513 （in Chinese）.［杨启文，蔡亮，薛云灿.差分进化算法综述 ［J］.模式识别与人工智能，2008，21 （4）：506－513.］

［5］WU Lianghong，WANG Yaonan，YUAN Xiaofang，et al.Differential evolution algorithm with adaptive second mutation［J］.Control and Decision，2006，21 （8）：898－902 （in Chinese）.［吴亮红，王耀南，袁小芳，等.自适应二次变异差分进化算法 ［J］.控制与决策，2006，21 （8）：898－902.］

［6］DENG Zexi，CAO Dunqian，LIU Xiaoji，et al.new differential evolution algorithm ［J］.Computer Engineering and Applications，2008，44 （24）：40－42 （in Chinese）.［邓泽喜，曹敦虔，刘晓冀，等.一种新的差分进化算法 ［J］.计算机工程与应用，2008，44 （24）：40－42.］

［7］Zaharie D.Influence of crossover on the behavior of Differential Evolution Algorithms［J］.Applied Soft Computing，2009，9（3）：1126－1138.

［8］Epitropakis M G，Pavlidis N G，Plagianakos V P，et al.Enhancing differential evolution utilizing proximity－based mutation operators ［J］.Evolutionary Computation，2011，15 （1）：99－119.

［9］HE Yichao，WANG Xizhao，KOU Yingzhan.A binary differential evolution algorithm with hybrid encoding ［J］.Journal of Computer Research and Development，2007，44 （9）：1476－1484（in Chinese）.［贺毅朝，王熙照，寇应展.一种具有混合编码的二进制差分演化算法 ［J］.计算机研究与发展，2007，44 （9）：1476－1484.］

［10］SHAO Liang.Differential evolutin algorithm based on individual ordering and samplng ［J］.Computer Engineering and Applications，2012，48 （1）：49－52 （in Chinese）.［邵梁.基于排序采样策略的差分演化算法 ［J］.计算机工程与应用，2012，48 （1）：49－52.］

［11］YONG Longquan，CHEN Tao，ZHANG Jianke.Solving complementarity problem based on maximum differential evolutionary algorithm ［J］.Application Research of Computers，2010，27 （4）：1308－1310 （in Chinese）.［雍龙泉，陈涛，张建科.求解互补问题的极大熵差分进化算法 ［J］.计算机应用研究，2010，27 （4）：1308－1310.］

［12］WANG Xiaozhen，LI Peng，YU Guoyan.Multi－objective chaotic differential evolution algorithm with grading second mutation ［J］.Control and Decision－Making，2011，26 （3）：457－163（in Chinese）.［王筱珍，李鹏，俞国燕.分阶段二次变异的多目标混沌差分进化算法 ［J］.控制与决策，2011，26 （3）：457－163.］

［13］MENG Hongyun，ZHANG Xiaohua，LIU Sanyang.A differential evolution based on double populations for constrained multi－objective optimization problem ［J］.Chinese Journal of Computers，2008，31 （2）：228－235 （in Chinese）.［孟红云，张小华，刘三阳.用于约束多目标优化问题的双群体差分进化算法 ［J］.计算机学报，2008，31 （2）：228－235.］

［14］GONG Maoguo，JIAO Licheng，YANG Dongdong，et al.A differential evolution based on double populations for constrained multi－objective optimization problem ［J］.Journal of Software，2009，20 （2）：272－289 （in Chinese）.［公茂果，焦李成，杨咚咚，等.进化多目标优化算法研究 ［J］.软件学报，2009，20 （2）：272－289.］

［15］XIE Tao，CHEN Huowang，KANG Lishan.Evolutionary algorithms of multi－objective optimization problems ［J］.Chinese Journal of Computers，2003，26 （8）：997－1003 （in Chinese）.［谢涛，陈火旺，康立山.多目标优化的演化算法［J］.计算机学报，2003，26 （8）：997－1003.］

［16］ZHOU Yuren， MIN Huaqing，XU Xiaoyuan，et al.A multi－objective evolutionary algorithm and its convergence［J］.Chinese Journal of Computers，2004，27 （10）：1415－1421（in Chinese）.［周育人，闵华清，许孝元，等.多目标演化算法的收敛性研究 ［J］.计算机学报，2004，27 （10）：1415－1421.］