基于蟻群算法與遺傳算法的TSP路徑規劃仿真

圣文順，徐愛萍，徐劉晶

(1. 南京工業大學浦江學院，江蘇 南京 211200；2. 武漢大學計算機學院，湖北 武漢 430072)

1 引言

蟻群算法和遺傳算法都是通過模擬自然界某種生物現象而得到的一種進化算法，它們在組合優化、規劃策略等領域都表現出了各自的優越性。蟻群算法利用正反饋機制[1]，能較快地向較優解收斂，但易出現早熟、停滯現象；而遺傳算法具有較強的全局搜索能力，可避免陷入局部最優。本文通過兩種算法的結合，發揮各自優勢，在加速收斂的同時有效地避免了陷入局部最優。另外通過引入貪心策略[2]，極大地提高了搜索速度，并在一定程度上解決了螞蟻算法在搜索初期由于信息素缺乏進化緩慢的問題。實驗表明，在求解旅行商問題時，與傳統的蟻群算法和遺傳算法相比，本文算法優勢較為明顯。

2 蟻群算法及遺傳算法

2.1 蟻群算法

蟻群算法(ACA)是由意大利學者M.Dorigo提出的一種新型模擬進化算法[3]。實驗觀察表明，螞蟻在其經過的路徑上會留下一種揮發性分泌物(即信息素[4]，pheiomcme)，后續的螞蟻會根據信息素的強度自主選擇要經過的路徑，通常的策略就是螞蟻會選擇信息素強度較大的路徑行走。蟻群的這種集體行為可以理解為一種信息的正反饋機制的形成，螞蟻通過該機制來定位通向目的地的最短路徑，如圖1所示。

圖1 蟻群算法示意圖

(1)

τij(t+1)=(1-ρ)τij(t)+Δτij

(2)

其中ρ∈(0，1)，表示信息量的衰減程度。信息量增量Δτij可表示為：

(3)

(4)

其中，Q是常數，Lk為螞蟻k在本次循環中所走路徑的總長度。

2.2 遺傳算法

遺傳算法(Genetic Algorithm，簡稱GA)最早于1975年由美國Michigan大學的J.Holland首先提出[6]，該算法基于達爾文的進化論，模擬了自然選擇、物競天擇和適者生存，通過N代的遺傳、變異、交叉、復制，進化出問題的最優解，是模擬生物遺傳選擇和優勝劣汰進化過程的一個計算模型。

遺傳算法的處理流程是將所求問題的每個可能解都看作是一個染色體個體，將可能解個體進行特定編碼，多個可能解個體即構成了一個群體。初始情況下，一般是隨機產生一個群體，根據初始群體中每個個體的適應度利用遺傳算子進行選擇(Selection)、交叉(Crossover)和變異(Mutation)操作，對它們進行重新組合，進而得到一個新的群體。新的群體由于繼承了上一代的優良特性，產生了一些向好的變化，從而逐步向著更優解的方向進化。

遺傳算法具有與領域無關的群體性全局搜索能力，并且它的過程簡單，可擴展性強，易于與其它優化技術結合。

3 蟻群算法與遺傳算法的融合

蟻群算法主要利用信息正反饋原理強化較優解，當進化到一定代數后螞蟻將聚集于信息量高的部分路徑上，易出現早熟、停滯現象，陷入局部最優。為解決該問題，本文利用遺傳算法具有隨機選擇性高、全局搜索能力強的特點，在蟻群算法進化到一定代數后，動態過渡到遺傳算法，從而有效避免陷入局部最優的困境。具體方法是這樣的：設定蟻群算法最小進化率Antmin-ratio，如果連續Antmax代沒有得到更優解或者更優解的進化率都小于Antmax-ratio，說明蟻群算法很可能已陷入局部最優，這時就自動過渡到遺傳算法。遺傳算法的初始群體在蟻群算法運行過程中動態生成，建立一個N×n的二維數組C，N為群體規模，n為染色體長度(城市個數)，每巡游完一次就對每只螞蟻所經路徑的長度進行計算，找出本輪最小值，并與數組C中的每個染色體所對應的路徑長度相比較，如果這個最小值小于某個染色體所對應路徑的長度，則用這個最小值對應的路徑替換掉該染色體。

