多变异策略差分进化算法的研究与应用

第40卷　第12期　Vol.40　No.12　计算机工程ComputerEngineering　　2014年12月December2014·人工智能及识别技术·文章编号:1000-3428(2014)12-0146-05　　　文献标识码:A　　　中图分类号:TP18基金项目:国家自然科学基金资助项目(60974048);2011年度湖南省高校创新平台开放基金资助项目(11K028);湖南科技大学博士启动基金资助项目(E51066)。作者简介:吕铭晟(1990-),男,硕士研究生,主研方向:智能优化算法,数据挖掘;沈洪远,教授、博士;李志高、王　汐、龚　明,硕士研究生;王俊年,教授、博士、博士生导师。收稿日期:2013-09-02　　修回日期:2013-09-27　　E-mail:[e-mail]多变异策略差分进化算法的研究与应用吕铭晟,沈洪远,李志高,王　汐,龚　明,王俊年(湖南科技大学信息与电气工程学院,湖南湘潭411201)摘　要:标准差分进化(DE)算法在高维多峰等复杂函数优化时易出现早熟现象,并且算法后期收敛速度较慢。为此,研究2种标准差分进化算法的变异策略(DE/rand/1和DE/best/1),并将其进行串行组合,提出一种多变异策略的差分进化算法(MDE)。在4个Benchmark函数上的测试结果表明,在多变异策略下,通过对MDE算法控制参数的调整能有效拓展和平衡改进后算法的全局与局部搜索能力,其所得最优解的精度、算法的收敛速度都较标准差分进化算法有明显优势,能较好地解决电力负载分配问题。关键词:差分进化;多变异;优化策略;电力负载分配中文引用格式:吕铭晟,沈洪远,李志高,等.多变异策略差分进化算法的研究与应用[J].计算机工程,2014,40(12):146-150.英文引用格式:LvMingsheng,ShenHongyuan,LiZhigao,etal.ResearchandApplicationofDifferentialEvolutionAlgorithmUnderMultipleMutationStrategy[J].ComputerEngineering,2014,40(12):146-150.ResearchandApplicationofDifferentialEvolutionAlgorithmUnderMultipleMutationStrategyLVMingsheng,SHENHongyuan,LIZhigao,WANGXi,GONGMing,WANGJunnian(SchoolofInformationandElectricalEngineering,HunanUniversityofScienceandTechnology,Xiangtan411201,China)【Abstract】InordertoovercometheshortcomingsofthestandardDifferentialEvolution(DE)algorithmintheoptimizationofcomplexfunctionslikedimensionmulti-modalfunctions,suchastheproblemofprematureandslowlaterconvergence,thispaperproposesaDEalgorithmbasedontheMutationstrategy(MDE)throughserialcombinationofDE/rand/1andDE/best/1.Itmakesanin-depthstudyofthisalgorithms,andfinallythealgorithmistestedonthefourBenchmarkfunctions.ResultshowsthatthroughthemodulationofthecontrolparametersofMDEcaneffectivelyexpandsandbalancestheglobalandlocalsearchcapabilitiesoftheimprovedalgorithm,anditsresultantoptimalaccuracy,andconvergencespeedarebetterthanstandardDEalgorithm.Itcanbewellappliedinelectricpowerloaddistribution.【Keywords】DifferentialEvolution(DE);multiplemutation;optimizingstrategy;electricpowerloaddistributionDOI:10.3969/j.issn.1000-3428.2014.12.0271　概述差分进化(DifferentialEvolution,DE)算法[1]采用模拟生物进化的机制,通过种群内个体差异度生成差异个体,然后进行交叉、选择操作实现种群的进化。DE算法适用性强,不依赖于问题辅助信息,容易实现,需要调整的参数少,非常适合于求解一些利用常规数学规划方法不能或难以求解的复杂优化问题。许多文献对标准差分进化的不足提出了改进,如文献[2-3]分别将交叉概率和缩放因子设计为自适应,文献[4]提出采用动态更新种群的策略,文献[5]提出一种自适应差分进化算法(SDE);文献[6]提出基于模糊控制的自适应差分进化算法(FADE);文献[7]提出基于适应值的自适应差分进化算法;文献[8]提出自适应群体差分进化算法;文献[9]提出广义的变异策略方案,用户可以方便选择适合自己所求问题的变异操作类型;文献[10]提出第40卷　第12期吕铭晟,沈洪远,李志高,等:多变异策略差分进化算法的研究与应用　　基于邻域搜索的DE/target-to-best/1算子;文献[11]提出多策略和控制参数自适应差分进化算法;文献[12]提出DE/rand/1/Either-or算子。文献[13]提出双种群伪并行差分进化算法。迄今为止DE已发展为一种在求解非线性、不可微、多峰值及高维复杂函数等类型问题的高性能强鲁棒的方法,已经在滤波器设计、聚类分析等领域取得了较好的应用[14-15]。根据变异机制的不同,DE有多种不同版本,其中,DE/rand/1是标准差分进化所采用的变异策略,相对而言该变异策略操作简单,在低维单峰函数优化问题中具有收敛速度快、寻优精度高等优点。但在高维多峰复杂函数优化时,存在算法易早熟或后期收敛速度慢等不足。针对该问题,本文提出一种多变异策略差分进化算法(MDE)。通过引入改进的DE/best/1变异策略对种群进行二次变异操作,以拓展算法搜索空间,使算法在交叉操作时能够有更大概率获取更多优秀的变异向量分量,进而从种群个体的“基因”上有效控制种群在进化过程中的多样性。为避免算法进化的盲目性,在其变异操作中都采用精英保留原则,并对其中部分优秀基因采用基因扩散处理。2　标准差分进化算法的变异策略与其他进化类算法类似,DE算法首先初始化种群,然后对种群个体依次执行变异、交叉和选择操作,产生出子代种群,经过反复迭代最终得到所需的结果。标准差分的变异策略如下:(1)第1种变异策略DE/rand/1:vG+1i=xGr1+F×(xGr2-xGr3)(1)　　(2)第2种变异策略DE/best/1:vG+1i=xGbest+F×(xGr1-xG+1r2)(2)其中,r1,r2,r3∈[1,N]为随机选择的整数,且须满足:r1≠r2≠r3≠i;F为变异操作缩放因子,取值在(0,2)之间,控制变异向量的幅值。3　多变异策略差分进化算法3.1　变异策略差分进化算法的核心操作为变异。对变异策略的选取决定了算法在进化过程中种群的走向,而贪婪的选择策略本身具有两面性,在低维单峰函数优化时能够保证算法始终向更小的方向进化,但在高维多峰复杂函数优化时,因为仅用贪婪选择策略,致使算法一旦搜索到某一较优秀局部最小时,算法在最优适应度上出现停滞,随着时间的累积,最终导致种群个体某些维变量陷入特定范围。根据式(1)和式(2)可知,如果所有个体某维变量过早趋于一致,在没有其他操作的干预下,种群丧失多样性,算法就会出现早熟。为了增强贪婪算法的全局最优能力,使算法在处理多峰高维复杂函数问题优化时,避免算法在某一局部最小值时可能出现的停滞,避免个体种群多样性过早地丧失。本文采用2种变异共存的方式优化经典差分算法。改进变异策略DE/best/1:vG+1i=xGbest+F2×(xGr1-xGr2)+α×F2×(xGr3-xGr4)(3)　　本文优化算法将2种策略纵向结合,增加了种群的多样性,使算法的全局搜索能力得到有效增强。将DE/rand/1作为变异策略1。将式(3)作为变异策略2,α为向量相关参数,α的加入使本次变异有了更多的选择空间;结合成多变异策略差分进化算法。变异策略2的加入极大增强算法的搜索空间和在局部区域的搜索能力。MDE算法较标准差分进化增加了多个控制参数和种群,使算法的搜索能力得到有效的加强且提供了更灵活的选择。差分算法使用精英保留的原则。在此基础之上,本文研究采取了精英扩散和限制原则,使优秀的精英个体能影响其他个体的部分基因,而一些带有欺骗性的精英个体对其影响力进行限制。这也符合生物社会的规律,即优秀的个体对整个种群的进步应产生更大的影响力。反之,应减少。在算法中加入扩散数值k,以决定精英的影响大小。本文算法中采取每一代进化,最优个体影响其他某一个体k维基因的方法。采取精英扩散原则后,算法能在各阶段更有效地保留优势个体,更好地发挥了多变异策略的优势,提高了收敛速度。3.2　算法流程多变异策略差分进化算法的具体流程(图1)如下:(1)初始化种群,对参数进行设定。(2)计算种群个体适应度。(3)采用策略1进行变异、交叉和选择操作。计算适应度,记录当前最优个体。更新整个种群的适应度。(4)采用策略2进行变异、交叉和选择操作。计算适应度,记录当前最优个体。更新整个种群的适应度。将策略2中最优个体的部分基因根据扩散741　　　　　　　计　算　机　工　程2014年12月15日数值k替代随机个体的对应基因。(5)判断步骤(4)得到的结果是否达到退出条件,若满足,结束,否则,跳转到步骤(2)继续执行。图1　多变异策略差分进化算法流程4　算法测试与结果分析4.1　测试环境与结果为验证MDE的有效性,以常用的4个Benchmark测试函数为例对MDE进行测试,同时,与标准差分DE/rand/1进行对比。算法最大函数评价次数为2．5e+05,各算法对于每个函数都独立连续运行20次。表1中,CR1,CR2分别表示DE/rand/1、DE/best/12种变异策略下算法的交叉概率;F1,F2分别表示缩放因子;α为相关系数;k为扩散系数。表1　MDE算法各控制参数设置函数CR1CR2F1F2αkSphere0.20.20.30.30.705Schwefel2.220.80.30.40.40.755Rosenbrock0.80.80.70.51.2015Schwefel2.260.20.20.80.81.105　　由表2结果可知,当DE/rand/1出现早熟现象时,DE/best/1能够通过参数的调节防止算法早熟,可见其稳定性不如DE/rand/2。正是由于F2的存在弥补了DE/rand/1稳定性的不足。而DE/rand/1和DE/best/1串行组合并非简单叠加,在结合两者优点的基础上,MDE性能有了进一步的提高,使其整体性能在测试中表现最为优秀。表2　20次独立运行的最优解平均值函数DE/rand/1MDESphere9.1004e-994.4866e-3031.6574e-980.0000e+00Schwefel2.225.4335e-521.8507e-1641.1245e-510.0000e+00Rosenbrock8.8000e-039.1118e-283.1072e-032.5707