混合蛙跳算法

优化混合蛙跳算法的WSN三维定位方法刘宏;王其涛;夏未君【期刊名称】《计算机工程与应用》【年(卷),期】2017(053)002【摘要】根据传统混合蛙跳算法（Shuffled Frog Leaping Algorithm，SFLA）收敛速度较慢、局部最优的不足，提出了优化混合蛙跳算法（Optimized Shuffled Frog Leaping Algorithm，OSFLA），并将其应用于无线传感器网络（WSN）节点三维定位。

在三维定位中运用极大似然法进行粗略定位，对锚节点进行加权处理，设定搜索区域，再使用优化蛙跳算法进行迭代求精。

仿真实验结果表明：优化混合蛙跳算法（OSFLA）比混合蛙跳算法（SFLA）具有更高的收敛速度和定位精度，同时更加适合于锚节点数较少场合。

且在三维定位中与常用的几种算法相比OSFLA算法在定位精确度和稳定性方面都具有一定的提高。

%According to the traditional Shuffled Frog LeapingAlgorithm(SFLA)that its convergence speed is slow and its local optimum has the shortcomings. The Optimized Shuffled Frog LeapingAlgorithm(OSFLA)is put forward here and applied to the three-dimensional positioning of the wireless sensor network node. In the three-dimensional positioning, at first, using maximum likelihood has a rough positioning, then having weighted processing for anchor nodes and setting the search area. Finally, using OSFLA achieves the effect of iterative refinement. The simulation result shows that, the OSFLA has higher convergence speed and precision than the traditional SFLA. At the same time, it is more suitable forthe occasion that has the less number of anchor node. Besides, in the three dimensional positioning, compared with the commonly used several kinds of algorithms, the OSFLA algorithm’s positioning accuracy and stability of OSFLA algorithm are obviously improved.【总页数】6页(P129-133,140)【作者】刘宏;王其涛;夏未君【作者单位】江西理工大学电气工程与自动化学院，江西赣州 341000;江西理工大学电气工程与自动化学院，江西赣州 341000;江西理工大学电气工程与自动化学院，江西赣州 341000【正文语种】中文【中图分类】TP393【相关文献】1.基于PSO优化LSSVR的三维WSN节点定位方法 [J], 张烈平;陈鸣;季文军;2.基于WSNs三维无线层析成像定位方法研究 [J], 黄炳华; 王满意; 刘增鑫3.基于跳距修正与狮群优化的WSNs三维定位算法 [J], 苟平章;刘学治;孙梦源;何博4.基于果蝇优化的WSNs三维节点定位算法 [J], 王海云;李洁;张姣5.带混沌映射的三维WSN蜂群优化定位算法 [J], 李田来;刘方爱因版权原因，仅展示原文概要，查看原文内容请购买。

带有选择和自适应变异机制的混合蛙跳算法刘悦婷【摘要】混合蛙跳算法易陷入局部最优,且收敛速度较慢.为此,提出一种带有选择和自适应变异机制的蛙跳算法.引入线性递减的动态惯性权重修正最差青蛙,按照一定的概率选择适应度值较优的青蛙代替较差青蛙,并对每只青蛙个体以不同概率进行自适应变异.仿真结果表明,该算法可以平衡全局搜索和局部搜索,寻优能力强、迭代次数少,解的精度较高,更适合高维复杂函数的优化.%Because of the problems of Shuffled Frog Leaping Algorithm(SFLA) such as local optimality and slow convergence rate, a leapfrog algorithm with selection and adaptive mutation mechanism is presented. This algorithm introduces the linear decreasing adaptive inertia weight to correct the poor frog update strategy. It selects the frog with better fitness value to substitute the poor, and makes very frog adaptively mutate with different probability. Simulation results show that this algorithm can balance the global search and local search, and its optimization ability is stronger, the number of iterations is less, the solution is better, and the suitable for high-dimensional optimization of complex functions is more.【期刊名称】《计算机工程》【年(卷),期】2012(038)023【总页数】6页(P206-210,218)【关键词】混合蛙跳算法;选择机制;自适应变异;惯性权重;更新策略;全局最优【作者】刘悦婷【作者单位】甘肃联合大学电子信息工程学院,兰州730000【正文语种】中文【中图分类】TP3911 概述混合蛙跳算法(Shuffled Frog Leaping Algorithm,SFLA)是一种群体智能优化算法[1]。

