蟻群算法在解決TSP問題中的應用

陳靈佳

文章首先對蟻群算法與TSP問題進行簡要介紹，在此基礎上對蟻群算法在解決TSP問題中的應用進行論述。期望通過本文的研究能夠對TSP問題的解決有所幫助。

【關鍵詞】蟻群算法 TSP問題 最優解

1 蟻群算法與TSP問題簡介

1.1 蟻群算法

蟻群算法是一種隨機的、概率搜索算法，它是目前求解復雜組合優化問題較為有效的手段之一，借助信息反饋機制，能夠進一步加快算法的進化，從而更加快速地找到最優解。蟻群算法可在諸多領域中應用，借助該算法能夠求得TSP問題的最短路徑。蟻群尋找最短路徑的過程如圖1所示。

蟻群算法之所以在多個領域獲得廣泛應用，與其自身所具備的諸多優點有著密不可分的關聯，如自組織性、正負反饋性、魯棒性、分布式計算等等，其最為突出的優點是能夠與其它算法結合使用。但是在應用實踐中發現，雖然蟻群算法的優點較多，其也或多或少地存在一定的不足，如搜索時間較長，規模越大時間越長；容易出現停滯現象等等。

1.2 TSP問題

TSP是旅行商的英文縮寫形式，這一術語最早出現于1932年，在1948年時，美國蘭德公司（RAND）引入了TSP，由此使得TSP廣為人知。從數學領域的角度上講，TSP問題是NP-完備組合優化問題，這是一個看似簡單實則需要天文數字計算能力方可獲得最優解的過程，其適用于搜索算法解決不了的復雜與非線性問題。

2 蟻群算法在解決TSP問題中的應用

2.1 蟻群算法的改進

（1）大量的實驗結果表明，標準蟻群算法在TSP問題的求解中，很容易陷入局部最優解。這是因為，蟻群的轉移主要是由各條路徑上的信息素濃度及城市間的距離來引導的，信息素濃度最強的路徑是蟻群的首選目標，該路徑與最優路徑極為接近。然而，各個路徑上初始信息素的濃度全部相同，因此，蟻群在對第一條路徑進行創建時，主要依賴于城市間的距離信息，這樣一來很難確保蟻群創建的路徑是最優路徑，如果以此為基礎，那么信息素便會在該局部最優路徑上越積累越多，其上的信息素濃度將會超過其它路徑，從而造成全部螞蟻都會集中于該路徑之上，由此便會造成停滯現象，不但會使搜索的時間增長，而且所求得的解也無法達到理想中的效果。

（2）由于本文研究的是利用蟻群算法來解決TSP問題，所以對蟻群算法的改進應當以此為依據，具體的改進方法如下：對于初始的TSP而言，利用蟻群算法求取最優解時，應考慮的首要問題是預處理環節，可采用近鄰法建立一個初始游歷，并對信息素的初始值進行計算；利用Ant-Q Systems算法，基于隨機性和確定性相結合的策略，在搜索的過程中，對狀態轉移概率進行調整；對信息素的更新可使用在線單步更新信息素與離線全局更新信息素相結合的方法予以實現。

2.2 改進蟻群算法在TSP求解中的應用

2.2.1 對算法進行初始化

對所有城市的坐標進行獲取，以此為依據，對距離矩陣Distmatrix進行計算，同時對隨機發生器狀態進行初始化，并以隨機的形式從n個城市中選出初始的出發城市，并將該城市設定為：

p（1）=round（Ncities*rang+0.5），其中的Ncities代表城市的數目。

通過最近鄰法創建一個初始游歷，并對距離矩陣進行更新，同步計算出距離總長度len在此基礎上對信息素的初始值Q0進行設定，即Q0=1/（Ncities*len）。

2.2.2 算法循環

Step1：對相關參數進行初始化，令NC（循環初始迭代）=1，MaxNC（最大循環次數）=5000，A（信息素因子）=1，B（啟發信息因子）=2，P1（局部揮發系數）=P2（全局揮發系數）=0.1，M（蟻群數量）=10，R0（選擇概率）=0.9。

Step2：將初始化信息素矩陣進行設定為：

Pheromone=Q0*ones（Ncities，Ncities）

同時將啟發信息矩陣設定為：

Heuristic=1./DistMatrix

在將初始化允許矩陣設定為：allow0=repmat（1：Ncities，M，1）

該矩陣的初始值設為0，最后將M置于Ncities個元素上。

Step3：設循環計數器NC=NC+1。

Step4：設螞蟻禁忌表索引號AK=1，螞蟻的數目=AK+1。

Step5：螞蟻個體按照Ant-Q Systems算法提出的狀態轉移概率，選擇下個城市j并前進。

Step6：對允許矩陣進行更新，使其變為allow（AK，j）=0，即將螞蟻所選城市標號在該矩陣中對應位置的值重新設定為0。

Step7：如果螞蟻為遍歷集合C中的所有元素，即AK

Step8：對每只螞蟻找到的路徑長度進行計算，并對最優的路徑長度及其對應的遍歷順序進行保存，記錄并找到最優解的螞蟻的搜索軌跡。

Step9：若NC≥MaxNC，則整個循環過程結束，如果未達到這一要求，則清空禁忌表，并跳轉至Step3，直至達到要求為止。

2.2.3 算法輸出

先將全局最優解的軌跡變化圖繪制出來，然后再繪制出全局最優解的路線圖，最后將最優的遍歷順序、最優的遍歷結果以及總體運行時間輸出，便可完成對TSP問題的求解。

3 結論

綜上所述，蟻群算法以其自身諸多的優點在多個領域中獲得了廣泛應用，但標準蟻群算法的搜索時間較長，并且容易出現停滯現象。對此，本文提出一種改進的蟻群算法，并對其在TSP問題解決中的應用進行分析。經過改進之后，不但縮短了搜索時間，而且停滯問題也隨之消除。

參考文獻

[1]杜鵬楨，唐振民，孫研.一種面向對象的多角色蟻群算法及其TSP問題求解[J].控制與決策，2014（10）：85-88.

[2]扈華，王冬青.蟻群算法解決TSP問題圖形化軟件設計[J].電腦編程技巧與維護，2014（10）：98-100.

[3]徐勝，馬小軍，錢海.基于遺傳-模擬退火的蟻群算法求解TSP問題[J].計算機測量與控制，2016（03）：125-127.

作者單位

同濟大學 上海市 201804