蛙跳算法完整

蛙跳算法（SFLA）制作人：吴兵海蛙跳算法简介蛙跳算法（ShuffledFrogLeadingAlgorithm）是一种启发式算法，通过启发式函数进行启发式搜索，从而找到组合最优问题的解。他结合了以遗传为基础的memetic算法和以社会行为为基础的粒子群优化算法的优点。蛙跳算法的原理在SFLA中，种群被分为若干个子群（memeplex），每一个子群包括一定数量的青蛙。不同的memeplex具有不同的文化，分别进行局部搜索。在每个子群中，每只青蛙都有自己的想法，并且受到其他青蛙想法的影响，通过memetic进化来发展。这样经过一定的memetic进化以及跳跃过程，这些想法思路就在各个memeplex中传播开来，然后，据需局部搜索和跳跃，知道收敛或满足标准为止。标准蛙跳算法步骤全局搜索

Step0：初始化。选择m和n，m表示子群的数量，n表示每个子群中的青蛙的数量。种群规模F=m*nStep1：生成一个初始种群。在可行解空间生成F个青蛙U(1),U(2),…..,U(F)，每个青蛙当前的位置对应于优化问题解空间的一个候选解：

，其中d表示解的维度。

计算出U(i)的性能f(i).标准蛙跳算法步骤全局搜索Step2:对青蛙划分等级。将F只青蛙按照性能的好坏依次排列，生成数组：

这样，i=1表示这只青蛙的位置最好，记录种群中最好青蛙位置px=U(1)Step3:将青蛙分组，放入不同的memeplex。将数组X分成为m个memeplex：Y1，Y2,…Ym。每个memeplex中包含n个青蛙。规则如下：比如m=3，那么第1只青蛙进入memeplex1，第2只青蛙进入memeplex2，第三只青蛙进入memeplex3，第4只青蛙进入memeplex1，….以此类推。标准蛙跳算法步骤全局搜索Step4：将每组memeplex执行memetic进化。在每组memeplex中，每只青蛙收到其他青蛙想法的影响，通过memetic进化，是的每只青蛙朝目标位置逼近。

接下来是每个memeplex中memetic进化的详细步骤：标准蛙跳算法步骤局部搜索Step4-0：设定最大进化次数N，iN=0为进化次数变量，子群个数m，im=0为子群计数变量。在每个memeplex中Pb和Pw分别表示性能最好和最坏的青蛙，Pg表示整个种群中最好的青蛙。在每一轮的进化中，改善最坏青蛙Pw的位置。注意，并非对所有青蛙都优化。Step4-1：im=im+1；Step4-2：iN=iN+1；Step4-3：调整最坏青蛙的位置，方法如下：青蛙移动的距离Di=rand()*(Pb-Pw)新的位置Pw=Pw（当前位置）+Di,（Dmax>=Di>=-Dmax）其中rand()是0-1之间的随机数，Dmax是青蛙移动的最大距离。标准蛙跳算法步骤局部搜索Step4-4：如果上述过程能够使得青蛙有一个更好的位置，即能产生一个更好的解，那么就用新的位置青蛙取代原来的青蛙；否则，用Pg代替Pb，重复上述过程。Step4-5：如果上述方法仍不能生成更好的青蛙，那么就随机生成一个新解取代原来最坏的青蛙Pw。Step4-6：如果iN<N,那么执行4-2.Step4-7：如果im<m，那么执行4-1，否则青蛙跳跃，重新执行全局搜索。标准蛙跳算法步骤全局搜索Step5：青蛙在memeplex之间跳跃。在每个memeplex中执行了一定的memetic进化之后，将各个子群Y1，Y2，….Ym合并到X，将X重新降序排列，并更新种群中最好的青蛙Pg。Step6：检查终止条件。如果迭代终止条件满足，则停止；否则，重新执行Step3.一般情况下，当执行了一定次数的循环进化，代表最好解的青蛙的位置不再改变的时候，算法停