基于两阶段变异交叉策略的差分进化算法

张大斌，江 华，徐柳怡，张文生

(1.华中师范大学信息管理学院，武汉 430079;2.中国科学院自动化研究所，北京 100190)

1 概述

差分进化(Differential Evolution，DE)算法是由Rainer Stoorn 和Kenneth Price［1］在1995 年共同提出的，它是一种简单、快速、基于全局的并行直接搜索优化算法。其原理简单、鲁棒性强、受控参数少、易于实现。由于差分进化算法对函数的可导性甚至连续性要求较低，近年来被广泛地应用于解决复杂的、离散的、非线性的优化问题，且具有良好的效果。DE 与传统的遗传算法(GA)不同，它采用实数编码、基于简单变异交叉操作和一对一的贪婪竞争生存策略，同时保有独特的记忆能力进行动态搜索，并可以不断调整其搜索策略，最后使种群个体趋于一致。标准的DE 算法在低维度函数寻优问题上能够使种群收敛于全局最优解，并且寻优速度快、求解质量高。但是在求解高维度、多峰值这些复杂函数问题过程中，很容易出现早熟现象，即算法经过多次迭代之后，个体间的差异变小，种群多样性降低并陷入局部收敛;后期收敛速度较慢并且缺乏稳健性。此外，在差分进化模式和参数取值上缺乏普遍的指导原则。为了提高差分进化算法搜索和开发能力及算法的收敛速度，许多学者对标准的DE 算法进行了一些研究和改进。如文献［2］提出一种基于DE 算法和NSGA-Ⅱ的多目标混合进化算法，确保最优解不会丢失并保证解的多样性。文献［3］提出一种带基向量种群的改进差分进化算法，通过缩小基向量选择范围减少迭代次数。文献［4］在DE 算法中引入搜索空间扩展机制，有效增强了算法的全局收敛能力，该算法在解决线性系统最优近似问题时有一定的优势;文献［5］提出一种基于适应性步长的局部搜索策略来确定合适的缩放比例因子F，从而加速算法全局搜索的进程;文献［6-8］采用反向学习方法初始化种群和实现个体跳变以加快算法的收敛速度。

本文将两阶段变异交叉策略引入到差分进化算法中，提出了一种改进的差分进化算法。该算法采用反向混沌搜索产生初始个体种群，进而根据种群适应值将个体种群分为好个体子种群和坏个体子种群，两阶段变异交叉操作依次对不同的子种群采取不同的差分策略，借助种群内个体的知识学习能力，使种群内全局搜索寻优信息和局部搜索寻优信息协同在种群间稳定扩散，以达到平衡搜索开发能力和加快收敛的目的，从而提高算法的收敛速度、稳健性和通用性。

2 差分进化算法

差分进化算法(DE)和传统的遗传算法(GA)相似，通过交叉、变异和选择3 种策略对候选种群进行反复的迭代，最终趋于全局最优解。但与其他进化算法不同的是，DE 是借助种群个体间不同粒子间的加权差异向量来对另一个体进行扰动实现变异操作，以产生新差异向量，种群中的每个个体都要进行干扰。接下来对父代个体和生成的变异个体按照一定的交叉概率进行交叉操作生成中间个体;最后采用贪婪淘汰策略在父代个体和中间个体之间进行适应度一对一比较选择操作，选择具有更佳适应度的个体作为下一代迭代种群。基本差分进化算法的主要操作如下［9］:

(1)种群初始化，定义参数向量个体:

式(1)表示的是第g 次迭代的第i 个个体，随机产生的种群规模为NP，每个个体均有D 个分量。在可行域内依据式(2)随机产生初始种群:

其中，xmax，j，xmin，j分别是xi个体中第j 个分量的上下限;randi，j(0，1)为［0，1］区间的一个随机数。

(2)变异操作，对种群中的每个目标向量xgi，随机寻找除自身外3 个不同的个体r1，r2，r3(此时需满足NP≥4)，根据式(3)，将其中2 个个体的向量差经缩放后加到另一个体上，得到变异后的个体

其中，F(通常取0.5)是缩放比例因子，起控制差异变量缩放幅度的作用。

其中，r∈(0，1)为向量第j 个分量对应的均匀分布的随机数;rd为［1，D］中第i 个向量对应的随机整数;它的作用是确保中间向量和目标向量的差异性。CR∈［0，1］(一般取0.5)是交叉概率，它是另外一个控制参数，指定变异向量的继承水平。

其中，f(x)是适应值函数。

(5)收敛判断，当算法运行达到预定进化代数Gmax或目标函数值VTR 小于某一阈值，即达到设定的精度时，结束整个算法的运行，否则将对种群进一步执行变异、交叉和选择操作。

