求解TSP問題的人工魚群算法

程春英　李海峰　包春花

摘要：人工魚群算法在函數(shù)優(yōu)化問題中取得了較好的應(yīng)用，但在組合優(yōu)化問題中的應(yīng)用相對(duì)較少。因此，文中用人工魚群算法來求解TSP問題，并與標(biāo)準(zhǔn)粒子群算法和基本遺傳算法進(jìn)行了比較分析。通過仿真實(shí)驗(yàn)對(duì)公認(rèn)的TSP測試數(shù)據(jù)中算例Oliver30進(jìn)行測試并與目前已知最優(yōu)解進(jìn)行了對(duì)比，結(jié)果表明，人工魚群算法解決TSP問題時(shí)可以收斂到已知最優(yōu)解，并且解的質(zhì)量要優(yōu)于標(biāo)準(zhǔn)粒子群算法和基本遺傳算法。

關(guān)鍵詞：旅行商問題；人工魚群算法；聚群行為；覓食行為；追尾行為

中圖分類號(hào)：TP18 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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）問題，即旅行商問題，是經(jīng)典的組合優(yōu)化問題。 在許多工程應(yīng)用問題中，如物流配送、網(wǎng)絡(luò)布線和電路板鉆孔等，都可以歸結(jié)為TSP求解問題。目前，對(duì)于解決TSP問題人們提出了很多有價(jià)值的方法，如模擬退火算法[1]、遺傳算法[2]、蟻群算法[3]和粒子群算法[4]等智能算法。而人工魚群算法（Artificial Fish Swarm Algorithm， AFSA）[5-6]是李曉磊等人于2002年在對(duì)動(dòng)物群體智能行為研究的基礎(chǔ)上提出的一種新型仿生優(yōu)化算法，該算法主要利用魚群的三大基本行為分別為覓食、聚群和追尾行為，采用自上而下的尋優(yōu)模式從構(gòu)造個(gè)體的底層行為開始，通過魚群中個(gè)體的局部尋優(yōu)，達(dá)到全局最優(yōu)值在群體中突現(xiàn)出來的目的。

人工魚群算法主要應(yīng)用還集中在解決函數(shù)優(yōu)化問題，在組合優(yōu)化問題中的應(yīng)用較少，尤其是TSP問題中的應(yīng)用少之又少。為此本文利用人工魚群算法來解決TSP問題，并與標(biāo)準(zhǔn)粒子群算法和基本遺傳算法進(jìn)行了比較分析。

1 旅行商問題

TSP問題，即旅行商問題，是經(jīng)典的組合優(yōu)化問題之一。旅行商問題的基本描述是：假設(shè)有一個(gè)旅行商人要訪問[n]個(gè)城市，他必須選擇要走的路徑，選擇路徑的限制條件是每個(gè)城市只能訪問一次，而且最后要回到原來出發(fā)的城市。路徑的選擇目標(biāo)是要求求出的路徑為所有路徑之中的最短路徑。簡單說，旅行商問題就是需要尋找這樣的一條旅行線路：從某個(gè)城市開始，經(jīng)過每個(gè)城市一次且僅一次，最終回到出發(fā)城市，使得旅游的路經(jīng)總長度為最短。

TSP問題的數(shù)學(xué)模型[7]可描述為：

[minf（X）]

[s.t.g（X）≥0，X∈D] （1）

公式（1） 中，[f（X）]為目標(biāo)函數(shù)，[g（X）]為約束函數(shù)，[X]為決策變量，[D]表示有限個(gè)點(diǎn)組成的集合。通常，一個(gè)組合優(yōu)化問題可用三個(gè)參數(shù)[（D，F(xiàn)，f）]來表示，其中[D]表示決策變量的定義域，[F={XX∈D，g（X）≥0}]，[f]表示目標(biāo)函數(shù)，滿足的可行解[X′]稱為問題的最優(yōu)解。

2 人工魚群算法

