基于反射变异策略的自适应差分进化算法

钱武文，柴军瑞，张子映，谈 然

西北旱区生态水利工程国家重点实验室培育基地（西安理工大学），西安 710048

1 引言

差分进化算法[1]（DE）于1995年提出，是一种类似遗传算法、蚁群算法的群优化算法，具有结构简单易于操作、对求解函数无特殊要求以及参数少的优点。作为一种群体智能优化算法，DE也同样易于发生算法早熟和进化停滞。缺乏种群多样性是导致DE发生早熟收敛的主要原因。DE使用贪婪的选择策略，个体只在生成了具有更好适应值个体的前提下才能发生进化。对于最小值优化问题，从统计上讲，个体函数值越小其发生进化的概率也越小。因此，如何更好地维持DE的种群多样性和增强子代生成策略的鲁棒性是改进DE的两个重要方向。

DE具有缩放因子(F)，交叉因子(CR)和种群规模(NP)三种参数，其中F和CR是子代生成策略直接使用的两种参数。相比原始DE使用固定的F和CR值，自适应变化的F和CR能改善DE的性能。针对这两个参数，研究者们提出了多种自动调节参数的方法[2-4]。文献[5]提出一种遗传成功个体的参数而失败个体参数重生成的参数调节方法（jDE）。Zhang等[6]提出一种具有反馈调节的自适应参数调节方法（JADE），该方法能根据成功个体的参数信息反馈调节F和CR的值。Tanabe等[7]在JADE的基础上，提出了一种带历史参数存储的自适应方法（SHADE），该方法在JADE的基础上进一步提升了算法的鲁棒性。

子代生成策略高度影响着DE的性能。算法的全局探测能力和局部开采能力是相互对立的。国内外学者针对怎样平衡DE的探测和开采能力方面提出了一些改进的子代生成策略[8-10]。Zhang等[6]基于current-to-best/1提出了一种新型的变异策略current-to-pbest/1，即从 p个最优个体任选一个代替current-to-best/1中的最好个体。Mohamed[11]提出了一种基于三角变异策略的改进DE，其在无约束全局优化问题中取得了不错的效果。Yi等[12]提出了一种混合的变异策略，该变异策略使用全局探测性能较强的ran/1和局部开采能力较强的currentto-best/1按一定规则混合使用。

NP作为DE的另一大参数，相比其他两个参数国内外学者对NP的研究较少。主要在于一些学者发现当引入一些自适应策略去控制种群规模后，可能使得算法停滞和早熟收敛变得更糟[13]。当前的自适应控制种群规模的方法[14-15]共同体现出了一个问题，那就是增加种群规模会降低找到正确搜索方向的可能性，而降低种群规模则导致早熟收敛和算法停滞的可能性增加。

Nelder-Mead方法是一种无约束非线性优化的直接搜索方法，使用D+1个点构成的广义三角形作为单纯形进行搜索，有着优秀的局部收敛速度。本文受Nelder-Mead方法启发，提出了一种类似Nelder-Mead方法中反射操作的变异策略，称为反射变异策略。该策略使用随机的4个个体完成一次变异操作，具有明确的变异方向。参与变异操作的个体的选择随机性降低了算法早熟的可能性。引入了一种控制参数自适应调节方法，结合本文提出的变异策略使用固定的种群规模组成了RMADE算法以期进一步提升算法的整体性能。大量实验测试表明反射变异策略的提出的价值。

2 基本差分进化算法

2.1 初始化种群

DE基于实数编码，首先在问题的可行域上随机生成初始种群，Xi=(xi,1,xi,2,…,xi,D),i={1,2,…,NP}，其中D为变量的个数，NP为种群规模。具体操作如下：

其中，xmin,j，xmax,j分别为第 j维的最小值和最大值，r为[0，1]之间的均匀随机数。

2.2 变异操作

与其他进化算法的变异操作不同的是，DE采用父代的差分矢量作为其最基本的变异成分，每个差分矢量是由父代中两个不同的个体相减得到，对差分矢量进行缩放后，与种群中另外的相异个体进行相加便得到变异矢量。目前，已有几种主要的变异矢量的生成方法，其相应表达式见表1，其中：g为代数，Xbest,g为第g代群体找到的最优位置；Xa,g,Xb,g,Xc,g,Xd,g,Xe,g为随机选择的5个不同个体，F为缩放因子。

