改進蟻群算法在TSP中的應用研究

鄭娟毅，程秀琦，付姣姣

(西安郵電大學通信與信息工程學院，陜西 西安 710121)

1 引言

近些年來，隨著我國經濟水平的增長，許多家庭都擁有了私家車，而且大量人口涌入城市，導致城市人口激增。但是城市的土地資源和交通資源有限，這種情況下，交通這種虛擬物品便“供不應求”。城市的交通設施漸漸負載不了日益增加的汽車和日益增多的人口，嚴重影響了城市人民的生活感受，城市的交通問題如何解決迫在眉睫。我國城市還正處于老城改造、新城建設的時期，這一時期正是實現生態城市、綠色交通的最佳時機[1]。因此，解決交通問題既是時代需求，也是城市發展的需求。

為了解決以上交通問題，智能交通應運而生。智能交通系統[2](Intelligent Transportation System，簡稱ITS)是一種在大范圍內、全方位發揮作用的，實時、準確、高效的綜合交通運輸管理系統[3]。在智能交通管理系統中，動態路徑誘導系統DGRS[4][5](Dynamic Route Guidance System，簡稱DRGS)是很重要的組成單元。動態路徑誘導系統的核心之一為路徑誘導算法[6]，其中比較常見的算法有最短路徑算法，蟻群算法、遺傳算法等。

姜波清[7]等人提出了一種基于混合蟻群粒子群的動態路徑規劃方法，該方法在城市路徑規劃中證明是行之有效的，但是存在路徑權值設置不優，混合算法對比算法少，說服力不強等缺點；鄧慧允[8]等人提出了一種用遺傳算法來優化蟻群算法，通過尋找最優參數和融合算法，使得蟻群算法在最優路徑規劃上收斂更快，不易陷入局部最優，但是也存在數據對比度不高，說服力不強的缺點；金仙力[9]等人研究了一種基于遺傳算法的多目標路徑優化算法，主要針對車輛路徑問題(Vehicle Routing Problem，簡稱VRP)，通過對遺傳算法的適當改進，使得遺傳算法更快收斂，很好的解決了VRP問題，但是存在應用范圍窄，算法優化程度不高的問題。本文提出的混合遺傳蟻群算法，首先通過遺傳算法改進了信息素初值，其次利用蟻群算法提高了算法迭代速度以及最優解的尋找，提高了迭代速度和精度，可以有效地提高出行的效率。

2 TSP關鍵算法

2.1 蟻群算法

蟻群算法[10](Ant Colony Algorithm，簡稱ACA)是一種仿生優化算法[11]，對于螞蟻而言，在螞蟻覓食過程中，真正起到關鍵作用的是一種被稱作“信息素”[12]的物質，隨著螞蟻多次搜索，越短的路徑經過的螞蟻越多，相應殘留在路徑上的信息素濃度會越來越高，路徑上的信息素濃度越高，螞蟻選擇這條路徑的概率就越大。由于信息素濃度初值的不確定性，正反饋有時會導致局部最優，但是在具有較好的初值時，算法收斂速度加快，能夠迅速找到極值。

2.2 遺傳算法

遺傳算法[13](Genetic Algrithm，簡稱GA)的核心在于適應度函數的設計，遺傳算法在一開始迭代速度很快，因為選擇算子是根據適度值來確定選擇概率的，遺傳算法要進行交叉和變異，隨著代數增加，遺傳算法會在某些代陷入平穩迭代狀態，將一直沒有更優秀的個體產生[14]，但是遺傳算法由于交叉因子和變異算子的存在，使得種群中每個解都有可能被搜索到，擴大了全局搜索的范圍，不易陷入局部較好解，這種特性使得遺傳算法很適合用來尋找初值。

3 混合遺傳蟻群算法

3.1 算法原理

混合遺傳蟻群(GA-ACO)算法[15]的原理是：在算法的初期，使用遺傳算法對種群進行初始化，由于遺傳算法初期收斂速度快，易得到較好值，使用遺傳算法迭代一定的代數，經過一段時間后，種群中會剩下很多優秀的染色體[16]。接下來，遺傳算法產生的較好解，作為蟻群算法中信息素的初始信息，然后再進行蟻群算法的迭代，這種情況下，蟻群算法由于具有較好的初值，不易陷入局部最優，得到的最優解也更加貼近于實際的最優解。

