一种基于选择策略的差分混合蛙跳算法-王林.pdf

《一种基于选择策略的差分混合蛙跳算法-王林.pdf》由会员分享，可在线阅读，更多相关《一种基于选择策略的差分混合蛙跳算法-王林.pdf（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、CN 431258TPISSN 1007130X计算机工程与科学Computer EngineeringScience第40卷第1期2018年1月V0140，No1，Jan。2018文章编号：1007130X(2018)01012107一种基于选择策略的差分混合蛙跳算法王 林1，万小雨1，万建超2(1华中科技大学管理学院，湖北武汉430074；2普天信息技术有限公司，北京100080)摘 要：设计了一种选择差分混合蛙跳算法SDSFLA，该算法通过增加组内个体更新个数提高了种群更新效率；通过引入差分进化算法的交叉算子和变异算子，加强了个体之间的信息交流；使用多种更新策略，提高了实验个体产生的成功

2、率；随机选择控制参数，增加了种群的多样性。基于16个基准测试函数，将SDSFLA与一种改进的蛙跳算法、两种改进的差分进化算法进行对比，实验结果证实了SDSFLA算法的有效性和稳定性。关键词：混合蛙跳算法；差分进化；实验个体选择；资源池中图分类号：TPl8 文献标志码：Adoi：103969jissn1007一130X201801018A hybrid differential shuffled frog leapingalgorithm based on selection strateWANG Linl，WAN Xiaoyul，WAN J iancha02(1School of Manage

3、ment，Huazhong University of Science and Technology，Wuhan 430074；2Potevio Information Technology CoLtd。，Beijing 100080，China)Abstract：A Selected Differential Shuffled Frog Leaping Algorithm(SDSFLA)is proposedCornpared with the classic Shuffled Frog Leaping Algorithm(SFLA)，SDSFLA improves the efficien

4、cy ofpopulationupdatingby increasingthe number of updated vectors，uses thecrossover operator and mutationoperator of Differential Evolution(DE)to strengthen information exchanges between vectors，uses multiple updating strategies to improve the success rate of the trial vectors，and increases the dive

5、rsity of thepopulation viarandomlyselected control parametersBased on 16 benchmark functions，SDSFLA is compared with an improved frog leaping algorithm and two improved differential evolution algorithmsThetest results confirm the validity and stability of the SDSFLA algorithmKey words：shuffled frog

6、leaping algorithm；differential evolution；trial vector selection；resource pool引言蛙跳算法SFLA(Shuffled Frog Leaping A1一gorithm)是由Muzaffar和Kevin在2003年提出的，他们通过模拟青蛙种群的自然觅食过程设计出的一种群智能优化算法，并将其成功运用于地下水资源管理问题1。混合蛙跳算法是一种基于群体协同搜索的算法，它融合了模因算法MA(Memetic Algorithm)和微粒群算法PSO(Partical SwarmOptimization)的优点，将基因进化和种群进化有效

7、集成在一起。蛙跳算法的原理简单、控制参数少，具有柔性的结构框架和较强的全局信息共享能力等优点，已被成功运用于多种自然科学以及工程领域的复杂优化问题24。蛙跳算法自提出以后，众多学者对其进行理论改进和应用推广。如许方等人51提出一种SFLA与K均值相结合的聚类算法，抑制了*收稿日期：2016-0817；修回日期：2016-1114基金项目：国家自然科学基金(7160201 5，71531009)；教育部人文社科规划项目(15YJA630095)通信地址：430074湖北省武汉市华中科技大学管理学院Address：School of Management，Huazhong University o

8、f Science and Technology，Wuhan 430074，Hubei，PRChina万方数据122 Computer Engineering&Science计算机工程与科学2018，40(1)早熟收敛问题；赵鹏军等人1在SFLA产生初始种群时采用对立学习策略提高了解的质量，并结合差分进化算法提高了种群的多样性；Roy等人7 3将遗传算法的交叉算子运用到最差青蛙个体向最好青蛙个体跳动的过程中，产生两个实验个体，提高了种群迭代效率；Zhu等人口一让所有青蛙个体在每一次更迭中进行跳动，并利用三因素方差分析方法对SFIA的控制参数进行分析，设计出一种自适应的SFLA，实验结果说明改进

