基于局部優化策略求解ＴＳＰ的蟻群算法
2008-12-31 00:00:00龔本燦李臘元蔣廷耀汪祥莉
計算機應用研究 2008年7期
摘 要：為了克服基本蟻群算法收斂速度慢、易于停滯的缺陷，提出了一種基于局部優化策略的蟻群算法（LOACA）。該算法根據TSP的特點，采用了三種局部優化算子來交換搜索路徑中城市的位置，以改進解的質量。以TSP為例進行的實驗結果表明，該算法優于ACA和ACAGA。
關鍵詞：蟻群算法；局部優化；旅行商問題
中圖分類號：TP301．6 文獻標志碼：A
文章編號：1001-3695(2008)07-1974-03
Ant colony algorithm based on local optimization for TSP
GONG Bencan1，2，LI Layuan2，JIANG Tingyao1，WANG Xiangli2
(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)
旅行商問題是一個經典的組合優化問題，在給定n個城市及其坐標位置的情況下，它要求一條經過每個城市一次且僅一次的最短Hamilton回路。設G=（V，E，d）表示一個加權圖。其中：V是城市vi的集合；E是連接兩個城市的邊集；d是邊的權值，即兩個城市之間的距離。TSP的數學描述為T=min({ni=1d(vi，vi+1)+d(vn+v1)})。TSP在許多工程領域具有廣泛的應用價值，如電路板布線、VLSI芯片設計、機器人控制、交通路由等。但TSP的求解是NPhard問題。隨著城市數目的增多，問題空間將呈指數級增長，無法在多項式時間內找到精確解。最近許多研究者用各種啟發式算法來求解該問題，比較流行的算法有蟻群算法(ACA)[1]、遺傳算法(GA)[2]、模擬退火(SA)[3]、禁忌搜索(TS)[4]、神經網絡(NN)[5]、粒子群優化算法(PSO)[6]、免疫算法(IA)[7]等。在這些算法中蟻群算法取得了較好的效果。蟻群算法是20世紀90年代由意大利學者Macro Dorigo等人提出的一種仿生算法。它模擬了自然界中螞蟻的覓食行為，螞蟻在覓食過程中會在經過的路徑上留下一種稱為信息素的物質，螞蟻選擇路徑的概率與路徑上信息素的強度成正比；經過某條路徑的螞蟻越多，在該路徑上留下的信息素也越多，后面的螞蟻選擇這條路徑的概率就越大。通過正反饋，螞蟻很快能夠找到從蟻巢到食物源的最短路徑。蟻群算法具有很多優點，如很強的發現較好解的能力、魯棒性強、分布式計算、簡單、易于與其他算法結合等；但也有一些缺陷，如收斂速度慢、易陷入局部最優解。局部優化能在一定程度上緩解螞蟻算法存在的不足，比較常見的局部優化方法有2OPT、3OPT、LK等。本文在這些方法的基礎上，提出了三種局部優化算子，有效地改進了蟻群算法的性能。
1 基本蟻群算法
下面以TSP為例說明基本蟻群算法模型。首先將m只螞蟻隨機放置在n個城市，位于城市i的第k只螞蟻選擇下一個城市j的概率為
其中：τ(i， j)表示邊（i， j）上的信息素濃度；η(i， j)=1/d(i， j)是啟發信息，d(i， j)是城市i和j之間的距離；α和β反映了信息素與啟發信息的相對重要性；tabuk表示螞蟻k已經訪問過的城市列表。
當所有螞蟻完成周游后，按式（2）（3）進行信息素更新。
其中：0<ρ<1是信息素揮發因子；Δτk(i， j)表示第k只螞蟻在邊(i， j)上留下的信息量；Q為常數；Rk表示第k只螞蟻走過的路徑；Lk為路徑長度。
2 局部優化算子
2．1 局部優化算子1
設路徑為:~，k，l，l′，~，p′，p，q，q′，~，r′，r，s，~，從當前節點k開始，依次檢測隨后的節點。如果某節點q滿足條件d(k，l)>d(k，q)，即節點k和l之間的距離大于節點k和q之間的距離，則從節點q繼續向后檢測；如果有節點r滿足條件d(k，l)+d(p，q)+d(r，s)>d(k，q)+(r，l)+d(p，s)，則進行變異，優化后的路徑為：~，k，q，q′，~，r′，l，l，l′，~，p′，p，s，~。根據TSP的特點，變異時應保持子路徑(l′，~，p′)和(q′，~，r′)中各節點間的鄰接關系不變。
為了便于處理，將路徑用單鏈表表示，單鏈表中節點的結構為cn。其中：c表示路徑中城市的編號；n是指向下一個節點的指針。程序偽代碼如下：
//定義指向節點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; //優化標志 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;//優化 flag=1; break; else L5=L5→n; L6=L6→n; End if End while End if if(flag==1) //進行優化 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 局部優化算子2 設路徑為：~，k，l，~，p，q，~。從當前節點k開始，依次檢測隨后的節點。如果有一個節點p滿足條件d(k，l)+ d(p，q)>d(k，p)+(l，q)，則進行變異，優化后的路徑為：~，k，p，~，l，q，~。變異時應保持子路徑(l，~，q)中各節點間的鄰接關系不變，但節點順序相反，變為(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)//距離變短，應變異 switch_num=(j-i)/2; //交換次數 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 局部優化算子3 TSP具有鄰域特征，螞蟻在選擇下一個城市時，最優路徑只可能出現在附近的幾個城市，這一搜索范圍稱為候選窗口。候選窗口的大小應根據TSP的規模而定，取值太小，會降低解的質量；取值過大，則影響搜索速度。螞蟻總是優先選擇候選窗口中的城市，只有當候選窗口中的城市都走過時，才選擇窗口外的城市。搜索結束后，根據候選窗口對路徑進行優化，如果將候選窗口內的節點交換到當前節點附近后距離更短，則進行變異。 設路徑為:~，k，l，l′，~，p′，p，t，q，q′，~，r′，r，s，~，對任一節點t，r和l是t候選窗口中的城市。如果d(t，q)+d(r，s)>d(t，r)+(q，s)，則進行變異，優化后的路徑為：~，k，l，l′，~，p′，p，t，r，r′，~，q′，q，s，~；如果d(p，t)+d(k，l)> d(l，t)+(k，p)則進行變異，優化后的路徑為：~，k，p，p′，~，l′，l，t，q，q′，~，r′，r，s，~。 另外，本文采用了最優路徑更新策略，每輪搜索結束后，只對最短路徑進行信息素更新。 對Kroa100，各算子優化前后的路徑如圖1所示。路徑長度分別為：優化前（28 596），算子1優化后（26 439），算子2優化后（23 012），算子3優化后（21 282）。 3 實驗結果 本文選用了國際上通用的TSP測試庫TSPLIB中的多個實例，用VC++編程進行測試，并將LOACA分別與結合遺傳算法的蟻群算法ACAGA[8]和基本蟻群算法ACA進行比較。 實驗參數設置為：螞蟻數=50；α=1；β=3；ρ=0.9；信息素初始值=0.1；迭代次數=1 000；對Eil51、Eil76和Kroa100，候選窗口大小w=10，對Lin318，w=30；對Eil51和Eil76，Q=20，對Kroa100，Q=1 000，對Lin318，Q=2 000。 對每個TSP共進行10次實驗，取平均值，實驗結果如表1所示。表中*標注的數據選自文獻[8]。 表1 不同算法的對比實驗結果 實例名稱Eil51Eil76Kroa100Lin318 已知最優值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可以看出，提出的算法在解的質量上明顯優于ACAGA和ACA，對Eil51、Eil76和Kroa100，分別有9、10和10次找到了已知最優解。各TSP實例所求得的最好路徑如圖2所示。 對Kroa100、LOACA和ACA算法的收斂特性比較如圖3所示。從圖中可以看出，對于基本蟻群算法，路徑長度變化大(22 288~38 218，前五次迭代在圖中未列出)，收斂速度慢；而優化算法路徑長度變化小(21 282~21 610)，收斂速度快，僅用了25輪即取得已知最優解21 282。 4 結束語 本文根據TSP的特點，設計了三種局部優化算子，每一輪搜索結束后，采用該算子對結果路徑進行變異，以尋求更優解。局部優化加快了螞蟻算法的收斂速度，避免了早熟和停滯現象的發生，增強了尋優能力。經過多個TSP實例測試，實驗結果表明：對中小規模的TSP，該算法基本上能找到最優解；對大規模的TSP，也能明顯地改善解的質量。 參考文獻： ［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 quantuminspired genetic algorithm for solving the traveling salesman problem[C]//Proc of IEEE International Conference on Industrial Technology.2004：11921197. [3]SONG Chihua，LEE K，LEE W D.Extended simulated annealing for augmented TSP and multisalesmen TSP[C]//Proc of International Joint Conference on Neural Networks.2003：23402343. [4]MICHEL G，GILBERT L，FREDERIC S.A tabu search heuristic for the undirected selective traveling salesman problem[J].European J of Operational，1998，106(1):539-545. [5]YANG Haiqing，YANG Haihong.An selforganizing neural network with convexhull expanding property for TSP[C]//Proc ofInternational Conference on Neural Networks and Brain.2005：379-383. [6]王文峰，劉光遠，溫萬惠.求解TSP問題的混合離散粒子群算法[J].西南大學學報：自然科學版， 2007， 29(1):85-88. [7]黃雪梅，李濤，徐春林，等.一種基于免疫遺傳的TSP求解方法[J]. 四川大學學報：工程科學版，2006， 38(1):86-91. [8]孫力娟，王良俊，王汝傳.改進的蟻群算法及其在TSP中的應用研究[J].通信學報，2004，25(10):111116. 注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。”
