蛙跳算法

出自 MBA智库百科(https://wiki.mbalib.com/)

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

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

　　蛙跳原理是由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)

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

　　其中， Ds 表示青蛙个体的调整矢量， Dmax表示青蛙个体允许改变的最大步长。如设Uw=[1 3 5 4 2]，UB=[2 1 5 3 4],允许改变的最大步长Dmax =3，若rand=0.5，则:

　　Uq=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]。