9、后的SFLA收敛精度有所提高，但是收敛时间增长；Luo等人91采用多种策略产生新个体，并加入一种改进的克隆选择过程，提高了产生的新个体的质量，以及增加了种群的多样性；肖文显等人叩将蛙跳算法的组内寻优思想嵌入和声算法中，设计了一种和声蛙跳算法，实现了两种算法的耦合动态搜索。但是，标准蛙跳算法和现有的改进蛙跳算法的搜索时间长，存在个体之间信息交流不足、容易陷入局部最优等问题。针对这些问题，本文提出一种改进的蛙跳算法，加入实验个体选择机制，增加局部搜索中青蛙个体改进个数，并将差分进化算法的交叉算子和变异算子运用到青蛙个体跳动策略中，增加个体之间的交流。实验结果表明本文所设计的选择差分混合蛙跳算法提高

10、了蛙跳算法的性能，该算法与其它三种改进的群智能优化算法相比，具有更好的有效性和稳定性。2标准蛙跳算法与缺点分析21蛙跳算法基本原理SFLA的基本思想是：在一个水池中有一群青蛙寻找食物，每一只青蛙都有自己寻找食物的路径信息，青蛙通过不断跳动改变自己与食物之间的距离；青蛙个体按照适应度大小分为m组，每个青蛙个体携带自己的路径信息，组内进行信息交换，最优青蛙个体指导组内局部搜索方向，按式(1)式(3)更新组内当代最差个体，重复这个过程直到满足组内搜索终止条件，具体操作如下：Step 1设置算法参数，包括组内进化代数Ne、种群总进化代数maxgen、子种群数量m、组内个体数n、种群规模popsize=

11、n、最大跳动步长S。Step 2随机生产初始种群pop，种群中第i个个体表示为x。=(X“，XX。，X。)，其中d是求解问题的维度，X：f6，“6。计算初始种群中每个个体的适应度，并按升序排列，找出初始种群最优个体gx。Step 3将种群分为m组，每组村只青蛙。分组规则是，排序后的个体，将第1、第1+m、第1+2m、第pops如Pm+1个个体放入第一组，将第2、第2+m、第2+2m、第popsize-m+2个个体放入第二组，以此类推。分组后找出组内最优个体户6和最差个体pw。Step 4组内进行局部搜索操作。按照式(1)式(3)对pw进行更新，具体操作如下。采取组内最优更新策略。组内最差个体p

12、w向组内最优个体加方向跳动更新。通过式(1)计算跳动步长S，如果s，S。，则S，=S。然后通过式(2)对pW进行更新操作，如果temPiub，则temp，=ub。计算temp的适应度值，如果temp的适应度小于pw，则pw=temp进入Step 5，否则继续进行操作。Srando，11(加pw)，S一S一，S(1)temppw+S，temp，为，汤 (2)采取全局最优更新策略。组内最差个体pw向全局最优个体gx方向跳动更新。通过式(3)计算跳动步长S，如果S，S，则Si=S。然后通过式(2)对pw进行更新操作，如果temp，ub，则temp，一ub。计算temp的适应度值，如果temp的适应度

13、小于pw，则pw=temp进人Step 5，否则继续进行操作。SrandO，13(gxj咖)，SS，Smx(3)随机生成新个体更新策略。随机生产一个新个体替代pw，进入Step 5。Step 5对组内个体重新计算适应度，并找出更新后的和pw。判断是否满足组内更新终止条件，若满足，则进行Step 6，否则进行Step 4。Step 6混合洗牌，将完成局部搜索的各组个体重新混合，计算个体适应度，并按照适应度大小重新排序，找出此时的gx。判断是否满足全局搜索终止条件，若满足，则进行Step 7，否则进行Step 3。Step 7输出最佳个体gx和对应的适应度值，则为找出的最优解。标准蛙跳算法的流程如

