自适应差分演化进化算法
贾丽媛，张弛
(湖南城市学院 信息科学与工程学院，湖南 益阳，413000)
摘要：针对差分进化算法易出现早熟收敛、局部搜索能力不足及收敛速度慢的特点，提出一种自适应差分演化进化算法(SDE)。该算法在标准差分演化算法的基础上，自适应调整缩放因子(F)和扰动向量，提高算法的搜索速度；混沌调整其遍历方向，促使算法跳出局部极值点，让算法达到全局最优。对多个函数进行仿真试验研究。研究结果表明：该方法具有快速的收敛能力、良好的稳定性，其优化性能有较明显提高。
关键词：差分演化算法；缩放因子；混沌；早熟收敛
中图分类号：TP301.6 文献标志码：A 文章编号：1672-7207(2013)09-3759-07
Self-adaptive differential evoultion
JIA Liyuan, ZHANG Chi
(Department of Computer Science Hunan City University, Yiyang 413000, China)
Abstract: In order to solve the problems of premature convergence, poor local search and slow covergence speed on differential evolution (DE) algorithm, a self-adaptive differential evolution (SDE) approach was proposed. Based on the differential evolution algorithmm, adaptive adjustment of its scale factor F and disturbance vector were introduced to improve its search speed. In order to make differential evolution jump out of local extreme value point and let the algorithm reach the global optimality, the chaotic adjustment of its traversal direction was added in the approach. The results show that SDE has rapaid convergence, good stablity and better performance than the original DE algorithm.
Key words: differential evolution; scale factor; chaos; premature convergence
差分进化(differential evolution, DE)[1]算法是一种采用浮点矢量编码在连续空间中进行随机搜索的优化算法。DE的原理简单，受控参数少，实施随机、并行、直接的全局搜索，易于理解和实现。在日本召开的第一届国际进化优化计算竞赛(ICEO)中[2]，DE表现突出，已成为进化算法(EA)的一个重要分支。近年来，DE在约束优化计算、模糊控制器优化设计、神经网络优化、滤波器设计等方面得到了广泛应用。DE是根据父代个体间的差分矢量进行变异、交叉和选择操作，与其他进化算法(如遗传算法) 一样易陷入局部最优，存在早熟收敛现象。目前的解决方法主要是增加种群的规模，但这样会增加算法的运算量，而且也不能从根本上克服早熟收敛的问题。为了提高DE的性能，很多学者提出了改进方法，如：Chiou等[3]在算法中加入了迁移算子和加速算子，提高了算法的种群多样性和收敛速率，但要计算适应度函数的梯度信息，实现较麻烦，应用受到限制；Liu等[4]针对差分矢量的缩放因子F和交叉概率2个参数对算法的影响，提出了一种模糊自适应差分进化算法，但要选择模糊隶属函数，实现较困难；谢晓峰等[5]将缩放因子F由固定数值设计为随机函数，减少了需调整的参数，实现了一个简化的DE版本，但并不能解决早熟收敛问题。
产生早熟收敛的根本原因是随迭代次数的增加和种群多样性的快速下降。为了改善DE的优化性能，国内外学者针对参数设计了不同自适应变异策略[6-8]。虽然这些方法在一定程度上提高了算法的性能，但复杂高维问题上仍易陷入局部最优，收敛精度的问题依然不能得到有效解决。为了克服早熟现象，跳出局部最优解和加快搜索速度，本文作者提出一种自适应差分进化算法(SDE)。对几种典型的Benchmarks函数测试结果表明：与遗传算法和进化算法相比，本文所提出的算法能有效地避免早熟收敛，全局收敛能力得到了显著提高。
1 经典差分演化算法
据文献[12]，个体用以下D维向量表示：
Xi,g=(Xi,1, Xi,2, …, Xi,D, CRi, Fi)T (1)
假设Xi,g(i=1, 2, …，NP)为某一代g产生的解集。其中：N P为群体规模；Xi,D为第i个个体的D维变量；Fi为第i个个体缩放因子；CRi为第i个个体交叉概率，为[0，1]之间的随机数。DE的主要思想是产生一个试验个体，差分和交叉建立新的变异试验个体，并决定哪一个个体能够进入下一代g。对于每一个g 中的个体Xi,g，变异个体的定义为
Vi, g =Xr1, g+F(Xr2, g-Xr3, g) (2)
式中：i = 1, 2, …, NP；r1，r2和r3是当i从1到NP取不同值时所选的不同随机整数索引值。与其他的演化算法一样，DE 也采用交叉操作，通过结合2个不同的个体来建立试验个体。试验个体定义如下：
Ui,g=(U1ig,U2ig,…,Ujig)T
式中：j=1, 2, …, D (D为问题的维数)，且
(3)
CR为预定义的交叉概率；rand(0, 1)为0和1之间的随机数；n为随机索引参数，
{1, 2, …, D}。该方法必须决定某个个体(Ui,g或Xig) 是否是下一个迭代g的成员。经典差分演化是一个基于群体和方向搜索的方法，与其他演化计算( EA)方法一样，从一个初始群体个体出发，这个初始群体个体是在没有可用的解空间情况下随机产生的。对DE除了式(2)所示方法外，还有几种改进方法。
(1) DE/best/1：
(4)
DE/target-to-best/1：
(5)
(2) DE/best/2：
(6)
DE/rand/2：
(7)
式中：r1，r2，r3，r4和r5为[1，NP]中5个随机整数；Xbest,g为当代种群最佳个体。
(3) 标准的DE算法：
Begin
While
do
For 每个独立的Xi,gdo
根据式(1)生成1个变异个体Vi,g
根据式(2)生成1个试验个体Ui,g
计算Ui,g个体的适应值
NE++
从Vi,g和Ui,g 2个当中选取1个作为新的Xi,g+1
End For
EndWhile
End
其中：Xi,g为g代群体中的第i个个体；Vi,g为Xi,g的变异个体；Ui,g为试验个体；NE为评估函数列举的数值；maxNE为评估函数的最大列举数值。
2 自适应差分演化进化算法
2.1 对变异算子采用DE/target-to-best/1策略
对于种群Ｐ，父代个体
，其临时子代Vi,g由以下变异算子产生，如下式所示[9]：
(8)
式中：
，为最佳个体对变异方向的影响程度权重；Xbest为父代最佳个体；F为扰动向量权重；k为扰动向量子空间的大小；
和
为从父代随机选取的除Xbest之外的其他个体；i表示种群中某一个体；k为种群中除i个体外的其他个体总数。从式(8)可以看出：DE的变异算子由2部分构成，一般将
称为差分向量，其后称为扰动向量。差分向量利用种群最佳个体信息，引导其他个体向最佳个体进化；扰动向量产生随机变异，为DE提供了自适应特性。
2.2 自适应调整缩放因子F
差分演化算法控制参数较少，但每个参数都对差分进化算法的优化能力有很大影响。其中CR控制变异的概率，F控制差异向量的缩放程度，它们的取值在很大程度上影响着演化过程的收敛性及收敛速度。毕晓君等[10]通过对测试函数的大量数值模拟研究发现：在一般情况下，F的最佳取值范围可设为[0.2, 0.9]；当优化问题含有10个以上设计变量时，F的最佳取值范围为[0.2, 0.6]。为此，动态调整缩放因子F。
本文提出的Fi自适应控制策略，考虑每个个体适应度及平均适应度和最大适应度。
(9)
式中：
为第i个个体的适应度；fmax为当代种群中个体最小适应度；Fm1为F的上界，Fm2为F的下界，为了保证群体的多样性[11]，Fm2定为0.2，Fm1定为0.9；favg为当代种群中所有个体平均适应度；rnd[a,b]为位于[a, b]之间的随机数；τ为用来调整F的系数，设为0.1。
算法基于以下思想：当个体适应度低于平均适应度时，其F应该比较大，通过F产生的后代在种群大范围内搜索，从而可以增加算法对父个体的利用和微调能力。因此，其子代能从父代中搜索到有用的信息从而加快其收敛速度。与文献[12-13]相比，本算法没有添加另外参数。
2.3 扰动向量子空间及维数的动态调整
为加快算法搜索速度，对式(8)中后半部分
扰动向量自适应调整为
。k个父体(向量)X=(X1, X2, …, Xk)所张成的子空间
作为搜索空间，其中
是k 维向量，满足条件
和-1≤
≤1。该扰动向量采用随机空间中的随机搜索(多父体重组)策略，特别是子空间中扰动向量的非凸性使算法搜索的子空间可覆盖多父体的凸组合空间，保证了随机搜索的遍历性，即解空间中不存在算法搜索不到的“死角”。
为了提高DE算法的收敛速度，动态调整V子空间的维数k：
k=int[kmax(Nmaxstep-Ncurrentstep)/Nmaxstep] (10)
其中：int( )函数是取其整数部分；kmax为k的初始值；Nmaxstep为算法的最大演化代数；Ncurrentstep为当前演化代数。在DE算法进化初期阶段，k较大，这样，子代能够充分获取父代中多个体有价值的信息，生成有发展空间的子代。在算法进化过程中慢慢降低k，特别是到后期，若k较大，则求解时间较长，不利于提高算法的收敛速度。
2.4 混沌理论跳出局部最优解
当算法陷入局最优时，设计双向搜索机制以提高DE的搜索能力。根据双向随机优化理论[14] (bidrectional random optimization，BRO)在进行搜索寻优的过程中同时，进行正向搜索和反向搜索。BRO理论证明了：若正向搜索所得的解不能达到优化期望，则反向搜索则会以更高的概率使所得的解达到优化。基于该理论，DE在扰动进化方向的过程中可以同时进行正向搜索和反向搜索，从而增强DE的局部搜索能力，加速收敛过程，这样保证了解的多样性，可避免所得解陷入局部最优。
混沌系统(chaos system, CS)具有遍历性与随机性。假设混沌系统从某初始状态出发根据一定的规律变化，最终可遍历空间中的所有状态。因此，通过混沌理论(chaos theory, CT)进行局部搜索有助于找出当前最优个体邻域范围内的更优解，从而提高算法的寻优能力。具体解决方案是：在每次迭代后利用CT的遍历性在当前最优个体邻域范围内进行T 次局部搜索，若搜索得到的个体优于原先的最优个体，则对其进行取代。常用的混沌模型是一维Logistic映射，其数学描述为[15]
；i=0, 1, 2, … (11)
其中：μ为控制参数。当μ确定后，由任意初始值
，可通过式(7)迭代得到一个确定的序列z0, z1,…, zT (其中，T为混沌向量个数)。当μ=4且
时，将呈现出完全混沌现象；
在(0,1)范围内遍历。随机生成1个D维向量
(其中，
；b=1, 2, …, D)。设置μ=4，并令
(其中，i=0, 1, …, T-1)，从而迭代产生T个混沌向量。当算法陷入局部最优时，随机从种群中选取T个个体，产生混沌变异。混沌变异算子产生方法为
(12)
其中：
为混沌调节参数。引入该参数的目的在于确保局部好的个体向正方向遍历，局部差的个体向正方向遍历，为算法跳出局部最优创造了条件。取值由下式决定：
(13)
其中：
代表-1, 0, 1这3个数中任何1个。
2.5 自适应差分演化算法描述(SDE)
算法如下：
Begin
While NE＜max NEdo
For 每个独立的Xi,gdo
将式(9)和(10)代入式(8)生成1个变异个体Vi,g
根据式(2)生成1个试验个体Ui,g
计算Ui,g个体的适应值
NE++
从Vi,g和Ui,g 2个当中选取1个作为新Xi,g+1
计算种群是否局部最优，若陷入局部最优，则根据式(11)，(12)和(13)进行混沌正负方向遍历，避免算法陷入局部而达到全局最优
End For
EndWhile
End
其中：Xi,g为群体中的第i个个体；Vi,g为Xi,g的变异个体；Ui,g为试验个体；NE为评估函数列举的数值；maxNE是评估函数的最大列举数值。
3 仿真测试
3.1 测试函数
为了验证本文算法的可行性，选取6个不同的全局优化问题，包括4个峰函数(f1，f2，f3和f4)和2个多模函数(f5和f6)进行实验。文献[16]对这些函数进行了研究。在本文中用到的所有函数都是最小化的，测试基准函数的描述和全局优化如下：
；
；
；全局最优值为0。
；
；；全局最优值为0。
；
；
；全局最优值为-7.833 23。
；
；；全局最优值为0。
；
；；全局最优值为-12 569.5。
；
；；全局最优值为0。
3.2 SDE和经典DE的比较
下面对改进的DE和经典DE进行比较，参数设定如下：NP=100，CR=0.5，子空间V的最大值为kmax=20，F最小值Fm2定为0.2，F最大值Fm1定为0.9，最大列举函数maxNE设定为100 000。算法对所有的函数都运行20次。表1所示为jDE，IDE和SDE这3种算法检测结果，表2所示为这3种方法的最优解析解。从表1可以看到：在所有测试案例中，SDE的平均误差和标准偏差比jDE[16]和IDE[17]的小；SDE算法产生的平均误差和标准偏差最小，说明SDE算法在函数的每次优化过程中稳定性更高；从收敛次数看，在优化过程中，SDE达到精度要求的次数明显比jDE和IDE算法的多。从表2可以看到：除f3外，在所有测试案例中，SDE的最优解均比jDE和IDE的大，SDE的最优解更接近于目标函数值。为了更直观地反映算法的寻优效果，将SDE算法与jDE算法和IDE算法的相关测试函数的收敛曲线的结果进行对比，结果如图1所示。将SDE算法与jDE算法和IDE算法的相关测试函数的时耗曲线的结果进行对比，结果如图2所示。从图1可以看出：对6个测试函数进行测试，算法SDE更快跳出局部最优，避免早熟收敛，更容易达到全局最优。从图2可以看出：对所有的测试函数的测试，算法SDE时耗最小，收敛速度最快。可见：无论是算法的收敛精度还是收敛能力，SDE算法都比jDE算法和IDE算法有较大提高。引入自适应调整缩放因子策略，提高了种群的多样性，从而提高了种群的全局寻优能力；引入扰动向量子空间及维数的动态调整策略，加快了算法的收敛速度；引入混沌调整正负方向搜索策略，可以使算法跳出局部极值点，避免早熟收敛。对于单峰函数和多峰函数，SDE算法都取得了相对满意的优化效果。本文提出的自适应差分演化进化算法提高了算法的全局搜索能力，改善了算法的寻优性能。
表1 jDE，IDE和SDE测验结果对比
Table 1 Comparision of experimental results among jDE, IDE and SDE
图1 测试函数收敛曲线
Fig.1 Convergence curves of test function
图2 SDE，jDE和IDE的时耗比较
Fig.2 Comparative time consumption among SDE and jDE and IDE
表2 jDE，IDE和SDE最优解比较
Table 2 Comparison of optimization results between jDE, IDE and SDE
4 结论
(1) 从DE/target-to-best/1策略出发，引入自适应调整缩放因子策略，提高了种群的多样性，从而提高了种群的全局寻优能力；引入扰动向量子空间及维数的动态调整策略，加快了算法的收敛速度；引入混沌调整正负方向搜索策略，可以使算法跳出局部极值点，避免了早熟收敛。
(2) SDE与jDE和IDE相比，在寻优能力上，提出的自适应差分演化进化算法具有快速的收敛能力，优化性能有明显提高，这表明提出的自适应差分算法是有效的。
参考文献：
[1] Storn R, Price K. Differential evolution: A simple and efficient heuristic for global optimization over continuous space[J]. Journal of Global Optimization, 1997, 11(4): 341-359.
[2] Price K. Differential evolution vs the functions of the 2nd ICEO[C]// IEEE Int Conf on Evolutionary Computation. Indianupolis, 1997: 153-157.
[3] Chiou J P, Wang F S. A hybrid method of differential evolution with application top timal control problems of a bioprocess system[C]// IEEE Int Conf on Evolutionary Computation Proceedings. New York, 1998: 627-632.
[4] Liu J H, Lampinen J. A fuzzy adaptive differential evolution algorithm[C]// IEEE Region 10 Confon Computers, Communications, Control and Power Engineering. Beijing, 2002: 606-611.
[5] 谢晓峰, 张文俊, 张国瑞. 差异演化的实验研究[J]. 控制与决策, 2004, 19(1): 49-52.
XIE Xiaofeng, ZHANG Wenjun, ZHANG Guorui. Empirical study of differential evolution[J]. Control and Decision, 2004, 19(1): 49-52.
[6] Brest J, Greiner S, Boskovic B. Self-adaptive control parameters in differential evolution: A comparative study on numerical benchmark problems[J]. IEEE Transactions on Evolutionary Computation, 2006, 10(6): 646-657.
[7] Das S, Abraham A, Chakraborty U K. Differential evolution using a neighborhood-based mutation operator[J]. IEEE Transaction on Evolutionary Computation, 2009, 13(3): 526-553.
[8] Qin A K, Huang V L, Suganthan P N. Differential evolution algorithm with strategy adaptation for global numerical optimization[J]. IEEE Transactions on Evolutionary Computation, 2009, 13(2): 398-417.
[9] Babu B, Jehan M M L. Differential evolution for Multiobjective optimization: Congress on Evolutionary Computation (CEC 2003)[C]// Canberra. Australia: IEEE, 2003: 2696-2703.
[10] 毕晓君, 李安宁. 差分演化算法的认知无线电决策引擎[J]. 智能系统学报, 2012, 7(6): 1-5.
BI Xiaojun, LI Anning. Cognitive radio decision engine based on improved binary differential evolution algorithm[J]. Transaction on Intelligent Systems, 2012, 7(6): 1-5.
[11] 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: 646-657.
[12] 敖友云, 迟洪钦. 多目标差分演化算法研究综述[J]. 计算机科学与探索, 2009, 3(2): 123-126.
AO Youyun, CHI Hongqin. A survey of multi-objective differential evolution algorithms[J]. Journal of Frontiers of Computer Science & Technology, 2009, 3(2): 123-126.
[13] Noman N, Jba H. Accelerating differential evolution using an adaptive localsearch[J]. IEEE Trans, Evolut Comput, 2008, 12: 107-125.
[14] Caponetto R, Fortuna L, Fazzino S. Chaotic sequences to improve the performance of evolutionary algorithms[J]. IEEE Transaction on Evolutionary Computation, 2003, 7(3): 289-304.
[15] Qin A K, Suganthan P N. Self-adaptive differential evolution algorithm for numerical optimization[C]// Proceedings of Congress on Evolutionary Computation. New Jersey: IEEE, 2005: 1785-1791.
[16] Brest J, Greiner S, Greiner, Boˇskovi'c B, et al. Self-adapting control parameters in differential evolution: A comparative study on numerical benchmark problems[J]. IEEE Trans on Evol Comput, 2006, 10(6): 646-657.
[17] 刘志军, 唐柳, 刘克铜. 差分演化算法中变异策略的改进与算法的优化[J]. 化工自动化及仪表, 2010, 37(9): 5-9.
LIU Zhijun, TANG Liu, LIU Ketong. Differential evolution algorithm in the mutation strategy improvement and algorithm optimization[J]. Control and Instrument in Chemical Industry, 2010, 37(9): 5-8.
(编辑 陈灿华)
收稿日期：2013-04-15；修回日期：2013-06-09
基金项目：湖南省科技计划项目(2012FJ4329)
通信作者：贾丽媛(1972-)，女，湖南益阳人，硕士，副教授，从事人工智能和演化计算研究；电话：13607371186；E-mail: jia_4211003@126.com
