自适应双模式差分进化算法

呼忠权，王洪斌，李 硕

（1.燕山大学 河北省工业计算机控制工程重点实验室，河北 秦皇岛066004；2.燕山大学图书馆，河北 秦皇岛066004）

0 引 言

近些年，智能优化算法为全局优化问题［1］提供了新的解决途径。其中，差分进化算法［2］的表现较为突出。

差分进化 （differential evolution，DE）算法［3］的优势主要表现在算法简单、高效并且受控参数少，但基本算法［4］同样具有缺点：早熟收敛［5］、搜索停滞以及对于控制参数［6］的选择比较敏感等。

因此，为了改善基本DE 的求解能力，在尽量不增加算法复杂性的基础上，降低算法对控制参数的敏感性，本文提出一种改进算法，并通过数值仿真进行验证，验证结果表明，该算法具有较强的寻优能力和鲁棒性。

1 标准差分进化算法［1］

DE算法是求解有n 个连续变量全局优化问题的算法。全局优化问题可以转化为求解如下函数的最小值问题

式中：D——问题空间的维数，用bj，aj分别表示xj的上下限。

DE算法流程如下：

（1）初始化种群

式中：NP 表示种群大小，Xi（0）表示初始种群中第i个个体，xi，j表示第i个个体的第j 个分量，rand（0，1）表示区间（0，1）内均匀分布的随机数。

（2）变异

生成新个体

式 中：i≠r1≠r2≠r3，i＝1，2，…，NP ，r1，r2，r3均为区间［1，NP］内的随机整数，F 为缩放因子，g 表示进化代数，Xi（g）表示第g 代种群中第i个个体。

通过变异后，第g 代种群产生一个新的中间种群｛Vi（g＋1），i＝1，2，…，NP｝。

（3）交叉

式中：i＝1，2，…，NP ，j＝1，2，…，D，rand（0，1）表示区间 （0，1）内均匀分布的随机数，Ui（g＋1）＝［ui，1，ui，1，…，ui，D］表示第g＋1 代新种群中第i个个体，ui，j（g＋1）和vi，j（g＋1）分别表示Ui（g＋1）和Vi（g＋1）中的第j个分量。CR 为交叉概率，jrand为区间 ［1，D］内的随机整数。这种交叉策略可确保新个体中至少有一个个体发生了变异和交叉操作。

为了保证求解的有效性和准确性，必须判断交叉后的新个体是否满足约束条件，满足条件的保留，不满足条件的舍弃，并用步骤 （1）的方式来产生新的个体用于替换被舍弃的个体。如式 （6）所示

式中：i＝1，2，…，NP ，j＝1，2，…，D。（4）选择操作

DE采用贪婪算法来选择进入下一代种群的个体

式中：i＝1，2，…，NP 。

（5）终止条件

如果最优解到达求解要求或者迭代次数g 超过了最大迭代次数Gm时，则停止求解，否则重复（1）～（4）操作。

2 自适应双模式差分进化算法

自适应［7－9］双模式差分进化算法是将两种变异模式［10］进行结合，每一次变异操作只选用其中的一种变异模式，这样不但不会增加该算法的复杂性，而且还会对该算法的性能有所改善。由于DE算法运行参数少，所以每个参数的选取都会影响DE 算法的求解。为了求得全局最优解，参数选择［11］至关重要。因此，变异因子F 和交叉概率CR 采用自适应的方式进行调节，以此来平衡局部搜索与全局搜索。

2.1 变异操作中的基向量和差分向量

根 据Rainer Storn 和Kenneth Price于1995 年 提 出 的DE算法，基本进化模式有10种［12］，详见表1。

表1 差分进化模式种类

这10种进化模式采用下面的通式表示

式中：DE——差分进化算法，x——种群中的待变异个体，y——差异向量的个数，z——交叉的模式。在应用中交叉模式一般选用二项交叉，有利于加快算法的收敛速度。

由图1所示的二维新个体的产生过程可以看出，待变异个体的选取会直接影响算法的收敛速度和全局寻优能力。若待变异个体为随机选取，则利于算法的全局寻优［12］，但是收敛速度慢；若待变异个体为当前种群中最优个体，则利于算法的快速收敛，但全局寻优能力差。为了解决收敛速度与全局寻优能力间的矛盾，在种群变异的过程中，将DE／rand／1／bin和DE／best／2／bin这两种变异模式进行结合使用，具体实现流程如图2所示。

实现方法如下所示

图1 二维新个体的产生过程

