改進(jìn)蟻群算法在TSP中的應(yīng)用研究

鄭娟毅，程秀琦，付姣姣

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

1 引言

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

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

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

2 TSP關(guān)鍵算法

2.1 蟻群算法

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

2.2 遺傳算法

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

3 混合遺傳蟻群算法

3.1 算法原理

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

3.2 算法步驟

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

步驟1：編碼，對(duì)于包含n個(gè)城市的TSP問題[17]，使用長(zhǎng)度為n的數(shù)組表示該問題的一個(gè)解，采用隨機(jī)鍵編解碼方法編碼。

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

步驟3：計(jì)算適度值，使用輪盤賭規(guī)則進(jìn)行選擇操作，對(duì)于當(dāng)前種群中的N個(gè)染色體，第i個(gè)染色體被選擇的概率值為

(1)

其中，f(·)表示目標(biāo)函數(shù)，即解xi對(duì)應(yīng)的路徑長(zhǎng)度。

步驟4：采用線性交叉，對(duì)于兩個(gè)染色體xi和xj(i=j)，線性交叉實(shí)現(xiàn)如下

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

其中，λ表示區(qū)間[0，1]上的隨機(jī)數(shù)。

步驟5：GA算法高斯變異，對(duì)于一個(gè)染色體xi，其變異個(gè)體為

步驟6：開始迭代，判斷是否到達(dá)最大迭代次數(shù)，到達(dá)最大迭代次數(shù)，進(jìn)入下一步，否則跳到步驟3。

步驟7：迭代結(jié)束后，得到優(yōu)化解，用優(yōu)化解來初始化信息素初始值，并初始化蟻群算法參數(shù)，螞蟻個(gè)數(shù)m和城市個(gè)數(shù)n，引導(dǎo)m個(gè)螞蟻移動(dòng)到n個(gè)節(jié)點(diǎn)上。

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

步驟9：螞蟻根據(jù)狀態(tài)轉(zhuǎn)移公式開始尋路。

步驟10：當(dāng)單個(gè)螞蟻完成路徑搜索時(shí)，進(jìn)行局部信息素更新，當(dāng)所有螞蟻完成路徑搜索時(shí)，進(jìn)行全局信息素更新。

步驟11：查看迭代次數(shù)是否到達(dá)最大值，若不小于最大值，則直接輸出結(jié)果，否則，轉(zhuǎn)到步驟9繼續(xù)執(zhí)行。

步驟流程圖如圖1。

圖1 GA-ACO算法流程圖

3.3 仿真結(jié)果與分析

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

為了驗(yàn)證所提混合遺傳蟻群算法(GA-ACO)的性能，共進(jìn)行三個(gè)實(shí)驗(yàn)：

實(shí)驗(yàn)中要用到的參數(shù)設(shè)置如下：

蟻群算法參數(shù)：螞蟻個(gè)數(shù)m為具體問題中城市個(gè)數(shù)，局部信息素?fù)]發(fā)系數(shù)ρ=0.45全局信息素?fù)]發(fā)系數(shù)ξ=0.25，信息素啟發(fā)因子α=2，期望值啟發(fā)因子β=3，Lnn為最優(yōu)路徑長(zhǎng)度，在不同的城市數(shù)據(jù)下，最優(yōu)路徑長(zhǎng)度不同。在本實(shí)驗(yàn)中用到的三個(gè)數(shù)據(jù)源att48、oliver30、eil76最優(yōu)值依次為10628、423和538。最大迭代次數(shù)MaxStep=800。

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

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

3.3.1 實(shí)驗(yàn)1

對(duì)蟻群算法、遺傳算法和混合蟻群算法分別在att48數(shù)據(jù)中求解，比較各算法對(duì)于att48問題最優(yōu)解的逼近程度，見表1。

表1 實(shí)驗(yàn)1結(jié)果表

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