表1 基本变异策略的名称及表达式

2.3 交叉操作

为了提高种群的多样性，DE引入交叉操作，使得实验向量至少有一位分量由变异矢量贡献，具体如下：

其中，CR为交叉算子，r为0～1的均匀随机数，jrand为[1，D]的随机整数。

2.4 选择操作

良好的选择策略能显著提高算法的收敛性能，DE采用“贪婪”的选择策略，通过由经过变异和交叉操作所生成的实验个体与父代个体进行竞争，择优选择进入下一代种群中的个体，具体如下：

（1）最小值问题

（2）最大值问题

为了不失一般性，本文的研究为最小值优化问题。

3 提出的算法

将详细介绍本文提出的基于反射变异策略的自适应差分进化算法（RMADE），首先介绍提出的反射变异策略。

3.1 反射变异策略

作为一种无约束非线性优化的直接搜索方法，Nelder-Mead方法使用单纯形进行搜索（对于D维优化问题，其单纯形是D+1个点构成的广义三角形）。首先，计算单纯形各顶点的函数值并对其按从小到大进行排序，得到最好点、次坏点和最坏点。由除最坏点外的其余个体计算单纯形中心，然后通过反射、扩张、收缩和压缩等操作搜索更好的点构成新的单纯形，当达到预期的精度或其他终止条件时，方法终止，否则，迭代单纯形。Nelder-Mead方法简单易于实现，且适用于导数未知的非线性最优化问题，有着优秀的局部收敛速度，因此，Nelder-Mead方法广泛应用于各个领域。

尽管Nelder-Mead方法存在上述优点，但它对初始解有着较强的依赖性，并且当求解多模态问题时，易于陷入局部收敛。因此，除了对于一些特定问题的优化外，Nelder-Mead方法有着很大的局限性。Nelder-Mead方法的反射是最坏点基于中心点的反射，其扩张操作进行的前提是反射点优于最好点。收缩操作是在反射点劣于次坏点的情况下进行的。若反射和收缩操作都不能找到优于次坏点的点时，才进行压缩操作。压缩操作的作用是压缩搜索空间。反射和扩张操作的搜索方向是一致的，都是最坏点到中心点的方向。差分进化算法经过一定的进化代数后，种群个体将呈现出往最优解附近聚集的趋势[16-17]。因此，差分进化算法的搜索过程实际上是和Nelder-Mead方法的压缩操作类似。受Nelder-Mead方法启发，提出一种新型的变异策略，本文称之为反射变异策略。该变异策略同样引入一种单纯形的概念，即不论求解问题的维数，始终选择种群中的4个任意个体组成单纯形，每完成一次变异操作须引入一个单纯形。该策略操作如下：

其中，Vi,g为i个体在g代的试向量；Xo,g是单纯形中心；Xa,g和Xd,g分别为单纯形中的最好点和最坏点，F为变异缩放因子。

不同于Nelder-Mead方法，本文使用的单纯形中心Xo,g是根据单纯形顶点的函数值计算的，并且除最坏点外的各个顶点均按其函数值权重分配到中心中。单纯形中心Xo,g的计算公式如下：

其中，w1，w2和w3分别为除最坏点外的其余单纯形顶点的权重；Xa,g,Xb,g和Xc,g为除最坏点外的剩余单纯形顶点。

这种变异策略既类似于Nelder-Mead方法中的反射操作，具有明确的搜索方向，又类似于基本差分进化算法中的rand/1变异操作，其基向量拥有一定的随机性。采用本文提出的变异操作生成子代个体的过程如图1所示。

图1 反射变异策略的变异操作示意图

3.2 控制参数自适应调整机制

传统的差分进化算法采用固定的变异因子和交叉因子，而针对不同的优化问题，使用固定的控制参数将严重妨碍了算法的性能。参数自适应调整机制允许每一个体使用不同于其他个体的缩放因子F和交叉因子CR去生成子代个体，且能根据算法进化过程中成功个体的经验反馈调节控制参数。本文采用SHADE[7]算法中的参数自适应调整方法。

