改進人工魚群算法求解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