蛙跳算法及其在函数优化中的应用

马 鲁， 陈国初， 王海群

（上海电机学院 电气学院，上海200240）

在科学研究、工程实践以及日常生活中，往往会遇到林林总总的最优化问题。人类在生产生活中，在不改变现有条件下，从多种方案中找到一个所需时间最短、效率最高、获利最多的方法，这就是最优化问题[1]。伴随着科技的进步，常规的优化方法已经不能很好地求解日益复杂的问题。随着对生物学的研究，人们发现自然界中的个体行为简单、能力非常有限，但当它们一起协同工作时，表现出的并不是简单的个体能力叠加，而是非常复杂的行为特征。如，蜂群通过协同工作，完成采蜜、御敌等任务；蚂蚁群也可以完成觅食、筑巢等行为。仿生智能优化算法大多以模仿自然界中不同生物种群的群体体现出来的社会分工和协同合作机制为目标，而非生物的个体行为，属于群体智能的范畴，故也被广泛称为群体智能优化算法[2-4]。

蛙跳算法（Shuffled Frog Leaping Algorithm，SFLA）是2003年由Eusuff和Lansey初次提出的一种新式仿生群体智能优化算法[5]。它结构简单，使用便利。关于蛙跳算法的研究目前可查的文献相对比较少。近年来，国内外一些学者提出将混合SFLA用于加工制造行业[6]、旅行商问题[7]、连 续 优 化 问 题[8]和 模 糊 控 制 器 设 计[9]等。本文分析SFLA的基本原理、数学模型和实现流程，讨论了常见的改进SFLA及其应用，并将SFLA用于函数的优化；最后，归纳了SFLA的优势并就SFLA进一步的研究工作进行展望和探讨。

1 基本SFLA

1.1 SFLA原理

如图1所示，种群有很多只青蛙组成，每只青蛙代表了一个潜在解。种群被分成m个子群（Group 1，Group 2，…，Groupm）；一个子群称为一个模因组，每个子群中含有一定数目的青蛙；每只青蛙都在寻找食物（Food）。不同的模因组拥有不同的文化信息，分别执行自己模因组内的搜索。在每个模因组内，青蛙不仅能得到各自的信息，且受到其他青蛙文化信息的影响，并通过这种进化来发展，使这些文化信息在各个子群中传播开来；而后，继续局部搜索和寻觅食物，直到满足收敛条件为止。

图1 蛙跳算法的原理图Fig.1 Schematic diagram of SFLA

1.2 SFLA的数学模型

SFLA结合了模因演算算法和粒子群算法（Particle Swarm Optimization，PSO）的很多优点，故具有更大的优越性。

在目标搜索空间中，随机初始化产生F只d维青蛙群体，构成初始种群P＝｛X1，X2，…，XF｝（i＝1，2，…，F），第i只青蛙Xi＝（xi1，xi2，…，xid）作为一个候选解，xid为第i只青蛙的第d维的解。其中，d为个体所带的文化基因中包含的文化特征数。对于每个个体计算适应值fit（i），对种群中青蛙个体按照适应值升序排列并存放于新数列中，记录种群中适应值最好的青蛙个体位置（最优解）Xg；继而将初始种群划分为m个模因组，划分过程如下：第1只青蛙划分入第1个模因组，第2只青蛙划分入第2个模因组，第m只青蛙划分入第m个模因组，第m＋1只青蛙重新划分入第1个模因组，依次类推。设Mk为第k个模因组青蛙的集合（k＝1，2，…，m），其表示为

式中，n为模因组内的个体数；l＝1，2，…，n。

种群中的最好适应值青蛙记为Xg，而每个模因组中最好青蛙和最差青蛙分别记为Xb和Xw；继而对模因组进行局部搜索，即对模因组中的Xw进行改进。

由基本蛙跳规则知更新方式为

式中，r为0～1之间的随机数；Smax为最大移动步长；S为最差青蛙移动步长。

