求解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問題，并與標準粒子群算法和基本遺傳算法進行了比較分析。……