嚴(yán)小燕 李 旸 夏桂林

（1安徽農(nóng)業(yè)大學(xué)信息與計(jì)算機(jī)學(xué)院，安徽 合肥 230036）

（2巢湖學(xué)院計(jì)算機(jī)系，安徽 巢湖 238000）

蟻群算法在求解旅行商問(wèn)題中的改進(jìn)

嚴(yán)小燕1，2李 旸1夏桂林2

（1安徽農(nóng)業(yè)大學(xué)信息與計(jì)算機(jī)學(xué)院，安徽 合肥 230036）

（2巢湖學(xué)院計(jì)算機(jī)系，安徽 巢湖 238000）

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

蟻群算法；旅行商問(wèn)題；信息素初始化；信息素更新

1 引言

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

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

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

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

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

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

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

2.1 蟻群算法的原理

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

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

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

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

（1）路徑選擇機(jī)制

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

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

（2）信息素更新機(jī)制

為了模擬避免殘留信息素過(guò)多引起殘留信息淹沒(méi)啟發(fā)信息，在每只螞蟻?zhàn)咄暌徊交蛘咄瓿蓪?duì)所有n個(gè)城市的遍歷（一個(gè)循環(huán)結(jié)束）后，要對(duì)殘留信息素進(jìn)行更新處理。（t+n)時(shí)刻，所有的螞蟻完成了一次周游，路徑（i，j）上信息素可根據(jù)以下公式做調(diào)整：

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

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

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

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

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

（2）在路徑狀態(tài)轉(zhuǎn)移上，增強(qiáng)搜索過(guò)程的指導(dǎo)性，同樣對(duì)每一個(gè)當(dāng)前城市，判斷下一個(gè)城市是否屬于這個(gè)子集，再確定轉(zhuǎn)移概率；

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

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

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

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

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

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

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

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

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

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

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

4 算法實(shí)現(xiàn)及結(jié)果分析

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

分別對(duì)基本蟻群算法和改進(jìn)的蟻群算法進(jìn)行仿真。改進(jìn)的蟻群算法的參數(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ù)都設(shè)置為1000次，分別進(jìn)行15次試驗(yàn)，結(jié)果如表1所示。另外，改進(jìn)的蟻群算法得到的最優(yōu)解如圖1所示。

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

表1 基本蟻群算法和改進(jìn)的蟻群算法求解Oliver30問(wèn)題結(jié)果比較

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

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

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

[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]李士勇.蟻群算法及其應(yīng)用[M].哈爾濱：哈爾濱工業(yè)大學(xué)出版社，2004.

[3]孫京浩，李秋艷，楊欣斌等.基于蟻群算法的故障識(shí)別[J].華東理工大學(xué)學(xué)報(bào)，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]段海濱.蟻群算法原理及其應(yīng)用[M].北京：科學(xué)出版社，2005.

[6]周康，強(qiáng)小利，同小軍等.求解 TSP 算法[J].計(jì)算機(jī)工程與應(yīng)用，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

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

責(zé)任編輯：陳 侃