14、图1所示。22标准蛙跳算法的局限性(1)标准SFLA和其它智能优化算法一样，没有参数设置的最优组合，而是根据不同的具体问题产生差异，并没有指导性的原则，仅能通过大量的实验得到。参数设置没有通用性，算法的稳定性不高。(2)标准SFLA的跳动步长始终保持固定值。进化最初最大步长太小，降低收敛速度；进化进入尾声时，最大步长又太大，减弱局部搜索能力。(3)标准SFLA在局部搜索的时候，采用三种更新策略，除了随机更新策略，另两种策略都是通过最差值向最优值方向进行跳动，更新方式过于单调，造成组内个体过分单一，种群多样性不强，容易万方数据王 林等：一种基于选择策略的差分混合蛙跳算法 123开始设置参数，产生

15、初始种群，计算个体适应度值按个体适应度排序分组找出种群最优个体萨每一组进行局部搜索混合洗牌Y算法结束，输出最佳值Y找出组内最隹跏，最差胛。按照式(1)和式(2)更新即。适应步N对删按照式(3)和式(2)更新裂拶迫廷少N纛函新的个体更新pll生成的新个体替代P1】，计算适应度值，组内排序判断是否满足 NY退出局部搜索Figure 1 Flowchart of SFLA图1 标准蛙跳算法流程图陷人局部最优。并且在个体更新的过程中，忽略了同组内其它个体，以及种群中其它个体的信息交流，可能会错过很多优秀的基因组合。针对以上问题，本文提出一种选择差分混合蛙跳算法，通过与差分进化算法混合，并加入选择机制和

16、资源池操作，提高蛙跳算法的性能。3选择差分混合蛙跳算法(SDSFLA)31 SDSFLA改进思路SDSFLA(Selected Differential Shuffled FrogLeaping Algorithm)主要是对组内局部搜索进行改进：增加一种选择机制提高实验个体的质量；利用差分进化算法的交叉算子、变异算子，增加个体与个体之间的信息交流；引入资源池操作，增加种群多样性。SDSFLA的改进思路如下：(1)标准蛙跳算法中，每一次组内更新只对最差个体进行一次更新操作之后，就重新排序，效率很低。在SDSFLA中，我们对组内第，z一2、咒一1、7个组内最差的三个个体进行更新操作，提高更新效率。

17、(2)组内三种更新策略产生新个体，策略维持标准蛙跳算法更新策略不变，策略和策略分别引入差分进化算法的两种变异算子。三种策略中，对于跳动更新后的实验个体，引入差分进化算法中的交叉操作，产生本次更新最终的实验个体。(3)SDSFLA的三种策略分别产生三种实验个体，选择最优的实验个体与原个体比较，这种操作有利于算法自适应地选择更好的个体进入下一代。采用多种策略产生多个实验个体，选择最优的，这种选择机制有助于增强算法的通用性。(4)建立变异算子F和交叉算子CR的资源池，SDSFLA三种策略对个体进行更新时，随机选择F和CR的组合，增加种群多样性。本文根据Lu等人111提到的F、CR组合，选择了五组F、

18、CR值，分别是1，01，1，09，1，01，o8，02，O5，09J，L05，03j。32 SDSFLA局部搜索的执行流程Step I找出组内最差的三个个体分别执行Step 2到Step 4。Step 2对要进行更新的个体local(i，：)，根据以下三个策略分别进行更新操作，产生相对应的三个实验个体templ、temp2、temp3，策略中F和CR的值是随机从F，cR资源池中选取出来的。策略：组内个体local(i，：)向组内最优个体加方向跳动更新。组内个体local(i，：)通过式(4)计算跳动步长S，如果sJS，则St=S。然后通过式(5)对local(i，：)进行更新操作，如果temp

