范秋生

（黃岡職業(yè)技術(shù)學(xué)院計算機科學(xué)與技術(shù)系，湖北 黃岡 438002）

淺談旅行商問題與蟻群算法

范秋生

（黃岡職業(yè)技術(shù)學(xué)院計算機科學(xué)與技術(shù)系，湖北 黃岡 438002）

蟻群算法是繼模擬退火算法、遺傳算法、禁忌搜索算法、人工神經(jīng)網(wǎng)絡(luò)算法等啟發(fā)式搜索算法之后的又一種應(yīng)用于組合優(yōu)化問題的算法。根據(jù)蟻群算法的特性，求解旅行商問題，利用仿真實驗程序?qū)ο伻呵蠼饴眯猩虇栴}進行模擬。

蟻群算法；信息素；旅行商問題(TSP)

引言

蟻群算法就是利用群集智能解決組合優(yōu)化問題的典型例子。它是繼模擬退火算法、遺傳算法、禁忌搜索(Tabu Search)算法、人工神經(jīng)網(wǎng)絡(luò)算法等啟發(fā)式搜索算法之后的又一種應(yīng)用于組合優(yōu)化問題的算法[1]。

1、旅行商問題(TSP)簡介及旅行商問題描述：

給定n個城市的集合{0，1，2，…，n-1}及城市之間環(huán)游的費用 ci(j0 ≤i≤n-1，0≤j≤n-1，i≠j)或者距離。TSP問題是指找到一條經(jīng)過每個城市一次且回到起點的最小費用的環(huán)游。若將每個頂點看成是圖上的節(jié)點，費用 為c連ij接頂點Vi、Vj邊上的權(quán)，則TSP問題就是在一個具有n個節(jié)點的完全圖上找到一條費用最小的Hamilton回路[1]。本文所討論的TSP問題為對稱的TSP問題，而不是非對稱的TSP問題，對于非對稱的TSP問題(ASTP)詳情訪問TSPLIB。

以下是5個城市集的TSP

圖1 -1 對稱的TSP

圖1 -2 非對稱的TSP

旅行商問題的傳統(tǒng)求解算法

當了解TSP問題后，我們會感覺到這種求解最優(yōu)解的問題不算復(fù)雜，并且可以很快地的利用所學(xué)的傳統(tǒng)方法進行模擬求解。

大致算法可能如下：

(1)得到問題的規(guī)模，即城市的數(shù)量大??；

(2)利用數(shù)學(xué)中的排列組合求出該問題的所有不同的回路；

(3)利用循環(huán)、判斷、比較得到最優(yōu)回路。

在第2步中，可以得到一個完全圖的Hamilton回路的數(shù)量為

當n=3時，a=1；當然n的最小值為3

當n=4時，a=3；

當n=5時，a=12；對于小規(guī)模的n，可以快速地得到最優(yōu)解。

……但在實際當中n是比較大的，如在TSPLIB提供的數(shù)據(jù)中n的大小往往不小于30，那么a的值由于(n-1)的作用變得異常的龐大，這對計算的速率帶來問題。

首先需要通過n得到所有的Hamilton回路，計算該步時程序片段將會根據(jù)n的大小而出現(xiàn)大量的嵌套循環(huán)，而這點是難以忍受的，而且由于不得不保存這些回路的各城市信息，大量的插入操作也影響了整體計算的效率，優(yōu)化的余地較小，如果這一步出現(xiàn)遺漏將影響下一步。

傳統(tǒng)算法中會對第3步進行優(yōu)化，如加上一個初始值較大的最小值Rmin，用于提前結(jié)束一些計算，而遺憾的是循環(huán)次數(shù)根本沒有減少。

2、旅行商問題的特點

TSP問題只是NP完全問題的一個縮影，類似TSP的問題較多，如：資源二次分配問題，圖的著色問題，車輛的交通調(diào)度問題，集成電路的設(shè)計問題，通信網(wǎng)絡(luò)負載問題，0-1背包問題，甚至軍事中巡航導(dǎo)彈的導(dǎo)航問題[11]等等。由此可見他們與生活聯(lián)系緊密，存在普遍性，普遍性的存在導(dǎo)致了處理數(shù)據(jù)的隨機性。

如圖的著色問題(三色地圖)：相鄰的著色塊顏色不同，用最少的顏色進行著色。

圖2 -3 著色前

圖2 -4 著色后