通过更新操作，如果X′w的适应值较Xw的适应度值好，则取代原来的青蛙；否则，用Xg取代Xb，按照式（2）、（3）进行更新操作；如仍未改进，则随机初始化新解，直接替代原来的Xw。重复上述局部搜索Lmax次，其中，Lmax为局部迭代次数，当局部搜索全部完成后，将所有F只青蛙重新混合、排序、划分模因组，再局部搜索，如此反复，直到满足算法终止条件。

1.3 SFLA算法的实现流程

根据SFLA的原理和数学模型，可以得到以下算法流程[10]：

步骤1 随机初始化F只青蛙种群，使得青蛙维数为d，模因组个数为m，每个模因组内的个体数为n，全局混合迭代次数为Gmax，局部迭代次数为Lmax，最大蛙跳步长为Smax。

步骤2 计算全部青蛙的适应度值。

步骤3 将所有的青蛙按适应度值结果升序排序，并记下全局最好个体Xg。

步骤4 将青蛙个体按式（1）划分到m个模因组中。

步骤5 对每一个模因组，重复执行以下局部搜索Lmax次：① 更新全局最好个体Xg、模因组中最好个体Xb、当前最差个体Xw；② 按照式（2）、（3）对Xw进行更新操作。

步骤6 当局部搜索完成后，若满足全局搜索Gmax次，则进化过程结束，输出全局最优解；否则，将全部青蛙混合，返回步骤2重新计算。

以上算法流程图如图2所示。

图2 SFLA流程图Fig.2 Flow chart of SFLA

1.4 参数性能分析

本文对SFLA的参数分析如下：

（1）种群规模。种群规模（青蛙总数F）的选取与所要求函数的类型、难易程度相关，在一定区域，F越大，越接近于全局最优，逼近效果越好。

（2）模因组个数m、每个模因组中的个体数n。由于F＝m×n，若m较小，使得n偏大，则会导致模因组间文化交流不全面，而不能很好地进行全局搜索，信息交流容易出现偏差，交流缓慢；若m偏大，使n偏小，则导致全局过搜索，算法收敛速度减慢，同时，使子群体内的青蛙不能很好地交流，交流信息匮乏，使得算法更容易陷入局部最优，无法找到全局最优解。

（3）局部迭代次数Lmax、全局混合迭代次数Gmax。若Lmax、Gmax偏小，易导致文化信息交换不全面，不能很好地互换信息，若Lmax偏大、Gmax偏小，将使得算法局部过搜索，收敛速度缓慢，全局信息交流出现偏差，从而无法寻得全局最优；若Lmax偏小、Gmax偏大，也会使收敛速度减慢，全局过搜索，更易陷入局部最优；若Lmax、Gmax太大，则会使收敛速度缓慢，收敛精度低。

（4）最大移动步长Smax。Smax在算法的寻优过程中具有相当重要的作用，若其偏小，会削弱算法的全局搜索能力，使算法陷入局部最优；其偏大，则易使青蛙跳过全局最优解，无法找到最优解。

关于SFLA的参数，目前主要来源于实验验证。因此，参数设置将是混合SFLA的一个重要环节，也是当前的研究热点之一。

2 SFLA的研究现状

2.1 改进的SFLA

针对SFLA收敛速度慢、收敛精度低、收敛早熟等问题，从种群的初始化、局部搜索及淘汰机制等方面对其进行探讨。

2.1.1 基于混沌序列的SFLA 初始种群布局的不平衡会严重影响算法的收敛性能。文献[11] 中提出了一种基于混沌序列产生的群体，使之具有更好初始解。由于混沌的遍历性——混沌运动能在一定范围内按其自身的“规律”不重复地遍历所有状态，可以使SFLA跳出局部最优。其初始化的主要思想是：最初产生一组与优化变量数目相同的混沌变量，然后，将混沌的遍历范围放大到优化变量的取值范围，继而，利用混沌的遍历性、随机性进行搜索，并提出了一个混沌模型。Tent迭代公式如下：

