蟻群算法在求解旅行商問題中的改進

嚴小燕 李 旸 夏桂林

（1安徽農業(yè)大學信息與計算機學院，安徽 合肥 230036）

（2巢湖學院計算機系，安徽 巢湖 238000）

蟻群算法在求解旅行商問題中的改進

嚴小燕1，2李 旸1夏桂林2

（1安徽農業(yè)大學信息與計算機學院，安徽 合肥 230036）

（2巢湖學院計算機系，安徽 巢湖 238000）

蟻群算法是一種啟發(fā)式優(yōu)化算法，在求解旅行商問題等多種組合優(yōu)化問題上有著優(yōu)越性。但基本蟻群算法收斂速度慢，易于陷入局部最優(yōu)解，導致停滯現(xiàn)象出現(xiàn)。針對算法的這些缺點，提出給各條邊賦予不同的信息素初始量以加強算法初期信息素的作用，縮小算法的搜索范圍；并在進行全局信息素更新時，對到目前為止的最優(yōu)解、最差解和普通解采用不同的更新策略。實驗結果表明，改進的蟻群算法在實驗環(huán)境下，解決旅行商問題時的性能較基本蟻群算法有較好的表現(xiàn)。

蟻群算法；旅行商問題；信息素初始化；信息素更新

1 引言

旅行商問題 （Traveling Salesman Problem，TSP），是近代組合優(yōu)化領域的一個典型難題。[1]TSP問題可以形象描述為：給定n個城市（記為：r1，r2，…，rn）和它們兩兩之間的直達距離（記為：d（ri，rj）），一個旅行商從某一個城市出發(fā)，訪問每個城市一次且僅一次后再回到原出發(fā)城市，要求找出一條最短的旅行路線。即尋找一條巡回路徑R=（r1，r2，…rn，），使得公式（1）所示的目標函數(shù)最小。

上式中ri為城市號，取值范圍為從1到n的自然數(shù)。

TSP問題在科學、工程及經(jīng)濟的各個方面具有廣泛的應用如：網(wǎng)絡通訊、電網(wǎng)規(guī)劃、管道鋪設、交通調度、物流貨物配送等。這些問題或者是TSP問題的原型，或者可以轉化為TSP問題。TSP問題形式簡單、易于描述，是諸多領域內出現(xiàn)的復雜問題的集中概括和簡化形式。因此，快速、有效地解決TSP問題有著極高的實際應用價值。

目前求解TSP問題的算法主要可以分為兩類：精確算法 （Exact Algorithm）和啟發(fā)式算法（Heuristic Algorithm）。近年來，啟發(fā)式算法在求解優(yōu)化問題領域顯示出了自身的優(yōu)越性。較精確算法，啟發(fā)式算法可以獲得較快的收斂速度和較高質量的全局解。

常用的啟發(fā)式算法有遺傳算法、模擬退火算法、粒子群算法和蟻群算法等。其中，蟻群算法是一種群體啟發(fā)式算法，與其他優(yōu)化算法相比具有信息正反饋性、較強的魯棒性、采用分布式并行計算機制、易于與其它算法相結合等主要特點。[2]

但其不足之處是由于螞蟻是隨機選擇路徑，導致算法收斂速度較慢，搜索時間較長；且易于陷入局部最優(yōu)解，易出現(xiàn)早熟、停滯現(xiàn)象。本文將針對基本蟻群算法的上述缺點，在信息素、搜索速度、搜索策略等相應方面對算法進行改進，以改善蟻群算法在解決TSP問題時的性能。

2 蟻群算法原理及數(shù)學模型

2.1 蟻群算法的原理

生物學家和仿生學家觀察研究發(fā)現(xiàn)，螞蟻在覓食走過的路徑上釋放一種特有的分泌物——信息素（Pheromone），[3]當它們碰到一個還沒有走過的路口時，就隨機地挑選一條路徑前行，同時釋放出與路徑長度有關的信息素。螞蟻走的路徑越長，則釋放的信息量越小。當后來的螞蟻再次碰到這個路口時，選擇信息素強度較高路徑的概率相對較大。當一條路徑上走過的螞蟻越來越多，其留下的信息素強度也會越來越高，后來的螞蟻選擇這條路徑的概率也越來越大，從而進一步增加該路徑的信息素強度，這樣便形成了一個正反饋機制。而其它的路徑上的信息素強度卻會隨著時間的流逝而削弱。螞蟻個體之間通過這種信息素傳遞信息，相互協(xié)作，最終蟻群尋找到從蟻穴到食物源的最短路徑。

從蟻群在覓食過程中尋找最短路徑得到啟發(fā)，20世紀90年代，意大利學者 Dorigo M，Maniezzo V和Colorni A提出了人工蟻群算法，[4]簡稱蟻群算法（Ant Colony Algorithm，ACA）。蟻群算法吸收了真實螞蟻的行為特性，是通過模擬真實螞蟻群體覓食行為的過程來完成對問題求解的一種仿生優(yōu)化算法。

