申鉉京，劉陽(yáng)陽(yáng)，黃永平，徐 鐵，何習(xí)文

（1.吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，長(zhǎng)春130012；2.吉林大學(xué)符號(hào)計(jì)算與知識(shí)工程教育部重點(diǎn)實(shí)驗(yàn)室，長(zhǎng)春130012；3.吉林石油集團(tuán)有限責(zé)任公司洮河農(nóng)場(chǎng)，吉林松原138000）

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

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

1 算法策略

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

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

當(dāng)q≤q0時(shí)，

當(dāng)q＞q0時(shí)，螞蟻根據(jù)轉(zhuǎn)移概率公式（2）選擇下一個(gè)點(diǎn)：

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

1.2 信息素自適應(yīng)更新策略

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

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

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

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

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

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

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

圖1 一定迭代次數(shù)后出現(xiàn)的重復(fù)路徑Fig.1 Repeated paths at a particular iteration

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

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

1.4 算法步驟

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

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

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

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

圖3 改進(jìn)算法求得的路徑Fig.3 Routes found by proposed algorithm

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

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

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

Step8 NA←NA＋1，如果NA＞Nmax＿A轉(zhuǎn)Step9，否則轉(zhuǎn)Step2。

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

2 實(shí)驗(yàn)結(jié)果與分析

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

圖4 改進(jìn)算法的收斂過(guò)程圖Fig.4 Convergence process map of proposed algorithm

圖5 改進(jìn)算法運(yùn)行15次結(jié)果圖Fig.5 Results of proposed algorithm after running 15 times

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

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

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

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

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

圖7 不同算法的平均運(yùn)行時(shí)間Fig.7 Average running time of different methods

3 結(jié)束語(yǔ)

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

［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ìn)混合蛙跳算法求解旅行商問(wèn)題［J］.通信學(xué)報(bào)，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.