基于蟻群算法的旅行商問題的研究

李輝

摘 要：群居性昆蟲行為的研究為計(jì)算機(jī)科學(xué)家提供了設(shè)計(jì)分布式控制和優(yōu)化算法的有力方法。對(duì)以蟻群算法為代表的群集智能的研究已經(jīng)逐漸成為一個(gè)研究熱點(diǎn)。蟻群算法在實(shí)際的生活中有很大的用處，比如求解旅行商問題，文章介紹了一種求解復(fù)雜TSP的蟻群算法，闡述了該算法的基本原理及實(shí)現(xiàn)過程，并且在本文中嘗試用編碼的形式將基本蟻群算法應(yīng)用到求解旅行商問題中去。

關(guān)鍵詞：基本蟻群算法；信息素；旅行商問題

1 意義和目標(biāo)

近年來，許多學(xué)者對(duì)蜜蜂、螞蟻等一些昆蟲的行為進(jìn)行了大量的研究，特別是他們的集體行為，而這些動(dòng)物一般都是群居昆蟲。每個(gè)昆蟲的能力雖然十分有限，但昆蟲群體的能力卻遠(yuǎn)遠(yuǎn)超過所有個(gè)體能力的總和。比如，螞蟻群可以快速建立起巢穴與食物之間的最短路徑。令人驚奇的是，每只螞蟻并不直接比較每條路徑，而僅僅只是遵守信息素釋放/跟隨規(guī)則就能找到最佳路徑。螞蟻群的這種能力很自然地引起了計(jì)算機(jī)科學(xué)家的興趣。旅行商問題的定義并不統(tǒng)一，一般廣泛認(rèn)為這樣定義：假若有多個(gè)城市，而這多個(gè)城市的距離為已知條件，這個(gè)距離也可以理解為多個(gè)城市之間的開銷，若要得到某一個(gè)旅行商走遍所有城市的一條回路，但必須滿足所有城市之間的距離的和為最小，也可以是城市之間的開銷達(dá)到最小值的這樣的一條回路。求解TSP問題的算法較多，但文章使用基本蟻群算法來解決旅行商問題。

2 國內(nèi)外研究現(xiàn)狀

為了得到解決組合優(yōu)化問題的某種計(jì)算機(jī)智能方法，Mnaeizzo、Cootmi、Dorigo在意大利的米蘭理工學(xué)院，發(fā)現(xiàn)了螞蟻系統(tǒng)，也就是本文中提到的蟻群算法，這是第一次提出的蟻群算法思想，是從螞蟻尋找食物的過程中發(fā)現(xiàn)的。人們由蟻群的集體行為得到了蟻群算法，可以說傳統(tǒng)求解組合優(yōu)化問題的算法可以稱之為新型仿生算法，而蟻群算法就是其中一種。從第一次提出蟻群算法以后，Dorigo等人又對(duì)蟻群算法做了不少改進(jìn)，這些改進(jìn)可以從以下模塊來理解：首先，加強(qiáng)了蟻群算法的實(shí)際應(yīng)用的背景；其次，又有新的算法模型的出現(xiàn)，是從原來蟻群算法的基礎(chǔ)上做了較大的改進(jìn)。20世紀(jì)初，科學(xué)家們逐漸關(guān)注了一種蟻群算法模型，這種模型叫做螞蟻群體優(yōu)化，也就是antcolonyoptimization，這是由Dorigo、cmabardena以蟻群算法為前期知識(shí)得到的一種求解組合優(yōu)化問題的方法。后來，wanger，stutzle，Mnomarhce等人在此基礎(chǔ)上不斷進(jìn)行研究。由此得到的兩種模型被實(shí)踐到了工作布置機(jī)器人和信息分析等領(lǐng)域，這兩種模型是分別由Bnobaeau得到的簡單閉值模型和Dneuebuogr等人得到的BM模型。其中，簡單閉值模型是從螞蟻群體的分工合作總結(jié)出來的，而BM模型是由螞蟻的筑造墓地的動(dòng)作集總結(jié)出來的。在用蟻群算法解決旅行商問題上，研究者Thomastuzel、Hoferhoos進(jìn)行了大量的研究，他們發(fā)現(xiàn)了一種叫做最大最小系統(tǒng)的求解旅行商問題的方法，他的英文是maxminantsysetm，他的求解結(jié)果要?jiǎng)儆谄胀ǖ南伻核惴ā６趪鴥?nèi)的蟻群算法研究領(lǐng)域，也呈現(xiàn)了一股熱浪，一些研究類的文獻(xiàn)也逐漸涌現(xiàn)。由此，在蟻群算法的應(yīng)用方面也做了很大的改進(jìn)，比如在路由調(diào)度應(yīng)用和優(yōu)化應(yīng)用等方面都進(jìn)行了大量的時(shí)間，當(dāng)然也有一些進(jìn)步的地方，下面舉出幾個(gè)有改進(jìn)和突出性的兩個(gè)人物：其中自適應(yīng)蟻群算法，是由王穎發(fā)現(xiàn)的，他的英文名字是adpativeAntSystem，在蟻群算法的基礎(chǔ)上加上變異參數(shù)，是由吳慶洪發(fā)現(xiàn)的，他的英文名字叫做MutationAntsystem。從世界自然的生物群中，可以模擬得到很多生物算法，在這很短暫的幾十年的發(fā)展中，這些生物算法是模擬仿生的，一般來說他的特征是：魯棒性和通用性，尤其優(yōu)秀表現(xiàn)在組合優(yōu)化問題中，特別是離散型方面，同時(shí)也獲得了大量科學(xué)家進(jìn)行研究。本文嘗試的是用蟻群算法解決旅行商問題，是因?yàn)橄伻核惴ㄔ诼眯猩虇栴}上有很好的解決結(jié)果，當(dāng)然，除了旅行商問題以外，在其他的方面，蟻群算法也能表現(xiàn)的非常優(yōu)秀、及其強(qiáng)大的生命力和非常好的進(jìn)步空間，這些主要的問題包括：作業(yè)調(diào)度問題、GCP問題、NP難題二次分配問題、LSI（Large Scale Integration）設(shè)計(jì)、通訊互聯(lián)網(wǎng)中的負(fù)載均衡問題、互聯(lián)網(wǎng)的routing table的選擇問題等等。