式中，ZV为混沌变量；V为迭代次数。

在（0，1）内，随机产生一个d维向量Z＝（Z11，Z12，…，Z1d），应用式（4）、（5）得到M个分量Z1，Z2，…，ZM（i＝1，2，…，M），Zi＝（xi1，xi2，…，xid）（j＝1，2，…，d），

式中，aj、bj为初始种群j维最小值、最大值。通过计算适应值，从M个初始种群中选择适应度值较优的F个青蛙作为初始解。

基于混沌序列的SFLA对某些问题可以得到满意的结果，但是，仅通过产生好的初始种群来对许多复杂的函数进行很好的优化问题还有很大困难，若尝试性地将其与其他改进融合在一起，也许会有更好的效果。

2.1.2 自适应移动因子SFLA 在基本SFLA中，rand（）函数的随机性不能很好地引导青蛙向着最优解的方向前进，在进化过程中可能陷入局部最优或跳过全局最优。经验证，在进化初期，SFLA一定程度上增大了局部搜索能力，可以扩大寻优范围，使得算法更好地定位到目标区域；而在进化的中后期，应考虑到解的全局搜索能力，减小局部搜索，从而促使解跳出局部最优。为选择更优的移动因子，文献[12] 中将设计的递增函数、凹递增函数、线性递增函数、对数递增函数、三角递增函数和rand（）移动因子通过仿真实验对比，确定了移动因子为对数函数时，测试函数均取得了较优的效果，故对数函数更适合作为移动因子。

自适应SFLA对许多问题可以取得令人满意的结果，但对于许多复杂的非线性优化问题，试图通过自适应移动因子调整一个全局系数来提高搜索精度的余地是有限的。

2.1.3 基于阈值选择策略的SFLA 由于算法按照式（2）、（3）对模因组中每个最差的解Xw进行更新操作时都要对每一维上的分量进行更新，这就使新的解的位置和原来有很大变化，而变化会随着维数的增加而增大。这种方法虽然可以扩大搜索范围，但却容易跳过最优解，从而增加了计算时间。因此，为减小局部更新操作带来的位置的巨大差异，文献[13] 中提出了基于阈值选择策略的SFLA，即由式（2）、（3）在对Xw不同维上的分量进行更新时增加一个随机判别条件，当该随机数大于等于阈值时，则该维分量上的迭代方法按式（2）确定；当该随机数小于阈值，则令S＝0，即对该维分量的数值不予更新。这种策略可减少Xw在更新前、后位置的差距，有利于循环过程中最优解的收敛。实验证明，其效果更好。

基于阈值选择策略的SFLA对简单和复杂的连续函数的优化都能取得一定的效果，但是对许多离散函数优化问题，还有待进一步研究。

2.1.4 小生境淘汰机制的SFLA 小生境技术[14]的基本思想如下：当两个青蛙之间的距离q（一般指欧氏距离）小于某个预先设定（小生境距离）Q时，再比较目标函数值的大小，惩罚目标函数值较差的个体。在各模因组内部进行局部搜索时，在一定连续进化代数内，若模因组满足

式中，xib、xjb为第i、j代最优青蛙个体；2≤i≤N，2≤j≤N，且i≠j，N为模因组内迭代次数，s为种群维数；δ为很小的数。当xib和xjb之间的距离小于Q，且满足其对应的目标函数值差的绝对值小于δ时，表明该子种群处于停滞状态，将其淘汰，并重新初始化数据。

小生境淘汰机制的SFLA能够防止种群过早的收敛，同时，使种群更容易跳出局部最优。但是，对于L、δ等参数的设定，还需要继续研究。

除了上述几类改进的SFLA外，还有差分扰动的SFLA[15]、模因内三角 SFLA[16]、PSO 改进的 SFLA[17]和免疫 SFLA[18]等。

