混合蛙跳算法研究综述-崔文华

第27卷第4期Vol.27No.4控制与决策ControlandDecision2012年4月Apr.2012混合蛙跳算法研究综述文章编号:1001-0920(2012)04-0481-06崔文华1,2,刘晓冰1,王伟1,王介生2(1.大连理工大学控制科学与工程学院，辽宁大连116023;2.辽宁科技大学电子与信息工程学院，辽宁鞍山114044)摘要:针对混合蛙跳算法(SFLA)是一种结合了基于遗传基因的模因演算算法和基于群体觅食行为的粒子群优化算法的亚启发式协同搜索群智能算法,系统地介绍了SFLA的基本原理和算法流程,讨论了SFLA的研究进展和应用现状,并指出了SFLA的发展趋势和下一步的研究方向.关键词:混合蛙跳算法；模因演算；粒子群优化；群智能中图分类号:TP29文献标识码:ASurveyonshuffledfrogleapingalgorithmCUIWen-hua1,2,LIUXiao-bing1,WANGWei1,WANGJie-sheng2(1.SchoolofControlScienceandEngineering，DalianUniversityofTechnology，Dalian116023，China；2.SchoolofElectronicandInformationEngineering，LiaoningUniversityScienceandTechnology，Anshan114044，China.Correspondent：CUIWen-hua，E-mail：[e-mail])Abstract：：：Shuffledfrogleapingalgorithm(SFLA)isasub-heuristiccollaborativesearchingswarmintelligentalgorithm,whichiscombinedwithmemeticalgorithm(MA)basedongeneticgenesandparticleswarmoptimization(PSO)basedonthefeedingbehaviorsofparticleswarm.Therefore,thebasicprincipleandprocedureflowchartofSFLAarediscussedindetails.TheresearchprogressandtheapplicationconditionsofSFLAareintroduced.Andthedevelopmenttendenciesandthefutureresearchdirectionsareproposed.Keywords：：：shuffledfrogleapingalgorithm；memeticalgorithm；particleswarmoptimization；swarmintelligence1引引引言言言20世纪90年代出现的群智能优化算法是受自然界中以群居方式生活的动物活动的启发,利用群体优势,对问题的数学描述不要求满足可微、凸性等条件,在没有集中控制,不能提供全局模型的前提下,为寻找复杂问题的解决方案提供的一种新的迭代搜索算法.混合蛙跳算法(SFLA)是Eusuff等人[1]于2003年提出的一种基于群体的亚启发式协同搜索群智能算法.该算法是建立在群中个体具有的模因进化和利用模因实现全局信息交换基础上的.模因演算算法(MA)是1989年由Moscato[2]所采用的一种通过启发式搜索解决优化问题的群智能算法,“memetie”是指寄存于人或动物大脑中能指导其行为并能传播的信息,类似于基因中的染色体.粒子群优化(PSO)算法是由Kennedy等人[3]于1995年提出的一种基于群智能方法的演化计算技术,该算法通过模拟鸟群的觅食行为实现优化问题的求解.而SFLA则结合了基于遗传基因的MA和基于群体觅食行为的PSO算法的优点,具有概念简单、参数少、计算速度快、全局寻优能力强、易于实现等特点[4-5].自SFLA提出以来,便受到国内外学者们的广泛关注,已在水资源网络优化、装配线排序、PID控制器参数优化、流水车间调度、聚类和风电场电力系统动态优化等领域得到成功应用.本文首先介绍SFLA的基本原理和算法流程;然后,对SFLA的研究现状和研究成果进行全面综述;最后指出了SFAL进一步的研究方向.2标标标准准准混混混合合合蛙蛙蛙跳跳跳算算算法法法2.1算算算法法法原原原理理理SFLA是一种结合了确定性方法和随机性方法的进化计算方法.SFLA的基本思想是[1]:随机生成收稿日期:2011-07-14；修回日期:2011-10-04.基金项目:辽宁省教育厅创新团队基金项目(2008T091).作者简介:崔文华(1968−),女,教授,博士生,从事生产调度及金融机具开发的研究；刘晓冰(1956−),男,教授,博士生导师,从事计算机制造与集成信息系统等研究.482控制与决策第27卷𝑁只蛙组成初始种群体𝑃={𝑋1,𝑋2,⋅⋅⋅,𝑋𝑁},𝑆维解空间中的第𝑖只蛙表示为𝑋𝑖=[𝑥𝑖1,𝑥𝑖2,⋅⋅⋅,𝑥𝑖𝑆].生成初始群体之后,首先将种群内蛙的个体按适应值降序排列,并记录蛙群中具有最优适应值的蛙为𝑋𝑔;然后将整个蛙群体分成𝑚个模因组,每个模因组包含𝑛只蛙,满足关系𝑁=𝑚×𝑛.其中:第1只蛙分入第1模因组,第2只蛙分入第2模因组,第𝑚只蛙分入第𝑚模因组,第𝑚+1只蛙重新分入第1模因组,依次类推.设𝑀𝑘为第𝑘个模因组的蛙的集合,其分配过程可描述如下:𝑀𝑘={𝑋𝑘+𝑚(𝑙−1)∈𝑃∣1⩽𝑙⩽𝑛},1⩽𝑘⩽𝑚.(1)每一个模因组中具有最好适应值和最差适应值的蛙分别记为𝑋𝑏和𝑋𝑤,而种群中具有最好适应值的蛙表示为𝑋𝑔;然后对每个模因组进行局部搜索,即对模因组中的𝑋𝑤循环进行局部搜索操作.根据最初蛙跳规则(如图1(a)所示),其更新方式为𝐷=𝑟⋅(𝑋𝑏−𝑋𝑤),(2)𝑋′𝑤=𝑋𝑤+𝐷,∥𝐷∥⩽𝐷max.(3)式中:𝑟表示0与1之间的随机数,𝐷max表示蛙所允许改变位置的最大值.在经过更新后,如果得到的蛙𝑋′𝑤优于原来的蛙𝑋𝑤,则取代原来模因组中的蛙;如果没有改进,则用𝑋𝑔取代𝑋𝑏,按式(2)和(3)执行局部搜索过程;如果仍然没有改进,则随机产生一个新蛙直接取代原来的𝑋𝑤.重复上述局部搜索𝐿max次,当完成局部搜索后,将所有模因组内的蛙重新混合并排序和划分模因组,再进行局部搜索,如此反复,直到定义的收敛条件结束为止,例如达到混合迭代次数𝐺max.全局信息交换和局部深度搜索的平衡策略使得算法能够跳出局部极值点,向全局最优方向进行[5].图1蛙跳规则示意图标准SFLA中全体粒子(青蛙)的运动过程本质上是一随机过程.2010年,骆剑平等人[6]采用Markov链模型对SFLA的收敛性进行了分析,证明了青蛙族群状态序列是齐次Markov链,并在此基础上,通过分析族群状态序列的转移过程,证明了混合蛙跳算法满足随机搜索算法全局收敛的两个条件,能够保证全局收敛.混合蛙跳算法中的种群分割(模因组的生成)是进化过程中的一个关键步骤,在整个种群优化中具有重要作用.标准SFLA采用个体适应度排序进行种群分割.文献[7]提出了几何分割和随机分割两种模因组的生成方法,针对几个低维和高维Benchmark函数进行分割性能的评估,实验结果表明了基于几何分割方法的SFLA具有更好的优化性能.2.2改改改进进进的的的蛙蛙蛙跳跳跳规规规则则则在蛙群的自然模因进化中,较差的蛙受较好蛙的影响而为了获得更多的食物跳向较好的蛙.根据上述初始蛙跳规则(如图1(a)所示),最差蛙的可能新位置被限定在当前值与最好蛙位置的线段上.这种规则限制了模因进化的搜索区域,不仅降低了收敛速度,而且易导致早熟收敛.Huynh[8]于2008年提出了一种基于改进的蛙跳规则的SFLA,并用其对多变量PID控制器参数调节问题进行求解,结果证明混合SFLA的优化性能优于GA等其他算法.改进的蛙跳规则如图1(b)所示,可表示为𝐷=𝑟⋅𝑐⋅(𝑋𝑏−𝑋𝑤)+𝑊;(4)𝑊=[𝑟1𝑤1,max,𝑟2𝑤2,max,⋅⋅⋅,𝑟𝑆𝑤𝑆,max]T;(5)𝑋′𝑤=⎧⎨⎩𝑋𝑤+𝐷,∥𝐷∥⩽𝐷max;𝑋𝑤+𝐷√𝐷T𝐷𝐷max,∥𝐷∥𝐷max.(6)式中:𝑟为[0,1]之间的随机数,𝑐为[1,2]之间的一个常数,𝑟𝑖(1⩽𝑖⩽𝑆)为[−1,1]之间的随机数,𝑤𝑖,max(1⩽𝑖⩽𝑆)为第𝑖维搜索空间的最大感知和运动的不确定性.此种蛙跳规则在一定程度上增大了算法搜索范围.针对早熟收敛问题,文献[9]对SFLA进行了改进,将PSO算法中的“个体认知”能力引入SFLA的蛙跳规则(式(2))中,从而达到改善SFLA的认知行为的目的.修改后的蛙跳规则为𝐷=𝑟1⋅(𝑋𝑏−𝑋𝑤)+𝑟2⋅(𝑃𝑤−𝑋𝑤).(7)式中:𝑟1和𝑟2均为0与1之间的随机数,𝑃𝑤为𝑋𝑤所经过的最好位置.针对典型的6个连续和离散函数进行的仿真结果表明,改进后的SFLA在求解效率和收敛速度上都得到了显著改善.2010年,郑仕链等人[10]提出了一种改进的蛙跳规则,即𝐷′=𝐷+𝑟⋅(𝑋𝑏−𝑋𝑤).(8)式中:𝐷表示上一次更新时的蛙跳距离向量,𝐷′表示本次更新时的蛙跳距离向量.群体初始化时,𝐷以随机方式产生.与式(2)相比,式(8)中包含了对过去经验的记忆,具备了初步的学习功能,因此具有更强的寻优能力.2.3算算算法法法流流流程程程Step1:ISFLA参数初始化.初始化蛙种群大小𝑁,搜索空间维数𝑆,模因组数𝑚,则每个模因组包含𝑛只蛙(𝑁=𝑚×𝑛),蛙所允许改变位置最大值为𝐷max,局部搜索次数为𝐿max,全局混合迭代次数为𝐺max,最第4期崔文华等:混合蛙跳算法研究综述483大局部搜索半径为𝑟max.Step2:蛙群生成.随机生成𝑁只蛙组成初始种群体𝑃={𝑋1(𝑡),⋅⋅⋅,𝑋𝑘(𝑡)⋅⋅⋅,𝑋𝑁(𝑡)},𝑘=1,2,⋅⋅⋅,𝑁,迭代计数值𝑡=0;将每只蛙𝑋𝑘(𝑡)作为连续函数的输入变量,计算函数值𝐹𝑘(𝑡)=𝐹(𝑋𝑘(𝑡));对蛙群依据适应度值按递增方式排序,并以𝑈𝑘(𝑡)={𝑋𝑘(𝑡),𝐹𝑘(𝑡)}的形式存储,记录蛙群最优蛙为𝑋𝑔(𝑡)=𝑈1(𝑡).Step3:模因组生成.将𝑈分成𝑚个模因组𝑀1(𝑡),⋅⋅⋅,𝑀𝑗(𝑡),⋅⋅⋅,𝑀𝑚(𝑡),𝑗=1,2,⋅⋅⋅,𝑚,每个模因组包含𝑛只蛙,根据式(1)进行分配,并记录模因组内最优蛙和最差蛙为𝑋𝑗𝑏(𝑡)和𝑋𝑗𝑤(𝑡).Step4:模因进化.对模因组𝑀𝑗(𝑡)中的最差蛙𝑋𝑗𝑤(𝑡)根据图1(a)所示蛙跳规则进行局部搜索,即根据式(2)决定蛙跳步长,根据式(3)进行位置更新,并将其作为连续函数的自变量,计算其适应度值.如果更新后的蛙优于原来的蛙,则取代原来模因组中的蛙;如果没有改进,则用𝑋𝑔(𝑡)取代𝑋𝑗𝑏(𝑡),按照式(2)和(3)执行局部搜索;如果仍然没有改进,则随机产生一个新蛙直接取代原来的𝑋𝑗𝑤(𝑡);重复上述局部搜索𝐿max次,得到蛙已经被进化的模因组𝑀1(𝑡)′,𝑀2(𝑡)′,⋅⋅⋅,𝑀𝑚(𝑡)′.Step5:模因组混合.将更新后的模因组𝑀1(𝑡)′,𝑀2(𝑡)′,⋅⋅⋅,𝑀𝑚(𝑡)′内的蛙重新混合,记𝑈(𝑡+1)={𝑀1(𝑡)′,𝑀2(𝑡)′,⋅⋅⋅,𝑀𝑚(𝑡)′},对𝑈(𝑡+1)中的蛙依据适应度值按递增方式排序,更新蛙群最优蛙为𝑋𝑔(𝑡+1)=𝑈1(𝑡+1).Step6:检测算法