求解TSP问题的人工鱼群算法

摘要：人工鱼群算法在函数优化问题中取得了较好的应用，但在组合优化问题中的应用相对较少。因此，文中用人工鱼群算法来求解tsp问题，并与标准粒子群算法和基本遗传算法进行了比较分析。通过仿真实验对公认的TSP测试数据中算例Oliver30进行测试并与目前已知最优解进行了对比，结果表明，人工鱼群算法解决TSP问题时可以收敛到已知最优解，并且解的质量要优于标准粒子群算法和基本遗传算法。

关键词：旅行商问题；人工鱼群算法；聚群行为；觅食行为；追尾行为

中图分类号：TP18 文献标识码：A 文章编号：1009-3044（2014）19-4527-03

Artificial Fish Swarm Algorithm for solving TSP

CHENG Chun-ying1， LI Hai-feng2， BAO Chun-hua1

（1.College of Computer Science and Technology， Inner Mongolia University for Nationalities， Tongliao 028043， China；2. Inner Mongolia Coal Industry Technical school， Tongliao 028021， China）

Abstract： Artificial fish swarm algorithm is well applied in function optimization problems， but it is relatively less used in combinatorial optimization problem。In this paper， using artificial fish swarm algorithm to solve TSP problem， and with the standard particle swarm optimization algorithm and analyzed the basic genetic algorithm.This paper compares the experimental simulation of recognized Oliver 30 TSP test data of an example test and the known optimal solution， and the quality of the solution is better than the standard particle swarm algorithm and the basic genetic algorithm.

Key words： traveling salesman problem； artificial fish swarm algorithm； the swarming behavior； the preying behavior； the following behavior

TSP（Traveling Salesman Problem）问题，即旅行商问题，是经典的组合优化问题。 在许多工程应用问题中，如物流配送、网络布线和电路板钻孔等，都可以归结为TSP求解问题。目前，对于解决TSP问题人们提出了很多有价值的方法，如模拟退火算法[1]、遗传算法[2]、蚁群算法[3]和粒子群算法[4]等智能算法。而人工鱼群算法（Artificial Fish Swarm Algorithm， AFSA）[5-6]是李晓磊等人于2002年在对动物群体智能行为研究的基础上提出的一种新型仿生优化算法，该算法主要利用鱼群的三大基本行为分别为觅食、聚群和追尾行为，采用自上而下的寻优模式从构造个体的底层行为开始，通过鱼群中个体的局部寻优，达到全局最优值在群体中突现出来的目的。

人工鱼群算法主要应用还集中在解决函数优化问题，在组合优化问题中的应用较少，尤其是TSP问题中的应用少之又少。为此本文利用人工鱼群算法来解决TSP问题，并与标准粒子群算法和基本遗传算法进行了比较分析。

1 旅行商问题

TSP问题，即旅行商问题，是经典的组合优化问题之一。旅行商问题的基本描述是：假设有一个旅行商人要访问[n]个城市，他必须选择要走的路径，选择路径的限制条件是每个城市只能访问一次，而且最后要回到原来出发的城市。路径的选择目标是要求求出的路径为所有路径之中的最短路径。简单说，旅行商问题就是需要寻找这样的一条旅行线路：从某个城市开始，经过每个城市一次且仅一次，最终回到出发城市，使得旅游的路经总长度为最短。

TSP问题的数学模型[7]可描述为：

[minf（X）]

[s.t.g（X）≥0，X∈D] （1）

公式（1） 中，[f（X）]为目标函数，[g（X）]为约束函数，[X]为决策变量，[D]表示有限个点组成的集合。通常，一个组合优化问题可用三个参数[（D，F，f）]来表示，其中[D]表示决策变量的定义域，[F={XX∈D，g（X）≥0}]，[f]表示目标函数，满足的可行解[X′]称为问题的最优解。

2 人工鱼群算法

人工鱼个体的状态可表示为向量[X=（x1，x2，...，xn）]其中[xi（i=1，2，...，n）]为要寻优的变量，人工鱼当前所在位置的食物浓度可表示为[Y=f（X）]，其中[X]为目标函数值，人工鱼个体之间的距离可表示为[dij]，[visual] 表示人工鱼的感知范围，[step]表示人工鱼移动的步长，[δ]表示拥挤度因子。

2.1 觅食行为

