定义

特点

原理

数学模型

过程

定义

蛙跳算法（SFLA）是一种全新的后启发式群体进化算法，具有高效的计算性能和优良的全局搜索能力。对混合蛙跳算法的基本原理进行了阐述，针对算法局部更新策略引起的更新操作前后个体空间位置变化较大，降低收敛速度这一问题，提出了一种基于阈值选择策略的改进蛙跳算法。通过不满足阈值条件的个体分量不予更新的策略，减小了个体空间差异，从而改善了算法的性能。数值实验证明了该改进算法的有效性，并对改进算法的阈值参数进行了率定

特点

SFLA由Eusuff和Lansey为解决组合优化问题于2003年最先提出。作为一种新型的仿生物学智能优化算法，SFLA 结合了基于模因（meme）进化的模因演算法（MA，memeticalgorithm）和基于群体行为的粒子群算法（PSO,particle swarm optimization）2 种群智能优化算法的优点。该算法具有概念简单，调整的参数少，计算速度快，全局搜索寻优能力强，易于实现的特点。混合蛙跳算法主要应用于解决多目标优化问题，例如水资源分配、桥墩维修、车间作业流程安排等工程实际应用问题。

原理

蛙跳算法的思想是：在一片湿地中生活着一群青蛙。湿地内离散的分布着许多石头，青蛙通过寻找不同的石头进行跳跃去找到食物较多的地方。每只青蛙个体之间通过文化的交流实现信息的交换。每只青蛙都具有自己的文化。每只青蛙的文化被定义为问题的一个解。湿地的整个青蛙群体被分为不同的子群体，每个子群体有着自己的文化，执行局部搜索策略。在子群体中的每个个体有着自己的文化，并且影响着其他个体，也受其他个体的影响，并随着子群体的进化而进化。当子群体进化到一定阶段以后，各个子群体之间再进行思想的交流（全局信息交换）实现子群体间的混合运算，一直到所设置的条件满足为止。

数学模型

算法参数

与其他优化算法一样，SFLA亦具有一些必要的计算参数，包括F：蛙群的数量；m：族群的数量；n：族群中青蛙的数量；Smax：最大允许跳动步长；Px：全局最好解；Pb：局部最好解；Pw：局部最差解；q：子族群中蛙的数量；LS：局部元进化次数以及SF：全局思想交流次数等。

更新策略

对于青蛙群体，具有全局最好适应度的解表示为U g；对于每一个子族群，具有最好适应度的解表示为UB，最差适应度的解表示为UW。首先对每个子族群进行局部搜索，即对子族群中最差适应度的青蛙个体进行更新操作，更新策略为

青蛙更新距离 Ds=rand()*(Pb-Pw) （1）

更新后的青蛙 newDw=oldPw+Ds（-Dmax≦Ds≦Dmax） （2）

其中， Ds 表示青蛙个体的调整矢量， Dmax表示青蛙个体允许改变的最大步长。如设Uw=[1 3 5 4 2],UB=[2 1 5 3 4],允许改变的最大步长Dmax =3，若rand=0.5 ，则U q(1) =1+min{int[0.5 × (2−1)],3}=1;U q(2) =3+max{int[0.5×(1−3)], −3}=2;依此相同的操作完成更新策略后可得到一个新解U q=[1 2 5 4 3].

过程

全局搜索过程

步骤l 初始化。确定蛙群的数量、种群以及每个种群的青蛙数。

步骤2 随机产生初始蛙群，计算各个蛙的适应值。

步骤3 按适应值大小进行降序排序并记录最好解Px，并且将蛙群分成族群。把F个蛙分配到m个族群Y，Y，Y…,Y中去，每个族群包含n个蛙，从而使得Yk=[X(j),f(j)|X(j)=X(k+m*(j-1), f(j)=f(k+m*(j-1),j=1,…,n,k=1,…,m].这里X（j）表示蛙群中的第j蛙，f(j)表示第j个蛙的目标函数值。

步骤4根据SFLA算法公式，在每个族群中进行元进化。

步骤5将各个族群进行混合。在每个族群都进行过一轮元进化之后，将各个族群中的蛙重新进行排序和族群划分并记录全局最好解Px。

步骤6检验计算停止条件。如果满足了算法收敛条件，则停止算法执行过程，否则转到步骤3。通常而言，如果算法在连续几个全局思想交流以后，最好解没有得到明显改进则停止算法。某些情况下，最大函数评价次数也可以作为算法的停止准则。

局部搜索过程

局部搜索过程是对上述步骤4的进一步展开，具体过程

如下：

步骤4—1设im=O，这里im是族群的计数器。用来与族群总数m进行比较。设iN=0，这里iN是局部进化的计数器，用来与Ls进行比较。

步骤4-2根据式(1)在第l，，1个族群中选择q个蛙进入子族群，确定Pb和Pw并设im=im+1。

步骤4-3设iN=iN+1。

步骤4—4根据式(2)和式(3)改进子族群中的最差蛙的位置。

步骤4—5如果步骤4—4改进了最差蛙的位置(解)，就用新产生的位置取代最差蛙的位置。否则就采用Px代替式(2)中的PB，重新更新最差蛙的位置。

步骤4—6如果步骤4-5没有改进最差蛙的位置，则随机产生一个处于湿地中任何位置的蛙来替代最差的蛙。

步骤4—7如果iN<LS，则转到步骤4-3。

步骤4—8如果im<m，则转到步骤4-2，否则转到全局搜索过程的步骤5。

算法停止条件

SFLA通常采用两种策略来控制算法的执行时间：

1)在最近的K次全局思想交流过程之后，全局最好解没有得到明显的改进；

2)算法预先定义的函数评价次数已经达到。

3)已有标准测试结果。

无论哪个停止条件得到满足，算法都要被强制退出整个循环搜索过程。