基于双种群两阶段变异策略的差分进化算法①

王丽颖,帅真浩

(大连海事大学 信息科学与技术学院,大连 116033)

差分进化算法(DE)是美国学者Storn[1]于1995年以技术报告的形式提出的基于种群优化理论的算法,通过变异、交叉和选择父代之间的差异向量来优化,与常见的进化计算技术[2-4]类似,进化计算使用逐代优化过程,然后使用并行处理在引导随机搜索中选择该群体,以实现期望的目的.近年来,许多改进变异策略的DE 的变体都得到了很好的改进.其在约束优化计算[5],聚类优化计算[6],非线性优化控制[7],神经网络优化[8],滤波器设计[9],阵列天线方向图综合[10,11]及其它方面[12-14]得到广泛应用.

1 差分策略

自DE 概念化以来,研究主要围绕着种群重构问题,差分策略问题以及控制参数问题3 个方面进行改进,本文则主要针对差分策略问题进行改进.为了更加有效的解决实际问题,国内外许多学者对DE 算法在差分策略上进行了大量的改进.Das 等人[15]和Zhang等人[16]在2009年对每个种群成员采用邻域的概念,并在DE 中采用DE/target-to-best/1 突变方案.Zhang 等人[16]在2009年提出了一种具有可选的外部存档和自适应更新控制参数的差分变异策略DE/current-to-bestp,其可选的归档操作利用历史数据来提供有关进展方向的信息.Mallipeddi 等人[17]在2010年提出了一种不同的突变策略池以及每个控制参数的值池在整个进化过程中共存,并竞争产生后代解的EPSDE 策略.Islam 等人[18]在2012年提出了一种新的具有二项交叉和自适应控制参数的变异策略.Piotrowski[19]在2013年提出了一种基于全局邻域和局部邻域的模因变异算子.Liao等人[20]在2014年利用基于环拓扑的突变策略提高DE 的性能,以更快地收敛到全局解.Aldabbagh 等人[21]同年提出了DE 的一种将标准变异方案DE/current-to-rand/1 替换为DE/current-to-rand 方案的新变体DE-bea,其新突变方案称为细菌突变方案.Yu 等人[22]在2015年提出了一种DE 变体,当种群聚集在局部最优时,他们考虑自适应控制参数.Mohamed[23]在2015年提出了一种基于凸组合向量的三角形突变方法.他随机选取3 个向量,计算出最佳和最差向量的差值,并将其与基本变异规则相结合.Cui 等人[24]在2016年发了一种MPADE 算法,该算法根据适应度值将种群分为3 部分,并在其上应用3 种变异策略进行开发或探索,进而设计一种参数调整的自适应技术.Sun 等人[25]在2017年将依靠邻域关系的DE 算法变异算子称为NDE 池的种群拓扑用于定义多个社区关系,为每个单独的邻里关系是自适应地选择.

差分策略可以被表示为DE/x/y,其中,x表示当前被变异的向量的状态,是随机的,最佳的或者其他;y表示在变异过程中所采用的差分向量的个数.多种变异策略中DE/best/1 和DE/rand/1 的应用最为广泛.其中,DE/best/1 策略的局部搜索能力强,但是与此同时,存在全局探测能力较差的特点;而DE/rand/1 策略全局探测能力强,但是拥有局部搜索能力弱的缺点.为了解决这一问题,本文基于差分突变的灵感提出了一种不需要作为参考的可行解的方法,即结合两个著名的DE 变体:DE/rand/1 和DE/best/1,提出了一种新的变异策略.结合外部存档的思想,同时将分治法的思想引入种群初始化,提出DE/bestbp-randw/2 策略和DE/bestwprandb/2 策略相结合的双种群两阶段变异策略(TPSDE),TPSDE 大致可以划分为两个阶段,分别是初始化后每i个邻域内的局部搜索阶段,以及在整个集合内的搜索阶段.首先,TPSDE 第一阶段是在初始化后,经过一轮训练,个体按照适应度大小排序完成后,将整个种群进行区域划分为子种群P1和子种群P2,其中P1种群个体适应度普遍比P2更高,然后分别按照不同的变异策略进行局部搜索.这种做法使得算法在进化过程的初期,两个子种群的内部进化可以让结构往好的方向发展,更好的提高算法的收敛速度找到最优解;但是,在种群进化后期,算法经过多次迭代之后,由于个体间差异过小,从而导致后期种群向全局最优解的进化停滞,收敛速度较慢.因此,为了增加个体多样性,同时需要第二个阶段勘测整个种群范围来提高全局搜索寻优能力.其相对于其他的变异策略主要的优势在于可以很好的平衡收敛性能的提高和种群多样性保持之间的关系.

