改进人工鱼群算法求解TSP问题

王岩

摘 要：针对TSP问题的特点，在经典最近邻点法基础上对其运行方式加以改进，结合基本人工鱼群算法的优势，对基本人工鱼群算法加以改进。利用改进最近邻点法为基本人工鱼群算法构造多个较优初始解，进而改进基本人工鱼群法的觅食行为。改进后的人工鱼群算法能更有效地搜索全局最优解。选取典型的TSP问题实例进行实验仿真，验证该算法的有效性。实验表明，改进后的人工鱼群算法在求解旅行商问题时，比基本人工鱼群算法搜索效果更好，寻优性能更强。

关键词：改进最近邻点法 人工鱼群算法 旅行商问题 NP难问题 寻优性能

中图分类号：FP393 文献标识码：A 文章编号：1672-3791（2014）11（c）-0001-02

旅行商问题（Traveling Salesman Problem，TSP）是一类经典组合优化问题。TSP问题描述：一个旅行商要拜访N个城市，从某个城市出发，最后返回该城市，路径限制为每个城市只能访问一次，路径选择的目标为使得到的路径为所有路径之中的最小值。

由于TSP问题属于NP难问题，精确算法已不符合实际要求，因此，求解这一类问题通常采用启发式算法。

1 基本人工鱼群算法

人工鱼群算法（Artificial Fish Swarm Algorithm，AFSA）[1]通过对鱼群的觅食、聚群和追尾等行为进行模拟，对个体鱼的相关行为进行构造，以期达到群体的全局最优。目前，针对不同问题，人们对基本人工鱼群算法给出了许多不同的改进方式[2-5]。

基本人工鱼群算法原理如下，人工鱼状态：，（）为欲寻优的变量；人工鱼所处位置的食物浓度：，为目标函数；个体鱼之间的距离：；人工鱼感知距离：Visual；人工鱼移动步长：Step；觅食最大试探次数：Try_number；拥挤度因子：。

（1）觅食行为。

表示人工鱼个体当前状态，在该个体人工鱼感知范围内随机选择状态，考虑极大值问题，若，则该人工鱼向方向移动，到达；反之，若，则在该个体人工鱼感知范围内重新选择状态，直到找到满足前进条件的新状态或达到最大试探次数Try_number，若达到最大试探次数后仍找不到符合前进条件的新状态，则在其感知范围内随机移动一步达到新状态。

即：

表示（0，1）之间的随机数。

（2）聚群行为。

表示人工鱼个体当前状态，表示在范围内搜索到的其它人工鱼个体数目，表示中心位置。若， 表明中心位置食物较多且拥挤度较小，则向人工鱼群中心位置前进；否则执行觅食行为。

即：

（3）追尾行为。

当鱼群中的一条或几条鱼发现食物时，与其邻近的鱼会尾随其快速到达食物地点。

表示人工鱼个体当前状态，表示在内进行搜索时最大的人工鱼个体状态，若，说明状态食物较多且拥挤度较小，则向方向前进；否则执行觅食行为。

即：

2 改进人工鱼群算法

2.1 改进最近邻点法

TSP问题要求最终回到出发的起始城市，形成封闭回路，而经典最近邻点法[6]是以单向行进方式运行的，强制形成回路，易使终点与起点距离偏大，从而导致最后的解路径值增大。

针对TSP问题这一特点，对经典最近邻点法进行改进。

城市节点：，城市节点距离矩阵：。

改进最近邻点法操作步骤：

对，开始循环。

Step1：设置，对距离矩阵D进行初始化；随机选取城市，并记为路径起点，搜索距离矩阵D，找到距其最近的城市，记为下一节点，设置，对距离矩阵D进行更新；继续寻找距最近的城市，记为节点，设置，对距离矩阵D进行更新，则得到初始路径；

Step2：判断是否成立，若成立，则停止；否则，继续搜索距已有路径右侧上一节点最近的下一节点，设置，对距离矩阵D进行更新；寻找距已有路径左侧上一节点最近的下一节点，设置，对距离矩阵D进行更新；更新路径有；

Step3：反复进行Step2；

Step4：连接得到的所有节点，则有最终路径；

Step5：循环终止，有路径集合（）。

2.2 改进人工鱼群算法

初始化人工鱼群算法的基本参数，利用改进最近邻点法为基本人工鱼群算法构造初始的解路径集合，在此基础上应用人工鱼群算法。

步骤如下：

Step1：初始化参数，设置人工鱼规模为n，最大迭代次数为Max_gen，最大试探次数为Try_number，感知距离为Visual，拥挤度因子为，利用改进最近邻点法生成初始鱼群；

Step2：计算初始鱼群的适应度值，记录最优鱼的状态信息；

Step3：对人工鱼个体进行觅食、聚群、追尾等行为的操作，产生的最优状态作为该个体下一状态，更新鱼群状态；

Step4：更新全局最优鱼状态；

Step5：判断是否达到设定的最大迭代次数，是则转为Step6，否则转为Step3，继续进行；

Step6：算法终止，输出结果。

3 实验验证

为验证改进人工鱼群算法的有效性，在TSPLIB[7]中选取算例gr17、fri26和swiss42，城市个数由少到多。已知算例的全局最优值分别为：2085、937、1273。程序在Matlab7.0中运行，算法初始参数设置为Max_gen=500，Try_number=100，Visual=8，=0.2。改进人工鱼群算法的寻优性能见表1。

gr17算例的解路径如下：

1—4—13—7—8—6—17—14—15—3—11—10—2—5—9—12—16。endprint

fri26算例的解路径如下：1—25—24—23—26—22—21—17—18—20—19—16—11—12—13—15—14—10—9—8—7—5—6—4—3—2。

swiss42算例的解路径如下：1—2—7—5—4—3—28—29—30—31—39—23—40—22—25—41—24—42—10—9—11—26—12—13—19—27—6—14—20—15—17—16—38—8—18—32—37—36—21—34—35—33。

与基本人工鱼群算法比较，改进人工鱼群算法分别在迭代4次、23次和65次时获得算例gr17、fri26和swiss42的最优解；而基本人工鱼群算法分别在迭代48次和222次时获得算例gr17、fri26的最优解，对于算例swiss42迭代了500次仍未获得最优解。由此可见，改进后算法的寻优速度大大增强。

4 结论

针对TSP问题改进的人工鱼群算法搜索能力更强，寻优速度更快，是一种有效的算法。

参考文献

[1] 李晓磊，邵之江，钱积新.一种基于动物自治体的寻优模式：鱼群算法[J].系统工程理论与实践，2002，22（11）：32-38.

[2] 柳毅.求解模糊需求可回程取货车辆路径问题的改进人工鱼群算法[J].模式识别与人工智能，2010，23（4）：560-564.

[3] 陈德为，张培铭.基于人工鱼群算法的智能交流接触器虚拟样机优化设计[J].电工技术学报，2011，26（2）：101-107.

[4] 郑根让.基于混合人工鱼群算法车辆拥堵调度方案[J].计算机仿真，2012，29（6） 328-331.

[5] 马宪民，刘妮.自适应视野的人工鱼群算法求解最短路径问题[J].通信学报，2014，35（1）：1-6.

[6] J. Rosenkrantz，R. E. Stearns， I. Philip，et al.An analysis of severalheuristics for the traveling salesman problem[J].SIAM Journal on Computing，1977，6（3）：563-581.

[7] G. Reinelt. TSPLIB—a traveling salesman problem library [J].ORSA Journal on Computing，1991，3（4）：376-384.endprint