基于平均值的混合蛙跳算法宋磊;王联国;张友华【摘要】针对基本混合蛙跳算法收敛速度慢，容易陷入局部最优的问题，提出了基于平均值的混合蛙跳算法。

该算法将基本蛙跳算法中子群的平均值，通过2种不同的更新策略分别引用到混合蛙跳算法的局部搜索中，对算法的更新策略进行了适当改进，以期提高混合蛙跳算法的局部搜索能力。

结果表明：更新策略1将子群的平均值与局部更新策略相结合，使算法在搜索过程中加快搜索速度，提高了局部搜索能力；更新策略2则通过采用自适应概率随机将子群的平均值取代子群部分最优个体进行策略更新，使算法在局部搜索时提高了寻优能力，有效的避免算法陷入局部最优。

通过对5个测试函数进行优化，并同基本混合蛙跳算法和文献中改进的算法进行比较，结果表明：该算法可以有效的避免局部搜索过早收敛，具有较好的优化性能。

%Aiming at slow convergence speed and falling into local optimum problems of shuffled frog leaping algorithm easily,the novel shuffled frog leaping algorithm based on average value is proposed.The algorithm references average value using two kinds of different update ideas to the basic shuffled frog lea-ping algorithm and improves the update policy of algorithm appropriately and the local search ability re-spectively.The former combines average value of subgroup with partial update strategy,speeding up the convergence rate in the iteration and improving the local search ability,the latter uses adaptive probability randomly to replace some best individual of partial subgroups by using the average value of subgroups,and increases the local search optimization ability of algorithm,and effectively avoids the algorithm falling into localoptimum.The algorithm is based on five test function optimization and compares with basic SFLA and the improved SFLA in related references;simulation experiments show that the algorithm based on average value can effectively avoid premature convergence and have better optimization performance.【期刊名称】《甘肃农业大学学报》【年(卷),期】2014(000)003【总页数】5页(P176-180)【关键词】混合蛙跳算法;平均值;自适应概率;局部最优【作者】宋磊;王联国;张友华【作者单位】甘肃农业大学工学院，甘肃兰州 730070;甘肃农业大学信息科学技术学院，甘肃兰州 730070;甘肃农业大学工学院，甘肃兰州 730070【正文语种】中文【中图分类】TP301.6混合蛙跳算法［1］（shuffled frog leaping algorithm，SFLA）是由Lansey和Eusuff于2003年提出的一种模拟青蛙觅食行为的群体智能算法，它具有概念简单、参数较少、计算快速等特点.然而，与其它群体智能算法相似，SFLA算法在优化部分函数时存在易陷入局部最优，效果不够理想等缺点.因此，许多研究者对SFLA进行了研究与改进［2－10］，如Emad等引入一种新的加速搜索参数到基本混合蛙跳算法中，提出了算法的一种改进形式；周建中等提出了一种改进的混合蛙跳算法通过阈值选择策略进行更新改进，对于不满足阈值条件的个体分量不予更新的策略，从而改善了算法性能；罗雪晖等将一种新的思想—调序思想巧妙的引入到基本混合蛙跳算法中，与此同时又将变异操作加入到基本混合蛙跳算法全局搜索中，提出了一种更为有效的改进混合蛙跳算法.本文将基本蛙跳算法中的平均值，通过粒子群算法［11］中出现的2种不同的更新策略分别引用到基本混合蛙跳算法中，对局部搜索更新策略进行适当改进，提出了基于平均值的混合蛙跳算法（novel shuffled frog leaping algorithm based on average value，NSFLA），为便于区分，将这2种更新策略改进的算法分别记为NSFLA1和NSFLA2.随机初始化种群，将青蛙的整个种群F分为m个子群，每个子群中含有n只青蛙，并且满足关系F＝m×n.其中，第1只青蛙分入到第1子群，第2只青蛙分入到第2子群，第m只青蛙分入到第m子群，第m＋1只青蛙分入到第1子群，第m＋2只青蛙分入到第2子群，依次类推，一直到所有青蛙划分完毕.在每个子群中，设Xk＝（xk1，xk2，…，xks）代表第k只青蛙的状态向量，s表示维数，当前青蛙目标函数适应度Y＝f（Xk），Xb＝（xb1，xb2，…，xbs）表示每个子群中适应度最好的青蛙，Xw＝（xw1，xw2，…，xws）表示每个子群中适应度最差的青蛙，Xg＝（xg1，xg2，…，xgs）表示整个青蛙种群中适应度最好的青蛙.然后对每个子群进行局部搜索，即对子群中的最差个体Xw循环进行更新，其更新策略为：式中：newXw表示由更新策略产生的新个体；dj表示分量上移动的位置，rand （）表示0到1之间的随机数；Dmax表示青蛙所允许改变的最大步长.如果更新后的新个体优于原来的Xw，则用newXw取代Xw.如果没有原来的解优，则用全局最优个体Xg取代子群中最好的个体Xb，然后重复执行更新策略（1）、（2）.如果仍然没有改进的话，则随机产生一个新个体取代原来的Xw.重复这种操作，直到达到终止条件为止.直到所有子群的局部搜索完成后，混合所有子群的青蛙个体，并重新进行排序和分组.按照以上方式再进行局部搜索，如此反复直到满足该种群的收敛的条件或者达到算法设定的最大进化迭代次数［12］.2.1 算法思想基于平均值的混合蛙跳算法的思想借鉴粒子群算法［11］中速度和位置更新公式与设计自适应概率的思想，将这2种思想分别引用到基本的SFLA中并对其局部更新策略进行改进，以提高算法的优化性能.1）第1种局部搜索更新策略（NSFLA1）NSFLA1实现算法的关键：把每个子群中的平均值Xa与公式（1）的更新策略相结合，用公式（3）对子群中的Xw循环进行更新操作，其更新策略公式如下所示：式中：Xa＝（xa1，xa2，…，xas）表示每个子群的平均值.2）第2种局部搜索更新策略（NSFLA2）NSFLA2实现算法的关键：将每个子群中的平均值Xa取代子群的部分最好个体进行更新策略，在混合蛙跳算法的子群平均值选取中，通过设计一个自适应概率p＝f／N，控制子群中的Xw循环并采用更新策略公式（4）对子群中的Xw循环进行更新操作，其更新策略公式（4）如下所示：式中：f表示当前子群的迭代次数；N表示子群的最大迭代次数.Xa＝（xa1，xa2，…，xas）表示每个子群中的平均值.从理论上说基于平均值的混合蛙跳算法的这两种更新策略能较好地克服SFLA算法在局部搜索时，容易陷入局部最优的缺点，能在更大的范围内进行局部搜索，提高了混合蛙跳算法的性能，使得群组内个体更好更快地向全局最优值的方向趋近.2.2 算法具体步骤基于平均值的混合蛙跳算法具体步骤如下：步骤1：初始化整个青蛙种群，设置混合蛙跳算法中一些参数，例如种群的总体青蛙个数为F，青蛙个体解的维数s等.步骤2：计算适应值和寻找全局的最优个体Xg.步骤3：将全部的青蛙个体按照一定的原则进行大小降序排列，将每一个青蛙个体按照一定的顺序分别分配到不同的子群体中去，可以看做是分配为为m个子群体，其中每个子群体有含有n只青蛙.步骤4：重复执行多次，找出根据适应度值更新而求得全局最好个体的位置Xg和最好个体的位置Xb，最终确定在当前迭代次数子群体中最差个体的位置Xw；依据文中提出的改进更新策略公式（3）或者（4）对最差个体Xw的进行循环更新. 步骤5：当局部搜索完成以后，就按照适应值的大小再次对每个子群体中的个体进行一定程度的排列，从而能够进行分配的重新，使得群体再次进行分配组合.步骤6：当青蛙全体都完成规定的迭代次数后判断是否满足终止条件，若满足终止条件，就可以结束迭代，同时给出全局的最优的解Xg；否则转到第二步继续执行下面的步骤.3.1 试验设计为了验证基于平均值的混合蛙跳算法的性能，文中应用SFLA、ISFLA［7］、NSFLA1和NSFLA2分别对测试函数f1～f5进行优化测试.具体测试函数如下：试验中的参数设置：种群规模F＝200，子群数m＝20，每个子群含n＝10只青蛙，子群内更新迭代次数N＝10，函数变量维数s＝30，混合迭代次数G＝500.文中NSFLA采用Dmax＝Xmax／10，每个测试函数参数如表1所示.采用如下方法对文中NSFLA算法进行性能评估：通过固定进化的迭代次数，记录达到的目标精度进而评估该算法的优化性能.3.2 试验结果及分析在算法性能测试中，固定进化迭代次数G＝500，将连续运行30次所得的函数全局平均最优值、标准差以及运行时间作为算法性能的衡量指标.测试函数的试验结果如表2所示.由表2可以看出基于平均值的混合蛙跳算法NSFLA1和NSFLA2的试验结果优于基本的混合蛙跳算法SFLA和文献［7］中改进的算法ISFLA，有效地提高了该算法的收敛速度，提高产生解的质量，同时也提高了该算法的局部搜索能力，避免局部过早进入最优，具有较强的优化能力.图1～5是函数f1～f5在相同条件下采用SFLA、ISFLA［7］、NSFLA1和NSFLA2运行30次后得到的平均最优值的进化曲线.从图中可以看出，NSFLA1和NSFLA2收敛速度较快，同时优化精度有显著的提高.SFLA是近几年来刚刚兴起的一种新的随机优化算法，对于全局搜索和局部搜索具有较强的寻优能力.文中提出的基于平均值的混合蛙跳算法NSFLA，在一定程度上提高了每个子群局部搜索的能力，在每次迭代进化中使得子群的搜索信息得到较好的更新，能在更大的范围内进行局部搜索，具有较强的寻优能力.由测试函数f1～f5的仿真试验结果表明：文中提出的NSFLA1和NSFLA2相对于基本的SFLA和文献［7］中ISFLA在性能方面都有了一定程度的提高，可以有效的避免局部搜索过早收敛，并且在收敛速度与稳定性方面有较强的优化能力.【相关文献】［1］ Eusuff M，Lansey K E.Optimization of water distribution network design usiong the shuffled frog leaping algorthm［J］.Water Resources Planning and Management，2003，129（3）：210-225［2］ Elbeltagi Emad，Hegazy Tarek，Grierson Donald.A modified shuffled frog-leaping optimization algorithm：Applications to project management［J］.Structure and Infrastructure Engineering，2007，3（1）：53-60［3］ Zhang X C，Hu X M，Cui G Z，et al.An improved shuffled frog leaping algorithm with cognitive behavior［C］.7th World Congress on Intelligent Control and Automation，Piscataway，USA：IEEE，2008：6197-6202［4］李英海，周建中，杨俊杰，等.一种基于阈值选择策略的改进混合蛙跳算法［J］.计算机工程与应用，2007，43（35）：19-21［5］赵鹏军.一种新的仿生优化算法及其改进［J］.商洛学院学报，2009，23（2）：19-22 ［6］栾垚琛，盛建伦.基于粒子群算法的混洗蛙跳算法［J］.计算机与现代化，2009（11）：39-42［7］赵鹏军，刘三阳.求解复杂函数优化问题的混合蛙跳算法［J］.计算机应用研究，2009，26（7）：2435-2437［8］赵守法.蛙跳算法的研究与应用［D］.上海：华东师范大学，2008［9］代永强，王联国.蛙跳算法投影寻踪模型及其在甘肃省主要城市国民经济综合指标评价中的应用［J］.甘肃农业大学学报，2011，46（2）：156-160［10］罗雪晖，杨烨，李霞.改进混合蛙跳算法求解旅行商问题［J］.通信学报，2009，30（7），130-135［11］唐岑琦，周育人.具有综合学习机制的粒子群算法［J］.计算机工程与应用，2007，43（31）：42-44［12］王辉，钱锋.群体智能优化算法［J］.化工自动化及仪表，2007，34（5）：7-13。

