均匀邻域对位的自适应差分进化算法

赵新超，熊 卿，冯 帅

(北京邮电大学理学院，北京 100876)

0 引言

差分进化(differential evolution,DE)由文献[1]提出，它是一种有效、简单、鲁棒的全局优化算法。该算法以初始种群向量开始搜索，关键思想在于构造差分变异信息，该信息来自于当前群体中不同个体的差异性，即不同个体的差分向量信息。近些年来，DE的发展得到学者的广泛关注[2-11]。为了提升差分算法的性能，Rahnamayan等[12]引入了对位学习(opposition-based learning， OBL)概念。OBL背后的主要思想是同时考虑当前位置及其相应的对位估计，以便实现对当前候选解和对位解的同时搜索。OBL策略已经被用于很多群智能优化算法研究中[12-16]。OBL被用于提升差分算法性能，这种方法被称为基于对位学习的差分进化(opposition-based differential evolution，ODE)[12]。ODE在种群初始化期间同时使用对位点，并且还用于进化过程中产生的新的种群。ODE自提出之后，因其收敛速度加快的特性被学者深入研究：文献[17]将种群划分为精英种群和普通种群，分别采用标准的和基于反向学习的差分进化策略，提出一种基于对位学习的跨种群差分进化算法；文献[18]通过反向精英学习机制和高斯随机分布提高算法的性能，提出一种基于反向学习的自适应差分进化算法。

先前对差分算法的研究使得算法性能得到了不同程度的提升，随着OBL策略引入差分算法，收敛速度慢的问题得到有效改善。然而，ODE易陷入局部最优以及早熟收敛等，这些不足问题还没有得到有效解决。针对此问题，本文提出了基于均匀邻域对位的自适应差分进化(neighborhood opposition-based differential evolution,NODE)算法，通过扩大当前解对位点邻域的搜索区域的思路提高群体多样性，针对对位邻域变异的操作，增加找到最优解的可能性，同时减缓了精英学习的强度，从而在一定程度上避免过早陷入局部陷阱的问题。

1 DE算法

DE是一种基于种群差分信息的进化搜索方法。在迭代过程中，变异运算是新解生成过程中最主要的运算，有很多变种的差分变异策略，本文以经典DE/rand/1/bin变异为例介绍,具体步骤为：

第1步，种群初始化。用方程(1)产生初始种群中每个个体向量xi：

xij=aj+rand(0,1)×(bj-aj),

(1)

其中：xi=(xi1,xi2,…,xiD),i=1,2,…,Np，D表示问题的维数，Np表示种群规模；bj与aj分别表示个体向量第j维的上界与下界；rand(0,1)表示[0,1]之间的均匀分布随机数。

第2步，变异操作。对于当前代的每个个体xi，在种群中随机选择3个互不相同的个体向量xa，xb，xc，a,b,c∈[1 …Np]，s.t.a≠b≠c≠i；依照式(2)生成变异个体vi，

vij=xaj+F(xbj-xcj),

(2)

其中：i=1,2,…,Np;j=1,2,…,D;放缩因子F∈[0,2]用于控制差分向量(xb-xc)的放缩程度。

第3步，杂交操作。该操作中差分算法以一定的概率Cr∈[0,1]依照式(3)生成测试个体向量ui，

(3)

其中：i=1,2,…,Np;j=1,2,…,D;jrand∈[1,2,…,D]是预先产生的一个随机整数，该参数交叉操作能够保证测试个体向量ui至少有一维分量来自变异个体向量vi，可以避免与父代个体向量xi相同，以达到提高种群多样性的目的。

第4步，选择操作。这一阶段处理种群中每一个目标个体向量xi，将目标个体向量与新产生的测试个体向量ui按式(4)进行评估并贪婪选择，将较优个体保留到下一代种群，

(4)

其中：i=1,2,…,Np;f(x)表示解向量x的适应度值，假设f(x)是最小化问题。

2 ODE算法

在专注于OBL之前，先给出对位数概念[12]。

(5)

类似地，该定义可以被延展到高维空间。

(6)

与所有其他群体优化算法类似，DE算法的两个主要操作是可分的，即种群初始化和通过诸如变异、交叉、选择的进化操作产生新一代。构建基于OBL的差分算法框架[12]，基于对位差分进化算法选择DE/rand/1/bin作为父算法，并将基于对位点搜索的思想嵌入到DE中加速其收敛速度，提高算法性能。

第1步，基于对位的种群初始化。按式(1)得到初始种群P，包含Np个随机产生的个体，按式(6)产生包含Np个对位个体的对位种群OP，最后从初始种群{P∪OP}中选择Np个适应度最高的个体。