设人工鱼当前状态[Xi]，在其感知范围内（即[dij

2.2聚群行为

设人工鱼当前状态为[Xi]， 探索当前感知范围内（即[dij

2.3 追尾行为

人工鱼当前状态为[Xi]，探索感知范围内（即[dij

2.4 随机行为

随机行为的实现较简单，就是在视野中随机选择一个状态，然后向该方向移动，其实它是觅食行为的一个缺省行为。

2.5公告板

公告板记录当前最优人工鱼个体的状态。各人工鱼个体每次行动完毕后与公告板上的人工鱼个体状态比较，如果自身优于公告板上人工鱼个体状态，就用自身状态更新公告板上人工鱼群个体状态。

3 求解TSP问题的人工鱼群算法

人工鱼群算法具有把握搜索方向和在一定程度上避免陷入局部最优解的特性，但当一部分人工鱼处于随机移动时，收敛速度就会减慢。为了克服此缺点，在算法中设立公告板以此记录最优人工鱼个体状态。每条人工鱼在行动一次以后将自身当前状态的值与公告板的当前状态进行比较，如果优于公告板，则用自身状态取代公告板状态。

3.1求解TSP问题的人工鱼群算法步骤

求解TSP问题的人工鱼群算法实现的具体步骤如下：

步骤1 产生初始化种群：定义最大迭代次数num，拥挤度因子[δ]，视野范围visual，试探次数trynumber并在可行域内随机生成N条人工鱼，形成初始鱼群。

步骤2 计算初始鱼群各人工鱼当前状态的值，比较大小，最小值进入公告板，并且把对应的人工鱼状态赋值给公告板。

步骤3 按照人工鱼群算法的行为准则，进行追尾行为和聚群行为，缺省行为为觅食行为。如果进行了追尾行为和聚群行后，最好值还是没有变化就进行随机行为。

步骤4 各人工鱼进行行为选择后，检查自身的值与公告板的值，如果优于公告板，则以自身取代，同时更新公告板上的人工鱼状态。

步骤5 判断是否满足终止条件，若不满足终止条件则转到步骤3执行，进行下一步鱼群优化过程，否则转到步骤6执行。

步骤6 算法终止，输出公告板上的最优解人工鱼群状态值。

3.2算例及仿真研究

算法的参数取为最大试探次数为100，人工鱼个数为10，最大迭代次数取100，拥挤度因子0.8，感知范围为10，采用Matlab7.0为编程工具，实验环境为Intel（R）Core（TM）i3，2.13GHz CPU，2GB内存，Windows 7操作系统。为了便于比较，该文将人工鱼群算法与标准粒子群算法和基本遗传算法分别连续进行30次实验，对其结果进行比较分析。该文使用TSP问题中的标准测试算例TSPLIB[8]库中的Oliver30（30个城市），Oliver30算例的目前已知最优解为423.7406。通过仿真实验对其结果进行比较分析，仿真结果如表1所示。

标准粒子群算法中粒子数为100，惯性权重[w]从1.4线性递减到0.5，加速常数[c1=c2=1.2]，最大迭代次数为1000。遗传算法中，最大代数为1000，种群为100，交叉概率为0.8，变异概率为0.05，实验结果如表1所示，人工鱼群算法的得到最优路径如图1所示，寻优曲线如图2所示。算例Oliver30如下：

City[30]={ {41，94}，{37，84}，{54，67}，{25，62}，{7， 64}，{2， 99}，{68，58}， {71，44}，{54， 62}，

{83，69}，{64，60}，{18，54}，{22，60}，{83，46}，{91，38}，{25，38}，{24，42}，{58，69}，{71，71}，{74，78}，

{87，76}，{18，40}，{13， 40}，{82，7}，{62，32}，{58，35}，{45，21}，{41， 26}，{44，35}，{4，50}}

表1 几种智能算法试验结果比较

[算法 平均值 最好值 最差值＼&人工鱼群算法 424.1245 423.7406 425.6024

标准粒子群算法 450.2314 425.5416 480.1452

基本遗传算法 430.5285 427.6918 437.4521＼&]

由表1中的实验结果可知，人工鱼群算法得到的最优解为423.7406，与当前已知的Oliver30问题的最优解一致。标准粒子群算法的最优解为425.5416，遗传算法的最优解为424.6918，都没有收敛到当前最优解。根据图1可知，人工鱼群算法求得的最优路径也于已知的最好解对应的路径是一致的。

图1 Oliver30问题最优路径 图2 Oliver30问题寻优曲线

4 结论

本文将人工鱼群算法应用于解决TSP问题，并将该算法与标准粒子群算法和基本遗传算法进行了比较分析。根据仿真实验结果可知，在解决算例Oliver30问题时，该文中的人工鱼群算法能够获得已知的最优解，且解的平均值要优于标准粒子群算法和基本遗传算法。

参考文献：

[1] 邓士杰，支建庄，于贵波.栾军英基于模拟退火算法的TSP问题研究[J].价值工程，2012（28） ：65-68.

[2] 谢胜利，唐敏.求解TSP问题的一种改进的遗传算法[J].计算机工程与应用，2002，38（8） ：58-60.

[3] 翁国栋.蚁群优化算法与遗传算法在TSP问题上的融合[J].福建电脑，2006（2）：115-116.

[4] 庄严.粒子群优化算法在TSP问题中的应用[J].科技信息，2008（30）：184-185.

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

[6] 李晓磊.组合优化问题的人工鱼群算法应用[J].山东大学学报：工学版，2004，34（5）：64-67.

[7] 邢文训，谢金星.现代优化技术方法[M].北京：清华大学出版社，1999.

[8] http：//www.iwr.uni-heidelberg.de/iwr/comopt/soft-ware/TSPLIB95.