F和CR分别由一个柯西分布和一个正态分布随机产生，这两个分布的标准差都为0.1。均值则是从两个大小都为H的用来存储控制参数均值的数组中随机抽取。初始这个数组中的元素为0.5。

变异因子F和交叉因子CR分别按式（7）和（8）自适应生成：

其中，randc(MF,ri,0.1)和randn(MCR,ri,0.1)分别为服从均值为MF,ri标准差为0.1的柯西分布和均值为MCR,ri标准差为0.1的正态分布的随机数。当Fi＞1，则令Fi＞1；若 Fi＜0，则重新使用公式（8）生成 Fi。CRi∈[0，1]，若超出边界，则使用距其最近的边界替换。MF,ri为MF中序号为ri的元素，MCR,ri为MCR中序号为ri的元素，ri为一个1～H的随机整数。MF和MCR内的值影响F和CR的随机产生，根据每一个优化问题的不同进化阶段中成功个体的参数信息反馈调节MF,ri和MCR,ri的值，将改进算法的性能。引入一个位置参数pos用来控制MF和MCR的更新位置，pos初始值为1，当 pos＞H ，则 pos=1，否则 pos每更新完一次则+1。MF,pos和MCR,pos的更新过程如下：

其中，SF和SCR是当前代中所有成功个体的相应控制参数信息。SF和SCR的数组大小等于当前代中成功个体的个数。当试向量Ui,G有一个更低的目标函数值（最小值优化问题）时，其相应的母个体的控制参数将保存在SF和SCR中，即Fi→SF，CRi→SCR。

其中，meanWA(·)是算术平均算子，meanWL(·)是Lehmer平均算子。wk为控制MF,i和MCR,i更新的权值，用于减缓进化过程中SCR和SCR可能偏于较小值的问题[18]。使用Δf来记录成功个体的减少的函数值Δf(k)=fold(k)-fnew(k)，数组Δf的大小等于当前代中成功个体的数目。

3.3 算法的基本思想和步骤

变异策略DE/rand/1具有很强的全局收敛能力，却有着较慢的收敛速度。传统的Nelder-Mead方法具有优秀的局部收敛能力，却有着很差的全局探测能力。怎样在全局收敛性和局部搜索速度之间寻求一个平衡是本文的核心。对此，本文受Nelder-Mead方法启发，提出了一种新型的变异策略。该策略既结合了rand/1的随机性，又结合了Nelder-Mead方法的搜索方向的明确性，因此能在降低早熟收敛的可能性的同时提高算法的收敛速度。使用自适应参数调节方法进一步提升了算法的整体性能。具体步骤如下：

步骤1初始化H、缩放因子均值MF和交叉因子均值MCR。

步骤2根据公式（1）随机产生初始种群并计算初始种群。

步骤3判定是否达到终止条件，若是转步骤8，若否则转步骤4。

步骤4按公式（7）和（8）随机生成控制参数。

步骤5对每一靶个体，从当前种群中随机抽取4个个体，比较它们的函数值，按公式（5）完成变异操作并按公式（2）完成交叉操作。

步骤6计算试向量的函数值并与靶个体比较，若好于靶个体，则替换靶个体。

步骤7根据公式（9）和（10）更新缩放因子均值MF和交叉因子均值MCR；返回步骤3。

步骤8输出最优个体。

4 测试函数与参数设置

本文使用的算法使用Frotran90编写，编译环境为Intel Visual FORTRAN Composer XE 2013 with VS2010，在配置为2.83 GHz Intel®Core™2 Quad CPU和4 GB内存的计算机上运行，运行Windows 7系统。

4.1 测试函数

本文采用和文献[19]相同的12个测试函数来进行测试算法的性能。 f1～f5为单峰函数，其中 f5为阶梯函数，f6为噪音函数，f7～f12为多峰函数。值得注意的是，f4是Rosenbrock函数，当其维数D=2和3时，是单峰函数，但其在高维问题上存在多个极小值点[20]。测试函数的相关特性如表2所示。

表2 测试函数的名称、维数、搜索空间和最优值

4.2 算法性能比较