此外，还有多种差分策略，习惯上将差分策略统一标记为DE/x/y/z，其中，x 限定当前被变异的向量是随机的或最佳的;y 表示变异过程采用的差分向量个数;z 表示交叉程序的操作方法，上面叙述的交叉操作就是bin。其他差分进化算法DE/best/1/bin 和DE/best/2/bin 策略的变异操作分别如下:

差分进化算法流程如图1 所示。

图1 差分进化算法流程

3 两阶段变异交叉策略

大多数研究人员专注于选择合适的控制参数值，并取得了不错的成就［10-11］。本文提出了一个新的方向，以改善DE 全局和局部搜索寻优能力。首先，种群根据适应值大小排列。然后，它们分为较好子种群、较差子种群。最后，种群进行变异、交叉和选择操作进入下一代。本文提出2 个变异交叉阶段子种群数量具有差异性的变异策略，较好子种群的数量随着阶段的发展逐级增加，持续稳定加强较好子种群的全局搜索寻优能力的学习，并同时提高较差子种群的局部搜索寻优能力的学习，使全局和局部搜索寻优信息协同在种群间持续稳定扩散，从而不断增加种群寻优质量。

3.1 第一阶段

根据种群的适应值大小，将种群分为较好子种群(better)M1 和较差子种群(worse)M2。

变异操作，对于较好子种群，选取3 个不同粒子，一个是较差子种群的最优粒子另外2 个不同粒子来自较好子种群，分别为具体公式DE/wbest/1 如下:

变异操作，对于较差子种群，选取3 个不同粒子，一个是种群最优粒子，另外2 个不同粒子来自较差子种群，分别为具体公式如下:

3.2 第二阶段

变异操作，对于较好子种群，选取3 个不同粒子，一个是较差子种群的最优粒子，另外2 个不同粒子来自较好子种群，分别为具体公式DE/wbest/1 如下:

变异操作，对于较差子种群，选取3 个不同粒子，一个是种群最优粒子另外2 个不同粒子来自较差子种群，分别为具体公式如下:

4 基于两阶段变异交叉策略的差分进化

4.1 反向混沌搜索的种群初始化

由于算法在进化初期缺少先验知识，即只能在可行域中随机产生初始种群，而寻优时间往往又与初始种群的质量有关，即个体到全局最优值的距离密切。因此，针对算法存在进化初期收敛速度慢的不足，利用反向学习方法［12］和混沌搜索［13］有机结合产生初始种群。首先利用混沌序列的随机性、遍历性和初值敏感性来提高初始随机数的质量。现在大多数都采用Logistis 映射来产生混沌序列，可以用下式描述:

其中，xi表示混沌序列变量在第i 次迭代时的值;v是控制变量常数。当v 取值范围为［3.56，4.0］，xi就是一个混沌变量。这时系统处于完全混沌状态，序列可以无重复。然后借助反向学习方法，为每个混沌序列产生的个体生成相应的反向个体，接着合并上述步骤产生的2 个种群，并对所有个体按适应值大小排序，最后选择其中相应规模的较优个体组成初始种群，以提高算法的收敛速度。反向混沌搜索过程如下:

Step 1混沌搜索产生规模为NP 的种群P，其个体为xi=(xi1，xi2…，xiD)，i=1，2，…，N，且每个分量xij∈［aj，bi］，j=1，2，…，D。

Step 2产生种群P 对应的反向种群OP，其个体其中，

Step 3合并种群P 和OP，按照适应值的大小进行排序，从中选取规模为NP 的较优个体组成算法的初始种群。

4.2 融合两阶段变异交叉策略的差分进化算法

融合两阶段变异交叉策略的差分进化算法(TMCDE)，采取两阶段子种群并行变异交叉进化策略。初始种群根据适应值分为较好和较差2 个子种群。较好子种群全局搜索寻优能力相对不足，较差子种群局部搜索寻优能力相对不足。因此，在种群进化寻优阶段，对较好和较差2 个子种群分别采取不同的变异交叉策略，使种群全局和局部搜索寻优能力并行发展。

第一阶段:较好子种群规模M1，较差子种群规模M2。较好子种群变异策略采用式(8)，可知，变异个体由较差子种群个体和较好子种群中2 个互不相同的随机个体组成，增强较好子种群的多样性。较差子种群变异策略采用式(9)，可知，变异个体由个体和较差子种群中2 个互不相同的随机个体组成，提高了较差子种群的局部搜索寻优能力、搜索精度和收敛速度。但在一定程度上会加大算法收敛速度过快，容易陷入局部最优点的可能性。较好子种群M1 采取交叉1 策略，目的是保持当前最优个体的引导作用的同时，相应增加种群的多样性。较差子种群M2 采取交叉2 策略，目的是提高较差子种群的寻优质量。第一阶段的目的是为了缩小种群内个体的差异性，使种群相对更加集中。

