基于局部優(yōu)化策略求解ＴＳＰ的蟻群算法

摘 要：為了克服基本蟻群算法收斂速度慢、易于停滯的缺陷，提出了一種基于局部優(yōu)化策略的蟻群算法（LOACA）。該算法根據(jù)TSP的特點，采用了三種局部優(yōu)化算子來交換搜索路徑中城市的位置，以改進解的質(zhì)量。以TSP為例進行的實驗結(jié)果表明，該算法優(yōu)于ACA和ACAGA。

關(guān)鍵詞：蟻群算法；局部優(yōu)化；旅行商問題

中圖分類號：TP301．6 文獻標志碼：A

文章編號：1001-3695(2008)07-1974-03



Ant colony algorithm based on local optimization for TSP

GONG Bencan1，2，LI Layuan2，JIANG Tingyao1，WANG Xiangli2

(1.College of Electrical Engineering Information Technology， China Three Gorges University， Yichang Hubei 443002， China;2.College of Computer Science Technology， Wuhan University of Technology， Wuhan 430063， China)

Abstract:This paper proposed an ant colony algorithm based on local optimization (LOACA) to avoid the default of slow convergence speed and early stagnation in the basic ant colony algorithm (ACA). According to the features of TSP， it used three local optimization operations to exchange the position of cities in the search paths to gain the better solutions. Experimental results for solving TSP show that the proposed algorithm performs better than ACA and ACAGA.

Key words:ant colony algorithm;local optimization;TSP (traveling salesman problem)



旅行商問題是一個經(jīng)典的組合優(yōu)化問題，在給定n個城市及其坐標位置的情況下，它要求一條經(jīng)過每個城市一次且僅一次的最短Hamilton回路。設(shè)G=（V，E，d）表示一個加權(quán)圖。其中：V是城市vi的集合；E是連接兩個城市的邊集；d是邊的權(quán)值，即兩個城市之間的距離。TSP的數(shù)學(xué)描述為T=min({ni=1d(vi，vi+1)+d(vn+v1)})。TSP在許多工程領(lǐng)域具有廣泛的應(yīng)用價值，如電路板布線、VLSI芯片設(shè)計、機器人控制、交通路由等。但TSP的求解是NPhard問題。隨著城市數(shù)目的增多，問題空間將呈指數(shù)級增長，無法在多項式時間內(nèi)找到精確解。最近許多研究者用各種啟發(fā)式算法來求解該問題，比較流行的算法有蟻群算法(ACA)^[1]、遺傳算法(GA)^[2]、模擬退火(SA)^[3]、禁忌搜索(TS)^[4]、神經(jīng)網(wǎng)絡(luò)(NN)^[5]、粒子群優(yōu)化算法(PSO)^[6]、免疫算法(IA)^[7]等。在這些算法中蟻群算法取得了較好的效果。蟻群算法是20世紀90年代由意大利學(xué)者Macro Dorigo等人提出的一種仿生算法。它模擬了自然界中螞蟻的覓食行為，螞蟻在覓食過程中會在經(jīng)過的路徑上留下一種稱為信息素的物質(zhì)，螞蟻選擇路徑的概率與路徑上信息素的強度成正比；經(jīng)過某條路徑的螞蟻越多，在該路徑上留下的信息素也越多，后面的螞蟻選擇這條路徑的概率就越大。通過正反饋，螞蟻很快能夠找到從蟻巢到食物源的最短路徑。蟻群算法具有很多優(yōu)點，如很強的發(fā)現(xiàn)較好解的能力、魯棒性強、分布式計算、簡單、易于與其他算法結(jié)合等；但也有一些缺陷，如收斂速度慢、易陷入局部最優(yōu)解。局部優(yōu)化能在一定程度上緩解螞蟻算法存在的不足，比較常見的局部優(yōu)化方法有2OPT、3OPT、LK等。本文在這些方法的基礎(chǔ)上，提出了三種局部優(yōu)化算子，有效地改進了蟻群算法的性能。

1 基本蟻群算法

下面以TSP為例說明基本蟻群算法模型。首先將m只螞蟻隨機放置在n個城市，位于城市i的第k只螞蟻選擇下一個城市j的概率為

其中：τ(i， j)表示邊（i， j）上的信息素濃度；η(i， j)=1/d(i， j)是啟發(fā)信息，d(i， j)是城市i和j之間的距離；α和β反映了信息素與啟發(fā)信息的相對重要性；tabuk表示螞蟻k已經(jīng)訪問過的城市列表。

當所有螞蟻完成周游后，按式（2）（3）進行信息素更新。

其中：0<ρ<1是信息素揮發(fā)因子；Δτk(i， j)表示第k只螞蟻在邊(i， j)上留下的信息量；Q為常數(shù)；Rk表示第k只螞蟻走過的路徑；Lk為路徑長度。