改进的混合蛙跳算法及其多目标优化的应用研究改进的混合蛙跳算法及其多目标优化的应用研究摘要：蛙跳算法（Frog Leap Algorithm, FLA）作为一种基于群体智能的优化算法，在解决单目标优化问题上具有较好的效果。

然而，传统的FLA在处理多目标优化问题时存在一些不足之处，如过早收敛和缺乏全局搜索能力。

为了克服这些问题，本文提出了一种改进的混合蛙跳算法（Improved Hybrid Frog Leap Algorithm, IHFLA），并通过实验证明其在多目标优化问题上的应用效果。

引言：随着计算机技术的迅猛发展，多目标优化问题在各个领域中得到越来越广泛的关注。

多目标优化问题是指在多个目标函数的约束下，寻找最优解空间中的非劣解集合。

针对多目标优化问题，传统的单目标优化算法效果不佳，因此需要开发新的算法来解决这一问题。

本文将基于群体智能的优化算法——蛙跳算法，进行改进，以提高其在多目标优化问题上的性能。

1.蛙跳算法的原理及不足蛙跳算法是一种基于仿生学的启发式优化算法，模拟了青蛙在寻找食物过程中的行为。

其基本思想是通过模拟蛙类的跳跃行为来搜索最优解。

每个蛙个体都含有一组决策变量，通过不断迭代调整这些变量，以达到最优解。

