引入反向学习机制的自适应差分进化算法研究∗

苗晓锋 刘志伟

（1.神木职业技术学院信息中心 神木 719300）（2.西北工业大学信息中心 西安 710072）

1 引言

差分进化（Differental Evolution，DE）是由Price和Storn［1］首先提出的一种简单而强大的基于种群的随机搜索技术。DE的性能在很大程度上取决于变异策略的选择和相关参数的设置［2～3］，不同的策略和参数设置导致了不同的算法性能，尤其是参数值很大程度上决定了最终所能获得最优解的质量和求解搜索的效率［4］，而如何选择适当的参数值是一个与问题特性相关的问题，往往需要依靠使用者的既有经验。许多研究都尝试解决这一问题，如模糊 DE（FADE）［5］，自适应 DE（SaDE）［6］，自适应控制参数 DE（SADE）［4］和相邻搜索自适应DE（SaNS⁃DE）［7］等。

本文提出了一种基于混合策略的差分进化算法MDE（Mixed DE），即结合反向学习机制和自适应控制参数的DE，并通过求解两个单峰函数和三个多峰函数所进行的测试实验，将MDE与已有的ODE［3］、SADE［4］、CEP［8］和 FEP［8］算法进行了性能比较。

2 差分进化算法

差分进化（DE）算法是一种基于种群和定向搜索策略的优化方法［1］。如同其他进化算法一样，从一个随机生成的初始解种群开始，模仿生物进化时基因变异和杂交的特点进行迭代求解，直至找到最终解。

DE有几种最基本的形式［1］，最流行的一种是“DE/rand/1/bin”。该算法基于以下工作模式，即首先随机生成初始试验解，然后通过变异和杂交操作产生新的试验解，再通过选择操作决定哪些试验解进入下一代种群成为候选解，然后反复进行变异、杂交和选择的迭代操作，直至所得到当前解的精度达到要求时停止求解。

首先，定义 Xri，G(i=1，2，…Np)是第 G 代种群的解向量，其中NP是种群的大小。

变异操作：每个G代种群中的解Xri，G变异生成一个试验解 Vi，G，定义如下：

其 中 ，i=1，2，…Np，r1，r2和 r3是 集 合{1，2，…Np}中任意互不相等随机整数，F是缩放系数。

杂交操作：如同其它遗传算法一样，DE也利用杂交算子结合两个不同的解来生成试验解，该试验解定义如下。

其中CR是预先定义好的杂交概率，randj(0，1)是（0，1）范围内的任意随机数，k∈{1，2，…，D}也是随机数。

选择操作：决定 Ui，G和 Xi，G二者当中哪一个成为下一代G+1种群的成员。对求最优值问题而言，能得到更好目标值的解将被选中继续进行迭代运算。

3 改进思路

经典DE算法的性能很大程度上依赖于变异策略和相关参数值F和CR的选择，不同的变异策略和参数选择会导致不同的性能表现。

Fan和Lampinen［9］提出了一种新的DE，它引入三角变异算子，以在算法收敛速度和鲁棒性之间取得较好的平衡，从而提高DE的性能。Ali和Torn［10］引入了辅助种群和放大因子F的自动计算。Sun［11］提出了结合DE和分布估计的DE/EDA算法。Liu和Lampinen［5］提出了一种模糊自适应DE（FADE），它使用一个模糊逻辑控制器设置杂交与变异概率。Brest等［4］研究了具有自适应控制参数的DE（SADE）。SADE采用自适应控制机制调整参数F和 CR。Qin 和 Suganthan［6］提出了一种自适应 DE（SaDE），研究参数CR和变异策略的适应性。Yang等［12］引入了邻域搜索策略DE（NSDE），用服从高斯和柯西分布的随机数生成参数F，而不是预定义常数F。基于SaDE和NSDE，Yang等［7］提出了另一个版本的DE（SaNSDE），它吸收了SaDE和NSDE的优点。Rahnamayan等［3］提出了一种基于反向的DE（ODE）来提高算法收敛速度。它基于反向学习的模式，同时评估当前解和相反解，从而增加了找到更接近全局最优解的机会。ODE的实验研究表明，它比经典DE更快更鲁棒。

3.1 反向学习

反向学习［13］（OBL）已被证明是一种行之有效的搜索方法。在求某个给定问题的解x时，我们初始考虑的x值，并不一定足够精确，而是基于经验或完全随机的猜测。我们也可以同时使用x的相反值来尝试得到一个更好的解x*，这样可以使下一代的x更快逼近最优解。相反解x*可以计算如下：

其中X∈R且在区间［a，b］上。

同样，这个定义可以扩展到更高的维度，如：

假设f（x）是一个给定问题的适应度函数，Pi（xi1，xi2，…，xin）是当前种群中第i个体，OPi（xi1*，xi2*，…，xin*）是Pi对应的反向个体，如果f（OPi）优于f（Pi），则用OPi代替Pi，并进入下一代种群。为了控制反向的步长，aj和bj应根据当前种群大小P动态更新，这意味着使用当前群每个维度的最小值和最大值（［aj（t），bj（t）］）来计算反向解，而不是用预先定义的固定（［aj，bj］）。动态的反向将有助于找到更好的解，并加速算法收敛［3］。新的反向计算方法为

其中Pij是种群P中第i个个体的第j维向量，OPi是Pi的反向个体，aj（t）和bj（t）分别是当前搜索空间第j维的最小值和最大值，而t=1，2，…，指进化代数。