第2步，对种群中每一个个体执行差分进化操作。按照式(2)对种群中每一个个体实施差分变异操作获得变异个体向量vi，再按照式(3)对种群中每一个个体xi和变异个体向量vi进行交叉操作获得测试个体向量ui。

第3步，按式(4)对个体目标向量xi和测试个体向量ui执行选择操作。

第4步，基于对位的种群跳转。产生一个[0,1]间的随机数r，判断是否小于跳转概率Jr∈[0,1]。若r

(7)

3 NODE算法

3.1 研究动机

经典ODE算法基于对位学习概念，利用当前解与其对位解一起竞争共同选择较优解，从而获得一个具有更好适用度的解，以达到加速收敛、提高算法性能的目的。然而经典ODE算法只是根据解群体搜索区域的几何中心获取一个确定的对位点。本文研究动机是：对于很多问题而言，这种OBL策略在一定程度上可以加速搜索最优解的过程，OBL策略之所以能有效的一个基本假设是问题对最优解的局部邻域不完全具有对称性，因此当前点和对位点一般具有适应度的差距。同时ODE选取一个对位点的做法使得找到最优解的可能性较低，假如几何中心偏离，对位点就会偏离，找到最优解的可能性就会降低。

3.2 NODE算法

针对这个问题，本文提出了NODE算法，在传统对位点的基础上做了一次步幅由当前群体信息和当前对位点决定的对位随机扰动，在保持经典OBL扩大搜索区域这一优势的前提下，扩大了OBL邻域有效范围，并充分利用了当前群体和当前个体的双重信息，有效提高了算法的搜索有效性。

本文提出的在经典对位点邻域做多阶段自适应均匀扰动的策略如下：

(8)

(9)

(10)

3)多阶段OBL 基于OBL的均匀邻域变异操作的优点是扩大搜索区域，增加找到最优解的可能性，不足之处在于，随着搜索区域的增大，收敛速度会相应减缓。为了更好地平衡收敛精度和收敛速度之间的关系，尽可能在保持多样性的同时提高收敛速度，在自适应调节搜索区域的同时，引入了多阶段扰动策略，通过控制半径扰动参数Ra来减小搜索区域。

算法初期，当Ra较大时，算法群体会沿对位点较大的邻域搜索，增加找到更有潜力区域的可能性；算法中期，当Ra较小时，扰动策略会保证算法群体在对位点较小的邻域搜索，使当前解在当前有潜力区域搜索，同时依然保持跳出区域的可能；算法临近结束阶段，半径参数Ra很小，保证算法群体几乎仅向当前对位点学习，从而保证算法有更好的收敛性。

3.3 算法流程

本文沿用经典的ODE算法框架，基于均匀邻域的自适应对位变异学习机制嵌入到种群初始化阶段和种群跳跃阶段，其伪代码如下。

算法1 对位种群初始化阶段

生成均匀分布的随机种群P0，

for(i=1;i≤NP;i++)，

for(j=1;j≤D;j++)，

OP0i,j=aj+bj-P0i,j，

算法2 对位种群跳跃阶段

if(rand(0,1)

{if(t≤T/3)，

Ra=Ra1，

else if (T/3

Ra=Ra2，

else，

Ra=Ra3，

}

for(i=1;i≤NP;i++)，

for(j=1;j≤D;j++)，

在当前种群{P∪OP*}中选择Np个适应度最高的个体。

4 仿真实验结果与分析

为了验证提出的NODE算法的性能，将NODE与经典DE(DE/rand/1/bin)、文献[12]提出的ODE进行了对比分析，测试函数采取CEC 2014测试函数集[19]。

4.1 测试函数与参数设置

在CEC 2014测试函数集的各类函数中选出代表性算例构成本文的基准测试函数集，所有测试函数均为高维可伸缩的函数。选取CEC 2014函数简介如下：f2、f3为单峰函数，f6、f9、f10、f11为多峰函数，f18、f20为混合函数，f27、f29为组合函数，为方便起见，这些函数在本文中重新标记为F1～F10。这些测试函数的编号、名称、分类、搜索区域以及理论最优值如表1所示，搜索区域为[-100，100]D，有关测试函数详细信息见文献[20]。算法对比实验的具体参数设置如下：种群规模Np=50，搜索空间维数D=50，跳转概率Jr=0.3，控制参数Ra1=10-2,Ra2=10-3,Ra3=10-6。

表1 基准测试函数

4.2 数值实验对比

DE、ODE和NODE算法的数值结果统计见表2，该统计结果包括30次独立运行最终结果的最优值Min、平均值Mean和标准差STD，最优的结果用粗黑体表示。从表2结果可以看出：

1)在10个测试函数中,NODE、ODE和DE在30次最终结果统计的最优值上分别取得7个、5个和4个最优结果。

2)NODE、ODE和DE在10个测试函数最终结果的平均值上分别取得10个、0个和0个最优结果。

