一种基于混合策略的差分进化算法研究

2019-04-01苗晓锋刘志伟

计算机应用与软件 2019年3期

苗晓锋刘志伟

1(榆林职业技术学院神木校区信息中心陕西神木 719300)2(西北工业大学信息中心陕西西安 710072)

0 引言

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

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

1 差分进化算法

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

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

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

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

Vi,G=Xr1,G+F(Xr2,G-Xr3,G)

(1)

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

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

Ui,G=(U1i,G,U2i,G,…,UDi,G)

式中：j=1,2,…,D(D是问题维数)，

(2)

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

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

2 改进设计

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

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

2.1 反向学习

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

x*=a+b-x

(3)

式中：x∈R且在区间[a,b]上。

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

(4)

OPij=aj(t)+bj(t)-Pij

(5)

式中：Pij是种群P中第i个个体的第j维向量，OPi是Pi的反向个体，aj(t)和bj(t)分别是当前搜索空间第j维的最小值和最大值，而t指进化代数。

2.2 自适应控制参数

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

(6)

(7)

式中：r1、r2、r3和r4是4个在[0,1]上的独立随机数；参数ε1和ε2分别代表了调整F和CR因子的概率。根据文献[4]中的建议，将ε1和ε2设为0.1，Fl和Fu分别设为0.1和0.9。因此，新F以随机方式从[0.1,1]中获取一个值，新的CR从[0,1]中获取一个值。

3 混合DE算法

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

Begin

po=反向概率;

best_fitness_value_so_far=当前最优适应值;

VTR=到达值;

MAXNFC=函数最大调用次数(NFC);

while(best_fitness_value_so_far>VTR and 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)

Ui,j=Vi,j;

else

Ui,j=Pi,j;

for end

评估Ui适应度;

if (f(Ui)

else

for end

if(rand(0,1)

在当前种群中更新区间[aj(t),bj(t)]的边界;

for i=1 to Np

根据式(5)计算Pi的反向个体OPi;

评估OPi适应度;

for end

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

while end

End

4 基准函数测试

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

表1 测试函数

4.1 ODE和HDE的比较

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

1) 种群规模NP=100；

2)F和CR自适应调整；

3) 反向概率po=0.3；

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

5) 最大NFC值MAXNFC=1e+6；

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

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

(8)

当AR>1时，意味着HDE快于ODE。

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

(9)

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

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

图1 ODE和HDE的比较结果

4.2 SADE、CEP、FEP和HDE的比较

我们再将常用的SADE、CEP、FEP和HDE进行比较研究，参数使用相同的设置。其中，最大调用次数值(MAXNFC)：1 500×100(代数×NP，f1、f3和f4)，2 000×100(f2和f5)。

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

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

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