3 算法理論分析

人們通過觀察螞蟻的覓食過程，總結(jié)出了蟻群算法。螞蟻在覓食的過程中，采取了分工合作的機(jī)制，并且依靠一種叫做信息激素的化學(xué)物質(zhì)來實(shí)現(xiàn)，人們發(fā)現(xiàn)，螞蟻總是能夠找到從螞蟻的窩巢找到食物的最近的路徑，這種是通過螞蟻之間的合作和信息激素來實(shí)現(xiàn)的。整個(gè)過程可以描述如下：首先，第一只螞蟻在尋找食物的過程中，是隨機(jī)行走路徑去尋找的，沒有一定的依據(jù)，也沒有前面提到的信息激素，但這只螞蟻在經(jīng)過的路徑上都會(huì)留下一定的信息激素，當(dāng)?shù)诙晃浵伮愤^尋找食物的時(shí)候，就根據(jù)留下的信息激素去尋找食物，而螞蟻留下的信息激素具有一定的特征，該信息激素會(huì)隨著時(shí)間的推移逐漸揮發(fā)，我們總是假設(shè)一只螞蟻在單位路程上留下的信息激素是相等的，那么經(jīng)常被螞蟻經(jīng)過的路徑上留下的信息激素就越高，所有的螞蟻都是行走在信息激素較高的路徑上，久而久之，行走的螞蟻就越來越多，那么隨著時(shí)間的推移，尋找的最短路徑上留下的信息激素也就最多，這樣，所有的螞蟻都會(huì)隨著這條最短的路徑去尋找食物，那么從螞蟻窩巢到食物的最短路徑就產(chǎn)生了，蟻群算法就是根據(jù)這個(gè)理論實(shí)現(xiàn)的。

4 算法的技術(shù)路線

從算法的理論分析看出，在蟻群算法中，正是因?yàn)樾畔⒓に氐淖饔茫軌蛘业阶疃痰穆窂剑哌^的螞蟻越多，留下的信息激素也就越多，而螞蟻又是根據(jù)信息激素較多的路徑行走的，正是這種激發(fā)的效應(yīng)實(shí)現(xiàn)了蟻群算法。我們的算法也是，在獲得最終的最優(yōu)解也就是最短解的過程中，總是由信息激素的多寡和一些啟發(fā)式的信息獲取下一步的解，并且這個(gè)解是對(duì)整個(gè)全局的最終解的最優(yōu)解，這樣一步一步得到解組合成最終解，注意在整個(gè)過程中信息激素是不斷揮發(fā)的。最后，將這一過程用算法來進(jìn)行表達(dá)：