19、l Jub，则templ，一“6。对templ，进行交叉操作，如果rands，则S，一S。然后通过式(7)对local(i，：)进行更新操作，如果temp2，ub，则temp2Jub。对temp2，进行交叉操作，如果randS，则S，=S。然后通过式(9)对local(i，：)进行更新操作，如果temp3Jub，则temp3J一“6。对temp3。进行交叉操作，如果randCR，temp3，一temp3，否则temp3Jlocal。SF(10cal(Jrl，：)一local(X2，：)，S一S，S (8)temp3=(10cal(x3，：)+S，temp3，16，拍 (9)万方数据124 Co

20、mputer EngineeringScience计算机工程与科学2018，40(1)Step 3将得出的三个实验个体tempi、temp2、temp3的适应度值进行比较，选择出适应度最优的个体作为最终的实验个体temp。Step 4将最终实验个体temp的适应度值与local(i，：)的适应度值进行比较，如果最终实验个体temp的适应度值优于local(i，：)的，则local(i，：)一temp，否则local(i，：)一local(i，：)。Step 5对组内个体重新计算适应度值，并且排序。判断是否满足组内更新终止条件，若满足，则退出组内局部搜索，否则转Step 1。4 SDSFLA性能

21、测试41测试函数介绍为检验SDSFLA的性能，本文选取了16个被广泛运用的标准测试函数m1 3【，包括8个单峰函数和8个复杂多峰函数。所选取的测试函数具备不同的特征，如对称、多极值、非线性、可分离或不可分离等。16个测试函数的具体描述如表1所示。Table 1 Test functions表1测试函数F7：，(z)一；。,37。1+II：一，l X：I，z。一10，10F8：，(z)一I谊+rand(O，1)，z：一128，128no：，(z)一20exp(-02i二。-r；)一exp(eos(2，xx。)一-20+e，T。32，32川批-o s+著张焉Expand tO，(z)一fl(jl，

22、72)+fl(xz，13)+，1(z。，aTl)z，一100，100F12：，(z)一二。z。sin(z。)十o11z。1 1。z。一10，a03F13：m)一志：。一：。cos(詈川m堋o，600F14：，(z)=：1(z?一10cos(2nx：)+10)，zi：一512，512F15：，(z)一：l(鲁(dcos(2rib(z。+05)一nkmax(ncos(27tbk05)Where d一05，b一03。k。=30，z。一05，05F16：，(。)=?：，(。p(一生二上三釜L去堕)。(4丁瓦磊了百瓦ii)涵5，516个测试函数中F3理论最优值为一1，F16理论最优值为1一Y，其它函数理

23、论最优值均为0。42测试结果本文将所提出的SDSFLA与ADE(AdaptiveDE)143、CMSFLA(Centroid MutatedSFLA)L15j、EPSDE(Ensemble of mutation strategies and control Parameters with the DE)163三种智能优化算法进行比较。其中CMSFLA和ADE算法都是2015年刚发表的改进SFLA和改进DE算法，而EPSDE算法是在其他文献中经常被用来做比较的算法之一，所以本文将提出的SDSFLA与这三种算法进行比较。最大进化代数maxgen设置为500，种群规模为50，本文提出的SDSFLA

24、的分组数为10，局部搜索代数为10，函数维度分别设置为30和50，每种算法对每个函数独立运行20遍，运算结果的平均值和标准差如表2和表3所示。本文利用威尔科克森秩和检验(WilcoxonSrank sum test)，在统计显著性为005的条件下，分析判断统计结果，将本文提出的SDSFLA的测试结果分别与ADE、CMSFLA、EPSDE的测试结果比较，30维和50维的比较结果如表4和表5所示(其中、代表算法结果差于、优于、等于SDSFLA)。图2图5分别是较复杂的多峰函数F11、F12、F13、F14的优化过程对比图。分析可知，针对这16个测试函数，SDSFLA明显优于其它三种算法。分析表3和

25、表5的结果，30维函数中，SDSFLA与其他算法比较，11个优于ADE和CMSFLA，13个优于EPSDE，仅分别有1个、2个相比较差；50维函数中，SDSFLA与其他算法相比，12个优于ADE、11个优于CMSFLA，12个优于EPSDE，仅分别有1个、2个、2个结果相比较差。对于少数几个测试函数，虽然SDSFLA的运行结果稍差于其它算法，但是对于这几个测试函数，SDSFLA同样也收敛到了比较理想结果。对于F1、F2、F4、F5、F6、F7、F9、F11这八个函数，SDSFLA的运算结果远远优于其它三种算法。分析图2图5，在有限的搜索代数内，SDSFLA可以较快收敛到理想值。另外，通过分析标

26、准差的结果，SDSFLA运行结果的波动性小，证明SDSFLA的稳定性较好。万方数据王 林等：一种基于选择策略的差分混合蛙跳算法 125Table 2 Experimental results of 30 variables表2 30维函数测试结果SDSFLA ADE CMSFLA EPSDE平均值 标准差 平均值 标准差 平均值 标准差 平均值 标准差F1 199E一106 526E一106 588E一08 287E08 831E一06 128E一05 937E 12 150E一11F2 106E一30 164E一30 133E+00 124E+00 576E一05 375E一05 263E一

27、02 570E02F3 100E+00 000E+00100E+00 569E一11一IOOE+00 000E+00100E+00 204E一13F4 293E一93 131E一92 6。09E一03 153E一03 125E+05 450E+04 591E一06 6。74E06F5 370E一13 102E一12 155E+04 207E+03 151E01 102E一01 698E+02 236E+03F6 341E一143 138E142 227E 36 426E一36 128E一10 922E11 179E一25 773E一25F7 199E一61 413E一61 117E一04 19

28、5E05 138E+00 691E01 439E04 583E04F8 899E+00 518E一01 107E+01 396E01 871E+00 407E一01 953E+00 423E一01F9 587E一101 2，20E一100 253E一06 835E一07 303E一14 2OOE一14 154E一10 307E10F10 454E一01 605E一01 442E一04 634E一05 306E+00 414E一01 101E一05 143E一05F11 367E+00 138E+00 553E+00 301E01 744E十00 752E一01 888E+00 974E一01F

29、12 605E一1 5 351E15 508E一03 832E一04 134E+00 873E一0l 682E02 126E一01F13 1_44E02 160E一02 407E一05 281E一05 947E一03 113E02 172E03 438E一03F14 153E+01 112E+01 322E+0l 364E+00 271E+01 745E+00 362E+01 585E+00F1 5 一143E+0l 214E0l 一144E+01 210E一04一144E+01 274E一04411E+0l 505EO】F16 19lE+01 1_80E+00201E+Ol 408E一01

30、212E+01 112E+00一162E+01 149E+00万方数据126 Computer EngineeringScience计算机工程与科学2018，40(1)Table 4 Comparison results based onWilcoxonS rank sum test of 30 variables表4 30维威尔科克森秩和检验结果Table 5 Comparison results based onWilcoxonS rank sam test of 50 variables表5 50维威尔科克森秩和检验结果、是墨连运运避鼍疑长Figure 2 Convergence res

31、ults for F1 1图2 F11收敛结果对比图Figure 3 Convergence results for F1 2图3 F1 2收敛结果对比图、冬专s运警墨Figure 4 Convergence results for F1 3图4 F13收敛结果对比图、毒是墨运e墨,v r良,v鼍警每Figure 5 Convergence results for F1 4图5 F14收敛结果对比图猢枷瑚万方数据王林等：一种基于选择策略的差分混合蛙跳算法 1275结束语本文将差分进化算法中产生新个体的策略与标准混合蛙跳算法结合，设计出一种SDAFLA，主要贡献如下：为解决混合蛙跳算法个体问信息

32、交流不充分的问题，结合差分算法的变异算子和交叉算子，采用三种改进策略产生新个体，加强局部搜索过程中个体与个体之间的信息交换；实验个体选择机制，能选择更优秀的新个体，加快收敛速度；引入资源池随机选择操作，增加了种群的多样性。测试函数结果表明，SDSFLA是一种有效的智能优化算法。本文将三种改进策略作为一个组合，并在资源池中随机选择F、CR两种控制参数的值，理论上加强了种群的多样性，提高了产生的实验个体的优秀率。未来可以利用本文提出的SDSFLA的框架，改进新个体产生策略的组合，以及资源池内控制参数的组合，加强SDSFLA解决更复杂更高维度的目标函数的能力，并用CEC2005中的测试函数进行测试，

33、将结果与近年IEEE Transactions系列期刊论文中提出的新算法的测试结果进行比较，进一步验证SDSFLA的有效性和稳定性。参考文献：1Eusuff M M，Lansey K EOptimization of water distributionnetwork design using the shuffled frog leaping algorithm-J3Journal of Water Resources Planning and Management，2003，129(3)：210-225E23 Ebrahimi J，Hosseinian S H，Gharehpetian G

34、 BUnit commitmerit problem solution using shuffled frog leaping algorithmJIEEE Transactions on Power Systems，2011，26(2)：573581E3Hasanien H MShuffled frog leaping algorithm for photovoltalc model identificationJIEEE Transactions on Sustainable Energy，2015，6(2)：509515E4Lei De-ming。Guo XiupingA shuffle

35、d frog-leaping algorithmfor hybrid flow shop scheduling with two agentsJExpertSystems with Applications，2015，42(23)：93339339E5Xu Fang，Zhang GuizhuClustering algorithm based on roodified shuffled frog leaping algorithm and KmeansrJCornputer Engineering and Applications，2013，49(1)：176180(inChinese)6Zh

36、ao Peng-jun，Shao Ze-junNovel improved shuffled frogleaping algorithmJComputer Engineering and Applieations，2012，48(8)：4850(in Chinese)7Roy P，Roy P，Chakrabarti AModified shuffled frog leapingalgorithm with genetic algorithm crossover for solving eeonomic load dispatch problem with valve-point effectJ

37、1Applied Soft Computing。2013，13(11)：424442528Zhu G Y，Zhang W BAn improved shuffled frogleaping algorithm to optimize component pick-and-place sequencing op-timization problemJExpert Systems with Applications，2014，41(15)：6818-68299Luo J，Li X，Chen M R，et a1A novel hybrid shuffled frogleaping algorithm

38、 for vehicle routing problem with time windows l-J1Information Sciences，2015，316(c)：26629210Xiao Wenxian，Wang Jun-ge，Ma Xiao-qinHarmony frogleaping algorithm and its application to complex optimizationproblemsJJournal of Central China Normal University(Natural Science Edition)，2016，50(2)：211215(in C

39、hi-nese)11Lu X，Tang K，Sendhoff B，et a1A new self-adaptationscheme for differential evolutionJ1Neurocomputing，2014，146(C)：2-1612Wang L，Shi Y，Liu SAn improved fruit fly optimization algorithm and its application to joint replenishment problemsJExpert Systems with Applications，2015，42(9)：431043231 3Ge

40、Yu，Wang Xue-ping，Liang JingAdaptive chaotic mutation shuffled frog leaping algorithmsJApplication Research of Computers，2011，28(3)：945947(ifl Chinese)14Wang L，Zeng Y，Chen TBack propagation neural networkwith adaptive differential evolution algorithm for time seriesforecastingJExpert Systems with App

41、lications，2015，42(2)：855-863151 Sharma S，Sharma T K，Pant M，et a1Centroid mutationembedded shuffled frogLeaping algorithmJProcediaComputer Science，2015，46：12713416Mallipeddi R，Suganthan P N，Pan Q K，et a1Differential evolution algorithm with ensemble of parameters and mutation strategiesJApplied Soft

42、Computing，2011，11(2)：16791 696附中文参考文献：5许方，张桂珠一种改进的混合蛙跳和K均值结合的聚类算法J1计算机工程与应用，2013，49(1)：1761806赵鹏军，邵泽军一种新的改进的混合蛙跳算法J1计算机工程与应用，2012，48(8)：4850101 肖文显，王俊阁，马孝琴和声蛙跳算法在复杂优化问题中的应用研究J华中师范大学学报(自然科学版)，2016，50(2)：211215133葛宇，王学平，梁静自适应混沌变异蛙跳算法J计算机应用研究，2011，28(3)：945947王林(1974一)，男，湖北枣阳人，博士，教授，研究方向为智能优化算法。E-mail：wanglin982163comWANG Lin，born in 1974，PhD，professor，his research interest includes intelligent optimization algorithmsL豢万方数据