3.2 算法步驟

混合遺傳蟻群算法(GA-ACO)的步驟和實現流程：

步驟1：編碼，對于包含n個城市的TSP問題[17]，使用長度為n的數組表示該問題的一個解，采用隨機鍵編解碼方法編碼。

步驟2：各種參數初始化。設置遺傳算法最大迭代次數NGmax，種群數量設置為城市數量m，交叉概率pc、變異概率pm選取第三章驗證的最佳值，設置適度值函數，針對TSP問題，適度值函數即為城市之間最短距離的倒數。

步驟3：計算適度值，使用輪盤賭規則進行選擇操作，對于當前種群中的N個染色體，第i個染色體被選擇的概率值為

(1)

其中，f(·)表示目標函數，即解xi對應的路徑長度。

步驟4：采用線性交叉，對于兩個染色體xi和xj(i=j)，線性交叉實現如下

xid=λ·xid+(1-λ)·xjd，i=1，2，…，N;d=1，2，…，D

其中，λ表示區間[0，1]上的隨機數。

步驟5：GA算法高斯變異，對于一個染色體xi，其變異個體為

步驟6：開始迭代，判斷是否到達最大迭代次數，到達最大迭代次數，進入下一步，否則跳到步驟3。

步驟7：迭代結束后，得到優化解，用優化解來初始化信息素初始值，并初始化蟻群算法參數，螞蟻個數m和城市個數n，引導m個螞蟻移動到n個節點上。

步驟8：設置蟻群算法最大迭代次數NAmax，信息素常量Q，信息素因子α，期望值啟發因子β，局部信息素揮發系數ρ，全局信息素揮發系數ξ。

步驟9：螞蟻根據狀態轉移公式開始尋路。

步驟10：當單個螞蟻完成路徑搜索時，進行局部信息素更新，當所有螞蟻完成路徑搜索時，進行全局信息素更新。

步驟11：查看迭代次數是否到達最大值，若不小于最大值，則直接輸出結果，否則，轉到步驟9繼續執行。

步驟流程圖如圖1。

圖1 GA-ACO算法流程圖

3.3 仿真結果與分析

本文算法參數仿真均以TSPLIB中的att48問題作為測試數據，TSPLIB是一個包含旅行商問題的各種實例數據的文件庫，att48是此文件庫中的一個數據文件，城市規模為48，官方給出的最優值為10628。(以下算法均用此數據)

為了驗證所提混合遺傳蟻群算法(GA-ACO)的性能，共進行三個實驗：

實驗中要用到的參數設置如下：

蟻群算法參數：螞蟻個數m為具體問題中城市個數，局部信息素揮發系數ρ=0.45全局信息素揮發系數ξ=0.25，信息素啟發因子α=2，期望值啟發因子β=3，Lnn為最優路徑長度，在不同的城市數據下，最優路徑長度不同。在本實驗中用到的三個數據源att48、oliver30、eil76最優值依次為10628、423和538。最大迭代次數MaxStep=800。

遺傳算法參數：交叉概率pc=0.6、變異概率pm=0.4，迭代代數為800。

混合遺傳蟻群算法參數：種群大小m為具體問題中城市個數，交叉概率pc=0.6、變異概率pm=0.4，遺傳算法最大迭代代數為200，蟻群迭代次數為NAmax=600，局部信息素揮發系數ρ=0.45，全局信息素揮發系數ξ=0.25，信息素啟發因子α=2，期望值啟發因子β=3。

3.3.1 實驗1

對蟻群算法、遺傳算法和混合蟻群算法分別在att48數據中求解，比較各算法對于att48問題最優解的逼近程度，見表1。

表1 實驗1結果表