然而，传统的FLA在多目标优化问题中存在一些问题：（1）易陷入局部最优解，过早收敛；（2）缺乏全局搜索能力。

2.改进的混合蛙跳算法(IHFLA)为了克服传统FLA中的问题，本文提出了一种改进的混合蛙跳算法（IHFLA）。

该算法在传统FLA的基础上引入了局部搜索和全局搜索的策略，以提高其多目标优化问题的能力。

具体步骤如下：（1）初始化种群：根据问题的约束条件，随机生成一定数量的蛙个体作为初始种群。

（2）目标函数计算：计算种群中每个蛙个体的目标函数值。

（3）更新个体位置：根据当前种群中每个蛙个体的目标函数值，更新其位置。

（4）局部搜索：对每个个体进行局部搜索，以增加探索空间。

（5）全局搜索：通过引入全局搜索策略，使蛙个体具有更好的全局搜索能力。

混合蛙跳算法神经网络在谐波检测中的应用张宏亮;顾文灿;李增;魏斌;黄雷【摘要】According to the harmonic measuring for traditional BP neural network, compares the problems of slow convergence speed, easily falling into local minimum value. Proposes a Shuffled Frog-leaping algorithm neural network using Shuffled Frog-leaping Algorithm, instead of a Gradient Search Algorithm in BP neural network method for Harmonic amplitude and phase measurements of power of system. The neural network model is developed according to the requirements of measuring harmonic. Expounds the basic principle of Shuffled Frog-leaping Algorithm neural network. Gives the training method of SFLA neural network and how to construct the training sample in the three har-monic as an example. The simulation results verify the feasibility of the proposed method. SFLA neural network convergence speed and detection accuracy is better than the BP neural network. Uses the neural network detection trained without training samples, the result proves that the neural network has good generalization ability.%针对传统BP神经网络用于谐波检测时存在收敛速度慢、易陷入局部最小值的缺点，提出用混合蛙跳算法代替BP神经网络中梯度搜索算法的混合蛙跳算法神经网络，并将其用于电力系统谐波幅值与相位测量。

