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

龙源期刊网 https://www.wendangku.net/doc/f810326065.html,

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

作者：程春英李海峰包春花

来源：《电脑知识与技术》2014年第19期

摘要：人工鱼群算法在函数优化问题中取得了较好的应用，但在组合优化问题中的应用相对较少。因此，文中用人工鱼群算法来求解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年在对动物群体智能行为研究的基础上提出的一种新型仿生优化算法，该算法主要利用鱼群的三大基本行为分别为觅食、聚群和追尾行为，采用自上而下