混合蛙跳算法改进及其对旅行商问题的求解

摘要：针对混合蛙跳算法在进化过程中容易陷入局部最优的问题，使用群体适应度值判断算法在进化过程中是否陷入局部最优，如果陷入局部最优，则对整个种群的当前最优解Gb进行贪婪倒位变异，如果变异后的Gb（新）要优于Gb（旧），则使用Gb （新）；否则，使用模拟退火算法判断是否接受Gb （旧）。通过实验，将改进前后的混合蛙跳算法用于对旅行商问题的求解，并通过对比，验证了改进后的算法较未改进的算法更有效。

关键词：混合蛙跳算法；旅行商问题；组合优化问题

DOIDOI：10.11907/rjdk.161741

中图分类号：TP312

文献标识码：A文章编号：16727800（2016）010004102

0引言

混合蛙跳算法（Shuffled Frog Leaping Algorithm，SFLA）由Eusuff和Lansey在2003年第一次提出，是一种全新的启发式群体智能进化算法，最初用于解决管道网络扩充中管道尺寸的最小化问题[1]。随后，混合蛙跳算法以自身参数设置少、全局搜索寻优能力强、计算强度小、简单易于实现等优势被国内外学者所关注。目前主要用于解决组合优化问题，如水资源分布安排[2]、电力系统的调度[3]、云计算环境下资源分配问题[4]等。

组合优化问题是从组合问题的可行解中求出最优解。旅行商问题属于一种典型的组合优化问题，是NP难题。旅行商问题的具体描述是：以一个城市为出发点，在N个城市各经历一次，最后回到出发点，使得所经过的路程达到最短。如果不考虑方向性和周期性，则总共存在的闭合路径数目是（N-1）！2。当N选取的数目很大时，计算量将特别大，在求解最优路径时很困难，因为该问题算法在运行过程中，需要很长的运行时间和很大的存储空间，以至于根本不可能在计算机中得到实现，产生了所谓的“组合爆炸”问题。如果采用传统算法（如穷举搜索算法、贪心算法和动态规划算法等），就会遇到上述问题。现代智能算法的出现解决了上述问题，如遗传算法、蚁群算法、粒子群算法等。鉴于此，本文将采用混合蛙跳算法对旅行商问题进行求解。

本文对旅行商问题使用混合蛙跳算法进行求解并针对混合蛙跳算法存在容易陷入局部最优的问题，使用了贪婪倒位变异对当前的全局最优解进行变异，从而使得混合蛙跳算法跳出局部最优，从而向最优解逼近。使用改进前后的混合蛙跳算法分别对旅行商问题进行仿真实验，验证了改进后算法的有效性。

1混合蛙跳算法

混合蛙跳算法是模拟青蛙觅食过程中群体信息共享和交流机制而产生的一种群智能算法。算法中每只青蛙被定义为问题的一个解。对所有青蛙进行模因分组，分为不同的子群体，青蛙在分组内共享自身的觅食经验和信息，当分组内信息交换到一定阶段后，再将所有分组混合进行分组间的信息交换。不断重复上述过程，一直向着食物源的位置逼近。混合蛙跳算法按照分组分类进行信息的传递，将这种局部进化和重新混合的过程相间进行，有效地将全局信息交互和局部进化搜索进行相互结合，具有高效的计算性能和优良的全局搜索性能。

混合蛙跳算法的具体描述[5]：

随机生成F只青蛙，当问题维度为d时，第i只青蛙表示为X（i）=（X1i，X2i，...，Xdi），其评价函数为f（X（i））。按照评价函数的降序对青蛙进行排序，将青蛙分成m个组（子种群），每个组有n只青蛙，则F=m*n。将分组后的第一只青蛙放到第一组，第二只青蛙放到第二组，以此类推，直到放到第m组，如果有剩余青蛙，将第m+1只青蛙放到第m+1组，直到所有青蛙都放到分组中。

整个种群的最优解记作Gb，子种群中的最优解和最差解分别记作Pb、Pw。在子种群中的寻优过程是以对Pb和Gb作为参考，对Pw的位置进行更新，更新公式如下：

其中，rand（）为0～1的随机数，Dmax为允许青蛙移动的最大步长。如果更新后Pw（新）要好于Pw（旧），则用Pw（新）代替Pw（旧）。否则，用Gb代替式（1）中的Pb，重新执行对Pw的更新。如果还得不到更好的解，则随机生成一个个体来替代Pw。多次执行上述更新过程，直到更新结果满足约定条件（迭代次数）。当所有子种群更新完成后，再对所有青蛙进行全局混合、排序，继续进行子种群中的更新。反复执行上述过程，直到达到最大迭代次数或者找到最优解。

2混合蛙跳算法改进

