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

圣文順，徐愛萍，徐劉晶

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

1 引言

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

2 蟻群算法及遺傳算法

2.1 蟻群算法

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

圖1 蟻群算法示意圖

(1)

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

(2)

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

(3)

(4)

其中，Q是常數(shù)，Lk為螞蟻k在本次循環(huán)中所走路徑的總長度。

2.2 遺傳算法

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

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

遺傳算法具有與領(lǐng)域無關(guān)的群體性全局搜索能力，并且它的過程簡單，可擴展性強，易于與其它優(yōu)化技術(shù)結(jié)合。

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

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

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

圖2 ACAG算法流程圖

4 基于ACAG求解TSP問題

4.1 ACAG中的蟻群算法規(guī)則

1)貪心策略

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

(5)

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

2)信息素更新策略

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

(6)

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

當(dāng)所有螞蟻完成一次循環(huán)以后，要對信息量進行全局更新，這里只對每次循環(huán)M最優(yōu)路徑上的信息量進行更新以強化最優(yōu)解。如下式

(7)

4.2 ACAG中的遺傳算法規(guī)則

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

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

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

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

經(jīng)過交叉操作后可得

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

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

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

首先執(zhí)行蟻群算法，并動態(tài)生成遺傳算法所需的初始種群，直到達到轉(zhuǎn)化條件為止，然后執(zhí)行遺傳算法直到結(jié)束。

1)蟻群算法部分

①初始化蟻群算法各參數(shù)，設(shè)置蟻群算法結(jié)束條件；

②反復(fù)執(zhí)行下列操作，直到滿足轉(zhuǎn)化條件：

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

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

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

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

e. 當(dāng)m只螞蟻完成一次周游以后，計算每只螞蟻所經(jīng)過的路徑長度，找到本輪最短路徑lmin，并與已得到的最優(yōu)長度lshortest相比較，若有l(wèi)min

f. 更新二維數(shù)組C；

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

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

2)遺傳算法部分

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

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

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

⑥反復(fù)執(zhí)行下列操作，直到達到最大遺傳代數(shù)[15]：

a. 根據(jù)個體適應(yīng)度計算每個個體被選擇的概率pi；

b. for(k=0；k

{

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

產(chǎn)生隨機數(shù)rand∈(0，1)；

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

}

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

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

e.f++；

⑦算法結(jié)束，輸出最優(yōu)長度和最優(yōu)路徑表。

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

圖3 ACAG算法遍歷旅行商問題優(yōu)化結(jié)果

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

5 實驗結(jié)果及分析

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

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

表1 三種算法的對比結(jié)果

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

圖5 三種算法優(yōu)化eil51的收斂特性比較

圖6 三種算法優(yōu)化pr107的收斂特性比較

由于對算法中各參數(shù)的確定并沒有嚴(yán)格的理論指導(dǎo)，都是通過實驗確定的，所以對不同TSP問題參數(shù)選取略有不同。如對eil51選取的參數(shù)如下：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選取的參數(shù)為：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可以看出，傳統(tǒng)蟻群算法和遺傳算法的收斂性大致相當(dāng)，而本文算法的優(yōu)勢很明顯，經(jīng)較少次數(shù)就能找到最優(yōu)解。如圖5中本文算法僅需10次就取得了437的值，而傳統(tǒng)蟻群算法和遺傳算法則需要幾百次才能找到這樣的值。

6 結(jié)語

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