蟻群算法的基本原理可大致描述如下：螞蟻屬于群居昆蟲，個體行為極其簡單，而群體行為卻相當復(fù)雜。相互協(xié)作的一群螞蟻很容易找到從蟻穴到食物源的最短路徑，而單個螞蟻則不能。人們通過大量的研究發(fā)現(xiàn)，螞蟻之所以能做到這一點是因為螞蟻個體之間通過在其所經(jīng)過的路徑上留下一種可稱之為信息素的物質(zhì)來進行信息傳遞。螞蟻可以嗅到這種信息素，而且可以根據(jù)信息素的濃度來指導(dǎo)自己對前進方向的選擇。同時，該信息素會隨著時間的推移逐漸揮發(fā)掉，基于此，路徑的長短及該路徑上通過的螞蟻的數(shù)量就對殘余信息素的強度產(chǎn)生影響。反過來信息素的強弱又指導(dǎo)著其它螞蟻的行動方向。螞蟻傾向朝著信息素強度高的方向移動。于是，由大量螞蟻組成的蟻群的集體行為便表現(xiàn)出一種信息正反饋現(xiàn)象：某一路徑上走過的螞蟻越多，則后者選擇該路徑的概率越大。螞蟻個體之間就是通過這種信息的交通達到搜索食物的目的。螞蟻算法是基于以上原理產(chǎn)生的。它是一種隨機搜索算法，與其他模型進化算法一樣，是通過候選解組成的群體進化過程來尋找最優(yōu)解[12]。

3、模擬蟻群算法

3.1 利用java語言模擬ant cycle system算法

3.1.1 城市類City.java

由于該類主要是用于存儲tsp文件數(shù)據(jù)，所以該類的設(shè)計比較簡單。

主要的屬性有：城市的編號id，城市的橫坐標coordinateX、縱坐標coordinateY。

主要的方法有：setId()，getId()，setCo o rd inateX()，getCo o rd inateX()，setCoordinateY()，getCoordinateY()。

3.1.2 螞蟻類Ant.java

利用java中的線程模擬蟻群中的螞蟻。

為了在以后螞蟻類能夠更好的擴展，使每只螞蟻都能夠設(shè)置自身的參數(shù)α、β、?、Q，所以增設(shè)了這些屬性。當然tabuk與allowedk是必不可少的，其他屬性有編號，初始城市編號，當前城市編號，當前螞蟻走過的距離，螞蟻選擇下一城市的概率數(shù)組等。

允許每只螞蟻可以根據(jù)自身的特點設(shè)置自身的選擇城市的方法以及更新信息素的方法。這樣便可以將螞蟻類設(shè)計為一抽象類，并繼承線程類。主要方法有設(shè)置選城概率setChooseProbability()，根據(jù)隨機數(shù)判斷所選城市，tabuk與allowedk的增減操作，對于run()方法只需按照步驟2至步驟5編寫即可。(由于更新信息素的方法的相同，所以將該方法提至到主類)

3.1.3主線程代碼

/**

*主線程

*/

public void run(){

while(loopCurrent＜loopCount&&!isAntsStop()){

if(getFinishAntCount()==antCount){//所有螞蟻完成一次遍歷

setBestResult()；//設(shè)置最短結(jié)果

if(bestChange){

bestDistanceField.setText(""+this.getBestDistance())；

changeTimesValue.setText(""+changeTimes)；

bestRoutArea.setText("起點"+this.getBestRout().toString().replaceAll("，"，"--＞")+"終點")；

tspCanvas.repaint()；

}

updateCitysPheromone()；//更新城市間的信息素

resetAnts()；//重新設(shè)置螞蟻們的相關(guān)數(shù)據(jù)

setFinishAntCount(0)；

loopCurrent++；

this.loopCurrentValue.setText(""+loopCurrent)；

if(loopCurrent＞=loopCount){

setAntsStop(true)；//終止螞蟻們的遍歷

}

for(int i=0；i＜antCount；i++){//喚醒所有等待的螞蟻

synchronized(ANTS[i]){

ANTS[i].notify()；

}

}

}

}

}

4、結(jié)語

本文描述了旅行商問題，利用傳統(tǒng)算法求解時的弊端，蟻群算法的基本原理，如何將蟻群算法運用與旅行商問題。

[1]姜長元.基于混合信息素遞減的蟻群算法[J].計算機工程與應(yīng)用,2007,43(32)：62-64.

[2]Colorni A，Dorigo M，Maniezzo V.An investigation of some properties of an ant algorithm[C]//Proc of the Parallel Problem Solving from Nature Conference(PPSN’ 92).Brussels，Belgium：Elsevier Publishing，1992：509～520

[3]王會穎,賈瑞玉,章義剛,齊平.一種求解0-1背包問題的快速蟻群算法[J].計算機技術(shù)與發(fā)展,2007,17(1)：104-107.

[4]吳慶洪，張紀會，徐心和.具有變異特征的蟻群算法[J].計算機研究與發(fā)展，1999，36(10)：1240-1245.

On the Traveling Salesman Problem with the Ant Colony Algorithm

FAN Qiu-sheng
(Huanggang Polytechnic College，Huanggang 438002 Hubei)

Ant colony algorithm is another algorithm applied in combinatorial optimization problems following the simulated annealing algorithm,genetic algorithm,tabu search algorithm,artificial neural network algorithm heuristic search algorithm.According to the characteristics of ant colony algorithm,solving the traveling salesman problem,we can use the simulation programs to simulate the ant colony algorithm traveling salesman problem.

Ant colony algorithm;Pheromone;Traveling salesman problem(TSP)

A

1 672－1047（2010）06－0017-0 3

10.3969/j.issn.1672－1047.2010.06.05

2010-10-03

范秋生，男，副教授。E-mail:fanqiu@hgpu.edu.cn.

［責(zé)任審校：金為民］