求解TSP 問(wèn)題的改進(jìn)蟻群算法

王 勝，譚家政，劉 勇，邱芹軍

(三峽大學(xué) 智能視覺(jué)與圖像信息研究所，湖北宜昌443002)

TSP 問(wèn)題是一個(gè)經(jīng)典的NP 難問(wèn)題，經(jīng)常被作為測(cè)試解決NP 難問(wèn)題的各種啟發(fā)式算法的案例。它對(duì)于科學(xué)和工程技術(shù)領(lǐng)域中的大量組合優(yōu)化問(wèn)題，尤其是NP 完全問(wèn)題的求解有著極為重要的價(jià)值［1］。目前，求解TSP 問(wèn)題的比較好的啟發(fā)式算法主要有粒子群算法［2］、遺傳算法、模擬退火算法、人工免疫算法和蟻群算法。在通常情況下，蟻群算法得到的最短路徑要好于其他的啟發(fā)式算法。

蟻群算法以先驗(yàn)信息和信息素的正反饋?zhàn)饔脕?lái)引導(dǎo)每只螞蟻的行為，使得蟻群整體上逐漸向全局最短路徑靠攏。但是基本蟻群算法對(duì)信息素的處理過(guò)于粗糙，對(duì)已經(jīng)尋找到的最短路徑缺乏較強(qiáng)的敏感性，使得算法的收斂速度太慢。為了加快蟻群算法的收斂速度，有學(xué)者提出了帶精英策略的蟻群算法［3］。該算法在已經(jīng)找到的最短路徑和基本蟻群算法的基礎(chǔ)上，額外加了一些信息素，雖然能使每只螞蟻向已經(jīng)找到的最短路徑進(jìn)一步靠攏，但是相對(duì)于那些在每次迭代中螞蟻?zhàn)哌^(guò)的非最短路徑，這種靠攏趨勢(shì)并不明顯。且一旦陷入了局部最優(yōu)，就很難跳出來(lái)，從而使得到全局最短路徑的概率比較低。針對(duì)這個(gè)問(wèn)題，又有學(xué)者提出了最大最小蟻群算法［4－6］。它能使每只螞蟻以較大的概率訪問(wèn)每條可能是全局最短路徑一部分的路徑，從而避免了陷入局部最優(yōu)。但是，它有一個(gè)較為明顯的缺點(diǎn)，就是降低了螞蟻在已經(jīng)得到的全局最短路徑附近較小范圍內(nèi)探索的能力，從而很大程度上降低了最大最小蟻群算法得到全局最優(yōu)解的概率。

為了加快蟻群算法的收斂速度，且使蟻群算法能以較大的概率找到問(wèn)題的全局最短路徑，近些年來(lái)，不斷有學(xué)者提出各種各樣的對(duì)蟻群算法的改進(jìn)策略。如顧軍華等提出了一種改進(jìn)的用于求解TSP 問(wèn)題的蟻群優(yōu)化算法［7－8］;李將軍等提出了采用動(dòng)態(tài)的先驗(yàn)信息權(quán)值和信息素權(quán)值的自適應(yīng)調(diào)整策略，提高了蟻群算法的求解性能［9］。

但是以上改進(jìn)算法都只是在基本蟻群算法的基礎(chǔ)上作了較小的改動(dòng)，很難從根本上解決基本蟻群算法收斂速度較慢，容易陷入局部最優(yōu)的問(wèn)題。因此筆者對(duì)蟻群算法做了一些適當(dāng)?shù)母倪M(jìn)。

1 求解TSP 問(wèn)題的改進(jìn)蟻群算法的思路

1.1 利用節(jié)約算法求初始最短路徑

改進(jìn)算法先用節(jié)約算法得到的路徑將蟻群定位在一個(gè)離全局最短路徑較近的區(qū)域，再使蟻群以較小的迭代為代價(jià)找到一個(gè)局部最短路徑，若經(jīng)過(guò)多次迭代后，蟻群沒(méi)有在該局部最短路徑附近找到一個(gè)更優(yōu)的路徑，則對(duì)次局部最短路徑及附近區(qū)域施行禁忌策略，使蟻群跳到下一個(gè)可能存在最短路徑的區(qū)域進(jìn)行搜索，快速找到下一個(gè)局部最短路徑，如此下去直到找到全局最短路徑為止。