2 局部優(yōu)化算子

2．1 局部優(yōu)化算子1

設(shè)路徑為:~，k，l，l′，~，p′，p，q，q′，~，r′，r，s，~，從當前節(jié)點k開始，依次檢測隨后的節(jié)點。如果某節(jié)點q滿足條件d(k，l)>d(k，q)，即節(jié)點k和l之間的距離大于節(jié)點k和q之間的距離，則從節(jié)點q繼續(xù)向后檢測；如果有節(jié)點r滿足條件d(k，l)+d(p，q)+d(r，s)>d(k，q)+(r，l)+d(p，s)，則進行變異，優(yōu)化后的路徑為：~，k，q，q′，~，r′，l，l，l′，~，p′，p，s，~。根據(jù)TSP的特點，變異時應(yīng)保持子路徑(l′，~，p′)和(q′，~，r′)中各節(jié)點間的鄰接關(guān)系不變。

為了便于處理，將路徑用單鏈表表示，單鏈表中節(jié)點的結(jié)構(gòu)為cn。其中：c表示路徑中城市的編號；n是指向下一個節(jié)點的指針。程序偽代碼如下：

//定義指向節(jié)點k，l，p，q，r，s的指針

LNode *L1，*L2，*L3，*L4，*L5，*L6;

L1=H; //H為單鏈表的頭指針

L2=L1→n; L3=L2→n; L4=L3→n;

for (i=1; i

while(L4→n→n!=NULL)

flag=0; //優(yōu)化標志

if(d[L1→c][L2→c]>d[L1→c][L4→c])

L5=L4→n; L6=L5→n;

while(L6!=NULL)

d1=d[L1→c][L2→c]+d[L3→c][L4→c]+d[L5→c][L6→c];

d2=d[L1→c][L4→c]+d[L5→c][L2→c]+d[L3→c][L6→c];

if(d1>d2)

L1→n=L4; L5→n=L2; L3→n=L6;//優(yōu)化

flag=1; break;

else

L5=L5→n; L6=L6→n;

End if

End while

End if

if(flag==1) //進行優(yōu)化

L2=L1→n; L3=L2→n; L4=L3→n; //指針置位

else

L3=L3→n; L4=L4→n;

End if

End while

L1=L1→n; L2=L1→n; L3=L2→n; L4=L3→n;

End for

2．2 局部優(yōu)化算子2

設(shè)路徑為：~，k，l，~，p，q，~。從當前節(jié)點k開始，依次檢測隨后的節(jié)點。如果有一個節(jié)點p滿足條件d(k，l)+ d(p，q)>d(k，p)+(l，q)，則進行變異，優(yōu)化后的路徑為：~，k，p，~，l，q，~。變異時應(yīng)保持子路徑(l，~，q)中各節(jié)點間的鄰接關(guān)系不變，但節(jié)點順序相反，變?yōu)楠?p，~，l)。程序偽代碼如下：

