改進(jìn)人工魚群算法求解TSP問題

王巖

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

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

中圖分類號：FP393 文獻(xiàn)標(biāo)識碼：A 文章編號：1672-3791（2014）11（c）-0001-02

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

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

1 基本人工魚群算法

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

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

（1）覓食行為。

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

即：

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

（2）聚群行為。

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

即：

（3）追尾行為。

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

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

即：

2 改進(jìn)人工魚群算法

2.1 改進(jìn)最近鄰點(diǎn)法

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

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

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

改進(jìn)最近鄰點(diǎn)法操作步驟：

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

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

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

Step3：反復(fù)進(jìn)行Step2；

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

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

2.2 改進(jìn)人工魚群算法

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

步驟如下：

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

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

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

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

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

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

3 實(shí)驗(yàn)驗(yàn)證

為驗(yàn)證改進(jìn)人工魚群算法的有效性，在TSPLIB[7]中選取算例gr17、fri26和swiss42，城市個(gè)數(shù)由少到多。已知算例的全局最優(yōu)值分別為：2085、937、1273。程序在Matlab7.0中運(yùn)行，算法初始參數(shù)設(shè)置為Max_gen=500，Try_number=100，Visual=8，=0.2。改進(jìn)人工魚群算法的尋優(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。

與基本人工魚群算法比較，改進(jìn)人工魚群算法分別在迭代4次、23次和65次時(shí)獲得算例gr17、fri26和swiss42的最優(yōu)解；而基本人工魚群算法分別在迭代48次和222次時(shí)獲得算例gr17、fri26的最優(yōu)解，對于算例swiss42迭代了500次仍未獲得最優(yōu)解。由此可見，改進(jìn)后算法的尋優(yōu)速度大大增強(qiáng)。

4 結(jié)論

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

參考文獻(xiàn)

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

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

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

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

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