2 差分进化过程

DE 是一种低空间复杂度,高可拓展性并且在解决非线性、多模态和不可分离性等各种具有挑战性问题时表现更高效的优化进化算法.DE 算法有两个阶段,分别是初始化和进化.在第一阶段,种群是随机生成的,是一次性的过程;在第二阶段,即进化,生成的种群会经历突变、交叉和选择过程,这些过程在DE 的搜索过程中重复进行,直到满足终止标准,最终在 D 维实参数空间中搜索全局最优点.终止条件可以通过如下来判断:根据目标函数的复杂性所对应固定次数的迭代Gmax值;群体的最佳适应度在连续迭代中没有明显变化;取得了预先指定的目标函数值.

算法的基本流程为:首先随机初始化一个随机设定的NP维实值参数向量的总体.每个向量,也称为基因组或者 染色体,形成多维优化问题的候选解.我们将用G=0,1,…,Gmax来表示DE 中的后代.从中随机选取两个解向量作差,用一个标量F来定标,定标后的差加到第3 个向量上进而产生一个新的解即变异个体vi,g.然后这个新的解与预先设定的初始解xi,g根据交叉原则进行操作,在保证变异个体一定对交叉后的解产生一些影响即有基因传给下一代的同时,按照一定的概率决定生成的个体ui,g继承的基因来自于哪个个体.交叉操作完成后,为了在随后的世代中保持种群大小不变,算法的下一步需要进行选择,需要将xi,g和ui,g进行一对一的锦标赛选择,如果的ui,g适应度值优于xi,g的适应度值,则ui,g取代xi,g继续进行进化活动,算法通过不断地迭代计算,保留适应度值更高的个体,即保留更优解取代局部最优解,直到向全局最优解逼近.下面为标准差分进化算法步骤:

(1)种群初始化,初始化是在 DE 中寻找位于D 维参数空间中的实数全局最优解的第一个过程.对于问题的每个参数,可能存在一定的范围,参数的值应该被限制在这个范围内.初始种群即在G= 0 时,应通过在受规定的最小和最大边界约束的搜索空间内均匀随机化个体来尽可能覆盖此范围.参数向量个体表示为:

xi,g表示的是第g代的第i个解,即目标个体,随机产生NP个初始解,每个解均有D维向量.式(2)为在可行域内随机产生的初始种群.

其中,xmax,j,xmin,j分别是个体中第j个分量的上下限;rand(0,1)为[0,1]区间的一个随机数.

(2)变异操作.生物学上,“突变”是指染色体基因特征的突然变化.然而,在进化计算范式的背景下,突变也被视为随机元素的变化或扰动.变异操作即将目标向量xi,g通过差分变异操作后与自身重组形成变异向量vi,g+1的过程,其最大优势之一是变异步长的大小和方向都会自动适应目标函数值.这个过程一般需要3 个个体,而这3 个目标向量索引的选取是从范围[1,NP]中随机选择的互斥整数r1、r2和r3,将任何两个向量差值都按标量F进行缩放,然后再将缩放后的差值添加到第3 个向量中.如图1所示.两个应用最广泛的变异策略DE/best/1 的第3 个个体xr1,g是种群中的最优个体;而DE/rand/1 策略的xr1,g是种群中的随机个体,然后将(xr2,g-xr3,g)乘上F后与xr1,g求和而产生变异个体Vi,g+1.具体如式(3)表示.

图1 TPSDE 基本流程图

其中,F是变异因子,位于[0,1]之间,一般取值0.5.g表示进化的代数,i表示第i个染色体,即第i个个体,r1,r2,r3表示索引,即随机第ri个个体.