2.2 蟻群算法數(shù)學模型[5，6]

以求解平面上n個城市（1，2，…，n為城市編號）的TSP問題為例，說明基本蟻群算法模型。首先引入算法相關記號：m是蟻群中螞蟻的總數(shù)目；n是TSP問題規(guī)模；dij為城市i與城市j之間的距離；?ij（t）為啟發(fā)函數(shù)，在 TSP 問題中，一般取?ij（t）=1/dij； τij（t）為 t時刻路徑（i，j）上的信息素量，以此來模擬實際螞蟻的分泌物；tabuk為禁忌表，用以記錄螞蟻k當前所走過的城市，tabuk集合隨著進化過程做動態(tài)調整；Pkij（t）表示在 t時刻螞蟻k由城市i轉移到城市j的概率；α是信息啟發(fā)式因子，表示軌跡的相對重要性；β是期望啟發(fā)式因子，表示能見度的相對重要性；ρ是信息素揮發(fā)系數(shù)（0≤ρ＜1)，表示信息素含量 τij（t)隨時間的推移而衰減的程度，1-ρ為信息素殘留系數(shù)。基本蟻群算法的優(yōu)化過程主要體現(xiàn)在兩個方面：路徑選擇機制和信息素更新機制。

（1）路徑選擇機制

在算法初始時刻，各條路徑上的信息素相等，并設τij（0）=非零常數(shù)。將m只螞蟻隨機放在n座城市上，并將每只螞蟻當前所在的城市設置為它的禁忌表的第一個元素。螞蟻k（k=1，2，…，m）在搜索過程中，根據(jù)各條路徑上的信息素量及路徑的啟發(fā)信息（城市之間的距離）來計算狀態(tài)轉移概率以決定其轉移方向。每只螞蟻被隨機放到其中的一個城市上，路徑構造依據(jù)一定的轉移概率進行，在t時刻，螞蟻k由城市i轉向城市j的狀態(tài)轉移概率為Pkij（t），其計算公式如下：

其中，allowedk={1，2，…，n}-tabuk表示螞蟻 k下一步允許選擇的城市。上式表明：轉移概率Pkij（t）與 ταi·jηβij成正比，螞蟻在選擇路徑時會盡量選擇路程短且信息素濃度較大的路徑。

（2）信息素更新機制

為了模擬避免殘留信息素過多引起殘留信息淹沒啟發(fā)信息，在每只螞蟻走完一步或者完成對所有n個城市的遍歷（一個循環(huán)結束）后，要對殘留信息素進行更新處理。（t+n)時刻，所有的螞蟻完成了一次周游，路徑（i，j）上信息素可根據(jù)以下公式做調整：

式中△τij（t）表示一次循環(huán)中路徑（i，j）上的信息素增量，初始時刻△τij（0）=0；τi（jk)（t）表示第 k 只螞蟻在一次循環(huán)中在路徑（i，j)上留下的信息素量。

3 蟻群算法的改進與實現(xiàn)流程

基本蟻群算法一般需要較長的搜索時間，且容易出現(xiàn)停滯現(xiàn)象。當一條路徑上的信息素較其他的路徑多時，后面的螞蟻會偏向于走這條路徑，使之信息素越來越多，算法易于陷入局部最優(yōu)，即搜索進行到一定時間或程度后，所有螞蟻個體所發(fā)現(xiàn)的解趨于一致。這樣不利于進一步搜索得到更好的結果，可能導致無法找到全局最優(yōu)解。

針對基本蟻群算法存在的不足，本文提出了一種改進的蟻群算法。先求出離各城市最近的若干個城市，構成一個子集。然后，

（1）對每一個當前城市，判斷下一個城市是否屬于這個子集，從而對各條邊賦予不同的初始信息素量以加強算法初期信息素的作用；

（2）在路徑狀態(tài)轉移上，增強搜索過程的指導性，同樣對每一個當前城市，判斷下一個城市是否屬于這個子集，再確定轉移概率；

（3）信息素更新上，對最優(yōu)解進行更大限度的增強，而對最差解進行削弱；

（4）為避免由于第（3）點中最優(yōu)與最差路徑信息量之間差距加劇而引起的搜索停滯現(xiàn)象，防止搜索過快地集中到局部最優(yōu)解的周圍，增加對TSP中的每條邊上的信息素量的范圍限制。

根據(jù)以上分析，改進的蟻群算法求解TSP問題的實現(xiàn)步驟如下：

第1步：參數(shù)初始化。并令循環(huán)次數(shù)Nc=0，設置最大循環(huán)次數(shù)Ncmax，將m只螞蟻置于n個頂點（城市）上，有區(qū)別的給每條邊（i，j）設置初始時刻信息量 τij（0），且初始時刻△τij（0）=0。

第2步：將各螞蟻的初始出發(fā)點置于各自的禁忌表中。