2.2 SFLA的应用

2.2.1 函数优化 函数优化是SFLA最早的应用领域，也是测试算法性能的经典算例。Elbeltagi等[19]针对典型的连续函数优化问题对遗传算法、PSO、蚁群算法和SFLA进行了执行时间、收敛速度和优化结果性能的比较。为保持种群多样性，文献[8] 中利用电荷的吸引和排斥原理对混合SFLA的更新策略进行了改进，用于求解复杂函数优化问题，并取得了很大的改进。文献[20] 中提出了一种基于SFLA优化径向基函数（Radial Basis Functions，RBF）神经网络参数的新方法，将RBF神经网络参数组成一个多维向量作为SFLA中的青蛙个体进行优化，实验证明了该优化效果较遗传算法、PSO具有更好的逼近能力。文献[21] 中将模拟退火和免疫接种思想引入到具有高斯变异和混沌扰动的SFLA中，用来求解有约束函数，并通过优化有约束测试函数的实验表明该改进后的算法是十分有效的。

2.2.2 组合优化 组合优化问题就是要从组合问题的可行解集中求出最优解。求解旅行商问题、背包问题、时间问题都是典型的组合优化问题。Eusuff等[3]将改进的SFLA用于组合优化问题，通过实验验证得出与遗传算法相比，SFLA无论从收敛精度还是速度上都是解决组合优化问题的一种有效工具。文献[7] 中提出了一种改进的混合SFLA，巧妙地将调整序思想和变异操作分别引入到SFLA的局部搜索和全局文化交换中，并将该算法用于求解旅行商问题，实验结果验证了该算法在求解TSP问题上具有更好的结果。文献[22] 中首先建立了背包问题基于0／1规划的数学模型，然后针对离散搜索空间提出了SFLA的改进算法，用来解决了背包问题。文献[23] 中借鉴了PSO与差分进化算法（Differential Evolution，DE）的进化算子提出了一种改进的混合蛙跳算法（ESFLA），分析了该算法的时间复杂性，并基于有限Markov链证明了该算法的全局收敛性。

2.2.3 电力行业 文献[24] 中将SFLA算法应用到统一考虑所有时段的动态优化计算中，并将其成功应用到含风电场电力系统中。文献[25] 中侧重于解决连续性问题以及易陷入局部最优解的不足，通过对解向量进行离散化处理并采用阈值选择策略，改进出了适用于电网规划的一种SFLA。算例应用结果表明，与PSO相比，该算法能够在较小的计算规模和较短的计算时间内得到全局最优解。文献[26] 中通过引入自适应因子，提高了个体向局部最优和全局最优进化的能力，维持了种群的多样性，并将其应用于电力系统的经济调度问题中。

2.2.4 聚类问题 文献[9] 中针对K-均值聚类算法对初始聚类中心的选取敏感和聚类过程中聚类中心数目不能动态调整的缺点，利用SFLA作了相应改进，并将改进的SFLA用于K-均值聚类算法的优化，通过对某种型号空气压缩机车柴油机燃油系统状态技术参数样本进行仿真，证明了算法的优越性。文献[27] 中采用变个体长度的混合SFLA，同时优化模糊聚类数和聚类中心，求得产品构成部件的最优模糊划分。切断算子和拼接算子用于对个体进行重新组合形成新的个体，采用迭代算法进行局部寻优。仿真研究表明，所提方法为产品族模块化设计提供了定量数学分析和快速配置的理论依据。文献[28] 中通过混沌搜索初始种群，变异产生了新个体，更新了一种新的搜索策略，改进了SFLA，从而把它与K-均值聚类算法相结合，实验表明改进的算法提高了聚类精度。此外还有很多应用，本文不一一列举。但这些改进都在某些方面优化了基本混合SFLA，或避免了陷入局部最优，或防止了搜索空间早熟，或提高了收敛速度等。总之，不存在某一种优化算法在各个方面都比其他算法性能好[29]，由此可见，上述改进算法各有所长。

