基于改進蟻群算法在TSP 問題中的應用

劉子墨

（首都經濟貿易大學管理工程學院，北京 100070）

蟻群算法從大自然中誕生，是尋優問題中一種優秀的解決策略[1]。最初是由DORⅠGO 等[2]首次向世人介紹了蟻群算法。由于螞蟻的移動是隨機的，當種群規模達到一定程度時，蟻群算法需要很長時間才能找到較優的解決方案。因此，GAMBARDELLA 等[3]又對經典的AS 算法進行了改進，提出了一種更為通用的算法“Ant-Q System”。針對蟻群算法易過早停滯的缺陷，1997 年，STUTZLE 等[4]提出了MAX-MⅠN Ant System，為其中每條邊可允許擁有的跟蹤信息素的量設置了范圍限制。而后GAMBARDELLA 等[5]提出了HAS，在HAS 的迭代中，利用螞蟻獲取的每個解，對局部進行檢測，尋找局部最優，從而提升解的品質。如今，蟻群算法已頻繁出現在專業學術會議上，許多關于蟻群算法的論文也被發表在Nature、Generation Computer System等專業的學術刊物上，許多計算機學者對其研究十分熱切。

針對蟻群算法的缺陷，國內的研究人員也有著不同的解決策略，其中吳慶洪等[6]提出將突變機制應用于蟻群算法中，提高算法收斂速率；王穎等[7]提出針對參數的自適應調整，解決不易求得全局最優的不足；李擎等[8]利用蟻群算法易于與其他方法結合的特點，結合粒子群與蟻群，改進了信息素的更新策略，對性能進行了一定的提升。

1 相關理論與技術基礎

1.1 ACO 算法

1.1.1 ACO 算法簡述

對ACO 算法的具體過程進行參數設置，設τij為0，螞蟻數目為m。第k（k=1，2，…，m）只的每一步選擇由信息素濃度決定，其狀態轉移概率為，計算公式為：

其中，ak={1，2，…，n}－tabuk為下一次可選擇的所有城市的集合，tabuk則是螞蟻k當前已經過的城市，它會隨著ACO 算法的運行而有一定變化。i代表螞蟻當前所位于的城市，j為集合tabuk中的一員，為螞蟻k由城市i轉移至下一個城市j的概率，為螞蟻從城市i去往j的期望程度，τij為路徑（i，j）上的信息素軌跡強度。由公式1 可知，與[τij（t）]α[ηij（t）]β的關系成正比例，因此當螞蟻進行路徑的選擇時會優先挑選信息素濃度較高的城市進行轉移[9]。

1.1.2 ACO 算法優點與缺陷

ACO 算法作為仿生算法，繼承了螞蟻行為的諸多特點，有以下幾點優點：①本質并行性。多個螞蟻個體可位于多點同時進行搜索，相當于多項代理的分布式系統，具有較高的算法運行效率。②易與其他算法相結合。以ACO 算法為基礎，引入其他算法的優秀機制與之進行互補，可進一步提升算法質量。③強魯棒性。ACO 算法只需進行很小的改動便能使用在其他方面，有助于拓寬使用領域范圍。

ACO 算法作為新生代仿生算法，仍有著一些缺陷，主要有：①不易取得最優解。由于ACO 算法的特性，信息素在運行時較易集群在個別路段上，從而陷入局部最優。②求解時間長。構造解的過程需要很大的計算量，當待解決問題需要構造的可行解數目增多時，螞蟻尋找最優解所需要的時間將會變長。③參數的設置理論不足。ACO 算法的性能與關鍵參數息息相關，目前還沒有對參數的設置給出嚴密的理論認證，多依賴實驗經驗而定[10-11]。

1.2 GA 算法

1.2.1 GA 算法簡述

GA 算法由HOLLAND 在1975 時首次提出，該算法參照的是達爾文的“優勝劣汰” 進化論原則。在遺傳算法的實現過程中，通過計算適應度函數所獲取的結果可較為直觀地判斷出種群個體（染色體）適應度的強弱程度，從而決定它們的存留[12]。

1.2.2 遺傳算法步驟

遺傳算法步驟如下。

步驟1：初始化種群。設置參數，選擇合適的編碼方式，產生非固定數據并進行組合來獲取初始種群。

步驟2：計算適應度值。使用適應度函數獲取值后，選擇后續操作個體。

