基本蛙跳算法（Frog leaping algorithm，FLA）

1.蛙跳算法原理

      蛙跳算法是基于种群进化的元启发式算法之一，通过模拟自然界中青蛙觅食过程中种群所体现出的交流与合作行为，以实现对问题的求解。在一片湿地中，分布着一群青蛙，每只青蛙有自己的想法，每只青蛙的想法则被定义为一个解。每只青蛙找到食物时，都会向其周围的青蛙传递信息，从而影响周围青蛙向其靠近，形成一个子种群(模因组)。可见，湿地中青蛙种群将形成多个这样的子种群。子种群内的青蛙相互影响，从而实现组内的局部搜索。当青蛙跳跃一定次数后，为了寻找更多的食物，所有青蛙将重新混合后再次形成子种群，寻找更多的食物。至此，完成种群的一次全局搜索。子种群局部搜索与整个种群全局搜索交替进行，从而实现对问题的求解。

2.蛙跳算法流程

基本蛙跳算法分为初始化、模因组划分、模因组进化、模因组合并 4 个操作。其中，

初始化阶段：用来确定算法可选参数以及初始化种群

随机生成的青蛙群体F，共有N只青蛙。将青蛙按个体适应度值的大小进行降序排列，

模因组划分阶段：将所有青蛙按照一定规则分为多个模因组

    设置模因组数为 m ,模因组内的青蛙个数为 n ,使其满足 N = m X n。将整个种群划分为m个模因组,第 1 只青蛙划入第 1 个模因组,第 2 只青蛙划入第 2 个模因组,第m mm只青蛙划入第m 个模因组,第 （m + 1）只青蛙划入第（m + 1）个模因组,依此类推,直至种群内所有青蛙分配完成。

模因组进化阶段：为实现模因组内青蛙个体的交流与进化（局部搜索）

     对于青蛙群体F，具有全局最好适应度的解表示为Pgbest；对于每一个子群，具有最好适应度的解表示为Pbest，最差适应度的解表示为Pworst。

找出每个模因组的 Pbest​, 依据以下公式 执行局部位置更新操作,更新每个模因组的Pworst。

​

式中，D表示青蛙个体的调整距离，rand()表示0和1之间的随机数，Dmax表示青蛙个体允许改变的最大步长。

    如果更新后得到的青蛙优于原来的青蛙,则替代原模因组内的青蛙Pworst, ,用 Pgbest代替Pbest,执行局部位置更新操作。
 

    如果以上操作仍然不能获得更好适应值的青蛙或移动过程中超过了青蛙所允许的最大移动距离,那么就随机生成一个新的青蛙直接替代原来的Pworst。重复以上局部位置更新操作，直到设定的子群内更新次数。

 模因组合并阶段：为实现整个青蛙种群的信息交换（全局搜索）

    当所有子群的局部搜索完成后 ,并将所有模因组内的青蛙重新混合排序和划分模因组,再执行下一轮的局部位置更新操作,直到满足预先设定的收敛条件或者达到最大迭代次数为止。

今天的文章基本蛙跳算法（Frog leaping algorithm，FLA）分享到此就结束了，感谢您的阅读。