王巖

摘 要：針對TSP問題的特點，在經(jīng)典最近鄰點法基礎(chǔ)上對其運行方式加以改進，結(jié)合基本人工魚群算法的優(yōu)勢，對基本人工魚群算法加以改進。利用改進最近鄰點法為基本人工魚群算法構(gòu)造多個較優(yōu)初始解，進而改進基本人工魚群法的覓食行為。改進后的人工魚群算法能更有效地搜索全局最優(yōu)解。選取典型的TSP問題實例進行實驗仿真，驗證該算法的有效性。實驗表明，改進后的人工魚群算法在求解旅行商問題時，比基本人工魚群算法搜索效果更好，尋優(yōu)性能更強。

關(guān)鍵詞：改進最近鄰點法 人工魚群算法 旅行商問題 NP難問題 尋優(yōu)性能

中圖分類號：FP393 文獻標識碼：A 文章編號：1672-3791（2014）11（c）-0001-02

旅行商問題（Traveling Salesman Problem，TSP）是一類經(jīng)典組合優(yōu)化問題。TSP問題描述：一個旅行商要拜訪N個城市，從某個城市出發(fā)，最后返回該城市，路徑限制為每個城市只能訪問一次，路徑選擇的目標為使得到的路徑為所有路徑之中的最小值。

由于TSP問題屬于NP難問題，精確算法已不符合實際要求，因此，求解這一類問題通常采用啟發(fā)式算法。

1 基本人工魚群算法

人工魚群算法（Artificial Fish Swarm Algorithm，AFSA）[1]通過對魚群的覓食、聚群和追尾等行為進行模擬，對個體魚的相關(guān)行為進行構(gòu)造，以期達到群體的全局最優(yōu)。目前，針對不同問題，人們對基本人工魚群算法給出了許多不同的改進方式[2-5]。

基本人工魚群算法原理如下，人工魚狀態(tài)：，（）為欲尋優(yōu)的變量；人工魚所處位置的食物濃度：，為目標函數(shù)；個體魚之間的距離：；人工魚感知距離：Visual；人工魚移動步長：Step；覓食最大試探次數(shù)：Try_number；擁擠度因子：。

（1）覓食行為。

表示人工魚個體當前狀態(tài)，在該個體人工魚感知范圍內(nèi)隨機選擇狀態(tài)，考慮極大值問題，若，則該人工魚向方向移動，到達；反之，若，則在該個體人工魚感知范圍內(nèi)重新選擇狀態(tài)，直到找到滿足前進條件的新狀態(tài)或達到最大試探次數(shù)Try_number，若達到最大試探次數(shù)后仍找不到符合前進條件的新狀態(tài)，則在其感知范圍內(nèi)隨機移動一步達到新狀態(tài)。

即：

表示（0，1）之間的隨機數(shù)。

（2）聚群行為。

表示人工魚個體當前狀態(tài)，表示在范圍內(nèi)搜索到的其它人工魚個體數(shù)目，表示中心位置。若， 表明中心位置食物較多且擁擠度較小，則向人工魚群中心位置前進；否則執(zhí)行覓食行為。

即：

（3）追尾行為。

當魚群中的一條或幾條魚發(fā)現(xiàn)食物時，與其鄰近的魚會尾隨其快速到達食物地點。

表示人工魚個體當前狀態(tài)，表示在內(nèi)進行搜索時最大的人工魚個體狀態(tài)，若，說明狀態(tài)食物較多且擁擠度較小，則向方向前進；否則執(zhí)行覓食行為。

即：

2 改進人工魚群算法

2.1 改進最近鄰點法

TSP問題要求最終回到出發(fā)的起始城市，形成封閉回路，而經(jīng)典最近鄰點法[6]是以單向行進方式運行的，強制形成回路，易使終點與起點距離偏大，從而導致最后的解路徑值增大。

針對TSP問題這一特點，對經(jīng)典最近鄰點法進行改進。