为了使算法的收敛速度更快，但又不至于使算法收敛到局部极小值，将rand（0，1）与进行比较，而不与a进行比较。从图3中可以看出，这种比较方式可以使rand的值以较大的概率落在曲线的下方，使进化模式DE／best／2／bin被选到的可能性增大，使收敛速度加快。这样算法就在全局搜索和收敛速度之间进行了平衡。

2.2 自适应变异缩放因子F 和自适应交叉概率CR

自适应参数［13］（F 和CR）会在一定程度上平衡收敛速度和全局搜索之间的关系，改善算法的求解能力。随着F的变大，全局寻优能力变强，但收敛速度变慢；随着CR的增大，算法收敛速度加快，但是算法稳定性和成功率变差，早熟收敛［14，15］情况越明显。因此，为了防止早熟收敛的发生，同时又能保证较快的收敛速度，采取自适应机制对F 和CR 进行赋值。

图2 算法流程

图3 函数对比曲线

F 和CR 是根据种群进化代数的变化来自适应调整的。如下式所示

式中：Fmax、Fmin——F的上下限，CRmax、CRmin——CR 的上下限。

此外，由于DE算法对控制参数的选取非常敏感，F 和CR 的选取可以按照这个经验范围来选取

式中：P表示函数峰值的个数。

3 仿真及分析

通过对8 个典型Benchmark 函数进行数值仿真，将ADDE算法与两种基本DE 算法 （采用DE／rand／1／bin 和DE／best／2／bin两种变异模式）、PSO－w、CLPSO 和DMSDELS算法进行比较。文中将基于DE／rand／1／bin 和DE／best／2／bin模式的DE 算法分别记为DE1 和DE2。在DE1和DE2中，F＝0.5，CR＝0.5。PSO－w、CLPSO 和DMSDELS的参数设置来自于文献 ［7］。

在表2 中，函数的最大迭代次数也分别给出。将ADDE与其它几种进行算法性能比较，得到数值求解结果（表中字体加黑的部分表示最优结果和算法），见表2。表中PSO－w、CLPSO 和DMSDELS的求解数据来自文献 ［7］。

Benchmark函数见表3。

对于单峰函数的求解，ADDE 和DMSDELS算法收敛的精度高，求得的最优解更加接近理论最优解。此外，ADDE比DMSDELS的搜索精度更高，实际值更加接近理论最小值，但对于函数f3（x），ADDE 和DMSDELS都没有DE2求解的效果好，主要是由于DE2算法比其它3种算法的收敛速度都要快很多，而且函数是单峰函数，不存在局部极小点，因而能够求解到最优值。

表2 算法性能比较

对于多峰函数f5（x）来说，只有ADDE 求得全局最优解，而对于f6（x）来说，虽然6种方法都不能求得全局最优解，但是ADDE的求解精度更高。

对于低维函数f7（x）和f8（x）来说，6种算法都能求得最优解，但ADDE的求解精度高于其它算法。

通过对上面8个函数的求解结果可以看出，改进算法结合了DE1和DE2的优点，使算法不论是对于低维函数还是高维单峰函数和高维多峰函数，最优解基本不会陷入局部极小点，而且求解精度高。

为了更加清晰的了解6种算法对高维函数的求解能力，分别对函数f5（x）和f6（x）进行了最优解收敛曲线的绘制。为了尽量消除算法的随机性，分别对两个函数进行20次求解，取其平均值。图4所示为平均值随迭代次数的变化曲线，其中图 （a）、图 （b）分别对应函数f5（x）和f6（x）的求解曲线。

图4 算法的收敛曲线

从图4 可以看出，对于高维多峰函数的求解，ADDE比其它算法的收敛速度都要快。

综上所述，对于函数f3（x），虽然ADDE 比DE2求解精度稍差一些，但从对8个函数的求解来看，ADDE 结合了DE1和DE2的优点，使算法在收敛速度与寻优能力之间能够做到很好的平衡。此外，ADDE 在求解高维多峰函数表现出来的性能更优，全局寻优能力更强，收敛速度更快，求解精度更高。

表3 Benchmark函数

4 结束语

将两种变异模式结合使用的自适应差分进化算法用于高维多峰函数的优化，并通过对典型Benchmark函数进行测试。测试结果表明，改进算法有效的实现了全局搜索，并且改进了原有算法的收敛速度和收敛精度，显示了算法的有效性和鲁棒性。为实际工程应用提供了有力的理论依据。虽然差分进化算法缺少成型的分析和论证方法，但其自身的并行计算和强鲁棒性等优点，相信随着研究的深入，差分进化算法定将成为解决复杂多维问题的优秀算法。

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