蟻群算法很難最終收斂到全局最短路徑，其中一個(gè)很重要的原因是，它選擇的初始路徑離全局最短路徑較遠(yuǎn)，為了向全局最短路徑逐步靠攏，所要越過(guò)的局部最短路徑較多。為了彌補(bǔ)蟻群算法的不足，使蟻群算法能以更大的概率選擇全局最短路徑，就必須為蟻群算法設(shè)置一個(gè)離全局最短路徑較近的初始路徑。節(jié)約算法是一種高效的精確啟發(fā)式算法，它得到的解一般要好于其他精確啟發(fā)式算法，有較好的交叉性能，同時(shí)為了提高算法的效率，應(yīng)把節(jié)約算法找到的路徑作為蟻群算法的初始最短路徑，對(duì)信息素進(jìn)行更新。

1.2 概率選擇公式的改進(jìn)

在傳統(tǒng)蟻群算法中，螞蟻把將要選擇路徑的長(zhǎng)短作為唯一的先驗(yàn)知識(shí)，優(yōu)先選擇較短的路徑。但是，傳統(tǒng)的蟻群算法中螞蟻在選擇路徑時(shí)是通過(guò)對(duì)路徑進(jìn)行單向的評(píng)價(jià)，這在很大程度上降低了先驗(yàn)信息的準(zhǔn)確性。因此，可以考慮將路徑的長(zhǎng)度在所有與其直接相連的路徑中的排名作為除了路徑的長(zhǎng)短之外的另一部分先驗(yàn)知識(shí)，使螞蟻在選擇路徑時(shí)有更充分的先驗(yàn)知識(shí)可以運(yùn)用，選擇的路徑更優(yōu)，這有利于提高算法的尋優(yōu)能力。故將螞蟻的概率選擇公式改成:

式中:allowedk為第t 次迭代中第k 只螞蟻還未訪問(wèn)的城市序號(hào)組成的集合;η′ij為路徑(i，j)在所有與i 相連的路徑中的排名的倒數(shù);γ 為其重要程度。

1.3 螞蟻的狀態(tài)轉(zhuǎn)移規(guī)則改進(jìn)

有時(shí)某一個(gè)城市到另外兩個(gè)或多個(gè)城市的距離與路徑上的信息素的量相差無(wú)幾，讓螞蟻根據(jù)概率公式直接選擇較優(yōu)的城市會(huì)比較困難。在這種情況下，為了能使螞蟻選擇到最優(yōu)的路徑，需要對(duì)蟻群算法的概率公式作一些調(diào)整。

在螞蟻選擇下一個(gè)將要訪問(wèn)的城市時(shí)，產(chǎn)生一個(gè)0 ～1 之間的隨機(jī)數(shù)rand。如果

R0為事先給定的0 ～1 之間的參數(shù)，則在第t次迭代中，位于城市i 的螞蟻下一個(gè)要訪問(wèn)的城市為:

否則，該螞蟻按照式(1)選擇下一個(gè)將要訪問(wèn)的城市。

1.4 信息素更新策略改進(jìn)

帶精英策略的蟻群算法的信息素更新策略為:

式中:Δτ*為精英螞蟻引起的路徑(i，j)上的信息素的增加量;σ 為精英螞蟻的個(gè)數(shù);L*為找出的最優(yōu)解的長(zhǎng)度。

從該信息素更新策略中可以看出，當(dāng)有一只或少數(shù)幾只螞蟻找到新的最短路徑時(shí)，最短路徑上的信息素相對(duì)于在本次迭代中螞蟻經(jīng)過(guò)的路徑增加得并不明顯。因此將導(dǎo)致蟻群整體上很難對(duì)找到的最短路徑做出快速而有效的反應(yīng)，從而有可能使該最短路徑在探索中被湮沒(méi)掉，導(dǎo)致蟻群對(duì)新發(fā)現(xiàn)的最短路徑不敏感，并降低了解的收斂速度。當(dāng)經(jīng)過(guò)多次迭代后，大部分螞蟻逐漸向該最優(yōu)路徑逼近時(shí)，經(jīng)過(guò)該最短路徑的螞蟻會(huì)很多，σ 值會(huì)變得很大，使得最短路徑上的信息素也會(huì)變得很大，由于蟻群對(duì)新發(fā)現(xiàn)的最短路徑解不敏感，使得蟻群在該最優(yōu)解的位置停滯不前。