第二阶段:较好子种群规模M3(M3 ＞M1)，较差子种群规模M4。较好子种群变异策略采用式(10)，可知，变异个体由较差子种群个体和较好子种群中2 个互不相同的随机个体组成，较第一阶段进一步提高了种群的多样性和全局搜索能力。较差子种群采用式(11)，可知，变异个体由个体和较差子种群中2 个互不相同的随机个体组成，较第一阶段继续提高种群的局部搜索能力、搜索精度和收敛速度。种群的交叉策略同第一阶段一样。第二阶段的目的是在增加对较好子种群个体进行扰动的同时，能促使种群向新产生的最优个体靠拢，从而起到边扰动种群，边聚集种群的作用，进而不断提升种群寻优的质量。

为平衡全局搜索寻优能力和收敛速度之间的矛盾。在2 个阶段，种群均独立进化若干代(一般是5 代)，有利于全局和局部搜索寻优信息在种群间的稳定传播。第一阶段，2 个子种群第一次独立并行进化完成后，重新融合成一个新的种群，根据适应值大小再次将新种群分为较好和较差2 个子种群，并持续进化5 代，综合提高了种群全局和局部寻优的搜索能力。第二阶段在第一阶段种群进化发展的基础上，相应增加了较好子种群的个数，持续加强较好子种群的全局搜索寻优能力，同时一定程度上维持了种群的局部搜索寻优能力，进一步加强全局和局部搜索寻优信息协同在种群内的均衡扩散。

4.3 算法的实现过程

算法的实现过程如下:

Step 1种群初始化。按照反向混沌搜索方法初始化种群，产生规模为NP 的初始种群。

Step 2将种群按适应值分为较好子种群M1 和较差子种群M2。

Step 3对较好子种群M1 的个体，采用DE/wbest/1/bin 的变异策略和交叉1 策略进行差分进化。

Step 4对较差子种群的M2 个体，采用DE/best/1/bin 的变异策略和交叉2 策略进行差分进化。

Step 5重新产生较好子种群和较差子种群，并跳到Step3，持续进行5 代，重新开始子种群的并行搜索。

Step 6合并2 个子种群，并重新产生较好子种群M3 和较差子种群M4。

Step 7对较好子种群M3 的个体，采用DE/wbest/1/bin 的变异策略和交叉1 策略进行差分进化。

Step 8对较差子种群的M4 个体，采用DE/best/1/bin 的变异策略和交叉2 策略进行差分进化。

Step 9重新产生较好子种群和较差子种群，并跳到Step7，持续进行5 代，重新开始子种群的并行搜索。

Step 10合并2 个子种群，并且按照适应值排序。若当前迭代次数小于最大迭代次数，则转Step2，否则转Step10。

Step 11结束寻优，输出结果。

两阶段变异交叉差分进化算法流程如图2所示。

图2 两阶段变异交叉差分进化算法流程

5 函数优化中的应用仿真与结果分析

5.1 函数仿真

由于不同差分策略的进化算法对多数单峰低维函数均有较好寻优效果，为测试所提出的TMCDE 算法的性能，主要选取了5 个具有不同特点的函数作为测试函数，根据所选的指标对算法的性能进行测试，各测试函数如表1 所示。

为考察TMCDE 算法的性能，选取了DE/rand/1，DE/best/1 及DE/best/2 这些差分策略的进化算法作比较，对测试函数进行寻优仿真。差分进化算法的参数设置主要由差分策略和待求解问题决定，其主要涉及缩放因子F 和交叉概率CR 这2 个参数。为了确保算法寻优的可比性，本文统一选取种群规模NP=100，M1=30，M3=40，{F=0.5，CR=0.9}，此外，TMCDE 算法中2 个阶段信息传递间隔均为5，对30 维函数寻优，迭代次数100 次，并独立运行30次，寻优结果如表2 所示。

表1 选取的测试函数

5.2 函数的实验结果分析

