多種智能算法求解不同規模的TSP 問題分析

段雙雙

1 TSP 問題描述

TSP 問題（Traveling Salesman Problem）又稱為旅行商推銷員問題，是一個易于描述但難于解決的問題之一。TSP 問題已知n 個城市各城市間的距離，某一旅行商從某個城市出發訪問每個城市一次且僅一次，最后回到出發城市，怎樣安排才使其所走路線最短[1]。由于TSP 問題代表一類組合優化問題，在實際工程中有許多應用，如產品的生產安排、計算機聯網、電子地圖、交通誘導、電氣布線、VLSI 單元布局、AT M 分組交換網等。因此TSP 問題的求解具有重要的理論意義和實際意義[2]。

2 TSP 問題的數學模型

2.1 TSP 問題可以用以下數學模型來描述

設有一個城市集合C=（c1，c2，…，cn），其中每對城市之間的距離，求一對經過C 中每個城市一次的路線，使：

3 智能算法求解TSP 問題

TSP 問題被證明是一個NP- hard 問題，即在P≠NP 的假設下，找不到一個多項式時間算法來求解其最優解。自1932 年提出以來，已引起許多學者的興趣，但至今尚未找到非常有效的求解方法。

解決TSP 常用的方法有兩類，一是傳統的確定性算法，如動態規劃DM，分支限界法LC等。第二類是現在流行的智能算法，如蟻群算法(ACA)[5]，遺傳算法(GA)，模擬退火(SA)，禁忌搜索(TS)，神經網絡(NN)，粒子群優化算法(PSO)，免疫算法(IA)等[4]。本文就模擬退火，禁忌搜索，遺傳算法，蟻群算法對n 為30，50，75 三種不同規模的TSP 問題進行求解。

3.1 部分參數設置

3.1.1 城市數目為n，城市坐標如下：

n=10 city10= {（0.4，0.4439）（0.2439，0.1463）（0.1707，0.2293）（0.2293，0.761）（0.5171，0.9414）（0.8732，0.6536）（0.6878，0.5219）（0.8488，0.3609）（0.6683，0.2536）（0.6195，0.26 34）}

n=30 city30={(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)}

n=50city50={(31 32)(32 39)(40 30)(37 69)(27 68)(37 52)(38 46)(31 62)(30 48)(21 47)(25 55)(16 57)(17 63)(42 41)(17 33)(25 32)(5 64)(8 52)(12 42)(7 38)(5 25)(10 77) (45 35) (42 57) (32 22) ( 27 23) (56 37)(52 41)(49 49)(58 48)(57 58)(39 10)(46 10)(59 15)(51 21) (48 28) (52 33) (58 27) (61 33) (62 63)（20 26）（5 6）（13 13）（21 10）（30 15）（36 16）（62 42）(63 69)(52 64)（43 67）}

表 1 SA，TS，GA，ACS 四種在 n=30，50，75 三種情況下求解結果

n=75city75={（48 21）（52 26）（55 50）（50 50）（41 46）（51 42）（55 45）(38 33)(33 34)(45 35)(40 37)(50 30)（55 34）（54 38）（26 13）（15 5）（21 48）（29 39）（33 44）(15 19)(16 19)(12 17)(50 40) (22 53) (21 36) (20 30) (26 29)（40 20）（36 26）（62 48）(67 41)(62 35)(65 27)(62 24)(55 20)(35 51)(30 50)(45 42)(21 45) (36 6) (6 25) (11 28) (26 59) (30 60)（22 22）（27 24）（30 20）（35 16）（54 10）（50 15）（44 13）（35 60）（40 60）(40 66)(31 76)(47 66)(50 70)(57 72)(55 65)(2 38)(7 43)(9 56)(15 56)(10 70)(17 64)(55 57)(62 57)(70 64)(64 4)(59 5)(50 4)(60 15)(66 14)(66 8)(43 26)}

3.1.2 參數設置

模擬退火（SA）算法參數：tf=0.01，alpha=0.80，L=100*Ci tyNum

禁忌搜索（TS）算法參數：cl=100，tl=50，l1=200

遺傳算法（GA）算法參數：inn=100，gnmax=1000，pc=0.8，pm=0.08

蟻群算法（ACS）算法參數：Alpha=1，Beta=5，Rho=0.5，NC_max=200，Q=100

Hopfield 神經網絡算法（HNN） 算法參數：A=500，B=500，C=200，D=500，arf=1，miu0=0.02，lan=0.00001，EndNum=1000。

3.2 算法運行結果

運用matlab7.0 版本進行編程計算[7]，分別用模擬退火，禁忌搜索，遺傳算法，蟻群算法4 種智能算法求解n=30，50，75 的tsp 問題結果對比如表1 所示。

3.3 結果分析

從表1 可以看出，綜合來說，SA 迭代搜索具有較強的局部尋優能力并且能使搜索過程避免陷入局部最優解，而且具有高效、魯棒、通用、靈活的優點，但在前期搜索過程較難最有希望的搜索區域，從而全局最優解難于找出，運算效率不高；TS 解決規模較大組合優化問題時，單純應用頻率記憶或改變參數來實現多樣性搜索有可能得不到理想的效果；GA 可大大減少陷入局部最小的可能，但相對其他三種算法主要缺點是搜索空間大，導致搜索時間比較長；ACS 雖然能快速找到最優解，但是很容易陷入局部最優的缺點[6]。綜合來說，對于 SA，TS，GA，ACS 這四種算法，都比較適合較大規模的TSP 問題求解，從最短距離和達到最優解的速度來看，解決TSP 問題，蟻群算法會更優于其他三種算法。

4 結束語

本文是用最基本的4 種智能算法對不同規模的TSP 問題進行求解，然后對他們的求解結果進行比較分析，以后會從這些算法本身或是將多種算法相結合這兩個方面一定的優化工作，能更好的求解TSP 問題，進而將這些算法應用到其他的工程實際問題上。