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

范秋生

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

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

范秋生

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

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

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

引言

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

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

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

以下是5個(gè)城市集的TSP

圖1 -1 對(duì)稱的TSP

圖1 -2 非對(duì)稱的TSP

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

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

大致算法可能如下：

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

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

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

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

當(dāng)n=3時(shí)，a=1；當(dāng)然n的最小值為3

當(dāng)n=4時(shí)，a=3；

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

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

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

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

2、旅行商問題的特點(diǎn)

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

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

圖2 -3 著色前

圖2 -4 著色后

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

3、模擬蟻群算法

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

3.1.1 城市類City.java

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

主要的屬性有：城市的編號(hào)id，城市的橫坐標(biāo)coordinateX、縱坐標(biāo)coordinateY。

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

3.1.2 螞蟻類Ant.java

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

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

允許每只螞蟻可以根據(jù)自身的特點(diǎn)設(shè)置自身的選擇城市的方法以及更新信息素的方法。這樣便可以將螞蟻類設(shè)計(jì)為一抽象類，并繼承線程類。主要方法有設(shè)置選城概率setChooseProbability()，根據(jù)隨機(jī)數(shù)判斷所選城市，tabuk與allowedk的增減操作，對(duì)于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("起點(diǎn)"+this.getBestRout().toString().replaceAll("，"，"--＞")+"終點(diǎn)")；

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)算法求解時(shí)的弊端，蟻群算法的基本原理，如何將蟻群算法運(yùn)用與旅行商問題。

[1]姜長(zhǎng)元.基于混合信息素遞減的蟻群算法[J].計(jì)算機(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]王會(huì)穎,賈瑞玉,章義剛,齊平.一種求解0-1背包問題的快速蟻群算法[J].計(jì)算機(jī)技術(shù)與發(fā)展,2007,17(1)：104-107.

[4]吳慶洪，張紀(jì)會(huì)，徐心和.具有變異特征的蟻群算法[J].計(jì)算機(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é)任審校：金為民］