求解TSP問題的快速蟻群算法

申鉉京，劉陽陽，黃永平，徐 鐵，何習文

（1.吉林大學計算機科學與技術學院，長春130012；2.吉林大學符號計算與知識工程教育部重點實驗室，長春130012；3.吉林石油集團有限責任公司洮河農場，吉林松原138000）

TSP是著名的NP難問題，在電路板布局、VLSI芯片設計、車輛調度等組合優(yōu)化問題中有著廣泛的應用。蟻群算法是由意大利學者Dorigo等［1］首先提出的一種基于種群模擬進化智能啟發(fā)式算法，并已經成功應用于TSP等多個NP難的組合優(yōu)化問題求解，但基本蟻群算法也存在著易出現早熟、停滯的缺陷。針對蟻群算法的這些缺點，人們提出了許多改進的算法，如結合Q-Learning提出的Ant-Q算法［2］、MMAS算法［3］，基于負反饋的蟻群算法［4］等。在逐漸認識到蟻群有組織、有分工的特性，人們又提出多態(tài)蟻群算法，在一定程度上改善了蟻群算法的性能，也是提高TSP求解效率的一個發(fā)展方向。但現有方法在收斂速度和求解精度上未達到一個很好的平衡。

本文算法通過采用信息素揮發(fā)因子自適應調整機制，保證算法的全局搜索能力，有效地避免算法陷入局部最優(yōu)解。另外，通過加強公共路徑的選擇引導算法尋找更優(yōu)路徑，使得在算法停滯前易于發(fā)現更好的路徑，并趨向最優(yōu)路徑解。該算法可以有效防止陷入局部最優(yōu)解，同時提高收斂的速度。

1 算法策略

1.1 螞蟻群體移動規(guī)則

該算法中，第k只螞蟻由城市i選擇到下一個城市j的規(guī)則是：

當q≤q0時，

當q＞q0時，螞蟻根據轉移概率公式（2）選擇下一個點：

式中：q0是一個給定的位于（0，1）之間的常數；q是一個在（0，1）之間均勻分布的隨機數；τiu（t）表示城市i和城市u之間路徑上的信息素濃度；dij為兩個城市之間的距離；信息啟發(fā)式因子α反映螞蟻在運動過程中所積累的信息量（即殘留信息量τiu（t））在指導蟻群搜索中的相對重要程度；期望值啟發(fā)式因子β反映螞蟻在運動過程中啟發(fā)信息（即期望值ηij）在指導蟻群搜索中的相對重要程度；allowedk表示第k只螞蟻當前的可行點集。由式（1）和式（2）組成的轉移規(guī)則稱為偽隨機規(guī)則，此規(guī)則傾向于選擇短且信息素濃度大的邊作為移動方向。

1.2 信息素自適應更新策略

每次搜索結束后，對每只螞蟻的信息素按式（4）（5）（6）進行更新：式中：m為螞蟻總個數；ρ為信息揮發(fā)率；τij為螞蟻在本次循環(huán)中留在路徑（i，j）上的信息量；Δτij為本次循環(huán)中所有經歷過路徑（i，j）的螞蟻留在該路徑上的信息量的增量；Q為一個常數（表示螞蟻循環(huán)一周所釋放的總信息量）；Lk為第k只螞蟻在本次循環(huán)中所走路徑的長度。這種信息更新規(guī)則正反饋性能強，能夠提高系統(tǒng)收斂速度。

ρ反應整個蟻群系統(tǒng)的進化狀態(tài)，它的大小直接關系到蟻群算法的全局搜索能力及收斂速度。當ρ過大時，也會影響到算法的隨機性能和全局搜索能力；反之，通過減小信息素揮發(fā)度ρ雖然可以改善該問題，但又會使算法的收斂速度降低。

為了使蟻群始終能夠在“探索”和“利用”之間保持平衡，使算法在具有較強的全局搜索能力的同時避免出現停滯狀態(tài)，文獻［5-6］都采用了不同的自適應調整方法動態(tài)調整ρ值，以提高算法全局搜索能力，快速收斂于較優(yōu)解。本文的改進算法中選用簡單而有效的自適應策略來調整ρ，其調整公式為

式中：ξ∈（0，1）為揮發(fā)因子調節(jié)系數；ρmin為ρ的最小值。算法初期賦予ρ較大的值，信息正反饋的作用占主導地位，以前搜索過的路徑被選擇的可能性較大，收斂速度比較快，但也很容易陷入局部最優(yōu)解。后期逐漸降低ρ的值，信息正反饋的作用會逐漸減至較弱，那些從未被搜索到的路徑信息素增大，搜索的隨機性就增強，提高了全局搜索能力，但又會影響蟻群算法收斂速度。所以，為其設置一個最小值，防止了ρ過小而降低算法的收斂速度。通過對揮發(fā)系數這種自適應地改變，既可以提高解的全局性，又可以保證收斂的速度。

