下载文档原格式
第36卷第1期2017年2月兰州交通大学学报Journal of Lanzhou Jiaotong UniversityVol. 36 No. 1Feb.2017文章编号：1001-4373(2017)01-0051-06 D O I:10. 3969/j.issn. 1001-4373. 2017. 01. 010一种改进的混合蛙跳算法赵红星1>2,常小刚2(1.兰州交通大学交通运输学院，甘肃兰州730070;2.兰州交通大学现代信息技术与教育中心，甘肃兰州730070)摘要：针对混合蛙跳算法后期收敛速度慢、精度低并易陷入局部最优的问题，提出一种改进的混合蛙跳算法。
在改进的混合娃跳算法中，对青娃的覓食机制和进化迭代公式重新定义，青娃的第一跳向模因组其它青娃单维搜索，第 二跳向模因组内最优青蛙单维搜索，第三跳向全局最优青蛙单维搜索，通过青蛙的三跳协同搜索，能够使算法的全局搜索能力和局部搜索能力得到显著改善。
通过7个测试函数与A B C算法和标准混合蛙跳算法实验对比，实验结果表明改进的混合娃跳算法具有比A B C算法和混合娃跳算法更优秀的搜索性能，在收敛速度和收敛精度方面具有明显的优势。
关键词：混合蛙跳算法；人工蜂群算法；全局搜索；函数优化中图分类号：T P301. 6 文献标志码：八An Improved Shuffled Frog Leaping AlgorithmZHAO Hong-xing1,2, CHANG Xiao-gang2(1. School of Traffic and Transportation, Lanzhou Jiaotong University, Lanzhou 730070 , China；2. Modern Information Technology and Education Center, Lanzhou Jiaotong University, Lanzhou 730070 , China)Abstract：To solve the problem of slow convergence speed, low precision and easy to fall into local optimum of SFLA algorithm, an improved shuffled frog leaping algorithm (BCSFLA) is proposed. The searching mechanism and the evolutionary iteration formula of frogs are redefined. In the frog's first and second jump search,it?s learning toward the other frogs and the optimal frog in the model group,and in the frog's third jump search,it?s learning toward the global optimal frog.Through the cooperation of the three jump search,the global search ability and local search ability of the algorithm are improved significantly. Experiments are conducted on a set of 7 benchmark functions and compared with ABC algorithm and SFLA algorithm. Finally, the result demonstrates a good performance of BCSFLA algorithm.Key words：shuffled frog leaping algorithm；artificial bee colony algorithm；global search；num erical optim ization混合娃跳算法（shuffled frog leaping algorithm，SFLA)[1]是Eusuff和Lansty依据群智能思想于2000 年提出的一种亚启发式算法，诙算法结合了模因算法 (MA)[2]和粒子群算法（particle swarm optimization，PSO)[3]的优点，通过模拟青蛙群体的觅食过程，以局部搜索和全局信息交流的方式，在搜索范围内寻找最 优解.S F L A因算法简单、易于理解、控制参数少且具 有相对较优的搜索能力而得到了学者的广泛关注.文 献W]建立了S F L A的Markov链数学分析模型.文献 [5]将人工鱼群算法（artificial bee colony algorithm，收稿日期：2016-10-28 学报网址：基金项目：兰州交通大学青年科学基金（2014027)作者筒介：赵红星（1989-)，男，甘肃庆阳人，工程师，博士研究生，主要研究方向为系统分析、智能计算.E-mail:zhaohx@ .S3兰州兖通大学學报第36卷A BO与SF L A结含提出:T混合算法CSFLACcompos-ite shuffled frog leaping algorithm)•文献[6]改'进"I* S F L A的进化计算公式，使进化计算受到模因组内的 最优个体、全讀,最优个体和干扰因爭|省共同的影 响，并成功解决了无线传感网的定位问题.文献[7]提 出了基于惯性因子的SFLA.文献[g]将自适应粒子群 (SAPSO)算法与SF L A相互结合，成功解决了配电网 的重构问题.文賦[||将幂律极值动力学优化与SFLA 融合，分析了容量约束车辆路径问题，并通过实例证 明了算法的有效性.文献[1C Q:弓丨人模拟退火(SA)、免疫接种(IV)、高斯变异和混沌扰动算子以提高SFLA 算法的深度搜索能力和广度搜索能力，改进后的SF-L A算法成功优化了支持向量机(SVM)的参数.针对S F L A的全局收搜索能力和深度搜索能力 的不足之处，提出了一种改进的混合蛙跳算法（bee colony sliuffled frog leaping algorithm,.BCSFLA)，在 BCSFLA的寻优过程中，绪合了人工蜂群算法的单维 搜索机制，并且根据模因组的最坏青蛙进化情况决定 是:否:宙模厲祖的最优青蛙进行精细化搜索.，通过对青 蛙觅食过程的重新定义，使BC SFLA的全_搜索能 力和精度搜索能力闻时#到提高•利用7个SO维的 测试函数，进行了 BCSFLA、ABC、S F L A的计算试验 对比}结果表明BC SFLA在函数优化方面具有比ABC和SFLA更:萌显的优勢，1 标准SFLASFLA是模拟青蛙觅食过程中的信息交流特点的一种启发式算法，通过硫定性方法和不确定性方法 相宜结食=,_达到群体进化的g的，在D维搜索:空间 中，拿娃群体可以表承为_P==(.i',!，心，…，•1,1)U =1，2,•••,域X:JV，SIY为蛙群的青蛙总数f M为模因组的个数，JV为每个模因组所包含的青蛙 数，A为第£只青蛙的具体表示，在S F L A中屬要将 蛙群根据青蛙的适应值进行降序排序,并逐一分配至 M个模因组，每一个模因组包含iV.R青蛙.其中，第1个模因组包含第1，M+1,…，CN—1)M+1只青蛙，第2个模因组包含第2，M+2，”-，（N—l)M+2R青 蛙，以此类推，第M个模因组包含第M，2M，N M只曹蛙.而在一个模:虜逾中，.由_本模菌組的最坏資蛙 不断进化实现整个模因组的局部搜索，直到所有模因 组完成规定次数的局部搜索，然后将M个模西组中 的所有青蛙混合阵序排序并重新逐一划分至M个模 因组进行局部搜索 <直到满足算法的终止条件.模因 组的烏部搜索进化方式如图1所示，在S F L A中，每个模因组的局部搜索苜先是由 该模因组的最坏青蛙在诙模西组的最优青蛙或者全 局最优青蛙的启发下计算进化，如果产生的新个体 优于该糢因組的最坏曹蛙，M利用新个体代替该模 :雇邀，的最坏嘗蛙，在r f U次计算时，新的.最:坏有:鮭必 然优于之前的最坏青蛙，经过多次计算，从而使整个 模因组实现进化.如果该模因组的最坏青蛙在进化 计算时产生的新个体不优于i前的最坏青蛙，则在 搜索范围内随机产生新个体代替唐前的最坏青蛙，从而拓展了:箅法的全貝搜索能力.组的最坏青蛙和最优青蛙，r为服从均勻分布的（0,1)之间的随机数，jC为■依据A进化计算的新个体。
进化策略自主选择的改进混洗蛙跳算法张强;李盼池【摘要】针对经典混合蛙跳优化算法寻优精度不高和易陷入局部收敛区域的缺点,本文提出一种基于进化策略自主选择的混洗蛙跳算法.算法中最差个体根据不同知识来源采取4种进化策略,每次迭代通过计算每种进化策略的立即价值、未来价值和综合奖励来决定最差个体的进化方式,并通过个体进化策略概率变异算法来提升寻优速度和避免陷入局部最优解.利用10个Benchmark函数对本文算法与8种进化算法进行性能比较.实验表明:所提的算法能较好地平衡全局探索能力和局部挖掘能力,可以用较少的迭代次数获取较优结果,具有很好的收敛速度和精度.【期刊名称】《哈尔滨工程大学学报》【年(卷),期】2019(040)005【总页数】7页(P979-985)【关键词】混洗蛙跳算法;进化策略;上限置信区间;变异;优化;模因演算;群体智能;自适应【作者】张强;李盼池【作者单位】东北石油大学计算机与信息技术学院,黑龙江大庆163318;东北石油大学计算机与信息技术学院,黑龙江大庆163318【正文语种】中文【中图分类】TP301.6混洗蛙跳算法[1](shuffled frog leaping algorithm, SFLA)，以其模型简单，寻优速度快等优点得到学者的广泛关注。
Elbeltagi等[2]通过实验表明SFLA在求解某些连续和离散优化问题时的成功率和寻优速度优于遗传算法、模因算法和蚁群算法；Babak等[3]利用SFLA改进K均值聚类方法，实验结果表明其优于遗传算法、模拟退火算法、蚁群算法等聚类算法。
目前SFLA已应用到经济负荷分配[4]、多目标优化[5]、优化调度[6]、信号重构[7]和故障诊断[8]等问题。
同时，针对SFLA的不足，许多学者在种群多样化[9-10]、进化方式改进[11-14]和算法融合[15-17]等方面提出了一些改进算法。
进化策略的本质是通过均衡全局寻优和局部探索来改进个体进化方式，但通过分析发现在整个进化过程中，个体进化策略的不变性也是造成算法寻优效果不高的重要原因，如在整个进化过程中个体均要受到当前最优个体的影响。
协同进化混合蛙跳算法戴月明;张明明;王艳【期刊名称】《计算机工程与科学》【年(卷),期】2018(40)1【摘要】To overcome the shortcomings of the basic shuffled frog leaping algorithm (SFLA),such as slow convergence speed,low optimization precision and falling into local optimum easily,etc.,we propose a novel coevolutionary shuffled frog leaping algorithm (CSFLA).As for the local search strategy of the proposed algorithm,we introduce the average value and make full use of the best individuals to update the worst frog individuals in the subgroup,which expands the searching space effectively and increases the diversity of population.Meanwhile,the interactive learning strategy for a small number of worse frog individuals in the subgroup is adopted to learn from the best frog individuals in neighboring subgroups,which increases the frequency of interaction between subgroups and improves the degree of information sharing,thus conducive to algorithm evolution.In the process of global iteration,we adopt the elite group self-learning mechanism to search through the elite space for a better solution,which can further improve the ability of global optimization and lead the evolution of algorithm for the better.Experimental results show that the proposed algorithm can converge to the optimal solution 0 in the seven test functions,and the success rate is 100％,which is betterthan the other comparative algorithms.The proposed algorithm can effectively avoid premature convergence,and greatly improve the convergence speed and the accuracy of the algorithm.%针对基本混合蛙跳算法收敛速度慢、求解精度低且易陷入局部最优的问题,提出了一种新的协同进化混合蛙跳算法.该算法在局部搜索策略中,对子群内最差个体的更新引入平均值的同时充分利用最优个体的优秀基因,可有效扩大搜索空间,增加种群的多样性;同时对子群内少量的较差青蛙采取交互学习策略向邻近子群的最优个体交流学习,增加子群间交互的频繁性,提高信息共享程度,有利于进化.在全局迭代过程中采取精英群自学习进化机制,以对精英空间进行精细搜索,获得更优解,进一步提升算法的全局寻优能力,正确导向算法的进化.实验结果表明,所提算法在七个测试函数中均能收敛到最优解0,成功率为100％,优于其他对比算法.所提算法可有效避免陷入早熟收敛,极大地提高了算法的收敛速度和优化精度.【总页数】9页(P139-147)【作者】戴月明;张明明;王艳【作者单位】江南大学物联网工程学院,江苏无锡214122;江南大学物联网工程学院,江苏无锡214122;江南大学物联网工程学院,江苏无锡214122【正文语种】中文【中图分类】TP18【相关文献】1.基于改进混合蛙跳算法的多约束车辆路径优化 [J], 鲁建厦;翟文倩;李嘉丰;易文超;汤洪涛2.基于混合蛙跳算法的高维生物医学数据特征选择方法 [J], 代永强;郭小燕;王敏;孙嫣娇3.混合蛙跳算法研究综述 [J], 黄世贤;何晓曦;刘一明4.基于混合蛙跳算法的极限学习机软测量建模 [J], 孙顺远;周乾5.基于改进混合蛙跳算法的个性化旅游路线推荐 [J], 申晓宁;王森林;吴俊潮;仇友辉;张磊;李常峰;王玉芳因版权原因，仅展示原文概要，查看原文内容请购买。
【word】求解多背包问题的混合蛙跳算法求解多背包问题的混合蛙跳算法总第263期2011年第9期计算机与数字工程Computer&DigitalEngineeringVo1.39No.913求解多背包问题的混合蛙跳算法马竹根”舒少华.(怀化学院计算机科学与技术系”怀化418008)(中方县职业中等专业学校怀化418000)摘要针对多背包问题,提出一种改进的离散混合蛙跳算法.算法中对青蛙个体采用十进制整数编码方式,应用遗传算法中的交叉操作来对个体进行更新,扩展了传统混合蛙跳算法模型.将改进的算法用于多背包问题求解,仿真实验表明了所提算法的有效性.关键词混合蛙跳算法;多背包问题;组合优化;交叉算子中图分类号TP301.6ShuffledFrogLeapingAlgorithmforSolvingMultipleKnapsackProblemMaZhugenShuShaohua.(DepartmentofComputerScienceandTechnology,HuaihuaUniversity”,Huaihu a418008)(SpecializedSchoolofZhongfangCountryVocationalSencondarf,Huaihua4180 08)AbstractADiscreteShuffledFrogLeapingAlgorithmisproposedtosolvetheMul tipleKnapsackProblem.Thealgo—rithmadoptsintegercodedschemeandanewmethodofindividualproductionbycr ossoveroperationtOextendthetraditionalmodelofShuffledFrogLeapingAlgorithm.Theexperimentalresultsshowthatth eproposedalgorithmiseffectiveandef—fient.KeyWordsshuffledfrogleapingalgorithm(SFLA),multipleknapsackproblem(M KP),combinatorialoptimization,crossoveroperationClassNumberTP301.61引言多背包问题(MultipleKnapsackProblem,MKP)是一个经典的组合优化问题,在现实生活中有着广泛的应用,如资源分配,投资决策,货物装载等均可建模为多背包问题.因此,多背包问题的求解一直以来是人们关注的一个研究热点,目前已经提出了如精确算法[1],动态规划法[2],启发式算法[引,遗传算法[,蚁群算法[引,人工鱼群算法[.]等多种求解方法.由于精确求解的时间复杂度大,所以精确算法仅能适用于小规模的MKP.基于生物进化和仿生的遗传算法,蚁群算法,人工鱼群算法等,由于具有自组织性,鲁棒性好,易于获得全局解等特点,在求解大规模组合优化问题中应用越来越广泛.混合蛙跳算法[](ShuffledFrogLeapingA1一gorithm,以下简称SFIA)是一种新型仿生群体智能优化算法,它结合了基于基因进化的模因演算法(MemeticAlgorithm,MA)和基于群体行为的粒子群算法(ParticleSwarmOptimization,PSO)两者的优hE,具有概念简单,参数少,计算速度快,全局寻优能力强,易于实现的特点,在资源分配,车间作业流程安排,旅行商问题[,0-1背包问题[1n]等工程实际问题中得到有效的应用.文献Elo]和文献[11]都是采用二进制编码对标准的0—1背包问题进行求解.本文针对多维背包问题,采用十进*收稿日期:2011年3月15日,修回日期:2011年4月28日作者简介:马竹根,男,讲师,研究方向:人工智能,软件工程. 马竹根等:求解多背包问题的混合蛙跳算法第39卷制整数编码方式,应用遗传算法中的交叉操作对个体进行更新,提出一种求解多维背包问题的离散混合蛙跳算法,在具体实例上的实验结果表明该算法对解决多维背包问题是行之有效的.2多背包问题数学模型多背包问题是指在一个物品集合N一{1,2,…,n}中选出一个子集分别装入m个背包中,在不超出每个包的限制容量6,的条件下,使选出的全部物品的总价值最大,其中?M,M一{1,2,…, m}.背包问题可形式化地描述为[6]:Max?CiX(1)f2aijzbiJ一1,2,…,m(2)满足.{?Nlz?{0,1}i一1,2,…,(3)其中:C表示物品i的价值a表示物品i放人背包所占的容量.式(2)表示背包约束,由于具有m个约束,多背包问题又被称为多维背包问题.在多背包问题中,除了确定每个物体是否装入背包外, 还需要确定它将装入哪个背包.显然对于多背包问题的优化会比背包问题复杂得多,它是一个NP一完全问题.3混合蛙跳算法混合蛙跳算法是模拟青蛙觅食过程中信息共享和交流的特点而提出的一种仿生算法.在SF—LA中,种群(解集)由一群具有相同结构的青蛙组成,每只青蛙代表一个解.种群被分成多个族群, 不同的族群被认为是具有不同思想和行为方式的青蛙的集合,不同的族群之间能够相互影响.在每个族群内以更新最差蛙为策略,按照预先定义的局部更新迭代次数进行更新,当所有族群内最差蛙完成局部更新后,各个族群间进行思想交流实现族群间的混合,重新产生新的族群.局部搜索和混合过程一直持续到满足收敛条件或达到最大迭代次数为止.具体来说,SFLA可分成以下步骤:1)初始化种群:随机生成P只青蛙组成初始种群,第i只青蛙表示问题的解为X===(,.27 …,),其中s为解空间的维数,即变量的个数.2)划分族群:将所有青蛙按照它们的适应值降序排列,然后将整个种群分成m个族群,每个族群包含n只蛙,要求满足P=mXn.在迭代过程中第一只蛙分人第一个族群,第二只蛙分人第二个族群,一直分配下去,直到第m只蛙分人第rn个族群.然后第+1只蛙分人第一个族群,第m+2只蛙分入第二个族群,依此类推,直到所有青蛙分配完毕. 3)族群进化:在每个族群中,用和X分别表示该族群中适应值最好和最差的青蛙,用X表示整个种群中最好的青蛙.然后对每个族群进行局部深度搜索,即对每个族群中的最差蛙按下式进行更新操作:D===rand()*(X一)(4)新的位置Xne-u2~一X(当前位置)+D,(DD三三=一D)(5)式中rand()是0,l之间的随机数,D表示青蛙所允许改变位置的最大值.如果这个过程能够产生一个较好解,那么就用新位置青蛙取代最差蛙; 如果没有改进,则用X代替X重复执行式(4)和式(5);如果仍没有改进,则在可行域中随机产生一个新解取代原来最差青蛙X.重复这种更新操作,直到达到设定的局部搜索迭代次数.4)混合:当所有族群的局部搜索完成后,将所有族群内的青蛙重新混合并排序,重复执行第2步和第3步直到满足终止条件,输出全局最优解.4离散混合蛙跳算法求解多背包问题在蛙跳算法中,相关参数大部分属于连续实数域,因此蛙跳算法主要适用于求解连续空间域的优化问题,难于直接处理离散的组合优化问题.在分析传统蛙跳算法优化机理的基础上,本文采用了整数编码方式和新的个体更新策略,提出一种解决多背包问题的离散蛙跳算法.4.1蛙体结构的编码和解性能评价设计蛙跳算法首先要建立个体矢量与问题域之间的映射关系.在蛙跳算法中,一只青蛙对应所求问题的一个解.设有n个物品m个背包,将n个物品按顺序组成一向量X一(z,35z,…,)表示青蛙个体,其中.?{0,1,…,n},i一1,2,…,n.===表示将第i个物品放人第m个背包,.27一0表示第i个物品不放入任何背包.例如,X===(2,3,1,0, 0,0,2,3,3,2,0,1,0,1,1)表示15个物品中,第3, 12,14,l5个物品放人第1个背包,第1,7,10个物品放人第2个背包,第2,8,9个物品放人第3个背包,第4,5,6,11,13个物品不放入任何背包.另外,以背包价值F(x)作为衡量个体X性能指标,F(x)一CiJC,其中各分量含义同式(1).iEN显然F(X)的值越大,表示解的性能越好.。
改进的混合蛙跳算法求解背包问题陈亮【摘要】混合蛙跳算法是一种全新的基于群体智能的后启发式计算技术,具有高效的计算性能和优良的全局搜索能力.文中描述了0/1背包问题的数学模型,分析了混合蛙跳算法基本流程,改进了混合蛙跳算法,并将该算法应用到0/1背包问题的求解过程中.【期刊名称】《长春工业大学学报（自然科学版）》【年(卷),期】2011(032)001【总页数】3页(P61-63)【关键词】混合蛙跳算法;背包问题;高斯变异算子【作者】陈亮【作者单位】泰山职业技术学院信息工程系,山东泰安271000【正文语种】中文【中图分类】TP181;TP1830 引言混合蛙跳算法(shuffled frog leaping algorithm，SFLA)是2000年由Eusuf和Lansey受青蛙群体觅食的行为启发，并总结其规律而提出的一种基于群体智能的后启发式仿生算法[1]。
该算法将全局信息交换和局部深度搜索相结合，通过局部搜索使得信息能在局部个体间传递，其采用的混合策略能使得局部信息在全局范围内得以传递[2]。
1 背包问题背包问题(knapsack problem)是一种组合优化的NP完全问题，通常背包问题分为0/1背包问题、完全背包问题、多重背包问题、混合背包问题4种，由于后3种可以转化为第一种，因此，文中只讨论0/1背包问题[3]。
0/1背包问题的数学模型描述为:式中:n——物体个数;w i——第i种物品的重量(i=1，2，…，n);vi——第i种物品的价值;xi——第i种物品的选择状态，当物件i被选入背包时，定义变量xi=1或0; C——背包的最大容量。
2 混合蛙跳算法基本流程随机生成P只青蛙，每只青蛙代表一个问题的解，记为U i，并视为初始族群。
然后计算族群内所有的青蛙的适应度，并将青蛙按适应度降序排列，再将整个族群内的青蛙分成m个子族群，每个子族群包含n只青蛙，因此满足关系P= m*n。
分配方法:按排定顺序把第1，2，…，n只青蛙分别分到第1，2，…，n个子族群中，第a+1只青蛙分到第1个子族群中，依次类推，直至全部青蛙分配完毕[4]。
自适应混合变异的蛙跳算法李晶晶;戴月明【摘要】Shuffled Frog Leaping Algorithm(SFLA)is a new group evolutionary algorithm prompted by the natrural biological phenomena, and it has fast calculation speed and strong search capability. But its local search ability is weak and it is easily caught in prematrue convergence. Combining with the advantages of Cauchy mutation and Gaussian mutation, a modified SFLA (MSFLA)is proposed to overcome the shortcoming. The MSFLA’s convergence speed is enhanced and the pheonomena that SFLA is trapped in local optimal solution will be avoided to a certain extent, so its ability of problem sloving for complex func-tions is improved. And experimental results prove the validity of the new SFLA.% 蛙跳算法是一种受自然界生物现象启发产生的群体进化算法，计算速度快，寻优能力强，但局部搜索能力较弱，容易陷入早熟收敛。
针对其缺点，结合高斯变异和柯西变异的优点，提出了一种改进的混合蛙跳算法。
改进后的算法收敛速度加快，在一定程度上避免陷入局部最优，提高了蛙跳算法解决复杂函数问题的能力。
对较好和较差个体双向更新的混合蛙跳算法庞凯立;梁昔明【摘要】针对基本蛙跳算法在处理复杂函数优化问题时求解精度低且易陷入局部最优的缺点,将共轭梯度法引入基本蛙跳算法,对排名靠前的p个模因组中的精英个体和排名靠后的q个模因组中的落后个体同时使用共轭梯度法进行更新,一方面增强对较差青蛙的指导能力,另一方面使最差的青蛙直接更新,提高了算法的收敛精度.所得混合蛙跳算法有效结合了基本蛙跳算法较强的全局搜索能力和共轭梯度法快速精确的局部搜索能力.将所得的混合蛙跳算法与其他智能优化算法进行对比,数值试验结果表明,无论从收敛精度还是进化代数而言,所得混合蛙跳算法较其他算法均有较大的改进,具有更高的收敛精度,能有效避免陷入局部最优,且优化结果更加稳定.【期刊名称】《北京建筑大学学报》【年(卷),期】2016(032)004【总页数】6页(P52-57)【关键词】混合蛙跳算法;共轭梯度法;数值试验;适应度函数【作者】庞凯立;梁昔明【作者单位】北京建筑大学理学院,北京100044【正文语种】中文【中图分类】TP301.6基本蛙跳算法[1]是一种新的基于群体智能的启发式算法，该算法是在2003年由Eusuff和Lansey受青蛙进食行为的启发进行建模和仿真研究的结果，该算法结合了粒子群算法和模因算法两者的优点，具有结构简单、收敛速度快和全局寻优能力强等特点.基本蛙跳算法与其他群体迭代算法一样，虽然具有较强的全局搜索能力，但是易陷入局部最优，且收敛精度不高. 为此，学者们进行了深入的研究，提出了一些改进算法，也都取得了不错的效果. 文献[2]对子群中每只青蛙个体引入了随机扰动，并让子群内每只青蛙个体都参与产生新个体，充分利用每只青蛙个体的信息，增加了种群多样性. 文献[3]引入全局共享因子和局部共享因子，由于共享因子随着迭代次数的增加而增大，使得在局部搜索初期，较小的共享因子初值能减弱最优个体对最差个体的指导，避免了青蛙个体更新步长过大而跳过局部最优；在进化后期，共享因子增大，增强了最优个体对最差个体的指导，使得个体跳过局部最优实现全局收敛，该算法动态改变最优个体对最差个体的指导能力，使得青蛙个体更容易跳出局部最优实现全局收敛. 文献[4]基于量子理论提出一种量子混合蛙跳算法，该算法采用量子位的Bloch球面坐标编码个体，利用量子位在Bloch球面上绕轴旋转的方法更新个体，通过自适应混沌旋转角度算子提高子群内部局部搜索能力，采用Hadamard门实现个体变异避免早熟，有效扩展了空间的搜索范围. 文献[5]定义了新的粒子分类标准，将所有青蛙按此标准进行分类，青蛙个体在迭代过程中根据自身状态动态调整惯性权重，并以停滞代数判断是否对最优个体进行优化，避免了陷入局部最优.以上文献中的改进算法都较好地改善了基本SFLA算法，在克服种群陷入局部最优缺陷的基础上增加了种群多样性. 考虑到传统优化算法—共轭梯度法具有较强的局部搜索能力，而现代智能优化算法—基本蛙跳算法收敛精度不高，寻找一种方法将蛙跳算法与共轭梯度法结合起来从而凸显各自的优点显得尤为重要，且历来很少有学者将传统优化方法与基本蛙跳算法结合起来研究. 本文提出的对较好和较差个体进行更新的混合蛙跳算法(SFLA_HH)，充分利用了SFLA算法和共轭梯度法两者的优点，弥补了两者的不足，将SFLA_HH算法与其他智能优化算法进行对比，对五个测试问题的试验结果表明，SFLA_HH算法收敛精度更高.对无约束连续优化问题：若x*∈Rd满足：则称x*为f(x)在全空间Rd上的全局最小点或整体极小点.1.1 SFLA原理SFLA算法将每个个体看做池塘中的一只青蛙[6]，搜索区间即为整个池塘. SFLA算法首先在寻优区间内随机初始化一组向量来组成青蛙的初始种群[7]P={X1,X2,…,Xi,…,XF}(i=1,2,…,F)，第i只青蛙为Xi=(xi1,xi2,…,xid)，每一只青蛙代表一个待选解，xij为第i只青蛙第j维的分量. 对于每个青蛙个体，计算适应度函数值fit(Xi)，本文中适应度函数取为目标函数，然后将所有青蛙个体按照它们的适应度值进行升序排列，并分别放入m个模因组中. 设Mk为第k个模因组青蛙的集合(k=1,2,…,m)，表达式如下：式中，n为每个模因组中的青蛙的个数.种群中适应度函数值最小的青蛙用Xg表示，用和分别表示第k个模因组Mk中适应度函数值最小和最大的青蛙，通过每个模因组Mk中的跳跃前进和位置调整进而影响整个族群的前进位置调整公式如下：青蛙移动的距离向量：更新最差青蛙位置：式中，rand()是0～1之间的随机数，Smax是青蛙跳跃每个分量上允许的最大值，Smin是青蛙跳跃每个分量上允许的最小值. 青蛙在跳跃前进时，如果经(5)更新后的的适应度值比小，用代替；否则用Xg取替重新进行更新操作位置更新公式如下：如果经过式(5)、式(7)计算后仍然产生不了适应度函数值更小的青蛙，那么就随机化一个新向量代替至此完成一次局部迭代，重复局部迭代L次. 当所有模因组都完成局部迭代L次后，判断是否达到全局搜索次数G次，若没有，则将所有F只青蛙重新混合、排序、分组，再按照上述局部搜索步骤重复搜索，直至符合终止条件. 一般情况下，当算法达到了预定的全局迭代次数时，算法终止并输出最优解，全局最优解即为Xg.1.2 共轭梯度法共轭梯度法[8]是由Hestenes和Stiefel( 1952)提出来的，是一种介于最速下降法和牛顿法之间的经典非线性无约束优化算法，它的基本思想是根据迭代点处的负梯度方向构造出一组共轭方向，再沿着这组方向搜索目标函数极值，共轭梯度法的机制保证了所得到的这组共轭方向就是函数值的下降方向. 共轭梯度法最大的优势在于同时解决了最速下降法收敛慢和牛顿法对目标函数要求较高且计算量大的不足，具有较好的局部搜索能力，是求解大型非线性无约束最优化问题的有效算法之一，其求解流程如下：步骤1 选取初始点X0，给定精度eps，计算初始搜索方向步骤2 若‖‖≤eps，输出X0并停止迭代；否则，令k=0，转步骤3；步骤3 求tk使得步骤4 令Xk+1=Xk+tkPk；步骤5 计算若‖‖≤eps，输出Xk+1并停止迭代；否则转步骤6；步骤6 计算共轭方向Pk+1，令k=k+1并转步骤3.考虑到基本蛙跳算法中精英个体更新效率较低、较差个体更新效果不明显等缺陷导致的进化后期易陷入局部最优这一缺点，本文提出在基本蛙跳算法中引入共轭梯度法，对前p个模因组中的精英个体和后q个模因组中的落后个体直接进行更新，一方面增强了对较差个体的指导能力，另一方面提高了最差个体的更新效率. SFLA_HH算法首先对种群和参数进行初始化，各青蛙的初始位置在给定搜索区间内随机生成；然后计算每只青蛙的适应度函数值，对函数值进行升值排序. 本文中适应度函数取为目标函数，故函数值越小代表点的位置越好，由此得到Xg；然后将排完序后的青蛙按照式(3)划分模因组，找到每个模因组中的Xb和Xw，对模因组中的前p组和后q组与共轭梯度法进行结合，具体更新规则为：前p组以Xb为初始点，即X0=Xb，初始搜索方向P0取为-g(Xb)，根据X1=X0+tP0对Xb进行更新，其中步长t根据：求解. 如果X1满足给定的精度要求，则跳出共轭梯度法循环，否则，按下式：进行下一点的迭代，重复计算直至达到给定的精度要求或次数，更新Xb，再按照式(4)、式(5)指导更新Xw；将排列在中间的的(m-p-q)个模因组按照式(5)、式(7)进行更新；将排列在最后的q个模因组与共轭梯度法结合，以Xw为初始点，初始搜索方向P0取为-g(Xw)，再按照上面的式(8)、式(9)、式(10)对Xw进行更新. 从整体效率来考虑，可以适当放低共轭梯度法的精度要求[9]，并且同时使用精度和循环代数一起作为判断共轭梯度法停止的条件. 当所有模因组的局部更新操作都完成后，判断是否达到全局搜索次数，若满足，则输出当前最好解，即为全局最优解；否则，将全部青蛙混合，重复进行下一轮搜索. SFLA_HH算法流程如下：步骤1 随机初始化F只青蛙，最大蛙跳步长为Smax，模因组数为m，每个模因组中的青蛙数为n，局部迭代次数为L，整体迭代次数为G；步骤2 计算所有青蛙适应度函数值；步骤3 将青蛙按照适应度函数值从小到大排序，适应度函数值最小的青蛙记为Xg；步骤4 青蛙种群根据分组规则按照(3)式划分为m个模因组；分别记下每个模因组中的Xb和Xw；步骤5 对前p个模因组结合共轭梯度法，以模因组中Xb为初始点进行循环迭代r 次或达到精度要求，更新Xb，再按照式(4)、式(5)指导更新Xw；对中间的(m-p-q)个模因组按照式(5)、式(7)进行局部搜索L次，更新Xw；对剩余的q个模因组以Xw为初始点行进行循环迭代r次或达到精度要求，更新Xw；步骤6 当局部搜索全部完成后，判断是否达到全局混合迭代次数G，若满足，则输出当前最好解，即为全局最优解；否则，将全部青蛙混合，返回步骤3进行下一轮搜索.因为共轭梯度法对于一个n元正定二次目标函数最多n次就可以寻得最优解，可见共轭梯度法的寻优效率之高. 由于共轭梯度法的运算涉及到梯度计算，运算过程中调用共轭梯度法的次数越多，耗时越久，在本文中共轭梯度法的运算次数与两个因素有关，一是结合共轭梯度法的组数，二是共轭梯度法的内部终止迭代次数r.为了整体寻优速度，本试验调用共轭梯度法的次数不宜太多，故只选取前两组和后两组，即p=q=2.共轭梯度法由于不涉及矩阵，仅仅存储向量，因而存储量小，适合于维数较高的优化问题，因此混合蛙跳算法SFLA_HH对较高维数的函数优化具有较大的优势.为验证混合蛙跳算法SFLA_HH的寻优效果和稳定性，将SFLA_HH算法与基本SFLA算法在不同维度下进行试验. 为了进一步验证文中所提出的混合蛙跳算法的优越性，将SFLA_HH与SFLA、文献[2]中提出的内嵌扰动变异的混合蛙跳算法(DVSFLA)、文献[10]中提出的自适应粒子群优化算法(APSO)以及文献[11]中提出的强化学习的人工蜂群算法(GABC)分别在30维时固定全局迭代次数情况下进行对比分析. 又将SFLA_HH与文献[5]中基于新搜索策略的混合蛙跳算法(NSSFLA)在固定精度情况下进行对比分析. 三种情况对比均使用表1中5个典型的无约束优化问题进行数值试验，各问题的目标函数表达式、搜索范围和理论最优值如表1所示[12]，其中D为问题的维度.函数f1为Sphere单峰函数，全局最小点是(0,0,…,0)；函数f2为Rastrigin函数，函数f3为Griewank函数，函数f4为Ackley函数，都是多峰函数，有很多局部极小点，全局最小点是(0,0,…,0)；函数f5为Rosenbrock函数，是非凸的病态函数，在极小值附近有陡峭的峡谷，用SFLA求解时很容易陷入局部极值，它的全局最小点是(1,1,…,1). 为了进一步比较各种算法的性能，并减少偶然性的影响，本文采用Matlab R2014b试验平台进行数值试验，并对每个测试问题进行30次独立试验，取试验所得的平均最优值、标准差进行对比. 其中，平均最优值为30次试验中每次求得的全局最优解相加除以30；标准差即为30次试验中全局最优解的标准差.本文所选取的试验参数如下，其余对比算法参数设置见对应文献：青蛙个体数F=200;族群数m=20;族群内青蛙个数n=10;局部循环迭代次数L=10;全局循环迭代次数G=200;青蛙最大移动步长设置规则根据文献[13]，即：Smax=可行域的界×45%；p=2；q=2；r=5；eps=1e-2.表2为将SFLA_HH算法与基本SFLA算法在不同维度下进行试验的结果对比. 由表2中对比结果可以看出，在不同试验维度下，无论是解的质量还是算法的稳定性，SFLA_HH算法较SFLA算法均有较大提高. 对于五个测试问题，SFLA算法均未找到最优解，且随着维数增高，SFLA寻优效果也越来越差，而SFLA_HH算法都找到了最优解，并且解的精度在维数变化较大的情况下保持一定的稳定性. 对于问题f1，f2，f3，SFLA_HH算法在三种维度下都找到了理论最优解，SFLA求解精度较差，且未找到最优解；对于问题f4，f5，SFLA_HH算法也都找到了最优解，SFLA算法求解效果较差，且未找到最优解.表3为30维时SFLA_HH与其他现代智能优化算法在固定全局迭代次数情况下结果对比.表4为SFLA_HH与基本蛙跳算法及文献[5]中NSSFLA算法在固定精度情况下结果对比.从表3对比结果中可以看出，SFLA_HH算法与其他算法相比有明显的优势，对于五个测试问题都找到了最优解，其中对于f1，f2，f3都找到了理论最优解；SFLA 算法对于所有的问题均未找到最优解；DVSFLA只对f1找到了最优解；APSO和GABC对于f1，f2和f4均找到了最优解，但求解精度都不如SFLA_HH，可见SFLA_HH的寻优精度之高.从表4可以看出，SFLA对于所有问题都没能达到指定的精度，NSSFLA和SFLA_HH都达到了指定精度；对于f2，NSSFLA和SFLA_HH进化代数没有太大差异；对于f3，SFLA_HH比NSSFLA效果略差；但对于f1和f5，SFLA_HH只需一次就可以达到指定精度，比NSSFLA所需次数少，对于f4，NSSFLA最少需要17次才可以达到指定精度，而SFLA_HH最少只需11次就可以达到指定精度，且平均次数也比NSSFLA少.综上，SFLA_HH收敛精度和平均进化代数均优于基本蛙跳算法和其他几种智能优化算法.共轭梯度法是经典无约束优化算法，由于采用梯度信息，因此可以较快的收敛到函数极小值；基本蛙跳算法在搜索区间广泛随机采点，然后从各点出发，依据青蛙觅食原理搜寻全局最小点，因而具有较好的全局搜索能力. 本文所提出的SFLA_HH算法正是结合了两者的优点，对于排列在前面位置较好的模因组和后面位置较差的模因组均引入共轭梯度法，不仅加强了对最差青蛙个体的指导能力，更提高了最差青蛙的更新效率，进而提高了算法的收敛精度. 改进算法无论从收敛精度、进化代数还是稳定性方面都有较大的优越性，但仍存在一些问题，由于共轭梯度法每次循环都需要计算梯度信息，故对于有些复杂问题，或者非凸问题无法很好地解决，这也是需要改进的地方.【相关文献】[1] 崔文华，刘晓冰，王伟,等.混合蛙跳算法研究综述[J]. 控制与决策，2012，4(3)：481-486[2] 季骏，戴月明，吴定会.内嵌扰动变异的混合蛙跳算法[J].计算机工程与应用，2015，51(12)：27-30[3] 刘立群，王联国，韩俊英,等.基于全局共享因子的混合蛙跳算法[J].计算机工程，2013，39(10)：162-166[4] 张强，李盼池.量子混合蛙跳算法求解连续空间优化问题[J].吉林大学学报：理学版，2013，51(3)：471-477[5] 赵芳，张桂珠.基于新搜索策略的混合蛙跳算法[J].计算机应用与软件，2015，32(8)：224-228[6] 杨淑莹，张桦.群体智能与仿生计算—Matlab技术实现[M].北京：电子工业出版社，2012：167-176[7] 马鲁，陈国初，王海群.蛙跳算法及其在函数优化中的应用[J].上海电机学院学报，2014，17(2)：68-75[8] 孙文瑜，徐成贤，朱德通.最优化方法[M].北京：高等教育出版社，2010：125-137[9] 梁昔明，李德生.嵌入共轭梯度法的混合粒子群优化算法[J].小型微型计算机系统，2014，35(4)：835-839[10] Zhan Zhihui, Zhang Jun, Li Yun, et al. Adaptive particle swarm optimization[J]. IEEE Transactions on Systems Man, and Cybernetics—Part B: Cybernetics, 2009,39(6): 1362-1381[11] Zhu Guopu, KWONG S. Gbest-guided artificial bee colony algorithm for numerical function optimization[J]. Applied Mathematics and Computation, 2010, 217(7): 3166-3173 [12] Meng Jia-na, Lin Hong-fei. Transfer learning based on graph ranking[C]∥Proc. Of the 9th International Conference on Fuzzy Systems and Knowledge Discovery. [S.1.]: IEEE Press, 2012[13] Eusuff M, Lansey K, Pasha F. Shuffled frog-leaping algorithm: a memetic meta-heuristic for discrete optimization [J]. Engineering Optimization, 2006, 38(2): 129-154。