本文把融合了這兩種算法的算法稱為ACAG算法(the Algorithm Combined by ACA and GA)，圖2為ACAG算法簡要流程圖。

圖2 ACAG算法流程圖

4 基于ACAG求解TSP問題

4.1 ACAG中的蟻群算法規則

1)貪心策略

根據文獻[7]，在一條遍歷所有城市的較優路徑中，城市i連接到城市j，j不可能是離城市i最遠的那些城市。所以，把下一個城市的選擇范圍限定在離當前城市最近的w個城市中，只需對這部分城市的轉移概率計算即可。在選擇下一城市時，先找到離當前城市最近的w個城市，然后在這w個城市中找出螞蟻本輪還未曾走過的h個城市。在h個城市中，按式(5)選擇下一城市j。

(5)

貪心策略的采用，由于把可選擇城市限定在一定范圍內，使得搜索速度大大提高，并同時解決了螞蟻算法搜索初期由于信息素缺乏進化緩慢的問題。

2)信息素更新策略

由于采用了貪心策略，螞蟻會集中在相對較優的幾條路徑上，如果按傳統的信息素局部更新方法，這幾條路徑上的信息素會迅速增加，從而導致過早陷入局部最優。為盡量避免這種情況，這里采用如下方法進行局部更新。

(6)

其中，τ0表示每條邊上所允許的信息量最大值，Q1、Q2是可以設定的常量，Q2取值一般要比Q1大，當某條路徑上的信息量大于τ0時，就較大幅度地削減其信息量，從而使螞蟻選擇其它路徑的概率增加。

當所有螞蟻完成一次循環以后，要對信息量進行全局更新，這里只對每次循環M最優路徑上的信息量進行更新以強化最優解。如下式

(7)

4.2 ACAG中的遺傳算法規則

遺傳編碼：采用最自然的路徑表達方式，如城市的編號為{1，2，3，4，5，6，7}，則某個染色體的編碼位串可能為(3 2 5 1 4 7 6)，表示按順序3-2-5-1-4-7-6來訪問各城市。

適應函數：設路徑總長度為f(n)，設置適應函數為1/f(n)，函數值越大表示路徑越短，適應度越大，個體被選取的概率也就越大[9]。

交叉算子：采用由Davis提出的OX算子[10-11]。通過從一個親體中挑選一個子序列并保存另一個親體的城市相對次序來構造后代，例如兩個親體(兩個“|”之間為挑選出的子序列)

p1=(1 2 3 | 4 5 6 7 | 8 9)=(4 5 2 | 1 8 7 6 | 9 3)

經過交叉操作后可得

變異算子：在染色體上隨機地選擇兩點，然后對兩點間的子串進行如下操作：從第一個城市開始，依次交換兩個鄰接城市的順序，若能改善解則交換，否則不交換，直到子串的最后兩個城市[12]。這樣能提高遺傳算法的局部搜索能力。

選擇算子：采用遺傳算法中應用最廣的賭輪盤選擇策略[13]。

4.3 ACAG求解TSP問題的算法過程

首先執行蟻群算法，并動態生成遺傳算法所需的初始種群，直到達到轉化條件為止，然后執行遺傳算法直到結束。

1)蟻群算法部分

①初始化蟻群算法各參數，設置蟻群算法結束條件；

②反復執行下列操作，直到滿足轉化條件：

a. 將m只螞蟻隨機分布在n個城市中并設置到禁忌表中；

b. 對于每一只螞蟻，按貪心策略選取下一城市j，選擇完后將j加入禁忌表tabuk；

c. 當每一只螞蟻走完一條邊以后，按式(6)進行信息素局部更新；

d. 重復b.和c.，直到所有螞蟻完成一次周游為止；

e. 當m只螞蟻完成一次周游以后，計算每只螞蟻所經過的路徑長度，找到本輪最短路徑lmin，并與已得到的最優長度lshortest相比較，若有lmin

f. 更新二維數組C；

g. 按式(7)進行信息素全局更新；

h. 清空并初始化禁忌表。

2)遺傳算法部分