3 在函数优化中的应用

3.1 问题提出

为说明SFLA的算法机理，本文所研究的函数优化问题如下：

式中，f（x）为所要求的函数；x为f（x）的解；xs为x的第s维；Pmin、Pmax为x的最小、最大值。

本文利用图2的蛙跳算法流程求解式（9）的问题。

3.2 测试实验与结果分析

为了更好地验证基本SFLA的优越性，本文通过3个典型的测试函数进行仿真实验。

（1）Sphere函数

（2）Rosenbrock函数

（3）Griewank函数

利用MATLAB 2009在CPU主频3.2GHz、512MB内存、Window 8操作系统下利用SFLA分别对3个测试函数进行仿真测试。经过反复试验，本文取实验效果较好的参数设置如下：F＝600，n＝30，m＝20，smax＝5，Lmax＝25，Gmax＝200。然后进行了30次独立实验。表1给出了利用SFLA对3个函数分别进行函数优化仿真的测试结果。

表1 利用SFLA进行函数优化的仿真测试结果Tab.1 Simulation results of function optimization with SFLA

图3给出了利用SFLA对3个函数进行优化的平均迭代曲线。

由表1和图3可见，利用SFLA对3个函数进行优化后，在低维处找到全局最优解的次数很高，收敛精度也很高；而对于高维函数优化，找到最优解的次数就相对较少，有的甚至陷入局部最优，同时精度也不是太高。由此可见SFLA有很强的寻优能力，且参数较少，计算方便，非常适用于函数（简单函数或复杂函数）优化问题，特别是对低维函数的优化效果甚好，对高维函数的优化也取得了一定的效果，但存在了很多的不足，故对于高维函数的优化依旧存在很大的改进空间，这将会是今后的研究内容。

图3 利用SFLA进行函数优化的平均迭代曲线Fig.3 Average iterative curve of function optimization using SFLA

4 结 语

混合SFLA是一种新兴的后启发式仿生智能优化算法，具有很强的寻优能力，而且参数较少、流程简单、计算方便，且该算法将局部优化搜索和全局循环跳跃的平衡策略相结合，有较强的全局寻优能力，因此，非常适用于函数优化问题。

SFLA是群体仿生类算法，缺乏理论依据，故利用有效的数学工具提供依据、证明其科学性是今后研究方向。关于参数取值问题，目前依旧没有具体的规律可循，大部分参数均来源于实验测试，故参数的设置也是当前的研究方向。针对SFLA收敛速度慢、寻优精度低、早熟收敛等问题，对算法进行改进是目前另一个研究热点。

由于现实生活中需要解决各式各样的优化问题，如何设计出更为有效的群体组合智能优化算法，使之适应于求解离散的、连续的等各类型的优化问题将在未来工作中继续研究。同时，要扩展SFLA的应用，将其应用到更多的领域，如生物制药、应用化工、机械加工、并网技术、分布式发电等。

[1] 汪定伟，王俊伟，王洪峰，等.智能优化方法[M] .北京：高等教育出版社.2007：1-7.

[2] Rahimi-Vahed A，Mirzaei A H.Solving a bi-criteria permutation flow-shop problem using shuffled frogleaping algorithm[J] .Soft Computing，2008，12（5）：435-452.

[3] Eusuff M，Lansey K，Pasha F.Shuffled frog-leaping algorithm：A mimetic meta-heuristic for discrete optimization[J] .Engineering Optimization，2006，38（2）：129-154.

[4] 杨淑莹，张桦.群体智能与仿生计算：Matlab技术实现[M] .北京：电子工业出版社.2012：1-5.

[5] Eusuff M M，Lansey K E.Optimization of water distribution network design using the shuffled frog leaping algorithm[J] .Journal of Water Resources Planning Management，2003，129（3）：210-225.

