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

劉子墨

（首都經(jīng)濟貿(mào)易大學管理工程學院，北京 100070）

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

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

1 相關(guān)理論與技術(shù)基礎

1.1 ACO 算法

1.1.1 ACO 算法簡述

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

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

1.1.2 ACO 算法優(yōu)點與缺陷

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

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

1.2 GA 算法

1.2.1 GA 算法簡述

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

1.2.2 遺傳算法步驟

遺傳算法步驟如下。

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

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

步驟3：執(zhí)行交叉運算。

步驟4：執(zhí)行變異運算。

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

1.3 TSP 問題

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

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

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

2.1 ACO-GA 混合算法

2.1.1 ACO-GA 混合算法原理

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

2.1.2 ACO-GA 混合算法步驟

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

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

步驟2：初始化種群。編碼并產(chǎn)生隨機數(shù)據(jù)并進行組合來生成初始種群，初始化染色體。

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

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

步驟5：如果蟻群的搜索未完成，那么就跳轉(zhuǎn)到步驟4，繼續(xù)進行循環(huán)搜索。

步驟6：執(zhí)行染色體選擇操作。

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

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

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

2.2.1 仿真實驗

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

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

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

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

2.2.2 測試結(jié)果與分析

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

表2 ACO-GA 混合算法在TSP 問題中的實現(xiàn)

3 實驗結(jié)果分析

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

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

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