(3)交叉操作.通过交换部分变异向量vi,g和目标向量xi,g维度产生中间向量Ui,g来提高种群的多样性,使用下面交叉策略进行交叉.染色体i=1,2,3,…,N;基因j=1,2,…,D;CR是交叉因子是[0,1]内随机数,一般取值0.5.jrand是1 到D随机数,以保证变异向量至少有一维信息被保存在交叉向量里.j取随机数保证了交叉过程中一定会有变异后个体vi,(g+1)的基因,而r1,r4 的取值小于等于CR,因此交叉后代ui,(g+1)的基因来自于变异后的染色体vi,(g+1),而r2,r3 的大于CR,因此交叉后代ui,(g+1)的基因来自于亲本的染色体xi,g.

(4)选择操作.选择所的生成的下一代个体是xi,g还是ui,g,即最优解是初始解还是经过一系列操作之后形成的新解.需要将这组新解根据适应度和原来那组解进行一对一的锦标赛选择,式(5)为差分进化算法适应度计算方法.对于求最小值问题,如果目标函数值比原来那组解小则将它们替换掉,否则保留原来解.f(x)为目标函数值,而对于应用在神经架构搜索中的差分进化算法的选择方法是根据适应度函数进行选择.

(5)适应度函数的计算.适应度指的是个体在种群生存的优势程度度量,用于区分个体的“好与坏”,通过比较适应度值的大小.对于求函数最优解问题时,标准差分进化算法需要将这组解和原来那组解根据适应度值的大小进行一对一的锦标赛选择,判断从上面得到的进化之后的解是否可以作为下一代的解,适应度函数即用来计算适应度值的函数.

3 改进差分策略的差分进化算法

本文通过重新构建子种群网络,并按照各自合适的变异策略进行变异,同时结合局部和全局同时进化的方法,取代使用单一变异策略,从而提高了种群的全局搜索寻优能力和局部搜索寻优能力,进而避免了过早收敛和搜索停滞等问题的出现,提升算法的收敛速度和求解精度.TPSDE 首先随机初始化固定长度的种群,经过一轮训练后得到种群的适应值大小,然后进行变异交叉的操作.为了进行下面的变异操作,TPSDE 提出了向量之间的邻域结构,向量的邻域是它所连接的其他参数向量的集合.该邻域是根据种群成员的适应度顺序确定的.例如,的两个邻域向量.因为邻域大小必须小于种群大小,所以每个向量都有一个半径为k的邻域,其中k是从0 到(NP-1)的非零正整数,取领域向量被表示为:

同时,他们适应度的大小为:

局部优化过程针对不同子种群运用不同的变异策略.结合DE/best/1 和DE/rand/1 策略的优点做出改进应用于不同的进化阶段,仿真实验结果表示这比整个进化过程中仅采用一种变异策略表现出了更加优越的性能.基于此,本文提出DE/bestbp-randw/2 策略和DE/bestwp-randb/2 策略相结合的变异策略使两个子种群协同进化,这种策略下较好个体的数量会随着阶段的发展逐级增加,不仅不断增强子种群P1的全局搜索寻优能力;而且子种群P2的局部搜索寻优能力同时得到提高.从而避免了其因个体间差异过小,种群个体多样性的缺失,从而导致的搜索停滞问题.双种群变异策略具体如下.

TPSDE 引入了新的参数ω在DE 中起着参数F的相同作用.参数ω控制勘探和开采之间的平衡,比如ω取较小的值时,比如趋近于0,有利于全局变量分量,即更好的开采,而取较大的值时,比如趋近于1 时,有利于局部邻域分量,即更好的勘探.

结合标准差分进化算法的框架以及双种群两阶段的变异策略,局部与整体协同进化的思想,提出基于双种群两阶段变异策略的差分进化算法(TPSDE),具体实现流程如下所示.

Step 1.种群初始化.随机生成种群规模为NP的初始解集合.

Step 2.第一阶段局部优化.将初始化的种群进行一轮训练,并且按照适应度从大到小排序,并在k=(NP-1)/2 处将其分成两个子种群区域,即子种群(better)P1和子种群(worse)P2.

Step 3.对于子种群P1的个体,采用DE/bestbprandw/2 的变异策略进行差分进化得到向量Vbi,g.

Step 4.对于子种群P2的个体,采用DE/bestwprandb/2 的变异策略进行差分进化得到向量Vwi,g.

Step 5.将子种群P1,P2变异后产生的Vbi,g和Vwi,g加权求和产生变异子向量V1i,g.

Step 6.第二阶段全局优化.采用DE/rand/1 的变异策略在全种群范围内搜索,得到变异子向量V2i,g.