[6] 蔡良伟，李霞.基于混合蛙跳算法的作业车间调度优化[J] .深圳大学学报：理工版，2010，27（4）：391-395.

[7] 罗雪晖，杨烨，李霞.改进混合蛙跳算法求解旅行商问题[J] .通信学报，2009，30（7）：130-135.

[8] 赵鹏军，刘三阳.求解复杂函数优化问题的混合蛙跳 算 法[J] .计 算 机 应 用 研 究，2009，26（7）：2435-2437.

[9] 毋建平.基于蛙跳思想的改进聚类模式识别算法[J] .计算机应用，2012，32（S2）：29-31.

[10] 邹采荣，张潇丹，赵力.混合蛙跳算法综述[J] .信息化研究，2012，38（5）：1-5.

[11] 张海玉，刘军，刘志都.基于混沌优化策略的SFLA算 法[J] .计 算 机 应 用 研 究，2013，30（6）：1708-1711.

[12] 马平莉.混合蛙跳算法的研究[D] .西安：西安电子科技大学，2013：23-26.

[13] 李英海，周建中，杨俊杰，等.一种基于阈值选择策略的改进混合蛙跳算法[J] .计算机工程与应用，2007，43（35）：19-21.

[14] 姜建国，李锦，龙秀萍，等.采用小生境技术的混合蛙跳算法[J] .计算力学学报，2012，29（6）：960-965.

[15] 赵鹏军.基于差分扰动的混合蛙跳算法[J] .计算机应用，2010，30（10）：2575-2577.

[16] 朱光宇.模因内三角概率选择混合蛙跳算法[J] .计算机集成制造系统，2009，15（10）：1979-1985.

[17] 栾垚琛，盛建伦.基于粒子算法的混沌蛙跳算法[J] .计算机与现代化，2009（11）：39-42.

[18] 王柏，李芳花.基于免疫蛙跳算法优化的投影寻踪水质评价模型[J] .中国农村水利水电，2010（5）：5-7.

[19] Elbeltagi E，Hegazy T，Grierson D.Comparison among five evolutionary-based optimization algorithms[J] .Advanced Engineering Informatics，2005，19（1）：43-53.

[20] 薛升翔，贾振红，杨杰，等.用蛙跳算法优化RBF神经网络参数的研究[J] .计算机工程与应用，2011，47（28）：59-61.

[21] 张潇丹，赵力，邹采荣.一种改进的混合蛙跳算法求解有约束优化问题[J] .山东大学学报：工学版2013，43（1）：1-8.

[22] 轩宗怡，张翠军.基于混合蛙跳算法的背包问题求解[J] .科学技术与工程，2009，9（15）：4363-4365.

[23] 贺毅朝，曲文龙，许翼伟.一种改进的混合蛙跳算法及其收敛性分析[J] .计算机工程与应用，2011，47（22）：37-40.

[24] 陈功贵，李智欢，陈金富，等.含风电场电力系统动态优化潮流的混合蛙跳算法[J] .电力系统自动化，2009，33（4）：25-30.

[25] 王茜，张粒子，舒隽，等.基于阈值选择策略的改进混合蛙跳算法在电网规划中的应用[J] .电力系统保护与控制，2011，39（3）：34-39.

[26] 代永强，王联国，施秋红，等.改进的混合蛙跳算法性能分析及其在电力系统经济调度中的应用[J] .电力系统保护与控制，2012，40（10）：77-83.

[27] 崔文华，刘晓冰，王伟，等.改进混合蛙跳算法优化的产品族模糊C均值聚类设计方法[J] .大连理工大学学报，2013，53（5）：760-765.

[28] 许方，张桂珠.一种改进的混合蛙跳算法和K均值结合的聚类算法[J] .计算机工程与应用，2013，49（1）：176-180.

[29] Holland J H.Adaptation in Natural and Artificial Systems：An introductory analysis with applications to Biology，control and artifical intelligence[M] .Ann Arbor：University of Miehigan Press，1975：20-23.