第 3 步：每只螞蟻 k（k=1，2，3，…，m)根據(jù)狀態(tài)轉移概率公式計算的概率選擇頂點（城市）j，并將螞蟻移至 j，其中 j∈allowedk，將頂點（城市）j置于該螞蟻的禁忌表中。

第4步：循環(huán)執(zhí)行第3步，直到每只螞蟻都生成一條路徑；

第5步：求出到目前為止的最優(yōu)解和最差解；

第6步：分別更新最優(yōu)解、最差解和普通解中邊上的信息量。

第7步：判斷各路徑上的信息素值是否在限制范圍內，如果超出此范圍，則強制設為最小值或者是最大值。

第8步：如果循環(huán)次數(shù)Nc≥Nmax，則循環(huán)結束并輸出最優(yōu)路徑，否則清空禁忌表，Nc←Nc+1并跳轉到第3步，繼續(xù)下一輪循環(huán)。

4 算法實現(xiàn)及結果分析

選用國際上通用的TSPLIB基準庫中的Oliver30為例，對本論文提出的改進的蟻群算法進行實驗仿真，用VC++編程實現(xiàn)，以驗證其有效性。實驗環(huán)境：操作系統(tǒng)為Microsoft Windows XP Professional，CPU 為酷睿 2 雙核（1.6GHz），內存為1G。

分別對基本蟻群算法和改進的蟻群算法進行仿真。改進的蟻群算法的參數(shù)配置為：m=26，α=1.0，β=5.0，ρ=0.53，Q=1500，q0=0.22， 基本蟻群 算 法 參 數(shù) 配 置 為 ：m=26，α=1.0，β=5.0，ρ=0.53，Q=1500，將兩種算法的最大迭代次數(shù)都設置為1000次，分別進行15次試驗，結果如表1所示。另外，改進的蟻群算法得到的最優(yōu)解如圖1所示。

圖1 改進的蟻群算法求解Oliver30問題的最優(yōu)解

表1 基本蟻群算法和改進的蟻群算法求解Oliver30問題結果比較

從表1中可以看出，在相同的實驗環(huán)境下，相同的參數(shù)設置，相同的最大迭代次數(shù)，本文提出的改進蟻群算法得到的最優(yōu)解（423.912)和平均值（428.585)都要優(yōu)于基本蟻群算法得到的最優(yōu)解（440.555)和平均值（456.472)。 仿真結果表明，改進后的算法是有效的。

5 結束語

本文提出的改進蟻群算法通過對信息素初始量以及信息素更新策略等方面的改進，有效地克服了基本蟻群算法收斂速度慢，易于陷入局部最優(yōu)解的缺點。對TSP問題（Oliver30）進行仿真實驗結果表明，改進蟻群算法的性能較基本蟻群算法有明顯的改善。

[1]E L Lawler，J K Lenstra and D B Shmoys（eds.）.The Traveling Salesman Problem： A Guided Tour of Combinatorial Opti mization[M].New York： John Wiley&Sons，1985.

[2]李士勇.蟻群算法及其應用[M].哈爾濱：哈爾濱工業(yè)大學出版社，2004.

[3]孫京浩，李秋艷，楊欣斌等.基于蟻群算法的故障識別[J].華東理工大學學報，2004，30（2）：194-198.

[4]Colorni A.，Dorigo M.，Maniezzo V，et al.Distributed optimization by ant colonies[C].Proceedings of the First European Conference on Artificial Life，1991：134-142.

[5]段海濱.蟻群算法原理及其應用[M].北京：科學出版社，2005.

[6]周康，強小利，同小軍等.求解 TSP 算法[J].計算機工程與應用，2007，43（29）：43-47.

AN ANT COLONY ALGORITHM BASED IMPROVEMENT FOR TSP SOLUTIONS

YAN Xiao-yan1，2LI Yang1XIA Gui-lin2
（1 School of Information and Computer Science，Anhui Agricultural University，Hefei Anhui 230036）
（2 Computer Department of Chaohu College，Chaohu Anhui 238000 ）

The ant colony algorithm is a heuristic algorithm.It has advantages on a variety of combinatorial optimization problems such as the TSP.However，basic ant colony algorithm may converge slowly and fall into local optimal solution easily，which leads to stagnation.to avoid these shortcomings of the algorithm，it is proposed that different initial amount of pheromone be given to different edges in order to enhance the effects of the pheromone in the early algorithm and narrow the algorithm search range； it is also the purpose to carry out the global pheromone update，the best solution，the worst solution and general solution with different update strategies.Experimental results show that improved ant colony algorithm has better performance in solving the TSP than the basic ant colony algorithm in experimental conditions.

ant colony algorithm；TSP；initialization of pheromone；update of pheromone

TP301.6

A

1672－2868（2010）06－0021－04

2010－08-21

嚴小燕（1984-），女，安徽廬江人。安徽農業(yè)大學計算機應用技術專業(yè)研究生，巢湖學院計算機系教師。研究方向：計算機網(wǎng)絡。

責任編輯：陳 侃