Step 7.将变异子向量V1i,g和变异子向量V2i,g按照同样的规则组合在一起得到最终的变异向量vi,g.

Step 8.按照式(4)交换部分变异向量vi,g和目标向量xi,g基因产生中间向量ui,g.

Step 9.算法初始化将产生的交叉向量ui,g和目标向量xi,g根据适应度的大小进行一对一的锦标赛选择,保留适应度更高的个体作为新的种群P′.

Step 10.种群初始化判断算法是否满足终止条件.若满足,则算法结束,输出当前最优值为最终结果;若不满足,则令g=g+1,并跳到Step 2.图1 即TPSDE 的基本流程图.

4 实验设计与结果分析

4.1 实验仿真

为了验证TPSDE 算法的有效性与先进性,在实验过程中将标准Benchmark 测试函数分别进行固定次数的仿真实验,这里我进行30 次实验之后进行统计,同时对于函数的选取也是极具代表性,选取的这些测试函数包括单峰函数以及多峰函数,单模态以及多模态函数,函数曲线是连续或者间断的以及有的具有多个局部最优解而有的函数没有局部最优解.他们的函数名称、搜索范围,维数以及理论上最优值如表1所示.所有函数维数取D=30,种群规模NP=50,F=0.5,CR=0.5,4 种算法独立运行30 次后的误差平均值与标准方差的统计结果如表2所示.

表1 测试函数及特征

表2 各算法运行30 次统计

4.2 实验结果分析

将TPSDE 算法与目前性能最优、应用范围最广的两种变异策略下的差分进化算法和我所提出算法的一种变体进行对比实验,分别为DE/best/1,DE/rand/1和TPSDE1,其中TPSDE1 是TPSDE 算法的变体,是邻域向量划分的时候,i和k的取值均为一个随机整数,即多种群的变异策略,此时i的取值范围为[0,(NP-1)/2)∪((NP-1)/2,NP-1] 范围内的随机整数,k为[1,(NP-1)/2)∪((NP-1)/2,NP-2]内随机生成的整数.选择最小误差、取得固定误差值所需要的函数评价次数这两个指标进行结果分析,具体如图2所示.

从表2 可以看出,无论是简单30 维单模态Sphere函数还是多模态Rantrigin 函数,无论是单峰函数还是多峰函数,从优化结果可以看出,各个算法的最优值、最差值、平均值和标准差结果显示,TPSDE 算法都具有的寻优能力明显优于其他算法,能够持续有效地搜索函数全局最优点.图2 为每个测试函数经过多轮迭代之后的误差值统计图.我们可以很明显的看出,TPSDE算法几乎在每个测试函数上相对于其他3 种差分策略的算法都表现出了突出的优势.当TPSDE 算法和各种差分策略算法都能找到函数的最优点时,TPSDE 算法表现出了较好的全局收敛性和健壮性,其前期收敛速度快,能够在最优极值点所在局部区域进行细致搜索,能够快速的找到最优解所在的局部区域,收敛曲线能够迅速地接近于最优点,利用较短的时间就可以接近于最小误差值;后期能够增加种群的多样性,跳出局部最优解,避免出现搜索停滞,从他们接近于最小误差时的迭代次数可以看出,对于Schaffer 和Griewank 测试函数图显示函数收敛到大概相同误差值时,DE/best/1算法使用的迭代次数最少;Rantrigin 函数的收敛曲线图说明在前期TPSDE1 变异策略能达到一个较好的效果,而更多的情况,比如Rosenbrock、Step 和Sphere测试函数误差图显示,TPSDE 算法使用最少的评估次数,可以做到快速收敛到极值点附近,而其他差分策略收敛速度较慢.

图2 测试函数收敛图

5 结论与展望

本文提出的基于双种群两阶段变异策略的差分进化算法,通过将全局优化和双种群协同进化策略下的局部优化相结合,在以最有效的方式搜索到最优解的同时,增加了种群多样性,防止了搜索停滞和陷入局部最优解现象的出现.以上函数仿真实验结果表明TPSDE算法在迭代次数明显减少,精度得到明显提高,以及鲁棒性上都达到了更加优秀的效果.另外,在接下来的研究中,由于差分进化算法的通用性强,易与其他算法相结合,诸如与人工免疫网络、神经架构搜索等相结合,进行模型参数优化,相信其在提高预测精度上会有较好的效果,能够更好地解决现实中的问题.