从表2、图3 所示的简单30 维单模态Sphere 函数的优化结果可以看出，各个算法的最优值、最差值、平均值和标准差结果显示，TMCDE 算法在单模态函数上具有较好的寻优能力，得到的优化结果明显优于其他算法。从收敛曲线可以看出，TMCDE 算法性能最好，能够持续、有效地搜索函数全局最优点。前期性能良好、收敛速度快，后期能够在最优极值点附近进行细致搜索。从表2、图4 中对于30 维多模态Rantrigin 函数，可以看出TMCDE 算法和各种差分策略算法都能找到函数的最优点，但是TMCDE 算法表现出了较好的全局收敛性和健壮性，收敛曲线在前期就能够迅速地接近于最优点，而其他差分策略收敛速度较慢，需要较多的迭代次数才能收敛到极值点附近，另外在图中DE 算法很容易停滞于局部极值点。从表2、图5 所示的复杂单模态Rosenbrock 函数优化结果来看，TMCDE 算法能够寻找到理论最优点，并且本文算法自寻优早期既有较好的收敛速度，又可以通过相对较少的迭代次数找到正确的搜索方向，从而保持继续下降，能够快速地找到最优极值点，并且DE/rand/1 算法目标函数值均大于0.01。表2、图6 显示了30 维Schaffer 函数的优化结果，虽然后期各算法均陷入了局部极值点，但是TMCDE 算法能保持正确的搜索方向，持续地寻找全局最优点，在搜索后期仍能够保持较好的种群多样性，算法性能显著。表2、图7 显示了30 维Step 函数的优化结果，TMCDE 算法表现出了较好的全局寻优能力，收敛曲线在前期就能够迅速地接近并且达到最优点，而其他DE 算法需要较多迭代次数才能收敛到极值点附近。综上所述，本文算法TMCDE 无论在单模态还是多模态优化问题中均表现出了较好的寻优结果和收敛速度，效果显著。

表2 运行30 次30 维函数的优化结果

图3 Rosenbrock 函数收敛曲线

图4 Schaffer 函数收敛曲线

图5 Step 函数收敛曲线

图6 Schaffer 函数收敛曲线

图7 Step 函数收敛曲线

6 结束语

本文提出了一种基于两阶段不同变异交叉策略的差分进化算法，通过在差分进化算法中引入反向混沌搜索初始化种群方法和两阶段不同变异交叉策略，使算法全局快速收敛，并提高了算法收敛精度。函数仿真表明，TMCDE 算法具有较好的收敛速度、优化精度和鲁棒性。然而，在引进两阶段变异交叉策略的同时也增加了算法参数的设置，如M1、M2、M3、M4。本文虽已借助函数仿真对算法进行了分析，但算法的参数设置在解决不同的实际问题时仍存在一定的难度。因此，在接下来的研究中，可以对算法的各个参数的性能进行比较分析，以降低参数设置的复杂度，增加搜索过程的随机性，从而提高整个算法的性能。由于差分进化算法的通用性强，易与其他算法相结合，诸如与人工免疫网络、灰色预测预警等相结合，进行模型参数优化，在提高预测精度上有较好的效果，能够更好地解决现实中的工程管理问题。

［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):58-64.

［2］王 林，陈 璨.一种基于DE 算法和NSGA-II 的多目标混合进化算法［J］.运筹与管理，2010，19(6):46-50.

［3］姜立强，强 洪.带基向量种群的改进差分进化算法［J］.计算机工程，2012，38(3):9-11.

［4］Cheng S L，Hwang C.Optimal Approximation of Linear Systems by a Differential Evolution Algorithm［J］.IEEE Transactions on Systems，Man，and Cybernetics，2001，31(6):698-707.

［5］Chiou J P，Chang C F，Su C T.Variable Scaling Hybrid Deferential Evolution for Solving Network Reconfiguration of Distribution Systems ［J］.IEEE Transactions on Power Systems，2005，20(2):668-674.

［6］Rahnamayan S，Tizhoosh H R.Opposition-based Differential Evolution ［J］.IEEE Transactions on Evolutionary Computation，2008，12(1):64-69.

［7］Wang Yuanhui，Wang Xiukun，Teng Hongfei.Oppositionbased Cooperative Co-evolutionary Differential Evolution Algorithm with Gaussian Mutation for Simplified Satellite Module Optimization ［J］.Information Technology Journal，2012，11(1):67-75.

［8］刘 罡，李元香，郑 昊.保存基因的2-Opt 一般反向差分演化算法［J］.小型微型计算机系统，2012，33(1):115-120.

［9］杨添柔.连续域优化问题的差分进化算法研究［D］.武汉:华中师范大学，2013.

［10］戈剑武，祁荣宾，钱 锋，等.一种改进的自适应差分进化算法［J］.华东理工大学学报:自然科学版，2009，35(4):600-605.

［11］王海伦，余世明，郑秀莲.自适应差分进化算法及其在参数估计中的应用［J］.计算机工程，2012，38(5):202-207.

［12］汪慎文，丁立新，谢承旺，等.应用精英反向学习策略的混合差分进化算法［J］.武汉大学学报:理学版，2013，59(2):111-116.

［13］卢有麟，周建中.基于混沌搜索的自适应差分进化算法［J］.计算机工程与应用，2008，44(10):31-33.