人工魚個(gè)體的狀態(tài)可表示為向量[X=（x1，x2，...，xn）]其中[xi（i=1，2，...，n）]為要尋優(yōu)的變量，人工魚當(dāng)前所在位置的食物濃度可表示為[Y=f（X）]，其中[X]為目標(biāo)函數(shù)值，人工魚個(gè)體之間的距離可表示為[dij]，[visual] 表示人工魚的感知范圍，[step]表示人工魚移動(dòng)的步長，[δ]表示擁擠度因子。

2.1 覓食行為

設(shè)人工魚當(dāng)前狀態(tài)[Xi]，在其感知范圍內(nèi)（即[dij

2.2聚群行為

設(shè)人工魚當(dāng)前狀態(tài)為[Xi]， 探索當(dāng)前感知范圍內(nèi)（即[dij

2.3 追尾行為

人工魚當(dāng)前狀態(tài)為[Xi]，探索感知范圍內(nèi)（即[dij

2.4 隨機(jī)行為

隨機(jī)行為的實(shí)現(xiàn)較簡單，就是在視野中隨機(jī)選擇一個(gè)狀態(tài)，然后向該方向移動(dòng)，其實(shí)它是覓食行為的一個(gè)缺省行為。

2.5公告板

公告板記錄當(dāng)前最優(yōu)人工魚個(gè)體的狀態(tài)。各人工魚個(gè)體每次行動(dòng)完畢后與公告板上的人工魚個(gè)體狀態(tài)比較，如果自身優(yōu)于公告板上人工魚個(gè)體狀態(tài)，就用自身狀態(tài)更新公告板上人工魚群個(gè)體狀態(tài)。

3 求解TSP問題的人工魚群算法

人工魚群算法具有把握搜索方向和在一定程度上避免陷入局部最優(yōu)解的特性，但當(dāng)一部分人工魚處于隨機(jī)移動(dòng)時(shí)，收斂速度就會(huì)減慢。為了克服此缺點(diǎn)，在算法中設(shè)立公告板以此記錄最優(yōu)人工魚個(gè)體狀態(tài)。每條人工魚在行動(dòng)一次以后將自身當(dāng)前狀態(tài)的值與公告板的當(dāng)前狀態(tài)進(jìn)行比較，如果優(yōu)于公告板，則用自身狀態(tài)取代公告板狀態(tài)。

3.1求解TSP問題的人工魚群算法步驟

求解TSP問題的人工魚群算法實(shí)現(xiàn)的具體步驟如下：

步驟1 產(chǎn)生初始化種群：定義最大迭代次數(shù)num，擁擠度因子[δ]，視野范圍visual，試探次數(shù)trynumber并在可行域內(nèi)隨機(jī)生成N條人工魚，形成初始魚群。

步驟2 計(jì)算初始魚群各人工魚當(dāng)前狀態(tài)的值，比較大小，最小值進(jìn)入公告板，并且把對(duì)應(yīng)的人工魚狀態(tài)賦值給公告板。

步驟3 按照人工魚群算法的行為準(zhǔn)則，進(jìn)行追尾行為和聚群行為，缺省行為為覓食行為。如果進(jìn)行了追尾行為和聚群行后，最好值還是沒有變化就進(jìn)行隨機(jī)行為。

步驟4 各人工魚進(jìn)行行為選擇后，檢查自身的值與公告板的值，如果優(yōu)于公告板，則以自身取代，同時(shí)更新公告板上的人工魚狀態(tài)。

步驟5 判斷是否滿足終止條件，若不滿足終止條件則轉(zhuǎn)到步驟3執(zhí)行，進(jìn)行下一步魚群優(yōu)化過程，否則轉(zhuǎn)到步驟6執(zhí)行。

步驟6 算法終止，輸出公告板上的最優(yōu)解人工魚群狀態(tài)值。

3.2算例及仿真研究

算法的參數(shù)取為最大試探次數(shù)為100，人工魚個(gè)數(shù)為10，最大迭代次數(shù)取100，擁擠度因子0.8，感知范圍為10，采用Matlab7.0為編程工具，實(shí)驗(yàn)環(huán)境為Intel（R）Core（TM）i3，2.13GHz CPU，2GB內(nèi)存，Windows 7操作系統(tǒng)。為了便于比較，該文將人工魚群算法與標(biāo)準(zhǔn)粒子群算法和基本遺傳算法分別連續(xù)進(jìn)行30次實(shí)驗(yàn)，對(duì)其結(jié)果進(jìn)行比較分析。該文使用TSP問題中的標(biāo)準(zhǔn)測試算例TSPLIB[8]庫中的Oliver30（30個(gè)城市），Oliver30算例的目前已知最優(yōu)解為423.7406。通過仿真實(shí)驗(yàn)對(duì)其結(jié)果進(jìn)行比較分析，仿真結(jié)果如表1所示。

標(biāo)準(zhǔn)粒子群算法中粒子數(shù)為100，慣性權(quán)重[w]從1.4線性遞減到0.5，加速常數(shù)[c1=c2=1.2]，最大迭代次數(shù)為1000。遺傳算法中，最大代數(shù)為1000，種群為100，交叉概率為0.8，變異概率為0.05，實(shí)驗(yàn)結(jié)果如表1所示，人工魚群算法的得到最優(yōu)路徑如圖1所示，尋優(yōu)曲線如圖2所示。算例Oliver30如下：

City[30]={ {41，94}，{37，84}，{54，67}，{25，62}，{7， 64}，{2， 99}，{68，58}， {71，44}，{54， 62}，

{83，69}，{64，60}，{18，54}，{22，60}，{83，46}，{91，38}，{25，38}，{24，42}，{58，69}，{71，71}，{74，78}，

{87，76}，{18，40}，{13， 40}，{82，7}，{62，32}，{58，35}，{45，21}，{41， 26}，{44，35}，{4，50}}

表1 幾種智能算法試驗(yàn)結(jié)果比較

[算法 平均值 最好值 最差值＼&人工魚群算法 424.1245 423.7406 425.6024

標(biāo)準(zhǔn)粒子群算法 450.2314 425.5416 480.1452

基本遺傳算法 430.5285 427.6918 437.4521＼&]

由表1中的實(shí)驗(yàn)結(jié)果可知，人工魚群算法得到的最優(yōu)解為423.7406，與當(dāng)前已知的Oliver30問題的最優(yōu)解一致。標(biāo)準(zhǔn)粒子群算法的最優(yōu)解為425.5416，遺傳算法的最優(yōu)解為424.6918，都沒有收斂到當(dāng)前最優(yōu)解。根據(jù)圖1可知，人工魚群算法求得的最優(yōu)路徑也于已知的最好解對(duì)應(yīng)的路徑是一致的。

圖1 Oliver30問題最優(yōu)路徑 圖2 Oliver30問題尋優(yōu)曲線

4 結(jié)論

本文將人工魚群算法應(yīng)用于解決TSP問題，并將該算法與標(biāo)準(zhǔn)粒子群算法和基本遺傳算法進(jìn)行了比較分析。根據(jù)仿真實(shí)驗(yàn)結(jié)果可知，在解決算例Oliver30問題時(shí)，該文中的人工魚群算法能夠獲得已知的最優(yōu)解，且解的平均值要優(yōu)于標(biāo)準(zhǔn)粒子群算法和基本遺傳算法。

參考文獻(xiàn)：

[1] 鄧士杰，支建莊，于貴波.欒軍英基于模擬退火算法的TSP問題研究[J].價(jià)值工程，2012（28） ：65-68.

[2] 謝勝利，唐敏.求解TSP問題的一種改進(jìn)的遺傳算法[J].計(jì)算機(jī)工程與應(yīng)用，2002，38（8） ：58-60.

[3] 翁國棟.蟻群優(yōu)化算法與遺傳算法在TSP問題上的融合[J].福建電腦，2006（2）：115-116.

[4] 莊嚴(yán).粒子群優(yōu)化算法在TSP問題中的應(yīng)用[J].科技信息，2008（30）：184-185.

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

[6] 李曉磊.組合優(yōu)化問題的人工魚群算法應(yīng)用[J].山東大學(xué)學(xué)報(bào)：工學(xué)版，2004，34（5）：64-67.

[7] 邢文訓(xùn)，謝金星.現(xiàn)代優(yōu)化技術(shù)方法[M].北京：清華大學(xué)出版社，1999.

[8] http：//www.iwr.uni-heidelberg.de/iwr/comopt/soft-ware/TSPLIB95.

2.2聚群行為

設(shè)人工魚當(dāng)前狀態(tài)為[Xi]， 探索當(dāng)前感知范圍內(nèi)（即[dij

2.3 追尾行為

人工魚當(dāng)前狀態(tài)為[Xi]，探索感知范圍內(nèi)（即[dij

2.4 隨機(jī)行為

隨機(jī)行為的實(shí)現(xiàn)較簡單，就是在視野中隨機(jī)選擇一個(gè)狀態(tài)，然后向該方向移動(dòng)，其實(shí)它是覓食行為的一個(gè)缺省行為。

2.5公告板

公告板記錄當(dāng)前最優(yōu)人工魚個(gè)體的狀態(tài)。各人工魚個(gè)體每次行動(dòng)完畢后與公告板上的人工魚個(gè)體狀態(tài)比較，如果自身優(yōu)于公告板上人工魚個(gè)體狀態(tài)，就用自身狀態(tài)更新公告板上人工魚群個(gè)體狀態(tài)。

3 求解TSP問題的人工魚群算法

人工魚群算法具有把握搜索方向和在一定程度上避免陷入局部最優(yōu)解的特性，但當(dāng)一部分人工魚處于隨機(jī)移動(dòng)時(shí)，收斂速度就會(huì)減慢。為了克服此缺點(diǎn)，在算法中設(shè)立公告板以此記錄最優(yōu)人工魚個(gè)體狀態(tài)。每條人工魚在行動(dòng)一次以后將自身當(dāng)前狀態(tài)的值與公告板的當(dāng)前狀態(tài)進(jìn)行比較，如果優(yōu)于公告板，則用自身狀態(tài)取代公告板狀態(tài)。

3.1求解TSP問題的人工魚群算法步驟

求解TSP問題的人工魚群算法實(shí)現(xiàn)的具體步驟如下：

步驟1 產(chǎn)生初始化種群：定義最大迭代次數(shù)num，擁擠度因子[δ]，視野范圍visual，試探次數(shù)trynumber并在可行域內(nèi)隨機(jī)生成N條人工魚，形成初始魚群。

步驟2 計(jì)算初始魚群各人工魚當(dāng)前狀態(tài)的值，比較大小，最小值進(jìn)入公告板，并且把對(duì)應(yīng)的人工魚狀態(tài)賦值給公告板。

步驟3 按照人工魚群算法的行為準(zhǔn)則，進(jìn)行追尾行為和聚群行為，缺省行為為覓食行為。如果進(jìn)行了追尾行為和聚群行后，最好值還是沒有變化就進(jìn)行隨機(jī)行為。

步驟4 各人工魚進(jìn)行行為選擇后，檢查自身的值與公告板的值，如果優(yōu)于公告板，則以自身取代，同時(shí)更新公告板上的人工魚狀態(tài)。

步驟5 判斷是否滿足終止條件，若不滿足終止條件則轉(zhuǎn)到步驟3執(zhí)行，進(jìn)行下一步魚群優(yōu)化過程，否則轉(zhuǎn)到步驟6執(zhí)行。

步驟6 算法終止，輸出公告板上的最優(yōu)解人工魚群狀態(tài)值。

3.2算例及仿真研究

算法的參數(shù)取為最大試探次數(shù)為100，人工魚個(gè)數(shù)為10，最大迭代次數(shù)取100，擁擠度因子0.8，感知范圍為10，采用Matlab7.0為編程工具，實(shí)驗(yàn)環(huán)境為Intel（R）Core（TM）i3，2.13GHz CPU，2GB內(nèi)存，Windows 7操作系統(tǒng)。為了便于比較，該文將人工魚群算法與標(biāo)準(zhǔn)粒子群算法和基本遺傳算法分別連續(xù)進(jìn)行30次實(shí)驗(yàn)，對(duì)其結(jié)果進(jìn)行比較分析。該文使用TSP問題中的標(biāo)準(zhǔn)測試算例TSPLIB[8]庫中的Oliver30（30個(gè)城市），Oliver30算例的目前已知最優(yōu)解為423.7406。通過仿真實(shí)驗(yàn)對(duì)其結(jié)果進(jìn)行比較分析，仿真結(jié)果如表1所示。

標(biāo)準(zhǔn)粒子群算法中粒子數(shù)為100，慣性權(quán)重[w]從1.4線性遞減到0.5，加速常數(shù)[c1=c2=1.2]，最大迭代次數(shù)為1000。遺傳算法中，最大代數(shù)為1000，種群為100，交叉概率為0.8，變異概率為0.05，實(shí)驗(yàn)結(jié)果如表1所示，人工魚群算法的得到最優(yōu)路徑如圖1所示，尋優(yōu)曲線如圖2所示。算例Oliver30如下：

City[30]={ {41，94}，{37，84}，{54，67}，{25，62}，{7， 64}，{2， 99}，{68，58}， {71，44}，{54， 62}，

{83，69}，{64，60}，{18，54}，{22，60}，{83，46}，{91，38}，{25，38}，{24，42}，{58，69}，{71，71}，{74，78}，

{87，76}，{18，40}，{13， 40}，{82，7}，{62，32}，{58，35}，{45，21}，{41， 26}，{44，35}，{4，50}}

表1 幾種智能算法試驗(yàn)結(jié)果比較

[算法 平均值 最好值 最差值＼&人工魚群算法 424.1245 423.7406 425.6024

標(biāo)準(zhǔn)粒子群算法 450.2314 425.5416 480.1452

基本遺傳算法 430.5285 427.6918 437.4521＼&]

由表1中的實(shí)驗(yàn)結(jié)果可知，人工魚群算法得到的最優(yōu)解為423.7406，與當(dāng)前已知的Oliver30問題的最優(yōu)解一致。標(biāo)準(zhǔn)粒子群算法的最優(yōu)解為425.5416，遺傳算法的最優(yōu)解為424.6918，都沒有收斂到當(dāng)前最優(yōu)解。根據(jù)圖1可知，人工魚群算法求得的最優(yōu)路徑也于已知的最好解對(duì)應(yīng)的路徑是一致的。

圖1 Oliver30問題最優(yōu)路徑 圖2 Oliver30問題尋優(yōu)曲線

4 結(jié)論

本文將人工魚群算法應(yīng)用于解決TSP問題，并將該算法與標(biāo)準(zhǔn)粒子群算法和基本遺傳算法進(jìn)行了比較分析。根據(jù)仿真實(shí)驗(yàn)結(jié)果可知，在解決算例Oliver30問題時(shí)，該文中的人工魚群算法能夠獲得已知的最優(yōu)解，且解的平均值要優(yōu)于標(biāo)準(zhǔn)粒子群算法和基本遺傳算法。

參考文獻(xiàn)：

[1] 鄧士杰，支建莊，于貴波.欒軍英基于模擬退火算法的TSP問題研究[J].價(jià)值工程，2012（28） ：65-68.

[2] 謝勝利，唐敏.求解TSP問題的一種改進(jìn)的遺傳算法[J].計(jì)算機(jī)工程與應(yīng)用，2002，38（8） ：58-60.

[3] 翁國棟.蟻群優(yōu)化算法與遺傳算法在TSP問題上的融合[J].福建電腦，2006（2）：115-116.

[4] 莊嚴(yán).粒子群優(yōu)化算法在TSP問題中的應(yīng)用[J].科技信息，2008（30）：184-185.

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

[6] 李曉磊.組合優(yōu)化問題的人工魚群算法應(yīng)用[J].山東大學(xué)學(xué)報(bào)：工學(xué)版，2004，34（5）：64-67.

[7] 邢文訓(xùn)，謝金星.現(xiàn)代優(yōu)化技術(shù)方法[M].北京：清華大學(xué)出版社，1999.

[8] http：//www.iwr.uni-heidelberg.de/iwr/comopt/soft-ware/TSPLIB95.

2.2聚群行為

設(shè)人工魚當(dāng)前狀態(tài)為[Xi]， 探索當(dāng)前感知范圍內(nèi)（即[dij

2.3 追尾行為

人工魚當(dāng)前狀態(tài)為[Xi]，探索感知范圍內(nèi)（即[dij

2.4 隨機(jī)行為

隨機(jī)行為的實(shí)現(xiàn)較簡單，就是在視野中隨機(jī)選擇一個(gè)狀態(tài)，然后向該方向移動(dòng)，其實(shí)它是覓食行為的一個(gè)缺省行為。

2.5公告板

公告板記錄當(dāng)前最優(yōu)人工魚個(gè)體的狀態(tài)。各人工魚個(gè)體每次行動(dòng)完畢后與公告板上的人工魚個(gè)體狀態(tài)比較，如果自身優(yōu)于公告板上人工魚個(gè)體狀態(tài)，就用自身狀態(tài)更新公告板上人工魚群個(gè)體狀態(tài)。

3 求解TSP問題的人工魚群算法

人工魚群算法具有把握搜索方向和在一定程度上避免陷入局部最優(yōu)解的特性，但當(dāng)一部分人工魚處于隨機(jī)移動(dòng)時(shí)，收斂速度就會(huì)減慢。為了克服此缺點(diǎn)，在算法中設(shè)立公告板以此記錄最優(yōu)人工魚個(gè)體狀態(tài)。每條人工魚在行動(dòng)一次以后將自身當(dāng)前狀態(tài)的值與公告板的當(dāng)前狀態(tài)進(jìn)行比較，如果優(yōu)于公告板，則用自身狀態(tài)取代公告板狀態(tài)。

3.1求解TSP問題的人工魚群算法步驟

求解TSP問題的人工魚群算法實(shí)現(xiàn)的具體步驟如下：

步驟1 產(chǎn)生初始化種群：定義最大迭代次數(shù)num，擁擠度因子[δ]，視野范圍visual，試探次數(shù)trynumber并在可行域內(nèi)隨機(jī)生成N條人工魚，形成初始魚群。

步驟2 計(jì)算初始魚群各人工魚當(dāng)前狀態(tài)的值，比較大小，最小值進(jìn)入公告板，并且把對(duì)應(yīng)的人工魚狀態(tài)賦值給公告板。

步驟3 按照人工魚群算法的行為準(zhǔn)則，進(jìn)行追尾行為和聚群行為，缺省行為為覓食行為。如果進(jìn)行了追尾行為和聚群行后，最好值還是沒有變化就進(jìn)行隨機(jī)行為。

步驟4 各人工魚進(jìn)行行為選擇后，檢查自身的值與公告板的值，如果優(yōu)于公告板，則以自身取代，同時(shí)更新公告板上的人工魚狀態(tài)。

步驟5 判斷是否滿足終止條件，若不滿足終止條件則轉(zhuǎn)到步驟3執(zhí)行，進(jìn)行下一步魚群優(yōu)化過程，否則轉(zhuǎn)到步驟6執(zhí)行。

步驟6 算法終止，輸出公告板上的最優(yōu)解人工魚群狀態(tài)值。

3.2算例及仿真研究

算法的參數(shù)取為最大試探次數(shù)為100，人工魚個(gè)數(shù)為10，最大迭代次數(shù)取100，擁擠度因子0.8，感知范圍為10，采用Matlab7.0為編程工具，實(shí)驗(yàn)環(huán)境為Intel（R）Core（TM）i3，2.13GHz CPU，2GB內(nèi)存，Windows 7操作系統(tǒng)。為了便于比較，該文將人工魚群算法與標(biāo)準(zhǔn)粒子群算法和基本遺傳算法分別連續(xù)進(jìn)行30次實(shí)驗(yàn)，對(duì)其結(jié)果進(jìn)行比較分析。該文使用TSP問題中的標(biāo)準(zhǔn)測試算例TSPLIB[8]庫中的Oliver30（30個(gè)城市），Oliver30算例的目前已知最優(yōu)解為423.7406。通過仿真實(shí)驗(yàn)對(duì)其結(jié)果進(jìn)行比較分析，仿真結(jié)果如表1所示。

標(biāo)準(zhǔn)粒子群算法中粒子數(shù)為100，慣性權(quán)重[w]從1.4線性遞減到0.5，加速常數(shù)[c1=c2=1.2]，最大迭代次數(shù)為1000。遺傳算法中，最大代數(shù)為1000，種群為100，交叉概率為0.8，變異概率為0.05，實(shí)驗(yàn)結(jié)果如表1所示，人工魚群算法的得到最優(yōu)路徑如圖1所示，尋優(yōu)曲線如圖2所示。算例Oliver30如下：

City[30]={ {41，94}，{37，84}，{54，67}，{25，62}，{7， 64}，{2， 99}，{68，58}， {71，44}，{54， 62}，

{83，69}，{64，60}，{18，54}，{22，60}，{83，46}，{91，38}，{25，38}，{24，42}，{58，69}，{71，71}，{74，78}，

{87，76}，{18，40}，{13， 40}，{82，7}，{62，32}，{58，35}，{45，21}，{41， 26}，{44，35}，{4，50}}

表1 幾種智能算法試驗(yàn)結(jié)果比較

[算法 平均值 最好值 最差值＼&人工魚群算法 424.1245 423.7406 425.6024

標(biāo)準(zhǔn)粒子群算法 450.2314 425.5416 480.1452

基本遺傳算法 430.5285 427.6918 437.4521＼&]

由表1中的實(shí)驗(yàn)結(jié)果可知，人工魚群算法得到的最優(yōu)解為423.7406，與當(dāng)前已知的Oliver30問題的最優(yōu)解一致。標(biāo)準(zhǔn)粒子群算法的最優(yōu)解為425.5416，遺傳算法的最優(yōu)解為424.6918，都沒有收斂到當(dāng)前最優(yōu)解。根據(jù)圖1可知，人工魚群算法求得的最優(yōu)路徑也于已知的最好解對(duì)應(yīng)的路徑是一致的。

圖1 Oliver30問題最優(yōu)路徑 圖2 Oliver30問題尋優(yōu)曲線

4 結(jié)論

本文將人工魚群算法應(yīng)用于解決TSP問題，并將該算法與標(biāo)準(zhǔn)粒子群算法和基本遺傳算法進(jìn)行了比較分析。根據(jù)仿真實(shí)驗(yàn)結(jié)果可知，在解決算例Oliver30問題時(shí)，該文中的人工魚群算法能夠獲得已知的最優(yōu)解，且解的平均值要優(yōu)于標(biāo)準(zhǔn)粒子群算法和基本遺傳算法。

參考文獻(xiàn)：

[1] 鄧士杰，支建莊，于貴波.欒軍英基于模擬退火算法的TSP問題研究[J].價(jià)值工程，2012（28） ：65-68.

[2] 謝勝利，唐敏.求解TSP問題的一種改進(jìn)的遺傳算法[J].計(jì)算機(jī)工程與應(yīng)用，2002，38（8） ：58-60.

[3] 翁國棟.蟻群優(yōu)化算法與遺傳算法在TSP問題上的融合[J].福建電腦，2006（2）：115-116.

[4] 莊嚴(yán).粒子群優(yōu)化算法在TSP問題中的應(yīng)用[J].科技信息，2008（30）：184-185.

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

[6] 李曉磊.組合優(yōu)化問題的人工魚群算法應(yīng)用[J].山東大學(xué)學(xué)報(bào)：工學(xué)版，2004，34（5）：64-67.

[7] 邢文訓(xùn)，謝金星.現(xiàn)代優(yōu)化技術(shù)方法[M].北京：清華大學(xué)出版社，1999.

[8] http：//www.iwr.uni-heidelberg.de/iwr/comopt/soft-ware/TSPLIB95.