3)结合这两个指标分析，NODE、ODE和DE分别取得17个、5个和4个最优结果。

4)结合这两个指标，NODE、ODE和DE最优结果数量加和的近似比分别为17/20、5/20和4/20。

5)NODE、ODE和DE在这两项指标的结果排名加和分别为24、41和47。

6)NODE、ODE和DE在这两项指标结果排名加和的近似比分别为24/20、41/20和47/20。

7)对于单峰函数和混合函数，NODE的结果略优于其他算法。

8)对于多峰函数，NODE在F5与F6的统计结果远优于其他算法，在F3与F4中略优于其他算法。

9)对于组合函数，NODE在F9与F10的统计结果明显优于其他算法。

综合表2结果和相应分析可以看出，在CEC 2014的10个测试函数上，NODE得到的平均结果有明显的优势，最优值统计结果也比ODE、DE表现得更好，特别是多峰函数和组合函数，优势更加明显。

为讨论3个算法在平均结果统计的显著性，对算法DE、ODE和NODE的平均值做Friedman统计检验[20]，其平均秩分别为5.888 9，5.222 2，3.888 9。可见，NODE与DE、ODE有显著性差异。综上所述，本文提出的NODE策略和算法能显著提高算法的性能，比ODE、DE能够取得更满意的结果。

4.3 在线进化趋势对比

为考查算法的平均进化趋势和综合在线性能，图2给出3个算法在30次独立运行中在线性能演示对比分析。第一类单峰函数相对简单，所以从后三类测试函数中选择6个函数代表，分别为多峰函数F3、F5、F6，混合函数F7、F8和组合函数F9。

从图2结果可以看出：1)NODE比ODE和DE有较为明显的进化优势；2)在算法的前期，NODE和ODE进化趋势表现大致相当，且都优于DE；3)随着算法的进行，在函数F3、F7、F8、F9上NODE比ODE表现略好，在函数F5、F6上NODE明显优于ODE；4)对于多峰函数，NODE在F5、F6上的进化趋势远优于其他算法，在F3略优于其他算法，可以分析出，当求解多峰函数时NODE的性能比其他算法优势较明显；5)对F7、F8、F93个函数，NODE的结果略优于其他算法，但当把后期进化图局部放大依然可以看出NODE相较于其他算法的进化优势。

表2 3种算法数值实验结果统计

综合表2和图2可以看出，本文提出的NODE算法具有更加明显的全局搜索优势和对最优解相对准确的定位能力，特别对多峰函数表现更加突出，从而证明本文所提几种策略的有效性。

4.4 最终结果离散度对比

为进一步考查3种算法在多次运行最终结果中的离散程度，图3给出3个算法6个函数在30次独立运行中在线性能对比分析和箱型图。纵坐标的5条线从上到下分别为最大值、上四分位数、中位数、下四分位数、最小值，同样选择函数F3、F5、F6、F7、F8、F9为代表。

从图3可以看出：1)中位数方面，NODE、ODE和DE分别取得6个、0个和0个最优结果；2)上下四分位数方面，NODE、ODE和DE分别取得4个、1个和1个最小；3)数据异常值方面，NODE、ODE和DE在函数F3、F9上分别有1个、0个和1个，NODE、ODE和DE在函数F8上各有1个；4)对于多峰函数，NODE在F3、F5、F6的中位数与其他算法的中位数差值较大，可以看出，当求解多峰函数时NODE的性能比其他算法优势较明显；5)对于混合函数和组合函数，NODE在F7、F8、F9的中位数略小于其他算法，可以看出，NODE当求解混合函数和组合函数时的性能比其他算法优势相对较小。

综合可以看出，本文提出的NODE算法中位数表现最优，且多次运行结果较集中，因此算法具有较好的性能表现，且具有较好的稳定性和鲁棒性，特别针对多峰函数优化具有较为明显的优势。

5 结论

本文在经典对位学习的差分进化算法ODE的基础上，引入了基于对位邻域的均匀变异算子和多阶段扰动策略，充分利用了当前群体和个体的双重信息，提出了一种基于对位邻域学习的自适应差分进化算法NODE。在经典对位点的邻域做均匀变异运算，有效扩大了搜索区域，增加找到最优解的可能性；在变异阶段，利用当前群体解中每一维度的最大值和最小值来自适应调控搜索区域的大小，提高了算法的收敛精度；算法引入多阶段扰动策略，根据算法的不同进化进程，调控算法的收敛速度。最后，选用CEC 2014每一类测试函数中10个代表性基准测试函数，对本文所提算法NODE与差分进化算法DE、经典对位差分进化算法ODE进行对比仿真实验，结果表明，本文提出的NODE算法总体性能更好，更容易找到最优解，收敛精度更高，并且具有更好的鲁棒性。