1.3 公共路徑處理規(guī)則

上述自適應策略有效地提高了蟻群算法的全局搜索能力，使得算法能夠較快地收斂到一些較優(yōu)解，但從較優(yōu)解到最佳解的進化所需時間較長，本文利用基于公共路徑尋優(yōu)的方法加快尋優(yōu)速度。該方法是在文獻［7］基礎上提出的改進策略。文獻［7］將數百次迭代后反復走過的路徑設為必經過邊，以降低算法的運算時間，但是蟻群算法容易陷入局部最優(yōu)，最終所求得的可能為局部最優(yōu)解，降低了算法的準確性。

根據該思想本文提出一種新的改進策略，將蟻群分為兩組分別以不同的方法尋徑。第一組按基本蟻群算法查找全局最優(yōu)路徑，第二組利用公共路徑尋優(yōu)。螞蟻尋徑時由于信息素的作用，一定會有一些較短并重復經過的路徑段，出現如圖1所示的情況，兩只螞蟻a1和a2會走過相同的路徑段。但是，在改進算法中求解這種公共路徑是有條件的，僅求取當前最優(yōu)與次優(yōu)解的公共路徑，這些公共路徑有極大的可能是更優(yōu)解路徑或全局最優(yōu)解的組成部分，為第二組螞蟻提供了良好的尋徑方向。另外，將當前公共路徑保存在結構體中，第二組螞蟻利用公共路徑去尋優(yōu)時，可減少算法求解的工作量，以犧牲一定空間復雜度的方式來換取更少的時間復雜度。在所有螞蟻尋徑結束后，統(tǒng)一修改信息素的值，供蟻群下一次尋徑使用，更新當前最優(yōu)與次優(yōu)解。公共路徑為算法在尋徑過程中提供了良好的導向，使得在算法停滯前易于發(fā)現更好的路徑，并逐漸趨向最優(yōu)路徑解，并可以減少大量的重復運算，提高算法收斂速度。算法的求解過程如圖2所示。

圖1 一定迭代次數后出現的重復路徑Fig.1 Repeated paths at a particular iteration

圖3為改進算法求解Eil51實例得到的路徑圖。圖3（a）和（b）分別為第i次迭代得到的最優(yōu)與次優(yōu)路徑，找到公共路徑（見圖3（c）），作為下一次迭代中第二組蟻群必經過的邊。當求取了公共路徑后，算法的后續(xù)運行實質上是從處于非公共路徑的城市中構造一條最短路徑將它們和公共路徑相連組成一條回路，這樣就避免了尋徑過程中的許多重復運算，當算法迭代一定次數后，最優(yōu)解與次優(yōu)解的公共路徑很有可能是實際最優(yōu)解的組成部分，所以又給了算法一個良好的方向導向。使得在算法停滯前易于發(fā)現更好的路徑。由圖3（c）和（d）可以看到，改進算法最終找到了非常接近實際最優(yōu)路徑的解，而且這個解里包含了大部分的公共路徑。

圖2 一次迭代中的蟻群尋徑流程圖Fig.2 Flowchart of looking for paths in an iteration

1.4 算法步驟

Step1初始化：Nmax＿A←蟻群算法允許迭代最大次數；m←螞蟻個數；NA←1，蟻群算法迭代計數器；蟻群信息素τij←C；Δτij←0。

Step2將蟻群分成兩組，第一組按公式（1）和（2）進行狀態(tài)轉移，生成蟻群路徑解。

Step3更新最優(yōu)和次優(yōu)解，并找到最優(yōu)解和次優(yōu)解的公共路徑。

Step4第二組利用得到的公共路徑尋徑，將公共路徑作為必經過的邊，非公共路徑上的城市按式（1）（2）進行狀態(tài)轉移與公共路徑連成一條回路，生成蟻群路徑解。

圖3 改進算法求得的路徑Fig.3 Routes found by proposed algorithm

Step5兩組蟻群所得最優(yōu)解如果小于當前最優(yōu)解，更新最優(yōu)和次優(yōu)解，轉Step7；如果大于當前最優(yōu)解，轉Step6。

Step6如果小于當前次優(yōu)解，更新次優(yōu)解。

Step7按式（4）（5）和（6）更新信息素。

Step8 NA←NA＋1，如果NA＞Nmax＿A轉Step9，否則轉Step2。

Step9輸出最優(yōu)路徑和最優(yōu)路徑的長度。

2 實驗結果與分析