為了使蟻群對(duì)已找到的最短路徑有較穩(wěn)定的敏感度，將式(1)修改為:

式中:V 為1 到螞蟻個(gè)數(shù)之間的一個(gè)參數(shù)，取一個(gè)較大值。這樣相對(duì)于螞蟻在本次迭代中經(jīng)過(guò)的路徑，新的最短路徑的影響會(huì)更明顯，就會(huì)使蟻群能快速地在新的最短路徑附近有效地探索，從而加快蟻群的收斂速度。當(dāng)蟻群在逐漸向已找到的全局最短路徑靠攏時(shí)，全局最短路徑上的信息素已經(jīng)足夠多，收斂速度已經(jīng)足夠快，沒(méi)有必要進(jìn)一步增加最短路徑上的信息素的量。而且收斂速度過(guò)快，會(huì)使蟻群?jiǎn)适г谝颜业降淖顑?yōu)路徑周圍發(fā)現(xiàn)新的最優(yōu)路徑的能力，因此將式(4)改為:

1.5 信息素最大最小限制

由于該算法在理論上已經(jīng)具備跳出局部最優(yōu)解的能力，因此利用最大最小蟻群算法中的策略，對(duì)信息素作最大最小限制的主要目的不是為了避免蟻群算法出現(xiàn)停滯狀態(tài)，而是為了能使蟻群跳出局部最優(yōu)的速度更快。為了使螞蟻能在找到的最短路徑附近較小的范圍進(jìn)行探索，可適當(dāng)放寬對(duì)信息素的最大限制。

經(jīng)過(guò)t 次迭代，信息素經(jīng)過(guò)式(5)更新后，有:

為了使τmax能在信息素更新的過(guò)程中被達(dá)到，令Q ＞(1－ρ)τmaxL*。

1.6 利用禁忌策略避免蟻群停滯于局部最短路徑

大多數(shù)基本蟻群算法及其改進(jìn)算法的缺點(diǎn)是，即使在已經(jīng)找到的最優(yōu)路徑附近找了很多次，仍然沒(méi)有找到更好的解，在基本可以斷定該問(wèn)題的全局最優(yōu)解不在其附近的情況下，蟻群仍不能在適當(dāng)?shù)臅r(shí)候跳出該區(qū)域。

為了處理這種情況，首先禁忌掉該最短路徑及其附近的路徑，然后尋找一個(gè)新的可能出現(xiàn)全局最優(yōu)解的區(qū)域。為了充分利用經(jīng)驗(yàn)信息，把沒(méi)有被禁忌掉的路徑中的最短路徑作為新的全局最短路徑來(lái)對(duì)信息素進(jìn)行更新。

(1)建立禁忌表forb［n，m］，禁忌掉經(jīng)過(guò)較多次迭代沒(méi)更新的局部最短路徑及其附近的路徑。令forb［i，j］=0，i=0，1，2，…，n;j =1，2，…，m;其中，n 為迭代次數(shù);m 為螞蟻的個(gè)數(shù)。

(2)如果經(jīng)過(guò)連續(xù)l 次迭代，已找到的最短路徑都沒(méi)有更新，則在所有已找到的路徑中禁忌掉該最短路徑及其附近路徑，令forb［besti，bestj］=1，(besti，bestj)∈G。其中，G 為已經(jīng)找到的所有路徑中，長(zhǎng)度大于或等于上次被禁忌掉的最短路徑，且排名在前T 名以內(nèi)的路徑上經(jīng)過(guò)的螞蟻的序號(hào)及該路徑所在迭代的序號(hào)對(duì)構(gòu)成的集合。

(3)在沒(méi)有被列入禁忌表的所有螞蟻經(jīng)過(guò)的路徑長(zhǎng)度比剛被禁忌掉最短路徑長(zhǎng)Δd 的路徑中，尋找最短路徑作為新的全局最短路徑，利用式(8)對(duì)信息素進(jìn)行更新。

(4)每一次迭代后，在所有蟻群找到的路徑中，禁忌掉路徑長(zhǎng)度與禁忌表中的某條路徑的長(zhǎng)度相等的路徑，再在此次迭代中沒(méi)有被禁忌掉的路徑中尋找最短路徑，如果該最短路徑要優(yōu)于在此次迭代之前沒(méi)有被列入禁忌表中的路徑中的最短路徑，則將該最短路徑作為新的已經(jīng)找到的全局最短路徑。否則，不對(duì)全局最短路徑進(jìn)行更新。

