基于控制参数双峰分布的小种群差分进化算法

作者:未知

  摘要:当前差分进化算法研究主要集中在常规种群上,对小种群差分进化(DE)算法的研究较少。小种群差分进化算法因种群规模小,存在多样性降低过快的问题。因此提出一种基于控制参数双峰分布的小种群差分进化算法(BiMDE)。该算法采用基于柯西双峰分布的参数调节机制处理变异缩放因子F和交叉概率因子CR,并对缩放因子F进行矢量化设定。将BiMDE算法在函数集CEC2014上进行测试,并与5种最新的小种群差分进化算法进行比较。结果表明,BiMDE算法在求解精度、收敛速度以及多样性保持上具有较大优势。
  关键词:差分进化;小种群;控制参数;双峰分布;多样性
  DOI:10.11907/rjdk.192142 开放科学(资源服务)标识码(OSID):
  中图分类号:TP312文献标识码:A 文章编号:1672-7800(2020)006-0074-05
  0 引言
  差分進化(Differential Evolution,DE)算法是一种结构简单且性能优异的全局优化算法,由Price&Storn提出。由于DE算法具有极好的鲁棒性及易实现等特点,所以被广泛应用于数据挖据、人工神经网络和核工业等领域。
  种群数目对DE算法的最终优化效果影响很大。种群数目多时,DE算法具有更好的种群多样性,从而为算法提供更好的全局搜索能力,且可减少陷入停滞和局部极值的可能性。但同时单次迭代需更多的评估,占用大量内存,因此不适用于内存小且实时性要求高的应用场景。近年来小种群DE(Micro-DE)算法引起研究者关注。Micro-DE算法种群大小取值一般小于10,因而具有硬件需求较低和内存需求较小的优势,在嵌入式系统有更好的应用前景。但是种群数目少也带来问题,如使种群易于收敛到局部最优解附近,从而导致过早收敛与停滞;此外,还会使种群多样性降低过快,子代个体会因为跳不出局部最优解而不能获取更好的优化结果。因此研究者们进行了相应改进。如Xuan等提出一种拥有新型变异策略的小种群DE算法(DESP),该算法在DE/randl/bin的基础上增加一个扰动策略,同时提出一种判断机制以调节扰动幅度,有效解决了小种群DE算法过早收敛停滞的问题;Brown等在JADE的基础上提出了一种自适应小种群DE算法(uJADE),该算法通过改进变异策略、引进重启和扰动机制,使优化效果得到明显提高;Salehinejad等提出矢量化的小种群DE算法(MDEVM),该算法将缩放因子F矢量化应用到小种群DE算法中,解决了小种群DE多样性降低过快问题,并引入并行机制以增强算法运行效率;一年后,Salehineiad等又提出了一种多种变异策略自适应的小种群DE算法(EMDE),该算法在MDEVM的基础上将5种典型的差分变异策略用随机选择的方式加入到算法差分变异中;随后再次进行改进,提出了一种新的逆向学习的多策略自适应小种群DE算法(OEMDE),该算法在EMDE的基础引入了逆向学习机制,逆向学习机制中的逆向群体初始化和逆向群体跳转可有效利用群体和逆向群体中的信息。还有研究者发现可通过调节参数、增强种群多样性缓解Micro-DE算法因种群个体数目少引起的过早收敛和停滞等问题。
  综上所述,本文设计一种基于双峰矢量分布的缩放因子F与双峰分布的交叉概率因子CR的参数自调节机制,使小种群DE算法在快速收敛的同时保持较好的多样性,从而获得更好的优化结果。
  1 控制参数双峰分布的小种群DE算法
  1.1 双峰分布参数调节机制
  双峰分布调节机制最早由Wang等在常规种群DE算法研究中提出,该机制特点是运用双峰分布的缩放因子F和交叉概率因子CR,使算法可平衡全局搜索与局部搜索能力。
  为解决小种群DE算法多样性降低过快的问题,本文将双峰分布参数调节机制引入到小种群DE算法中,将缩放因子F矢量化,从而增强小种群DE算法多样性。
  在BiMDE算法中对缩放因子F和对交叉概率因子CR的具体设置为:
  其中,randci(θ,e)为柯西分布;缩放因子F的取值范围为[0.1,1.5],交叉概率因子CR取值范围为[0,1]。通过前期数据仿真实验,确定F中的。取值分别为0.65和1.5,F中的e取值为0.1;CR中的θ取值分别为0.1和0.95,CR中的e取值为0.1。
  缩放因子F的双峰分布具体取值方法为:当缩放因子F取值为randci(0.65,0.1)中的值时,若其值小于0.1,则将值截断为0.1;若其值大于1时,则将值截断为l。当缩放因子F取值为randci(1.5,0.1)中的值时,若其值小于l,则截断为1;若其值大于1.5时,将值截断为1.5。
  交叉概率因子CR双峰分布具体取值方法为:当交叉概率因子CR取值为randci(0.1,0.1)中的值时,若其值超过取值范围,则采用randci(0.1,0.1)重新生成一个取值范围内的值;若交叉概率因子CR取值为randci(0.95,0.1)中的值时,若其值超过取值范围,则用randci(0.95,0.1)重新生成一个取值范围内的值。
  在DE算法参数中,缩放因子F和交叉概率因子CR对优化结果影响较大,缩放因子F越大,全局优化效果越好,缩放因子F越小,局部优化效果越好;交叉概率因子CR越大,种群多样性越好,交叉概率因子CR越小,种群多样性越差。在设计双峰分布矢量化缩放因子F时充分考虑全局搜索和局部搜索能力的平衡,所以选用柯西分布及对超过取值范围的值采用截断操作,使其取值主要集中在两个值附近,在保证全局搜索的同时兼顾局部搜索,从而使优化效果更好,如式(2)所示。小种群DE算法种群多样性丢失过快是影响优化效果的主要原因,虽然较大的交叉概率因子CR会增强种群个体多样性,但一直使用较大的交叉概率因子CR会使子代个体从父代个体中继承的信息少,含有较多父代信息的子代个体将被丢失,从而影响最终优化结果。因此在对交叉概率因子CR进行设计时需充分考虑该情况,设定一种双峰柯西分布设计,如式(3)所示。   1.2 BiMDE算法流程
  将双峰分布参数调节机制引入Micro-DE算法,可得到基于控制参数双峰分布的Micro-DE算法(Micro DEBased on Bimodal Distribution of Control Parameters.BiMDE)。采用变异策略a/b的BiMDE记为BiMDE/a/b。
  2 仿真实验结果与分析
  2.1 测试函数与实验参数设置
  实验采用CEC2014测试函数集。在CEC2014中共有30个测试函数,分别为C1:3个单峰函数F1-F3、G2:13个简单多峰函数F4-F16、G3:6个混合函数F17~F22和G4:8个组合函数F23~F30。根据CEC2014的要求,每个测试函数运行51次并记录统计结果。
  根据文献,本文所有小种群DE算法的种群个数Np全部设为8;DE算法中的缩放因子F和交叉概率因子CR全部按照文献中算法的值设定;将最大计算代价(maxFES)按文献设为2000xD。为了更好地了解算法运行状态及检验算法是否适用于不同维度,在D=10、D=30、D=50、D=100四个维度对算法进行测试和数据分析。
  本文仿真实验中的各种DE算法采用MATLAB语言实现,软件为MATLAB2014a。运行环境为:Windows 7,双核3.9GHz CPU,4GB内存。
  2.2 算法比较
  2.2.1 BiMDE算法与MDEVM算法比较
  选取DE算法中5种典型变异策略,分别采用BiMDE与MDEVM方法在CEC2014的4类函数上进行Wilcoxon秩和检验对比,然后从各维度分析两类算法优缺点。选用DE/a/b策略的MDEVM算法,记为MDEVM/a/b。
  如表1所示,BiMDE与MDEVM在相同维度时相比,在5种不同变异策略下BiMDE均有明显优势。例如,当D=10时,BiMDE/rand/1与MDEVM/rand/1相比,在2l组函数上有优势,仅在3组上有劣势;当D=10时,BiMDE/rand/2与MDEVM/rand/2相比,在25组函数上有优势,仅在1组上有劣势;同样当D=10时,在best/1、best/2和current-to-best/1这3种变异策略下,与MDEVM算法相比,BiMDE算法有绝对优势。
  此外,BiMDE与MDEVM相比,在不同维度下均更有优势。例如,当D=10时,BiMDE/rand/1与MDEVM/rand/1相比在21组函数上有优势,仅在3组上有劣势;当D=30时,BiMDE/rand/1与MDEVM/rand/1相比,在21组函数上有优势,仅在2组上有劣势;当D=50时,BiMDE/rand/1与MDEVM/rand/1相比在2l组函数上有优势,仅在3组上有劣势;当D=100时,BiMDE/rand/1与MDEVM/rand/1相比,在2l组函数上有优势,仅在4组上有劣势。在不同维度下,均利用另外4种变异策略rand/2、best/1、best/2和current-to-best/1,與MDEVM算法相比,BiMDE算法有绝对优势。维度越高代表问题的复杂程度越高,算法在不同维度的分析有助于检验算法维度扩展性,所以BiMDE算法具有很好的维度扩展性。
  综上所述,BiMDE算法与MDEVM算法相比,在不同变异策略、不同维度下均具有明显优势,体现了双峰分布参数调节机制对比均匀分布参数调节机制的有效性。
  2.2.2 BiMDE算法与其它小种群DE算法比较
  将BiMDE系列算法中性能最优异的BiMDE/rand/1和BiMDE/current-to-best/1算法分别与另外4种小种群DE算法进行比较,包括:EMDE、OEMDE、DESP和uJADE。在CEC2014的30组测试函数上进行Wilcoxon秩和检验,对比结果如表2所示。
  首先,将BiMDE与DESP、EMDE和OEMDE进行比较。BiMDE与DESP相比,在不同维度下,至少在24组函数上有显著优势;BiMDE与EMDE相比,在不同维度下,至少在17组函数上有显著优势;BiMDE与OEMDE相比,在不同维度下,至少在24组函数上有明显优势。综合可知,BiMDE算法相较于DESP、EMDE、OEMDE算法,在不同维度均表现出绝对优势。
  其中,W表示BiMDE算法有优势的函数个数,T表示两种算法效果相似的函数个数,L表示MDEVM算法有优势的函数个数。
  “w”表示BiMDE算法有优势的函数个数,“T”表示两种算法效果相似的函数个数,“L”表示其它小种群DE算法有优势的函数个数。
  其次,将BiMDE与uJADE进行比较。uJADE加入位置扰动、个体重启策略和带有存档功能的变异策略,是一种性能非常优异的小种群DE算法。由表2可以看出,在低维度下BiMDE劣于uJADE。然而,随着维度的上升,BiMDE比uJADE表现更好。例如,当D=10时,BiMDE/current-to-best/1与uJADE相比,在13组函数中占有优势,在15组函数中处于劣势;当D=30时,BiMDE/current-to-best/1与uJADE相比,在13组函数中占有优势,但劣势函数下降到了组;当D=50时,BiMDE/current-to-best/1与uJADE相比,有优势的函数组数上升到15组;当D=100时,BiMD E/current-to-best/1与uJADE相比,有优势的函数组数达到了18组。值得注意的是,uJADE在低维度下的优势是由于其采用的位置扰动、个体重启与新式变异等策略,这些策略的引人大幅增加了uJADE复杂度。BiMDE简洁性好,并且随着维度的上升更有优势,因而对复杂问题更有潜力。
  由以上分析可知,BiMDE与DESP、EMDE和OEMDE在不同维度上进行对比,均表现出明显优势。与uJADE相比,BiMDE在高维度下更简洁、优势更明显。   2.3 BiMDE多样性与收敛性分析
  选取D=30时BiMDE系列算法中的BiMDE/rand/1和BiMDE/current-to-best/1,分别与MDEVM系列算法中MDEVM/rand/1和MDEVM/current-to-best/1在收敛性、多样性上进行对比。收敛速度通过最优值下降速度体现,多样性评价指标如式(4)所示。图2(a)、(c)、(e)、(g)分别为单峰测试函数F2、简单多峰测试函数F11、混合测试函数F17、合成测试函数F27的收敛状态;(b)、(d)、(f)、(h)分别展示这4组测试函数多样性。
  如图2(a)、(c)、(c)、(g)所示,在多峰问题F2和F11上BiMDE与MDEVM相比,BiMDE收敛速度和精度更高。在函数F17和F27上,BiMDE/rand/1在前期比MDEVM/rand/1收敛慢,但在中期时收敛速度加快且精度也有所提高;而BiMDE/current-to-best/1比MDEVM/current-to-best/1拥有更好的收敛速度与精度。
  如图2(b)、(d)、(f)、(h)所示,在單峰问题F2上,前期两种BiMDE与两种MDEVM多样性相似,在中后期时BiMDE/current-to-best/1可快速收敛到最优解附近,因而其多样性快速下降,而MDEVM/current-to-best/1一直保持相对较高的多样性,收敛相对较慢。在多峰问题F11、F17和F27上,两种MDEVM多样性下降过快,而两种BiMDE均可保持较好的值,因此在这3种复杂多峰问题上可保持较好的全局搜索能力,在中后期不会陷入局部最优导致的停滞。
  综上分析可知,与MDEVM算法相比,BiMDE算法在处理不同类型问题时均拥有较好的收敛速度与精度:在单峰问题上可快速找到近似最优解,多样性下降较快;在多峰问题上可保持较高的多样性以加强全局搜索能力。
  3 结语
  本文设计了一种双峰柯西分布的参数调节机制以解决小种群DE算法多样性降低过快问题,并提出了BiMDE算法。将BiMDE算法与MDEVM、DESP、EMDE、OEMDE、uJADE算法在计算代价较小的情况下进行比较,得到如下结论:
  (1)BiMDE双峰分布参数调节机制比MDEVM均匀分布参数调节机制在不同变异策略、不同维度下均具有显著优势。
  (2)BiMDE算法与DESP、EMDE、OEMDE、uJADE等小种群DE算法相比,未引入过多策略,简洁性更好。在所有维度下BiMDE均优于DESP、EMDE和OEMDE。在高维度下BiMDE算法优于uJADE。
  (3)在不同类型问题上BiMDE均拥有较好的收敛性和多样性。
  以上3点表明双峰参数调节机制在小种群DE上的有效性与BiMDE算法的优异性能。
  尽管BiMDE算法比已有的小种群差分进化算法优势更大,但不同变异策略的BiMDE算法对不同类型的问题优化效果不同。下一步可通过分析不同变异策略的BiMDE算法优缺点,设计变异策略自适应的小种群DE算法。此外,还可将BiMDE算法应用于实际工程问题,以期进一步改进算法。
转载注明来源:https://www.xzbu.com/8/view-15278144.htm

服务推荐