根据文中混合蛙跳算法所描述，在子种群的更新过程中，使用Pb和Gb作为Pw更新的参考。但是在子种群的更新过程中，Pb和Gb的状态是不会改变的，使得每次的更新范围不会超过Pb和Gb，这样算法就容易陷入局部最优。为了能跳出局部最优，可以在Pw得不到更好解的情况下对Pb和Gb进行变异，增加Pw取得更好解的可能性，并能够加速向全局最优解收敛。本文将贪婪倒位变异和模拟退火算法相结合对Gb进行变异。

2.1更新陷入停滞的判断

由于算法的整个过程是在不断的迭代循环中进行，因而需要判断对Gb进行变异的位置节点，本文使用文献[6]中的群体适应度方差δ2，定义为：

其中，N为种群中青蛙个体的总量，fi是第i只青蛙适应度的大小，favg是所有青蛙适应度的平均值，f是用于限制δ2大小的归一化因子。如果δ2=0说明陷入局部最优，此时需要对Gb进行变异。

2.2贪婪倒位变异

以个体X={5，8，2，1，3，7，4，6，9}为例，变异方式按照如下步骤执行：

步骤1：随机在X中选择一个坐标点1，选择1左右2和3中距离1远些的坐标2。

步骤2：除去这3个点，从其它点中选出距离1最近的点4。

步骤3：对2和6之间的左边坐标点进行倒位，得到变异之后的X={9，6，4，1，3，7，2，8，5}。

2.2种群最优解接受准则

文中使用模拟退火算法[7]中的接收准则来判断是否接受通过贪婪倒位变异得到Gb （新）。如果变异后得到的Gb （新）要好于Gb （旧），则接受Gb （新）。否则按照概率s接受Gb （新），其中T是温度。

2.3改进混合蛙跳算法求解旅行商问题

（1）初始解的生成。

在旅行商问题中每一只青蛙代表问题的一条可能的访问路径。假设第i只青蛙表示为X（i）=（x1，x2，...，xn），其中x1，x2，...，xn表示需要访问的城市的序列。因此，在生成初始解时，随机生成F只青蛙，用于后续操作。

（2）局部最差解Pw的更新。

根据式（1）和式（2），在混合蛙跳算法中对Pw的更新是基于实数的，显然这种方式不能解决旅行商问题，这里使用的是另一种方式对Pw进行更新。例如：局部最优解Pb=（2，3，5，1，4），Pw=（1，3，4，2，5）。则Pw向Pb靠近的过程中要经过两次变换，变换次数记为c=2，第一次由（1，3，4，2，5）变为（2，3，4，1，5），记为S0=（1，2），表示Pw中的1号城市变为2号城市，因为不能有相同的城市出现，相应地Pw后面的2号城市变为1号城市。第二次变换由（2，3，4，1，5）变为（2，3，5，1，4），记为S1=（4，5），变换方式同上。同时，对于式（1）中的随机值rand（）的取值，使用r=rand（）*c。假设rand（）=0.6，此时的变换次数c=2，则r=1.2，对r进行向下取整得r=1，则在对Pw更新时，只使用S0=（1，2）的更新方式。如果得到的r=2，则同时使用S0=（1，2）和S1=（4，5）对Pw进行更新。

其它的求解过程根据混合蛙跳算法，每次执行全局混合、排序后，根据式（3）判断δ2的值，如果δ2=0，则使用贪婪倒位变异对排序后Gb进行变异，并根据2.2中所述的方法对Gb进行更新。

3实验结果

本文使用TSPLIB中的burma14、bayg29、gr96和ch130作为测试数据，比较混合蛙跳算法改进前后的运行结果，对每组数据分别测试50次，利用平均值进行比较。相应的参数设置如下：蛙跳算法的种群数为200，子种群数为20，子种群的内循环为10次，全局最大进化迭代次数为300。模拟退火算法中的初始温度T0=100 000，终止温度Tf=10，退火系数为0.95。在同样实验条件下对TSP问题进行50次测试并且取平均值进行比较，实验结果如表1所示。

也在快速增加。当坐标点过大时，例如文中在测试gr96和ch130时，改进前后都在300次的全局最大迭代次数附近得到最优解，说明如果增加全局迭代次数，测试结果会更好。

4结语

本文针对混合蛙跳算法的种群最优解，使用贪婪倒位变异和模拟退火算法对其进行变异和概率接受。实验表明，改进后的算法比未改进的算法更加有效，并且该算法还有改进空间。

参考文献参考文献：

[1]EUSUFF M M，LANSEY K E.Optimization of water distribution network design using the shuffled frog leaping algorithm[J].American Society of Civil Engineers，2003，129（3）：210225.

[2]EUSUFF M M，LANSEY K E.Optimization of water distribution network design using the shuffled frog leaping algorithm[J].American Society of Civil Engineers，2003，129（3）：210225.

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

[4]骆剑平，李霞，陈泯融.云计算环境中基于混合蛙跳算法的资源调度[J].计算机工程与应用，2012，48（29）：6772.

[5]杨淑莹.群体智能与仿生计算[M].北京：电子工业出版社，2012.

[6]吕振肃，侯志荣.自适应变异的粒子群优化算法[J].电子学报，2004，32（3）：416420.

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