3.2 自适应控制参数

如何选择合适的控制参数值［14～15］通常是一个与问题本身特征相关的任务。一般使用试错模式以调整控制参数，但需要多次优化运行。Brest等［4］提出了一种新机制来调整控制参数F和CR。这种新的方法为每个Pi定义了Fi和CRi，每一代参数的自动调整机制如下：

其中r1、r2、r3和r4是四个在［0，1］上的独立随机数。参数ε1和ε2分别代表了调整F和CR因子的概率。将ε1和ε2设为 0.15，Fl和 Fu分别设为 0.15 和0.9。因此，新F以随机方式从［0.1，1］中获取一个值，新的CR从［0，1］中获取一个值。

4 新的DE算法

本文提出了一种兼具两种机制的差分进化算法MDE，它结合了反向学习和自适应控制参数机制。其中，反向学习可以减少计算时间开销而自适应控制参数可以减少求解过程与问题自身的相关度。MDE的算法流程如下：

Begin

po=反向概率；

best_fitness_value_so_far=当前最优适应值；

VTR=到达值；

MAXNFC=函数最大调用次数（NFC）；

while（best_fitness_value_so_far＞VTRand NFC＜=MAXNFC）

for i=1 to Np

根据式（6）和（7）计算Fi和CRi；

从当前种群P选取任意三个个体Pi1，Pi2，和Pi3，

其中 i≠ i1≠ i2≠i3；

Vi=Pi1+Fi×（Pi2-Pi3）；

for j=1 to D

if（rand（0，1）＜CRi）

Ui，j=Vi，j；

else

Ui，j=Pi，j；

for end

评估Ui适应度；

if（f（Ui）＜f（Pi））

Pi'=Ui；

else

Pi'=Pi；

for end

Pi=Pi'；

if（rand（0，1）＜po）

在当前种群中更新区间［aj（t），bj（t）］的边界；

for i=1 to Np

根据式（5）计算Pi的反向个体OPi；

评估OPi适应度；

for end

在P和OP中选择n个最适应个体作为下一代种群成员；

while end

End

5 基准函数测试试验

为了比较算法性能，在常用的全局优化问题中选择了2个单峰函数（f1-f2）和3个多峰函数（f3-f5）来进行Matlab环境下的仿真求解实验。表1中给出了所有基准测试函数、变量维数、定义域及其全局最优解。

表1 测试函数

5.1 ODE和MDE的比较

首先将ODE和MDE的优化性能进行比较。参考文献［3］的测试方案，我们采用相同的参数设置和比较度量标准如下：

种群规模NP=100；

F和CR自适应调整；

反向概率po=0.3；

变异策略为DE/rand/1/bin；

最大NFC值MAXNFC=1e+6；

最终到达值VTR=1e-8。

为了比较MDE和ODE的收敛速度，通过测量函数调用次数（NFC）来进行度量和比较，较小的NFC值意味着更快的收敛速度。运行终止标准是在达到最大调用次数前，算法找到一个小于到达值（VTR）的解。为了比较收敛的速度，我们使用基于NFC的加速率参数AR，定义如下。

当AR＞1时，意味着MDE快于ODE。

再定义成功运行率SR如下。

其中较大的SR意味着该算法鲁棒性更强。

图1给出了5个测试函数调用求解的平均成功率SR和平均加速率AR的最终结果。从SR结果来看，ODE对f1、f2和f4的求解都取得了成功，但是对f3和f5求解的最终值未能全部达到要求的精度，而MDE对5个函数的求解取得100%成功率，这表明MDE的求解性能优于ODE，MDE比ODE更鲁棒。加速率AR的值始终大于1，说明对5个函数进行求解时，MDE的收敛速度始终快于ODE。AR总平均值为1.12，意味着MDE比ODE收敛速度平均快12%。

表2 SADE、CEP、FEP和MDE的比较结果

5.2 SADE、CEP、FEP和MDE的比较

我们再将常用的SADE、CEP、FEP和MDE进行比较研究，参数使用相同的设置。

其中，最大调用次数值（MAXNFC）：1500×100（代数×NP，f1、f3和f4），2000×100（f2和 f5）。

表2给出了测试函数的求解结果，其中Mean表示上一代最优解的平均值，STD代表标准方差。

显然，在同等条件下，MDE和SADE在所有的测试用例实验中求解的最优值精度都优于CEP和FEP。其中，SADE对于f1和f2函数的求解值精度平均优于CEP和FEP多达1e+24倍和1e+20倍，而MDE又优于SADE1e+1倍和1e+3倍。对f3和f5的求解中，MDE和SADE都取得了相同的全局最终最优解0。对f4的求解中，MDE和SADE求得的最优解值精度相同，但MDE的解比SADE的解更接近全局最终最优解。其中MDE对f1和f4求解时的收敛过程分别如图2和图3所示，可见其收敛过程也非常迅速，并未陷入局部最优。

图2 MDE求解f1时的收敛过程

图3 MDE求解f4时的收敛过程

6 结语

本文提出了一种结合反向学习和自适应控制参数机制的新差分进化算法MDE。通过在5个著名的基准测试函数上进行性能测试比较实验，结果表明，所提出的算法MDE在求解测试函数时的性能表现明显优于ODE，SADE，CEP和FEP。今后的工作重点是如何更加有效地改进所提出的算法，以使其具备更加广泛的适用性。