［2］WANG Xu，ZHAO Shuguang.Differential evolution algorithm for high dimensional optimization problem ［J］.Journal of Computer Applications，2014，34 （1）：179－181 （in Chinese）. ［王旭，赵曙光.解决高维优化问题的差分进化算法［J］.计算机应用，2014，34 （1）：179－181.］

［3］YANG Yanxia.A hybrid differential evolution algorithm based on simulated annealing operation ［J］.CAAI Transactions on Intelligent Systems，2014，9 （1）：1－6 （in Chinese）. ［杨 艳霞.一种基于模拟退火操作的混合差分进化算法 ［J］.智能系统学报，2014，9 （1）：1－6.］

［4］LIU Ruochen，JIAO Licheng，MA Yajuan.A differential multi－objective optimization algorithm ［J］.PR ＆ Al，2011，24 （6）：748－755 （in Chinese）. ［刘若辰，焦李成，马亚娟.一种差分多目标优化算法 ［J］.模式识别与人工智能，2011，24 （6）：748－755.］

［5］YAO Feng，YANG Weidong，ZHANG Ming，et al.Improved space－adaptive－based differential evolution algorithm ［J］.Control Theory ＆Applications，2010，27 （1）：32－38（in Chinese）.［姚峰，杨卫东，张明，等.改进自适应变空间差分进化算法 ［J］.控制理论与应用，2010，27 （1）：32－38.］

［6］Daniela Zaharie.Influence of crossover on the behavior of differential evolution algorithms ［J］.Applied Soft Computing，2009，9 （3）：1126－1138.

［7］ZHANG Xuexia，CHEN Weirong，DAI Chaohua.Dynamic multi－group self－adaptive evolution algorithm with local search for function optimization ［J］.ACTA Electronica Sinica，2010，38 （8）：1825－1830 （in Chinese）. ［张雪霞，陈维荣，戴朝华.带局部搜索的动态多群体自适应差分进化算法及函数优化 ［J］.电子学报，2010，38 （8）：1825－1830.］

［8］Pan Quan－Ke，Suganthan PN，Wang Ling，et al.A differential evolution algorithm with self－adapting strategy and control parameters［J］.Computers ＆Operations Research，2011，38（1）：394－408.

［9］TUO Shouheng.Self－adaptive ant colony differential evolution algorithm ［J］.Computer Engineering and Design，2012，33（7）：2804－2808 （in Chinese）.［拓守恒.自适应蚁群差分进化算法 ［J］.计算机工程与设计，2012，33 （7）：2804－2808.］

［10］ZHANG Chunmei，CHEN Jie，XIN Bin.Distributed differential evolution algorithm with adaptive parameters ［J］.Control and Decision，2014，29 （3）：1－6 （in Chinese）.［张春美，陈杰，辛斌.参数适应性分布差分进化算法 ［J］.控制与决策，2014，29 （3）：1－6.］

［11］Daniela Zaharie.Influence of crossover on the behavior of differential evolution algorithms ［J］.Applied Soft Computing，2009，9 （3）：1126－1138.

［12］XU Xiaojian，HUANG Xiaoping，QIAN Deling.Adaptive accelerating differential evolution ［J］.Complex Systems and Comlexity Science，2008，5 （1）：87－92 （in Chinese）. ［许小健，黄小平，钱德玲.自适应加速差分进化算法 ［J］.复杂系统与复杂性科学，2008，5 （1）：87－92.］

［13］Ali MM.Differential evolution with preferential crossover［J］.European Journal of Operational Research，2007，181（3）：1137－1147.

［14］ZHAO Guangquan，PENG Xiyuan，SUN Ning.A modified differential evolution algorithm with local enhanced operator［J］.ACTA Electronica Sinica，2007，35 （5）：849－853 （in Chinese）.［赵光权，彭喜元，孙宁.带局部增强算子的微分进化改进算法 ［J］.电子学报，2007，35 （5）：849－853.］

［15］HE Yichao，WANG Xizhao，LIU Kunqi，et al.Convergent analysis and algorithmic improvement of differential evolution［J］.Journal of Software，2010，21 （5）：875－885 （in Chinese）.［贺毅朝，王熙照，刘坤起，等.差分演化的收敛性分析与算法改进 ［J］.软件学报，2010，21 （5）：875－885.］