由表1可知，在求解att48問題上，蟻群算法比遺傳算法收斂速度快，且精度較遺傳算法更好。這個結果有兩個原因：一是遺傳算法對迭代代數比較敏感，代數少時，遺傳算法進行交叉和變異的機會就少，最重要的是，遺傳算法在迭代過程中會有很多無用的迭代過程，浪費了迭代時間，因此遺傳算法迭代時間更長，另一個原因是由于蟻群算法的正反饋機制，在蟻群算法中，當信息素基本穩定后，迭代速度加快，快速找到了最優解，而遺傳算法只能通過不斷地選擇、交叉和變異來更新染色體的適度值，使之向最優解靠近，但是在800代中，這個工作可能還沒有結束，迭代次數就到頭了。因此，遺傳算法的收斂精度也沒有蟻群算法好。

再比較下混合遺傳蟻群算法和蟻群算法、遺傳算法的結果，由上表可知，混合遺傳蟻群算法迭代時間相對于蟻群算法較慢，相對于遺傳算法較快。這是由于混合遺傳蟻群算法要先跑若干代遺傳算法，求出較好的染色體，接著初始化信息素，再進行蟻群算法的迭代，因此相對于單純的蟻群算法而言，迭代時間更長，但是由于遺傳算法一開始迭代快，蟻群算法在有較好的信息素初值時，正反饋作用使得算法迭代速度也會加快，因此，混合遺傳蟻群算法融合了兩者的優點，比單純的遺傳算法要快。至于最優解的精度，混合蟻群遺傳算法要比遺傳算法和蟻群算法好，因為混合遺傳蟻群算法相當于一個蟻群算法有了更好的初值，這種算法陷入局部最優的概率就會變小，因此求解精度更高。

從另一個角度來看，混合蟻群遺傳算法也可以理解為加入了正反饋機制的遺傳算法，相較于基本的遺傳算法，節約了很多迭代時間。接下來通過實驗驗證800代的混合算法相當于多少代的遺傳算法的效果。選擇2000代作為實驗對象。見表2。

表2 2000代實驗結果表

從表2可看出，800代混合遺傳蟻群算法與2000代遺傳算法的求解精度接近，這也說明了混合遺傳蟻群算法通過引入蟻群算法的正反饋機制，避免了遺傳算法對于迭代時間的浪費。除了單純的數據，可以通過收斂曲線圖和路徑仿真圖來看蟻群算法、遺傳算法和混合遺傳蟻群算法在實際仿真中的效果。實驗結果圖如下。

1)att48城市示意圖

圖2 att48城市示意圖

2)ACO算法優化結果圖

圖3 ACO算法優化結果圖

3)GA算法優化結果圖

圖4 GA算法優化算法結果圖

4) GA-ACO算法優化結果圖

5)三種方法在att48問題上的迭代次數比較圖

由圖5可看出，基礎GA在迭代剛開始時，迭代速度很快，隨著迭代的進行，初始GA會陷入十分平穩的階段，這一階段屬于無用迭代，無用迭代結束后，通過交叉算子和變異算子，基本GA向著最優解的方向繼續迭代，但是又陷入了更長時間的平穩迭代過程，由于此實驗只迭代了800代，所以在GA迭代到800代時，其實它還處于無用的迭代狀態，但是終止條件滿足，因此退出了迭代，它的最優解精度比不上ACO和GA-ACO的精度。

圖5 GA-ACO算法優化結果圖

圖6 迭代次數比較圖

ACO一開始迭代沒有GA快，但是當ACO中每條路徑上信息素累計程度趨于穩定時，ACO在正反饋的作用下，迭代速度加快，向著最優解的方向迭代。800代對于一個ACO算法來說足夠了，因為ACO在趨于最優值后，信息素濃度越高的路徑，螞蟻經過這條路徑的概率也越大，并且由于經過的螞蟻多，信息素濃度也在不斷增加，最后幾乎所有的螞蟻都會選擇走信息素濃度最高的路徑，最終算法趨于穩定。

GA-ACO算法在開始的時候用遺傳算法來迭代，從圖5中可以看出，開始時GA-ACO的曲線和遺傳算法很類似，這是由于開始時都采用相同的選擇方式，相同的適應度函數，因此一開始全局搜索方面GA-ACO繼承了遺傳算法這一優點，在GA-ACO的遺傳算法迭代途中，也短暫出現了一小段的平穩迭代過程，平穩迭代結束后，開始按照遺傳算法求出的較優值給蟻群算法賦初值，賦了初值以后，可以看出，蟻群算法在有較好初始值的情況下，最終的精度要優于傳統的蟻群算法，雖然傳統的遺傳算法可以達到，不過要付出迭代很多次的代價。