for (i=0;i

j=i+2;

while(j

d1=d[tabu[i]][tabu[i+1]]+d[tabu[j]][tabu[j+1]];

d2=d[tabu[i]][tabu[j]]+d[tabu[i+1]][tabu[j+1]];

if(d1>d2)//距離變短，應(yīng)變異

switch_num=(j-i)/2; //交換次數(shù)

for(k=1;k<=switch_num;k++)

temp=tabu[i+k]; //城市號

tabu[i+k]=tabu[j+1-k];

tabu[j+1-k]=temp;

end for

j=i+2;

else 

j++;

end if

end while

end for

2．3 局部優(yōu)化算子3

TSP具有鄰域特征，螞蟻在選擇下一個城市時，最優(yōu)路徑只可能出現(xiàn)在附近的幾個城市，這一搜索范圍稱為候選窗口。候選窗口的大小應(yīng)根據(jù)TSP的規(guī)模而定，取值太小，會降低解的質(zhì)量；取值過大，則影響搜索速度。螞蟻總是優(yōu)先選擇候選窗口中的城市，只有當候選窗口中的城市都走過時，才選擇窗口外的城市。搜索結(jié)束后，根據(jù)候選窗口對路徑進行優(yōu)化，如果將候選窗口內(nèi)的節(jié)點交換到當前節(jié)點附近后距離更短，則進行變異。

設(shè)路徑為:~，k，l，l′，~，p′，p，t，q，q′，~，r′，r，s，~，對任一節(jié)點t，r和l是t候選窗口中的城市。如果d(t，q)+d(r，s)>d(t，r)+(q，s)，則進行變異，優(yōu)化后的路徑為：~，k，l，l′，~，p′，p，t，r，r′，~，q′，q，s，~；如果d(p，t)+d(k，l)> d(l，t)+(k，p)則進行變異，優(yōu)化后的路徑為：~，k，p，p′，~，l′，l，t，q，q′，~，r′，r，s，~。

另外，本文采用了最優(yōu)路徑更新策略，每輪搜索結(jié)束后，只對最短路徑進行信息素更新。

對Kroa100，各算子優(yōu)化前后的路徑如圖1所示。路徑長度分別為：優(yōu)化前（28 596），算子1優(yōu)化后（26 439），算子2優(yōu)化后（23 012），算子3優(yōu)化后（21 282）。

3 實驗結(jié)果

本文選用了國際上通用的TSP測試庫TSPLIB中的多個實例，用VC++編程進行測試，并將LOACA分別與結(jié)合遺傳算法的蟻群算法ACAGA^[8]和基本蟻群算法ACA進行比較。

實驗參數(shù)設(shè)置為：螞蟻數(shù)=50；α=1；β=3；ρ=0.9；信息素初始值=0.1；迭代次數(shù)=1 000；對Eil51、Eil76和Kroa100，候選窗口大小w=10，對Lin318，w=30；對Eil51和Eil76，Q=20，對Kroa100，Q=1 000，對Lin318，Q=2 000。

對每個TSP共進行10次實驗，取平均值，實驗結(jié)果如表1所示。表中*標注的數(shù)據(jù)選自文獻[8]。

表1 不同算法的對比實驗結(jié)果

實例名稱Eil51Eil76Kroa100Lin318

已知最優(yōu)值426*538*21 282*42 029*

ACAGA最好值426*540*21 292*45 733*

ACA最好值427*543*21 389*48 416*

LOACA最好值42653821 28242 091

LOACA平均值426.153821 28242 106.2

從表1可以看出，提出的算法在解的質(zhì)量上明顯優(yōu)于ACAGA和ACA，對Eil51、Eil76和Kroa100，分別有9、10和10次找到了已知最優(yōu)解。各TSP實例所求得的最好路徑如圖2所示。

對Kroa100、LOACA和ACA算法的收斂特性比較如圖3所示。從圖中可以看出，對于基本蟻群算法，路徑長度變化大(22 288~38 218，前五次迭代在圖中未列出)，收斂速度慢；而優(yōu)化算法路徑長度變化小(21 282~21 610)，收斂速度快，僅用了25輪即取得已知最優(yōu)解21 282。

4 結(jié)束語

本文根據(jù)TSP的特點，設(shè)計了三種局部優(yōu)化算子，每一輪搜索結(jié)束后，采用該算子對結(jié)果路徑進行變異，以尋求更優(yōu)解。局部優(yōu)化加快了螞蟻算法的收斂速度，避免了早熟和停滯現(xiàn)象的發(fā)生，增強了尋優(yōu)能力。經(jīng)過多個TSP實例測試，實驗結(jié)果表明：對中小規(guī)模的TSP，該算法基本上能找到最優(yōu)解；對大規(guī)模的TSP，也能明顯地改善解的質(zhì)量。

參考文獻：

［1］

DORIGO M，GAMBARDELLA L M.Ant colony system: a cooperative learning approach to the traveling salesman problem[J].IEEE Trans on Evolutionary Computation，1997，1(1):53-66.

[2]TALBI H，DRAA A，BATOUCHE M.A new quantuminspired genetic algorithm for solving the traveling salesman problem[C]//Proc of IEEE International Conference on Industrial Technology.2004：11921197.

[3]SONG Chihua，LEE K，LEE W D.Extended simulated annealing for augmented TSP and multisalesmen TSP[C]//Proc of International Joint Conference on Neural Networks.2003：23402343.

[4]MICHEL G，GILBERT L，F(xiàn)REDERIC S.A tabu search heuristic for the undirected selective traveling salesman problem[J].European J of Operational，1998，106(1):539-545.

[5]YANG Haiqing，YANG Haihong.An selforganizing neural network with convexhull expanding property for TSP[C]//Proc ofInternational Conference on Neural Networks and Brain.2005：379-383.

[6]王文峰，劉光遠，溫萬惠.求解TSP問題的混合離散粒子群算法[J].西南大學(xué)學(xué)報：自然科學(xué)版， 2007， 29(1):85-88.

[7]黃雪梅，李濤，徐春林，等.一種基于免疫遺傳的TSP求解方法[J]. 四川大學(xué)學(xué)報：工程科學(xué)版，2006， 38(1):86-91.

[8]孫力娟，王良俊，王汝傳.改進的蟻群算法及其在TSP中的應(yīng)用研究[J].通信學(xué)報，2004，25(10):111116.

注：“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文。”