再比較下混合遺傳蟻群算法和蟻群算法、遺傳算法的結(jié)果，由上表可知，混合遺傳蟻群算法迭代時(shí)間相對(duì)于蟻群算法較慢，相對(duì)于遺傳算法較快。這是由于混合遺傳蟻群算法要先跑若干代遺傳算法，求出較好的染色體，接著初始化信息素，再進(jìn)行蟻群算法的迭代，因此相對(duì)于單純的蟻群算法而言，迭代時(shí)間更長(zhǎng)，但是由于遺傳算法一開始迭代快，蟻群算法在有較好的信息素初值時(shí)，正反饋?zhàn)饔檬沟盟惴ǖ俣纫矔?huì)加快，因此，混合遺傳蟻群算法融合了兩者的優(yōu)點(diǎn)，比單純的遺傳算法要快。至于最優(yōu)解的精度，混合蟻群遺傳算法要比遺傳算法和蟻群算法好，因?yàn)榛旌线z傳蟻群算法相當(dāng)于一個(gè)蟻群算法有了更好的初值，這種算法陷入局部最優(yōu)的概率就會(huì)變小，因此求解精度更高。

從另一個(gè)角度來看，混合蟻群遺傳算法也可以理解為加入了正反饋機(jī)制的遺傳算法，相較于基本的遺傳算法，節(jié)約了很多迭代時(shí)間。接下來通過實(shí)驗(yàn)驗(yàn)證800代的混合算法相當(dāng)于多少代的遺傳算法的效果。選擇2000代作為實(shí)驗(yàn)對(duì)象。見表2。

表2 2000代實(shí)驗(yàn)結(jié)果表

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

1)att48城市示意圖

圖2 att48城市示意圖

2)ACO算法優(yōu)化結(jié)果圖

圖3 ACO算法優(yōu)化結(jié)果圖

3)GA算法優(yōu)化結(jié)果圖

圖4 GA算法優(yōu)化算法結(jié)果圖

4) GA-ACO算法優(yōu)化結(jié)果圖

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

由圖5可看出，基礎(chǔ)GA在迭代剛開始時(shí)，迭代速度很快，隨著迭代的進(jìn)行，初始GA會(huì)陷入十分平穩(wěn)的階段，這一階段屬于無用迭代，無用迭代結(jié)束后，通過交叉算子和變異算子，基本GA向著最優(yōu)解的方向繼續(xù)迭代，但是又陷入了更長(zhǎng)時(shí)間的平穩(wěn)迭代過程，由于此實(shí)驗(yàn)只迭代了800代，所以在GA迭代到800代時(shí)，其實(shí)它還處于無用的迭代狀態(tài)，但是終止條件滿足，因此退出了迭代，它的最優(yōu)解精度比不上ACO和GA-ACO的精度。

圖5 GA-ACO算法優(yōu)化結(jié)果圖

圖6 迭代次數(shù)比較圖

ACO一開始迭代沒有GA快，但是當(dāng)ACO中每條路徑上信息素累計(jì)程度趨于穩(wěn)定時(shí)，ACO在正反饋的作用下，迭代速度加快，向著最優(yōu)解的方向迭代。800代對(duì)于一個(gè)ACO算法來說足夠了，因?yàn)锳CO在趨于最優(yōu)值后，信息素濃度越高的路徑，螞蟻經(jīng)過這條路徑的概率也越大，并且由于經(jīng)過的螞蟻多，信息素濃度也在不斷增加，最后幾乎所有的螞蟻都會(huì)選擇走信息素濃度最高的路徑，最終算法趨于穩(wěn)定。

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

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

3.3.2 實(shí)驗(yàn)2

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

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

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

表3 oliever30和eli76實(shí)驗(yàn)結(jié)果表

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

3.3.3 實(shí)驗(yàn)3

將混合遺傳蟻群算法運(yùn)行20次，查看最優(yōu)解的范圍，驗(yàn)證此算法是否穩(wěn)定。

一個(gè)算法的性能好壞，一方面體現(xiàn)在最優(yōu)解的精度上，另一方面體現(xiàn)在算法的穩(wěn)定性?；旌线z傳蟻群算法在蟻群算法和遺傳算法處理同一問題時(shí)表現(xiàn)出較好的性能，但是穩(wěn)定性并不確定，此處做30次針對(duì)att48問題的GA-ACO算法，對(duì)結(jié)果進(jìn)行分析。見表4。

表4 GA-ACO 30次實(shí)驗(yàn)結(jié)果表

從表中可知，30次計(jì)算結(jié)果的平均值為11058.2667，從表中數(shù)據(jù)來看，大多數(shù)數(shù)據(jù)集中在這個(gè)范圍內(nèi)，因此本文認(rèn)為混合遺傳蟻群算法是穩(wěn)定的。

4 結(jié)語

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

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

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