2 求解TSP 問(wèn)題的改進(jìn)蟻群算法步驟

求解TSP 問(wèn)題的改進(jìn)蟻群算法步驟如下:

(1)初始化參數(shù)，令n=1;

(2)利用節(jié)約算法得到初始最短路徑;

(3)將螞蟻放在起始城市上;

(4)產(chǎn)生隨機(jī)數(shù)rand，如果rand ＜R0，螞蟻按照式(3)選擇下一個(gè)城市，否則，按照式(1)選擇下一個(gè)城市;

(5)如果螞蟻訪問(wèn)完所有城市，讓螞蟻回到起始城市上，否則跳到步驟(4);

(6)如果所有螞蟻都已回到起始城市，進(jìn)行下一步，否則跳到步驟(3);

(7)從所有已訪問(wèn)的沒(méi)有被禁忌掉的路徑中選出最短路徑，作為已找到的最短路徑，結(jié)合該次迭代中所有螞蟻的訪問(wèn)路徑，按照式(8)對(duì)這些路徑上的信息素進(jìn)行更新，并利用式(10)對(duì)信息素進(jìn)行修正;

(8)如果連續(xù)迭代l 次，最短路徑都沒(méi)有更新，將該最短路徑及其附近路徑放入禁忌表中;

(9)如果迭代次數(shù)等于預(yù)先設(shè)定的最大迭代次數(shù)，則算法結(jié)束;否則，令迭代次數(shù)n =n +1，跳到步驟(3)。

3 仿真實(shí)驗(yàn)

采用TSPLIB 中eil51 問(wèn)題，分別對(duì)帶精英策略的最大最小蟻群算法和筆者改進(jìn)的蟻群算法進(jìn)行測(cè)試，并與文獻(xiàn)［9］中的改進(jìn)文化蟻群算法進(jìn)行比較。參數(shù)設(shè)置為:n=100，m =50，α =4.5，帶精英策略的最大最小蟻群算法中β =4，改進(jìn)的蟻群算法中β =0，γ =3，ρ =0.75，Q =800，V =50，l=20，T =1，Δd =0，R0=0.3，τmin=1.00，τmax=7.00，表1 為經(jīng)過(guò)20 次獨(dú)立實(shí)驗(yàn)后的結(jié)果比較，表明筆者改進(jìn)后的算法比其他算法能得到更短的最短路徑，而且更穩(wěn)定。

圖1 展示了求解eil51 問(wèn)題過(guò)程中，隨著迭代次數(shù)的增加，帶精英策略的最大最小蟻群算法和筆者改進(jìn)的蟻群算法找到的最短路徑朝全局最短路徑收斂的性能，從圖1 中可以看出，帶精英策略的最大最小蟻群算法雖然能不斷收斂，但是最后收斂到的解并不十分優(yōu)良，與改進(jìn)的蟻群算法比它的最優(yōu)解要大得多。因此，與帶精英策略的最大最小蟻群算法相比，筆者改進(jìn)的蟻群算法具有更好的尋優(yōu)能力。

表1 eil51 問(wèn)題3 種算法結(jié)果比較 km

圖1 帶精英策略的最大最小蟻群算法與筆者改進(jìn)的蟻群算法的收斂性比較

采用TSPLIB 中eil101 問(wèn)題，分別對(duì)帶精英策略的最大最小蟻群算法與筆者改進(jìn)的蟻群算法進(jìn)行測(cè)試。參數(shù)設(shè)置為:n =100，m =50，α =4.5，β=4，γ=2.0，ρ=0.75，η′0=0.000 01，Q=200 0，V=101，l=10，T=1，Δd=0，R0=0.3，τmin=1.00，τmax=16.00，表2 為經(jīng)過(guò)20 次獨(dú)立實(shí)驗(yàn)后的結(jié)果比較，表明筆者改進(jìn)后的算法在較大規(guī)模TSP 問(wèn)題上能比帶精英策略的最大最小蟻群算法更穩(wěn)定地得到更短的路徑。