城市節(jié)點：，城市節(jié)點距離矩陣：。

改進最近鄰點法操作步驟：

對，開始循環(huán)。

Step1：設(shè)置，對距離矩陣D進行初始化；隨機選取城市，并記為路徑起點，搜索距離矩陣D，找到距其最近的城市，記為下一節(jié)點，設(shè)置，對距離矩陣D進行更新；繼續(xù)尋找距最近的城市，記為節(jié)點，設(shè)置，對距離矩陣D進行更新，則得到初始路徑；

Step2：判斷是否成立，若成立，則停止；否則，繼續(xù)搜索距已有路徑右側(cè)上一節(jié)點最近的下一節(jié)點，設(shè)置，對距離矩陣D進行更新；尋找距已有路徑左側(cè)上一節(jié)點最近的下一節(jié)點，設(shè)置，對距離矩陣D進行更新；更新路徑有；

Step3：反復進行Step2；

Step4：連接得到的所有節(jié)點，則有最終路徑；

Step5：循環(huán)終止，有路徑集合（）。

2.2 改進人工魚群算法

初始化人工魚群算法的基本參數(shù)，利用改進最近鄰點法為基本人工魚群算法構(gòu)造初始的解路徑集合，在此基礎(chǔ)上應(yīng)用人工魚群算法。

步驟如下：

Step1：初始化參數(shù)，設(shè)置人工魚規(guī)模為n，最大迭代次數(shù)為Max_gen，最大試探次數(shù)為Try_number，感知距離為Visual，擁擠度因子為，利用改進最近鄰點法生成初始魚群；

Step2：計算初始魚群的適應(yīng)度值，記錄最優(yōu)魚的狀態(tài)信息；

Step3：對人工魚個體進行覓食、聚群、追尾等行為的操作，產(chǎn)生的最優(yōu)狀態(tài)作為該個體下一狀態(tài)，更新魚群狀態(tài)；

Step4：更新全局最優(yōu)魚狀態(tài)；

Step5：判斷是否達到設(shè)定的最大迭代次數(shù)，是則轉(zhuǎn)為Step6，否則轉(zhuǎn)為Step3，繼續(xù)進行；

Step6：算法終止，輸出結(jié)果。

3 實驗驗證

為驗證改進人工魚群算法的有效性，在TSPLIB[7]中選取算例gr17、fri26和swiss42，城市個數(shù)由少到多。已知算例的全局最優(yōu)值分別為：2085、937、1273。程序在Matlab7.0中運行，算法初始參數(shù)設(shè)置為Max_gen=500，Try_number=100，Visual=8，=0.2。改進人工魚群算法的尋優(yōu)性能見表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的最優(yōu)解；而基本人工魚群算法分別在迭代48次和222次時獲得算例gr17、fri26的最優(yōu)解，對于算例swiss42迭代了500次仍未獲得最優(yōu)解。由此可見，改進后算法的尋優(yōu)速度大大增強。

4 結(jié)論

針對TSP問題改進的人工魚群算法搜索能力更強，尋優(yōu)速度更快，是一種有效的算法。

參考文獻

[1] 李曉磊，邵之江，錢積新.一種基于動物自治體的尋優(yōu)模式：魚群算法[J].系統(tǒng)工程理論與實踐，2002，22（11）：32-38.

[2] 柳毅.求解模糊需求可回程取貨車輛路徑問題的改進人工魚群算法[J].模式識別與人工智能，2010，23（4）：560-564.

[3] 陳德為，張培銘.基于人工魚群算法的智能交流接觸器虛擬樣機優(yōu)化設(shè)計[J].電工技術(shù)學報，2011，26（2）：101-107.

[4] 鄭根讓.基于混合人工魚群算法車輛擁堵調(diào)度方案[J].計算機仿真，2012，29（6） 328-331.

[5] 馬憲民，劉妮.自適應(yīng)視野的人工魚群算法求解最短路徑問題[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