为了使本文算法具有可比性，将RMDE与HSDE[12]，jDE[5]和SHADE[7]进行比较。参与比较的算法的参数与原文参数一致。对于上述12个问题，种群规模都设置为100。记录独立运行30次的平均值（Mean）和标准差（Std Dev）。为使实验结果的比较具有统计性，使用Wilcoxon符号秩检验对各算法的实验结果进行检验，使用符号“+”、“=”和“－”分别表示本文算法比目标算法在统计学上“显著更好”、“没有显著的更好或更差”和“显著更差”。为了增加测试结果的可读性，将性能表现最好的实验结果加粗显示。实验结果如表3所示，表中后3行分别统计了“+”、“=”和“－”的数目。

由表3可知，RMADE在单峰函数和多峰函数上的求解中都表现出了最好的性能。对于单峰函数 f1～f5，RMADE表现在函数 f3和 f4上相比其他算法具有显著优势，在噪音函数 f6的优化中，RMADE表现最佳，其次为SHADE、jDE表现最差，说明了本文的算法在求解噪音函数方面具有较好的抗干扰能力，这主要归功于本文提出的反射变异策略在生成试向量的过程中使用了较多个体的信息。RMADE在多峰函数 f7～f12相比其他算法表现最佳，特别在求解函数 f8～f9中，RMADE相比表中其他算法具有显著的优势，说明RMADE具有不错的全局收敛能力。需要注意的是，RMADE在对函数 f8的优化中在给定的较少函数评价次数的情况下能收敛到全局最优值，而其他算法均未完成收敛，说明RMADE相比参与比较的其他算法具有更快的收敛速度。总的来说，使用反射变异策略并结合3.2节中的参数自适应调整机制的RMADE能较好地平衡算法的探测和开发能力。

表3 RMADE和其他DE变体在12个测试函数上的测试结果

为了更直观地对比各算法的收敛速度，绘制了各算法求解上述12个测试函数时的收敛过程曲线，如图2所示。从图中可以看出，RMADE在单峰函数和多峰函数下都具有最佳的收敛速度。RMADE与SHADE具有可比性，RMADE和SHADE使用相同的参数调整机制但RMADE的收敛速度比SHADE更好，这是由于RMADE采用的反射变异策略利用4个个体的信息去指导试向量的生成，并且将其中的最优个体和最劣个体的差分向量作为变异的方向，从某种程度上讲反射变异策略属于贪婪变异策略。

4.3 变异策略比较

为进一步考察本文提出的变异策略在探测和开发方面的性能，从表2中选取单峰函数 f1和多峰函数 f8作为测试函数，将本文提出的反射变异策略与表1中基本变异策略进行比较。为了保证比较的公平性，所有的变异策略使用二项式交叉策略，并使用3.2节描述的自适应参数方法。绘制两种函数下的收敛过程曲线如图3所示。

由图3可知，对于单峰函数 f1，策略best/1的收敛速度最快、精度最高，其次就是本文提出的反射变异策略，rand/2的收敛速度最慢。对于多峰函数 f8，只有本文提出的反射变异策略在给定的函数评价次数下搜索到了全局最优值0，因此精度最高，其后为rand/1和rand/2。策略best/1、best/2和current-to-best/1在前期收敛速度快，但它们过于强调算法的开采能力而忽略了算法的探测性，因而陷入了早熟收敛。从总体上看，本文提出的反射变异策略既具有不错的局部收敛速度，又具有良好的全局收敛能力。因此本文提出的反射变异策略相比其他基本的变异策略具有更好的性能，因而其的提出是有意义的。

4.4 自适应参数分析