————————————————————————————————————————————————混合蛙跳算法的最优参数研究作者孟凯露，尚俊娜，岳克强机构杭州电子科技大学通信工程学院；杭州电子科技大学电子信息学院DOI 10.3969/j.issn.1001-3695.2018.05.0304基金项目浙江省基础公益研究计划资助项目（LGG18F010010）；国家自然科学基金资助项目（11603041）；浙江省基础公益研究计划项目（LGG18F010010）；广西精密导航技术与应用重点实验室开放基金资助项目（DH201714）预排期卷《计算机应用研究》2019年第36卷第11期摘要介绍了混合蛙跳算法的最优参数选取过程。

在种群总数以及总迭代数给定的情况下，分组数、允许青蛙个体位置改变的最大步长和组内迭代数是影响混合蛙跳算法优化性能的重要参数。

不同的参数值选取会对算法的结果产生不同的影响。

对混合蛙跳算法中这3个参数的值进行选择，首先进行了参数对算法的影响分析，其次取每个参数的3个常用值，利用正交试验设计法设计三因素三水平的实验；接着设置相同的环境条件，用CEC2013实参函数测试集验证不同参数组合算法的寻优性能。

最后以最优值误差的Friedman检测的得分为评价指标，选出最优参数组合(20，5，10)，为后续算法改进及应用打下基础。