從以上實驗可以得出結論，在TSP問題中，混合遺傳蟻群算法在求解精度上要比單純的蟻群算法和遺傳算法更好，這種算法是切實可行的。

3.3.2 實驗2

將混合遺傳蟻群算法應用于att48、oliver30和eil76等不同規模的問題，研究具體問題的規模是否對混合遺傳蟻群算法有影響。

在att48問題上，混合遺傳蟻群算法取得了不錯的效果，相較于遺傳算法，它的精度和迭代速度都得到了提升，當遺傳算法和蟻群算法混合以后，發揮了遺傳算法初始迭代快這一優點，在初始迭代若干代以后，將初始遺傳算法的最優解給蟻群算法作為信息素初始值，接著對蟻群算法求解，蟻群算法由于有了較好的初值，迭代速度加快，且精度提高，而且這一過程有效的減弱了遺傳算法平穩迭代期對迭代時間的浪費，因此混合遺傳蟻群算法迭代速度比遺傳算法快，且在同樣的代數內，迭代精度也高于遺傳算法。但是相對于蟻群算法，由于開始時運行了遺傳算法，遺傳算法具有高速初始迭代，中期平穩迭代的特性，又浪費了一些迭代時間，因此比蟻群算法迭代速度要慢。

接下來測試在不同規模上混合蟻群遺傳算法的性能，此處測試兩個規模，eli76和oliver30，分別運行10次，見表3：

表3 oliever30和eli76實驗結果表

oliver30問題的官方最優解是423，由表3可看出，10次結果中，混合遺傳蟻群算法有一次達到最優解，平均最優解為425.3，這表明混合遺傳蟻群算法很適合解決規模較小的問題，解決這類問題時，精度很高。eli76問題的官方最優解是538，10次結果中，混合遺傳蟻群算法最好的最優解是553，離官方最優解有一定差距，但差距不大，這表明對于規模稍大的問題，混合遺傳蟻群算法仍有用武之地。

3.3.3 實驗3

將混合遺傳蟻群算法運行20次，查看最優解的范圍，驗證此算法是否穩定。

一個算法的性能好壞，一方面體現在最優解的精度上，另一方面體現在算法的穩定性。混合遺傳蟻群算法在蟻群算法和遺傳算法處理同一問題時表現出較好的性能，但是穩定性并不確定，此處做30次針對att48問題的GA-ACO算法，對結果進行分析。見表4。

表4 GA-ACO 30次實驗結果表

從表中可知，30次計算結果的平均值為11058.2667，從表中數據來看，大多數數據集中在這個范圍內，因此本文認為混合遺傳蟻群算法是穩定的。

4 結語

1)本文將蟻群算法、遺傳算法混合后的算法稱為混合遺傳蟻群算法，并設計了3個實驗分別對混合遺傳蟻群算法進行了實驗仿真，實驗1測試了混合遺傳蟻群算法在TSP中的att48問題中相對于蟻群算法、遺傳算法的性能，實驗2測試了混合遺傳蟻群算法對于不同規模大小的TSP問題的性能，實驗3測試了混合遺傳蟻群算法的穩定性。最終，通過三個實驗，得出結論：混合遺傳蟻群算法迭代精度(95.96%)優于蟻群算法(94.56%)、遺傳算法(81.13%)，迭代速度快于遺傳算法，慢于蟻群算法；對于小規模的TSP問題，混合遺傳蟻群算法精度很高(99.46%)；對于大規模TSP問題，精度下降了3.49%，但是也達到了96.51%；混合遺傳蟻群算法是相對穩定的算法。

2)本文采用的主要算法為混合遺傳蟻群算法，算法雖然取得了不錯的效果，但仍有提升的空間，其它的優秀算法，如粒子群算法，魚群算法，模擬退火算法等，也可作為以后路徑優化算法結合的方向。

3)由于實際問題中需要考慮的因素有很多，而本文中，只是針對理想情況下進行仿真，后續將對真實情況進行仿真。