缩放因子F和交叉因子CR的取值对算法的性能具有很大的影响，为了研究算法RMADE的参数自适应机制，绘制了12个测试函数下的控制参数进化曲线，如图4所示。从图4可以看出，两参数的均值(MF和MCR)随算法的进化而取不同的值，以满足不同阶段下的参数要求。算法求解的函数类型不同时，较优的参数取值亦不相同。相比缩放因子F，交叉因子CR对算法的收敛性有着更加重要的作用。当求解单峰函数时(f1～f5)，由图2中可知，交叉因子CR随着进化的进行变得越来越大。而在多峰函数(f7～f12)时，算法在搜索过程中会先后经历两个阶段，即探测和开采。在探测阶段，算法所需CR相对较小以满足维持种群多样性的要求，而当算法搜索到最优解的山谷时，则即将进入开采阶段，此时算法所需的CR相对较大，以达到加速开采的目的。从图2（g）、图2（h）和图2（l）中可以明显地看到 CR 的这一变化过程。对噪音函数 f6的求解中，由于噪音元素为0～1之间的随机数，因此噪音在搜索初期相对较小，可以看成普通单峰优化问题，随着进化的进行，噪音干扰将变得越来越明显，CR变大将更偏于随机搜索。由图4可知，本文所使用的参数调节机制能有效地调整算法各个进化阶段下控制参数的值。

图2 各算法收敛过程曲线比较

图3 各变异策略在函数 f1和 f8下的收敛过程曲线

[3]张春美，陈杰，辛斌.参数适应性分布式差分进化算法[J].控制与决策，2014，29（4）：701-706.

[4]张锦华，宋来锁，张元华，等.加权变异策略动态差分进化算法[J].计算机工程与应用，2017，53（4）：156-162.

[5]Brest J，Greiner S，Boskovic B，et al.Self-adapting control parameters in differential evolution：A comparative study on numerical benchmark problems[J].IEEE Transactions on Evolutionary Computation，2006，10（6）：646-657.

[6]Zhang J，Sanderson A C.JADE：Adaptive differential evolution with optional external archive[J].IEEE Transactions on Evolutionary Computation，2009，13（5）：945-958.

[7]Tanabe R，Fukunaga A.Success-history based parameter adaptation for differential evolution[C]//IEEE Congress on Evolutionary Computation，2013：71-78.

[8]Wang Y，Cai Z，Zhang Q.Differential evolution with composite trial vector generation strategies and control parameters[J].IEEE Transactions on Evolutionary Computation，2011，15（1）：55-66.

[9]Mallipeddi R，Suganthan P N，Pan Q K，et al.Differential evolution algorithm with ensemble of parameters and mutation strategies[J].Applied Soft Computing，2011，11（2）：1679-1696.

[10]Wu G，Mallipeddi R，Suganthan P N，et al.Differential evolution with multi-population based ensemble of mutation strategies[J].Information Sciences，2016，329（C）：329-345.

[11]Mohamed A W.An improved differential evolution algorithm with triangular mutation for global numerical optimization[J].Computers&Industrial Engineering，2015，85（C）：359-375.

[12]Yi W，Gao L，Li X，et al.A new differential evolution algorithm with a hybrid mutation operator and selfadapting control parameters for global optimization problems[J].Applied Intelligence，2015，42（4）：642-660.

[13]Yang M，Li C，Cai Z，et al.Differential evolution with auto-enhanced population diversity[J].IEEE Transactions on Cybernetics，2015，45（2）：302.

[14]Teo J.Differential evolution with self-adaptive populations[M]//Knowledge-Based Intelligent Information and Engineering Systems.Berlin Heidelberg：Springer，2005：1284-1290.

[15]Brest J，Maučec M S.Population size reduction for the differential evolution algorithm[J].Applied Intelligence，2008，29（3）：228-247.

[16]Tasoulis D K，Plagianakos V P，Vrahatis M N.Clustering in evolutionary algorithms to efficiently compute simultaneously local and global minima[C]//IEEE Congress on Evolutionary Computation，2005：1847-1854.

[17]Epitropakis M G，Plagianakos V P，Vrahatis M N.Balancing the exploration and exploitation capabilities of the differential evolution algorithm[C]//IEEE Congress on Evolutionary Computation，2008：2686-2693.

[18]Peng F，Tang K，Chen G，et al.Multi-start JADE with knowledge transfer for numerical optimization[C]//IEEE Congress on Evolutionary Computation，2009：1889-1895.

[19]李牧东，赵辉，翁兴伟，等.基于最优高斯随机游走和个体筛选策略的差分进化算法[J].控制与决策，2016，31（8）：1379-1386.

[20]Yao Xin，Lin Guangming，Liu Yong.Evolutionary programming made faster[J].IEEE Transactions on Evolutionary Computation，1999，3（2）：82-102.