关键词混合蛙跳算法；正交试验；CEC2013评价标准；参数选择作者简介孟凯露（1993-），女，浙江诸暨人，硕士研究生，主要研究方向为智能算法；尚俊娜（1979-），女，副教授，博士，主要研究方向为通信信号处理､智能算法；岳克强（1984-），男（通信作者），讲师，博士，主要研究方向为进化计算､通信信号处理（839534673@）．中图分类号TP301.6访问地址/article/02-2019-11-029.html投稿日期2018年5月22日修回日期2018年7月18日发布日期2018年8月10日混合蛙跳算法的最优参数研究————————————————————————————————————————————————引用格式孟凯露, 尚俊娜, 岳克强. 混合蛙跳算法的最优参数研究[J/OL]. 2019, 36(11). [2018-08-10]./article/02-2019-11-029.html.第36卷第11期 计算机应用研究V ol. 36 No. 11 优先出版Application Research of ComputersOnline Publication——————————收稿日期：2018-05-22；修回日期：2018-07-18 基金项目：浙江省基础公益研究计划资助项目（LGG18F010010）；国家自然科学基金资助项目（11603041）；浙江省基础公益研究计划项目（LGG18F010010）；广西精密导航技术与应用重点实验室开放基金资助项目（DH201714）作者简介：孟凯露（1993-），女，浙江诸暨人，硕士研究生，主要研究方向为智能算法；尚俊娜（1979-），女，副教授，博士，主要研究方向为通信信号处理､智能算法；岳克强（1984-），男（通信作者），讲师，博士，主要研究方向为进化计算､通信信号处理（839534673@ ）．混合蛙跳算法的最优参数研究 *孟凯露a ，尚俊娜a ，岳克强b †(杭州电子科技大学 a. 通信工程学院; b. 电子信息学院, 杭州 310018)摘 要：介绍了混合蛙跳算法的最优参数选取过程。

混合蛙跳算法基本原理
嘿，朋友们！今天咱们来聊聊超有意思的混合蛙跳算法的基本原理！
你想想啊，就好比一群青蛙在一个大大的池塘里蹦跶（这就像算法中各种可能的解）。

它们有的蹦得远，有的蹦得近，但是它们都在努力寻找最好的位置。

混合蛙跳算法呢，就是让这些青蛙们分成小组（可以类比为不同的解集群）。

每个小组里的青蛙们会一起交流，互相学习，然后各自根据学到的东西蹦一蹦（调整解）。

比如说，有一只青蛙发现旁边那只蹦得挺不错，它就会跟人家学学，也试着往那个方向多蹦一点。

然后呢，各个小组之间还会交换信息（这就像是不同解集群之间的交互）！哎呀，这多棒啊！这样就可以让大家都能知道其他小组找到的好地方，都朝着更好的方向去努力。

就好像一群小伙伴一起玩游戏，互相分享经验，然后一起进步！
那这个算法到底有啥用呢？这么说吧，假如你要规划一条最优的物流路线，那它就能帮你找到最合适的那条路，能省好多时间和成本呢！这不就像你找路的时候有人给你指了一条明路一样吗？
再比如，在设计一个复杂的系统时，它能让你快速找到最佳的参数组合。

这不就相当于有个超级聪明的助手帮你把一切都安排得妥妥当当嘛！
我觉得混合蛙跳算法真的太神奇了，就像给我们打开了一扇通往高效解决问题的大门。

它让我们能在各种复杂的情况下都能找到最好的办法，难道不是很了不起吗？朋友们，你们说呢！
观点结论：混合蛙跳算法是一种非常有创意和实用的算法，能帮助我们高效地解决各种问题，具有很大的价值和潜力。

对较好和较差个体双向更新的混合蛙跳算法庞凯立;梁昔明【摘要】针对基本蛙跳算法在处理复杂函数优化问题时求解精度低且易陷入局部最优的缺点,将共轭梯度法引入基本蛙跳算法,对排名靠前的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。