為了更好地說明該算法的有效性，選用國際上通用的TSPLIB測試庫中的Eil51實例進行測試。實驗仿真環(huán)境：1.60 GHz主頻的Intel處理器，1 G內存，仿真軟件Microsoft Visual C＋＋6.0。實驗中螞蟻數量m＝51／1.5＝34，參數α＝ 1.0、β＝3.0、q0＝0.5，信息素揮發(fā)因子初始值ρ0設為0.9，揮發(fā)因子調節(jié)系數ξ設為0.98，ρmin設為0.5。圖4是本文改進算法連續(xù)運行4次的收斂過程圖，算法在600次之后基本收斂，最差收斂到430，最好收斂到428。圖5是算法連續(xù)運行15次的結果圖，所得最長路徑值為433，最短路徑值為427，路徑均值為428。

圖4 改進算法的收斂過程圖Fig.4 Convergence process map of proposed algorithm

圖5 改進算法運行15次結果圖Fig.5 Results of proposed algorithm after running 15 times

本文以Eil51為例比較了幾種算法的性能，結果如表1所示。其中，ACS算法每次迭代3000次；ShyiMing Chen與Chih Yao Chien提出的方法內層遺傳算法迭代100次，外層蟻群算法迭代30次，每代120只螞蟻；改進的混合蛙跳算法每一代蛙有510只，外層迭代50次。

表1 本文算法與其他算法的比較Table 1 Comparison between proposed algorithm and other algorithms

表1中給出了不同算法的平均解與最優(yōu)解相對TSPLB庫中已知Eil51最優(yōu)解（426）的偏差百分比PDav和PDbest，圖6和圖7將各算法針對Eil51實例求得的平均值與已知最優(yōu)解偏差和運行時間做了一個直觀的比較。PDav和PDbest具體描述如下：

從表1、圖6和圖7可知，本算法在迭代次數較少的情況下，算法的性能優(yōu)于或接近所列出的對比算法，從而進一步驗證了算法的有效性。

圖6 不同算法的平均解與已知最優(yōu)解的偏差Fig.6 Percentage deviations of average solution to best known solution for different methods

圖7 不同算法的平均運行時間Fig.7 Average running time of different methods

3 結束語

本文算法采用信息素揮發(fā)因子自適應調整機制調節(jié)算法收斂速度，避免過度集中在某些較優(yōu)的路徑上。并通過加強算法對公共路徑的利用使算法盡量減少尋徑過程中的重復運算，降低蟻群算法的運算時間，而且有助于跳出局部最優(yōu)，增強了算法的全局尋優(yōu)能力。實驗結果表明，改進算法在迭代次數相對較少的情況下，求得的解優(yōu)于或接近所列出的其他算法，平均解與已知最優(yōu)解偏差為0.46%，最優(yōu)解與已知最優(yōu)解偏差為0.23%，較好地適用于求解TSP問題。

［1］Dorigo M，Maniezzo V，Colorni A.Ant system：optimization by a colony of cooperating agents［J］. IEEE Transaction on Systems，Man，and Cybernetics，Part B：Cybernetics，1996，26（1）：29-41.

［2］Dorigo M，Gambardella L M，Middendorf M，et al. Guest editorial：special section special section on ant colony optimization［J］.IEEE Transaction on，Evolutionary Computation，2002，6（4）：317-319.

［3］Stutzle T，Hoos H H.Max-min ant system［J］.Future Generation Computer Systems，2000（16）：889-914.

［4］Malisia A R，Tizhoosh H R.Applying oppositionbased ideas to the ant colony system［C］∥2007 IEEE Congress on Swarm Intelligence Symposium，Hono-lulu，HI，2007：182-189.

［5］Duan H B，Zhang X Y，Wu J，et al.Max-min adaptive ant colony optimization approach to multi-UAVs coordinated trajectory replanning in dynamic and uncertain environments［J］.Journal of Bionic Engineering，2009，6（2）：161-173.

［6］Yu B，Yang Z Z，Yao B Z.An improved ant colony optimization for vehicle routing problem［J］.European Journal of Operational Research，2009，196（1）：171-176.

［7］Tseng S P，Tsai C W，Chiang M C，et al.A fast ant colony optimization for traveling salesman problem［C］∥2010 IEEE Congress on Evolutionary Computation，Barcelona，2010：1-6.

［8］羅雪暉，楊燁，李霞.改進混合蛙跳算法求解旅行商問題［J］.通信學報，2009，30（7）：130-134.

Luo Xue-hui，Yang Ye，Li Xia.Modified shuffled frog-leaping algorithm to solve traveling salesman problem［J］.Journal on Communications，2009，30（7）：130-134.

［9］Masutti T A S，Castro L N D.A self-organizing neural network using ideas from the immune system to solve the travelling salesman problems［J］.Information Sciences，2009，179（10）：1454-1468.

［10］Chen S M，Chien C Y.Solving the traveling salesman problem based on the genetic simulated annealing ant colony system with particle swarm optimization techniques［J］.Expert Systems with Applications，2011（38）：14439-14450.