表2 eil101 問(wèn)題帶精英策略的最大最小蟻群算法與筆者改進(jìn)的蟻群算法結(jié)果比較 km

圖2 展示了在eil101 問(wèn)題上帶精英策略的最大最小蟻群算法在前10 次迭代就已陷入局部最短路徑，而筆者改進(jìn)的蟻群算法在迭代完30 次后，還能進(jìn)一步跳出局部最優(yōu)，最終收斂于一個(gè)比帶精英策略的最大最小蟻群算法找到的最短路徑好得多的最短路徑，表明筆者改進(jìn)的蟻群算法在較大規(guī)模的TSP 問(wèn)題上，收斂性也明顯優(yōu)于帶精英策略的最大最小蟻群算法。

圖2 帶精英策略的最大最小蟻群算法與筆者改進(jìn)的蟻群算法的收斂性比較

從表1 和表2 對(duì)照中可以看出，不論對(duì)于小規(guī)模還是較大規(guī)模的TSP 問(wèn)題，每次實(shí)驗(yàn)中，筆者改進(jìn)的蟻群算法找到的最短路徑的長(zhǎng)度都極為穩(wěn)定，且穩(wěn)定性強(qiáng)于帶精英策略的最大最小蟻群算法。從圖1 和圖2 可以看出，隨著TSP 問(wèn)題規(guī)模的增大，筆者改進(jìn)的蟻群算法找到的最短路徑的質(zhì)量和帶精英策略的最大最小蟻群算法找到的最短路徑的質(zhì)量的差距也在進(jìn)一步擴(kuò)大。

4 結(jié)論

筆者對(duì)帶精英策略的最大最小蟻群算法的關(guān)鍵策略作了進(jìn)一步改進(jìn)，通過(guò)大量實(shí)驗(yàn)表明，筆者提出的改進(jìn)蟻群算法要明顯優(yōu)于帶精英策略的最大最小蟻群算法。但筆者提出的改進(jìn)蟻群算法缺乏對(duì)參數(shù)的自適應(yīng)調(diào)整策略，采用何種參數(shù)才能進(jìn)一步提高算法的綜合性能，以及如何進(jìn)一步提高算法對(duì)大規(guī)模TSP 問(wèn)題的尋優(yōu)能力，還值得進(jìn)一步研究。

［1］ 申紅蓮，張國(guó)立，李振濤.一種求解TSP 問(wèn)題的新算法［J］.計(jì)算機(jī)工程與應(yīng)用，2008，44(6):65－67.

［2］ 梁曉磊，李文鋒，張煜，等.具有動(dòng)態(tài)拓?fù)浣Y(jié)構(gòu)的聚類粒子群算法研究［J］.武漢理工大學(xué)學(xué)報(bào):信息與管理工程版，2011，33(1):22－26.

［3］ BULLNHEIMER B，HARTL R F，STRAUSS C.A new rank based version of the ant system:a computational study［R］.Vienna:University of Vienna，1997.

［4］ STUTZLE T，HOOS H. Improvements on the ant system:introducing max－min ant system［C］//Proceedings of the International Conference on Artificial Neural Networks and Genetic Algorithms.Wien:Springer Verlag，1997:245－249.

［5］ 熊德國(guó)，李穎. 蟻群算法在最小極大流問(wèn)題中的應(yīng)用［J］. 武漢理工大學(xué)學(xué)報(bào):信息與管理工程版，2010，32(6):882－885.

［6］ 王越超，李毅. 基于蟻群算法的產(chǎn)品銷售渠道優(yōu)選策略［J］.武漢理工大學(xué)學(xué)報(bào):信息與管理工程版，2011，33(6):1011－1014.

［7］ 顧軍華，范培培，宋慶增，等. 改進(jìn)的求解TSP 問(wèn)題文化蟻群優(yōu)化方法［J］. 計(jì)算機(jī)工程與應(yīng)用，2010，46(26):49－52.

［8］ 趙吉東，胡小兵，劉好斌. 改進(jìn)的蟻群算法及其在TSP 中的應(yīng)用［J］. 計(jì)算機(jī)工程與應(yīng)用，2010，46(24):51－52.

［9］ 李將軍，葉仲泉，宮子風(fēng).改進(jìn)蟻群算法及其仿真研究［J］.計(jì)算機(jī)應(yīng)用，2008，28(12):94－96.