⑴算法涉及到的參數(shù)必須在第一步進(jìn)行確定。主要的參數(shù)包括，螞蟻：N只，信息激素：Y，一般激素的單位為強(qiáng)度，城市：m個(gè)，總的迭代次數(shù)：k，信息啟發(fā)式因子：r，期望啟發(fā)式因子：I，信息素?fù)]發(fā)系數(shù)：d。城市一般不用名稱，用數(shù)字代替，分別為：1，2，3，4…m，接著進(jìn)入下一步。

⑵根據(jù)總的迭代次數(shù)的值，如果此次迭代次數(shù)的值小于k，那么進(jìn)入第六步，否則進(jìn)入下一步。

⑶在其中一個(gè)時(shí)間，將一個(gè)城市定為mi，命令其中一只螞蟻從mi開始游歷所有的城市，當(dāng)然，螞蟻會(huì)在游歷的過程中留下所謂的信息激素，當(dāng)這只螞蟻游歷完以后，再命令另外一只螞蟻進(jìn)行游歷，同樣，該螞蟻也會(huì)在路上留下信息激素，同樣的過程，命令所有螞蟻都對(duì)所有城市進(jìn)行一次游歷，接著進(jìn)入下一步。

⑷這一步是讓所有的城市都要作為起點(diǎn)進(jìn)行游歷，如果有沒有作為起點(diǎn)的城市，接著執(zhí)行上一步，當(dāng)所有城市作為起點(diǎn)游歷完畢，進(jìn)入下一步。

⑸統(tǒng)計(jì)得到群補(bǔ)螞蟻游歷的路徑距離值，且獲取路徑上的新的信息激素的值，然后將迭代次數(shù)累計(jì)，計(jì)入上面的第二步。

⑹得到最終值，算法終止。

5 數(shù)據(jù)實(shí)驗(yàn)及結(jié)果

針對(duì)51、76個(gè)城市的TSP問題的解決方案，將上述提出的蟻群算法結(jié)合到改問題中并應(yīng)用到該問題中，最后進(jìn)行了仿真實(shí)驗(yàn)。

實(shí)驗(yàn)采用visual C++ 6.0 作為開發(fā)工具，所用語言為c++。

實(shí)驗(yàn)所需要的硬件環(huán)境：硬件為內(nèi)存為256M，CPU為Pentium Ⅲ的計(jì)算機(jī)。

實(shí)驗(yàn)的仿真結(jié)果如表1、表2所示：

6 結(jié)語

文章最初的目的只是一個(gè)簡單的應(yīng)用，用蟻群算法來解決著名的旅行商問題，只是將理論實(shí)踐到了具體的問題，所以，本文還有很多的改進(jìn)空間，這只是一個(gè)基本蟻群算法的實(shí)現(xiàn)，所以，在實(shí)驗(yàn)設(shè)計(jì)方面還有很大的改進(jìn)空間。

[參考文獻(xiàn)]

[1]GutjahrW J.A graph2based ant system and its convergence[J].Future Generation Computer System，2000，16（8）：873-888.

[2]Dorigo M，Dicaro G.The ant colony optimization metaheuristic New Ideas in Optimization.London，U K：McGrawHill， 1999：11-32.

[3]鄒鵬，周智，江賀，等.求解旅行商問題的循環(huán)局部搜索算法的運(yùn)行時(shí)間和性能分布分析[J].計(jì)算機(jī)學(xué)報(bào)，2006，29（1）：92-99.

[4]李士勇.蟻群算法及其應(yīng)用[M].哈爾濱：哈爾濱工業(yè)大學(xué)出版社，2004：22-40.

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

[6]林威.基于遺傳算法的Job Shop調(diào)度問題求解[J].計(jì)算機(jī)應(yīng)用，2006，26（7）：1694-l696.

[7]蔡之華，彭錦國，高偉，等.一種改進(jìn)的求解TSP問題的演化算法[J].計(jì)算機(jī)學(xué)報(bào)，2005（28）：823-828.

[8]朱喜基.基于蟻群算法的旅行商問題的研究[J].無線互聯(lián)科技，2012（8）：23-25..