步驟3：執行交叉運算。

步驟4：執行變異運算。

步驟5：判斷是否能夠結束，若滿足條件則輸出結果，否則回到步驟2，最終得出最優解。

1.3 TSP 問題

TSP 問題指有N個城市，由初始位置出發，遍歷每一個城市，不能重復，且最終回到原來出發點的問題，同時需找到在過程中所付出的代價最小，即最短的路徑。TSP 問題雖然描述起來并不困難，但是要獲取其精確的解卻并不是一件容易的事情，單是其所有可行路徑就有（n－1）！/2 條，學術界將其稱為NP-Hard問題[13-14]。

TSP 是NP 完全問題，若一種算法在對解決TSP應用而言表現良好，則通常在解決其他的應用上也可以獲得不錯的結果，因此以TSP 問題來驗證算法的改進是否有效是比較可靠的[15-16]。

2 ACO-GA 混合算法及其在TSP 中的應用

2.1 ACO-GA 混合算法

2.1.1 ACO-GA 混合算法原理

ACO-GA 混合算法將ACO 算法和GA 算法進行結合，每進行一次迭代，最差螞蟻個體就會被最好染色體所取代，替換后的解影響了信息素矩陣，從而影響最后所求最優解。同時，在迭代過程中融入輪盤賭算法，讓適應值與個體選中概率成正比。

2.1.2 ACO-GA 混合算法步驟

ACO-GA 混合算法步驟如下。

步驟1：初始化算法參數。將Nc（迭代次數）置0，初始化τij和Δτij，對m、ρ、α、β、Q、Ncmax等參數賦值，設置啟發值和信息素矩陣。

步驟2：初始化種群。編碼并產生隨機數據并進行組合來生成初始種群，初始化染色體。

步驟3：執行染色體選擇、變異、交叉、解碼操作。

步驟4：解空間的構建。將m個螞蟻分配到n個城市，并根據狀態轉移概率對未經過的城市進行計算，并在其中選擇算得的概率最大的城市逐步進行下一步的轉移，該過程持續至螞蟻遍歷完所有的城市為止。最終每個成員都遵循規則獲取了一條路徑，在路徑表中實現更新路徑。

步驟5：如果蟻群的搜索未完成，那么就跳轉到步驟4，繼續進行循環搜索。

步驟6：執行染色體選擇操作。

步驟7：進行總路程的計算，使用最好染色體取代最差螞蟻，更新信息素矩陣。

步驟8：當Nc≥Ncmax，即算法循環迭代次數已到達設定的最大值，終止條件已滿足，則循環結束并輸出計算結果；否則，跳轉至步驟3。

2.2 改進算法在TSP 問題中的應用

2.2.1 仿真實驗

本文從通用TSPLⅠB 庫中選取了eil51、rand75、eil76、pr152、bier127 等10 個實例，算例名稱即為城市數目，分別對ACO 算法和ACO-GA 混合算法的性能進行測試，對比分析ACO 與ACO-GA 混合算法的仿真實驗結果。

ACO 算法參數設置：α=1，β=3，ρ=0.4，m=城市數，Q=100，迭代次數為200。

ACO-GA 混合算法的參數設置：α=1，β=3，ρ=0.4，m=城市數，Q=100，Pc=0.6，Pm=0.02，迭代次數為200。

每組測試案例獨立運行20 次，選擇其中最佳優化路線，即20 次尋優中求解出的距離最短的一次。

2.2.2 測試結果與分析

分別對ACO 算法和ACO-GA 混合算法的數據進行整理，保留4 位小數，結果如表1 和表2 所示。

表2 ACO-GA 混合算法在TSP 問題中的實現

3 實驗結果分析

運行時間對比。ACO-GA 混合算法和ACO 算法的運行時長均隨著城市問題量的擴大而擴大。當城市規模較小、循環次數相同時，2 種算法在運行時間上并未有明顯差距。但當測試數據達到并超過eil51 時，ACO-GA 混合算法的求解速度體現了明顯優勢，且隨規模增大，優勢更加明顯。

最優解對比。ACO-GA 混合算法整體上獲取的最優解值較ACO 算法好。

最差解對比。從表1、表2 可知，ACO 算法獲得的最差解大于ACO-GA 混合算法，且與最優解差異較大。表明ACO-GA 混合算法較均勻，尋優效果較好。