③設置雜交概率pc和變異概率pm，設置最大遺傳代數[14]；

④初始群體P(0)(t=0)由二維數組C表示，群體規模為N；

⑤計算P(0)中每個個體的適應度；

⑥反復執行下列操作，直到達到最大遺傳代數[15]：

a. 根據個體適應度計算每個個體被選擇的概率pi；

b. for(k=0；k

{

根據每個個體的Pi及賭輪盤規則在P(t)中選擇兩個父體；

產生隨機數rand∈(0，1)；

if(rand≤pc)，對兩個父體進行交叉操作，將兩個后代加入到新群體P(t+1)中；

}

c. 對P(t+1)中的每個個體按概率pm進行變異操作[16]；

d. 計算P(t+1)中每個個體的適應度，并更新最優長度lshortest和最優路徑表；

e.f++；

⑦算法結束，輸出最優長度和最優路徑表。

按照以上算法步驟在MATLAB運行實驗，所得結果如圖3、圖4。其中圖3為城市中各點分布坐標，紅色線段為起始坐標點(城市)的連線。圖4為路徑長度變化曲線，可獲得最優長度及最優長度所對應的迭代次數。

圖3 ACAG算法遍歷旅行商問題優化結果

圖4 ACAG算法中路徑長度變化曲線及規律

5 實驗結果及分析

利用Java程序分別實現了傳統蟻群算法和遺傳算法以及上述ACAG算法，并從TSPLIB實例庫[17]下載了多個典型的TSP問題進行實驗，都取得了比較好的結果。表1是三種算法的對比測試結果。表中第二列是指到目前為止對某個TSP問題已知的最優解，第四列表示各算法得到的最優解，最后一列表示達到最優解的平均迭代次數，ACA、GA和ACAG分別表示傳統蟻群算法、傳統遺傳算法和本文算法。各個問題名稱中的數字即所包含的城市數。

由表1可以看出，本文算法具有較強搜索最優解的能力，在berlin52、dl98、lin318三個典型的TSP問題中，采用本文算法得到的最優解與目前此TSP問題最優解最為接近，在berlin52問題中，兩者數值相等。在蟻群算法階段通過引入貪心策略大大加快了收斂速度，經較少的迭代次數能找到最優解。對問題lin318，傳統蟻群算法和遺傳算法分別需要5000多次和6000多次才能找到最優解，而本文算法僅需2000次左右。

表1 三種算法的對比結果

另外，圖5、圖6還給出了三種算法求解同一TSP問題的收斂特性比較。圖中橫坐標表示迭代次數，縱坐標表示路徑長度，曲線1對應的是本文算法，曲線2對應的是蟻群算法，曲線3對應的是遺傳算法。圖5是eil51的收斂過程，圖6是prl07的收斂過程。

圖5 三種算法優化eil51的收斂特性比較

圖6 三種算法優化pr107的收斂特性比較

由于對算法中各參數的確定并沒有嚴格的理論指導，都是通過實驗確定的，所以對不同TSP問題參數選取略有不同。如對eil51選取的參數如下：m=30，w=5，q0=0.8，β=3，ρ=0.15，Q=1000，Q1=1，Q2=5，Antmax=60，Antmin-ratio=1%，N=50，pc=0.8，pm=0.3。而對prl07選取的參數為：m=70，w=10，q0=0.8，β=3，ρ=0.1，Q=10000，Q1=10，Q2=100，Antmin-ratio=2%，N=50，pc=0.8，pm=0.15。

由圖5、圖6可以看出，傳統蟻群算法和遺傳算法的收斂性大致相當，而本文算法的優勢很明顯，經較少次數就能找到最優解。如圖5中本文算法僅需10次就取得了437的值，而傳統蟻群算法和遺傳算法則需要幾百次才能找到這樣的值。

6 結語

本文對蟻群算法和遺傳算法進行了有效結合，利用各自優勢，在加速收斂的同時有效避免了陷入局部最優，并通過實驗證明達到了預期效果。但該算法中的參數較多，不易控制，需經過反復實驗尋找最優參數組合，在接下來的工作中需要對這些參數的選擇作進一步的深入研究。