蟻群算法的原理與應(yīng)用

1、蟻群算法的原理與運(yùn)用摘要：意大利學(xué)者通過模擬蟻群覓食行為提出了一種基于種群的模擬進(jìn)化算法蟻群算法。該算法已經(jīng) 在組合優(yōu)化、函數(shù)優(yōu)化、系統(tǒng)辨識、網(wǎng)絡(luò)路由、機(jī)器人路徑規(guī)劃等領(lǐng)域獲得了廣泛應(yīng)用，并取得了較好結(jié) 果。本文圍繞蟻群算法的原理、理論及其應(yīng)用，就TSP（旅行商問題X以及OPP（最優(yōu)路徑問題）在matlab 中進(jìn)行仿真并分析其結(jié)果。關(guān)鍵詞：蟻群算法；旅行商問題；最短路徑問題；仿真Abstract:A population-based simulated evolutionary algorithm called ant colony algorithm（ACA for short）was pr

2、oposed by Italian researchers. The algorithm has been widely applied to the fields of combinatorial optimization , function optimization, system identification, network routing, path planning of robot, good effects of application are gained. This paper focuses on the principles, theory, and applicat

3、ion of ACA, trying to solve the the traveling salesman problem and the optimal path problems by simulating in matlab to analyze the result.Keywords: ant colony algorithm; traveling salesman problem; shortest path problem ; simulation1緒論1.1引言各個螞蟻在沒有事先告訴他們食物在什么地方的前提下開始尋找食物。當(dāng)一只找到食物 以后，它會向環(huán)境釋放一種揮發(fā)性分泌物ph

4、eromone （稱為信息素，該物質(zhì)隨著時間的推移 會逐漸揮發(fā)消失，信息素濃度的大小表征路徑的遠(yuǎn)近）來實(shí)現(xiàn)的，吸引其他的螞蟻過來，這 樣越來越多的螞蟻會找到食物。有些螞蟻并沒有象其它螞蟻一樣總重復(fù)同樣的路，他們會另 辟蹊徑，如果另開辟的道路比原來的其他道路更短，那么，漸漸地，更多的螞蟻被吸引到這 條較短的路上來。最后，經(jīng)過一段時間運(yùn)行，可能會出現(xiàn)一條最短的路徑被大多數(shù)螞蟻重復(fù) 著。螞蟻究竟是怎么找到食物的呢？在沒有螞蟻找到食物的時候，環(huán)境沒有有用的信息素， 那么螞蟻為什么會相對有效的找到食物呢？這要?dú)w功于螞蟻的移動規(guī)則，尤其是在沒有信息 素時候的移動規(guī)則。首先，它要能盡量保持某種慣性，這樣使得

5、螞蟻盡量向前方移動（開始， 這個前方是隨機(jī)固定的一個方向），而不是原地?zé)o謂的打轉(zhuǎn)或者震動；其次，螞蟻要有一定 的隨機(jī)性，雖然有了固定的方向，但它也不能像粒子一樣直線運(yùn)動下去，而是有一個隨機(jī)的 干擾。這樣就使得螞蟻運(yùn)動起來具有了一定的目的性，盡量保持原來的方向，但又有新的試 探，尤其當(dāng)碰到障礙物的時候它會立即改變方向，這可以看成一種選擇的過程，也就是環(huán)境 的障礙物讓螞蟻的某個方向正確，而其他方向則不對。這就解釋了為什么單個螞蟻在復(fù)雜的 諸如迷宮的地圖中仍然能找到隱蔽得很好的食物。當(dāng)然，在有一只螞蟻找到了食物的時候，大部分螞蟻會沿著信息素很快找到食物的。但 不排除會出現(xiàn)這樣的情況：在最初的時候，一

6、部分螞蟻通過隨機(jī)選擇了同一條路徑，隨著這 條路徑上螞蟻釋放的信息素越來越多，更多的螞蟻也選擇這條路徑，但這條路徑并不是最優(yōu) （即最短）的，所以，導(dǎo)致了迭代次數(shù)完成后，螞蟻找到的不是最優(yōu)解，而是次優(yōu)解，這種 情況下的結(jié)果可能對實(shí)際應(yīng)用的意義就不大了。螞蟻如何找到最短路徑的？這一是要?dú)w功于信息素，另外要?dú)w功于環(huán)境，具體說是計(jì)算 機(jī)時鐘。信息素多的地方顯然經(jīng)過這里的螞蟻會多，因而會有更多的螞蟻聚集過來。假設(shè)有 兩條路從窩通向食物，開始的時候，走這兩條路的螞蟻數(shù)量同樣多(或者較長的路上螞蟻多， 這也無關(guān)緊要)。當(dāng)螞蟻沿著一條路到達(dá)終點(diǎn)以后會馬上返回來，這樣，短的路螞蟻來回一 次的時間就短，這也意味著重

7、復(fù)的頻率就快，因而在單位時間里走過的螞蟻數(shù)目就多，灑下 的信息素自然也會多，自然會有更多的螞蟻被吸引過來，從而灑下更多的信息素；而長 的路正相反，因此，越來越多地螞蟻聚集到較短的路徑上來，最短的路徑就近似找到了。也 許有人會問局部最短路徑和全局最短路的問題，實(shí)際上螞蟻逐漸接近全局最短路的，為什么 呢？這源于螞蟻會犯錯誤，也就是它會按照一定的概率不往信息素高的地方走而另辟蹊徑， 這可以理解為一種創(chuàng)新，這種創(chuàng)新如果能縮短路途，那么根據(jù)剛才敘述的原理，更多的螞蟻 會被吸引過來。1.2蟻群算法的基本原理蟻群算法是受自然界中真實(shí)蟻群算法的集體覓食行為的啟發(fā)而發(fā)展起來的一種基于群 體的模擬進(jìn)化算法，屬于隨

8、機(jī)搜索算法，所以它更恰當(dāng)?shù)拿謶?yīng)該叫人工蟻群算法，我們一般 簡稱為蟻群算法，至于人工蟻群和真實(shí)蟻群的區(qū)別,雙橋?qū)嶒?yàn)里面所顯示的那樣，螞蟻這種社 會性動物,雖然個體行為及其簡單，但是由這些簡單個體所組成的群體卻表現(xiàn)出及其復(fù)雜的 行為特征。這是因?yàn)槲浵佋趯ふ沂澄飼r，能在其經(jīng)過的路徑上釋放一種叫做信息素的物質(zhì)， 使得一定范圍內(nèi)的其他螞蟻能夠感覺到這種物質(zhì)，且傾向于朝著該物質(zhì)強(qiáng)度高的方向移動。 蟻群的集體行為表現(xiàn)為一種正反饋現(xiàn)象，蟻群這種選擇路徑的行為過程稱之為自催化行為， 由于其原理是一種正反饋機(jī)制，因此也可以把蟻群的行為理解成所謂的增強(qiáng)型學(xué)習(xí)系統(tǒng) (Reinforcement Learning s

9、ystem)下面引用M.Dorigo所舉的例子來說明蟻群發(fā)現(xiàn)最短路徑的 原理和機(jī)制，見圖1所示。假設(shè)D和H之間、B和H之間以及B和D之間通過C的距離為 1, C位于D和B的中央(見圖1(a)現(xiàn)在我們考慮在等間隔等離散世界時間點(diǎn)(t=0,1,2.)的 蟻群系統(tǒng)情況。假設(shè)每單位時間有30只螞蟻從A到B,另三十只螞蟻從E到D,其行走速度 都為1 (一個單位時間所走距離為l),在行走時，一只螞蟻可在時刻t留下濃度為1的信息素為 簡單起見,設(shè)信息素在時間區(qū)間(t十1,t+2)的中點(diǎn)(t+0.5)時刻瞬時完全揮發(fā)。在t=0時刻無 任何信息素，但分別有30只螞蟻在B、30只螞蟻在D等待出發(fā)。它們選擇走哪一條

10、路徑是完 全隨機(jī)的，因此在兩個節(jié)點(diǎn)上蟻群可各自一分為二，走兩個方向。但在t=1時刻，從A到B的 30只螞蟻在通向H的路徑上(見圖1 (b)發(fā)現(xiàn)一條濃度為巧的信息素，這是由巧只從B走向H 的先行螞蟻留下來的;而在通向C的路徑上它們可以發(fā)現(xiàn)一條濃度為30的信息素路徑，這是 由巧只走向BC的路徑的螞蟻所留下的氣息與15只從D經(jīng)C到達(dá)B留下的氣息之和(圖 1(C)。這時，選擇路徑的概率就有了偏差，向C走的螞蟻數(shù)將是向H走的螞蟻數(shù)的2倍。對 于從E到D來的螞蟻也是如此。這個過程一直會持續(xù)到所有的螞蟻?zhàn)罱K都選擇了最短的路徑為止。這樣，我們就可以理 解蟻群算法的基本思想：如果在給定點(diǎn)，一只螞蟻要在不同的路徑

11、中選擇，那么，那些被先行 螞蟻大量選擇的路徑(也就是信息素留存較濃的路徑)被選中的概率就更大，較多的信息素意 味著較短的路徑，也就意味著較好的問題回答。(a)Et=0蟻數(shù)30蟻數(shù)15蟻數(shù)15蟻數(shù)J5蟻數(shù)15蟻數(shù)30蟻數(shù)10蟻數(shù)20蟻數(shù)30A(b)蟻群路徑搜索實(shí)例1.3蟻群算法的算法描述蟻群算法可以看作為一種基于解空間參數(shù)化概率分布模型(c)(Parameterized ProbabilisticModel）的搜索算法框架Model 一 based search algorithms）。在蟻算法中，解空間參數(shù)化概率, 模型的參數(shù)就是信息素，因而這種參數(shù)化概率分布模型就是信息素模型。在基于模型的搜

12、索 算法框架中，可行解通過在一個解空間參數(shù)化概率分布模型上的搜索產(chǎn)生，此模型的參數(shù)用 以前產(chǎn)生的解來更新，使得在新模型上的搜索能夠集中在高質(zhì)量的解搜索空間內(nèi)這種方法 的有效性建立在高質(zhì)量的解總是包含好的解構(gòu)成元素的假設(shè)前提下，通過學(xué)習(xí)這種解構(gòu)成元 素對解的質(zhì)量的影響有助于找到一種機(jī)制，并通過解構(gòu)成元素的最佳組合來構(gòu)造出高質(zhì)量的 解。一般來說，一個記憶模型的搜索算法通常使用以下兩步迭代來解決優(yōu)化問題：1）可行解通過在解空間參數(shù)化概率分布模型上的搜索產(chǎn)生。2）用搜索產(chǎn)生的解來更新參數(shù)化概率模型，即更新解空間參數(shù)化概率分布的參數(shù)，使得 在新模型上的參數(shù)搜索能夠集中在高質(zhì)量的解搜索空間內(nèi)。在蟻群算法中

13、，基于信息素的解 空間參數(shù)化概率模型（信息素模型）以解構(gòu)造圖的形式給出。在解構(gòu)造圖上，定義了一種作為 隨機(jī)搜索機(jī)制的人工蟻群，螞蟻通過一種分布在解構(gòu)造圖上被稱為信息素的局部信息的指引, 在解構(gòu)造圖上移動，從而逐步的構(gòu)造出問題的可行。信息素與解構(gòu)造圖上的節(jié)點(diǎn)或弧相關(guān)聯(lián)， 作為解空間參數(shù)化概率分布模型的參數(shù)。由于TSP問題可以直接的映射為解構(gòu)造圖（城市為 節(jié)點(diǎn)，城市間的路徑為弧，信息素分布在弧上），加之TSP問題也是個NP難題，所以，蟻群算 法的大部分應(yīng)用都集中在TSP問題上。一般而言用于求解TSP問題、生產(chǎn)調(diào)度問題等優(yōu)化 問題的蟻群算法都遵循下面的統(tǒng)一算法框架。1.4蟻群算法的特點(diǎn)從蟻群算法的原

14、理不難看出，蟻群的覓食行為實(shí)際上是一種分布式的協(xié)同優(yōu)化機(jī)制。單 只螞蟻雖然能夠找到從蟻穴到食物源的一條路徑，但是找到最短路徑的可能性極小，只有當(dāng) 多只螞蟻組成蟻群時，其集體行為才突現(xiàn)出螞蟻的智能發(fā)現(xiàn)最短路徑的能力。在尋找最短路 徑的過程中，蟻群使用了一種間接的通信方式，即通過向所經(jīng)過的路徑上釋放一定的信息素， 其他螞蟻通過感知這種物質(zhì)的強(qiáng)弱來選擇下一步要走的路。總的來說，人工蟻群算法的主要 特點(diǎn)可以概括為以下幾點(diǎn)：1）采用分布式控制，不存在中心控制；2）每個個體只能感知局部的信息，不能直接使用全局信息；3）個體可以改變環(huán)境，并通過環(huán)境來進(jìn)行間接通訊；4）具有自組織性，即群體的復(fù)雜行為是通過個體

15、的交互過程中突現(xiàn)出來的智能；5）是一類概率型的全局搜索方法，這種非確定性是算法能夠有更多的機(jī)會求得全局最優(yōu) 解；6）其優(yōu)化過程不依賴于優(yōu)化問題本身的嚴(yán)格數(shù)學(xué)性質(zhì)，比如連續(xù)性、可導(dǎo)性以及目標(biāo)函 數(shù)和約束函數(shù)的精確數(shù)學(xué)描述；7）是一種基于多主體（Multi Agent）的智能算法，各主體之間通過相互協(xié)作來更好的適應(yīng) 環(huán)境；8）具有潛在的并行性，其搜索過程不是從一點(diǎn)出發(fā)，而是同時從多個點(diǎn)同時進(jìn)行。這種 分布式多智能體的協(xié)作過程是異步并發(fā)進(jìn)行的，分布并行模式將大大提高整個算法的運(yùn)行效 率和快速反應(yīng)能力。1.5蟻群算法的研究現(xiàn)狀1991年,意大利學(xué)者M(jìn).Dorigo等提出了第一個蟻群算法一螞蟻系統(tǒng)（AS

16、）并成功的應(yīng)用 于求解TSP問題。實(shí)驗(yàn)結(jié)果證明AS算法具有較強(qiáng)的魯棒性和發(fā)現(xiàn)較好的解的能力,但與此 同時也存在著一些缺陷,如收斂速度慢、易出現(xiàn)停滯現(xiàn)象等。該算法的問世引起了學(xué)者們的 普遍關(guān)注，并且針對AS算法的缺點(diǎn)，提出了一些改進(jìn)的蟻群算法。L.M.Gambardella,M.Dorig 提出了 Ant 一 Q算法,該算法用偽隨機(jī)比例狀態(tài)轉(zhuǎn)移規(guī)則(Pseudo random proportional state transition rule)替換 AS 算法中的隨機(jī)比例轉(zhuǎn)移規(guī)則(Stochastic proportional choice rule),從而 使Ant 一 Q算法在構(gòu)造解的過程

17、中能夠更好的保持知識探索(Exploration)與知識利用 (Exploitation)之間的平衡。除此之外，該算法中還引用了局部信息素更新機(jī)制和全局信息素 更新中的精英策略。國內(nèi)對蟻群算法的研究直到上世紀(jì)末才拉開序幕，目前國內(nèi)學(xué)者對蟻群算法的研究主要 是集中在算法的改進(jìn)和應(yīng)用上。吳慶洪和張紀(jì)會等通過向基本蟻群算法中引入變異機(jī)制，充 分利用2交換法簡潔高效的特點(diǎn)，提出了具有變異特征的蟻群算法。吳斌和史忠植首先在蟻 群算法的基礎(chǔ)上提出了相遇算法,提高了螞蟻一次周游的質(zhì)量，然后將相遇算法與采用并行 策略的分段算法相結(jié)合，提出一種基于蟻群算法的TSP問題分段求解算法。王穎和謝劍英通 過自適應(yīng)的改變

18、算法的揮發(fā)度等系數(shù),提出一種自適應(yīng)的蟻群算法以克服陷于局部最小的缺 點(diǎn)。覃剛力和楊家本根據(jù)人工螞蟻所獲得的解的情況動態(tài)地調(diào)整路徑上的信息素，提出了自 適應(yīng)調(diào)整信息素的蟻群算法。蟻群算法的應(yīng)用研究一直非?；钴S。繼 M.Dorig首先將AS算法用于TSP問題之 后,V.Maniezz等人首先將 AS算法應(yīng)用于指派問題(Quadratic Assignment Problem,簡稱 QAP).最近幾年,Gambardella, Thailard和Stutzle等也發(fā)表了 一些用蟻群算法求解QAP問題 的文章。目前，蟻群算法是求解QAP問題最有效的算法之一。2對蟻群算法的改進(jìn)與應(yīng)用范圍2.1對蟻群算法

19、的改進(jìn)雖然傳統(tǒng)的蟻群算法具有很強(qiáng)的全局尋優(yōu)解的能力。但也存在一些缺陷，例如:該算法 的搜索時間過長,大部分計(jì)算時間被用于解的構(gòu)造;在執(zhí)行過程中容易出現(xiàn)停滯現(xiàn)象,當(dāng)問題 規(guī)模較大時存在陷人局部最優(yōu)的可能性等。因此，研究者對傳統(tǒng)的蟻群算法進(jìn)行了很多改進(jìn) 研究。下面介紹兩種有代表性的改進(jìn)方法。最大最小蟻群系統(tǒng) 最大最小蟻群系統(tǒng)(Max 一 Min Ant System,MMAS)是德國學(xué)者 T.Stuetzle和H.Hoos提出的，是最具有貪婪式尋優(yōu)特征的改進(jìn)蟻群算法，目的在于防止過早 的算法停滯現(xiàn)象。如果信息素過度集中到幾條較好的路徑上，而其他路徑由于長時間沒有 螞蟻經(jīng)過,信息素逐漸揮發(fā)并趨近于零

20、，那么這些路徑就最終不再有螞蟻經(jīng)過。這種情況下, 有可能喪失尋求最佳路徑的機(jī)會，此時就出現(xiàn)停滯的現(xiàn)象。MMAS就是針對這種現(xiàn)象,對算法中信息素的濃度引人最大值和最小值限制:當(dāng)某條路徑 上的信息素濃度大于所設(shè)定的上限，則強(qiáng)制其為上限值相反，則令其為下限值。通過設(shè)定信息 素的上下限，一方面避免了某條路徑上的信息素濃度遠(yuǎn)大于其它路徑的信息素濃度從而有 效降低了過早停滯的可能。另一方面，不會因?yàn)槟承┞窂降男畔⑺貪舛冗^低而喪失發(fā)現(xiàn)新路 徑的可能。有研究實(shí)驗(yàn)表明,對于要求迭代次數(shù)較多的問題求解過程,MMAS算法與傳統(tǒng)的蟻 群算法相比，在尋找解的有效性方面和防止算法的過早停滯方面具有更好的效果。但是，需要

21、說明的是，僅采用最大最小信息素濃度的限制還不足以在較長的時間里持久消除停滯現(xiàn)象 因此，可以對其進(jìn)行進(jìn)一步改進(jìn)，例如，在該算法中引人信息素的平滑機(jī)制等。動態(tài)蟻群算法與傳統(tǒng)的蟻群算法相比，動態(tài)蟻群算法的改進(jìn)主要如下：在應(yīng)用于求解旅行商問題時，傳統(tǒng)的蟻群算法是據(jù)信息素和啟發(fā)函數(shù)來選擇目標(biāo)城市的, 這兩個因子對路徑選擇的影響力度是固定的。而動態(tài)蟻群算法在迭代過程中，選擇目標(biāo)城市 時引人動態(tài)因子。在傳統(tǒng)的蟻群算法中，對信息素的強(qiáng)度沒有限制，其揮發(fā)因子是一個常數(shù),因而有陷人局 部最優(yōu)的可能。而動態(tài)蟻群算法中設(shè)置動態(tài)變化的揮發(fā)因子，信息素濃度越高,則揮發(fā)因子越 大;濃度越低,揮發(fā)因子越小。通過限制，信息素的

22、濃度不可能無限增大，也不可能為零。這樣，由于目標(biāo)城市的動態(tài)選擇和信息素?fù)]發(fā)因子的動態(tài)性，動態(tài)蟻群算法有力地減少 進(jìn)化停滯現(xiàn)象。2.2蟻群算法的應(yīng)用蟻群算法能夠?qū)栴}求解的快速性、全 優(yōu)化特性和有限時間內(nèi)答案的合理性結(jié)合起來， 因此對于能夠直接轉(zhuǎn)化為路徑優(yōu)化問題的組合類尋優(yōu)問題能取得比較理想的效果。大規(guī)模集成電路的線網(wǎng)布局在大規(guī)模集成電路的線網(wǎng)布局中，需要根據(jù)電路和工藝 的要求完成芯片上單元或功能模塊的布局，然后實(shí)現(xiàn)它們之間的互連。此問題可看作是尋找 一個網(wǎng)格平面上兩端點(diǎn)之間繞過障礙的最短路徑問題。線網(wǎng)上的每個Agent根據(jù)啟發(fā)策略， 像螞蟻一樣在開關(guān)盒網(wǎng)格上爬行，所經(jīng)之處便設(shè)置一條金屬線,歷經(jīng)

23、一個線網(wǎng)的所有引腳之 后，線網(wǎng)便布通了。應(yīng)用蟻群算法，可以找到成本最低、最合理的線網(wǎng)布局，而且由于其本身 的并行性,比較適合于解決此類問題。通信網(wǎng)絡(luò)路由 近年來，許多學(xué)者將蟻群算法應(yīng)用于通訊領(lǐng)域,特別是通信網(wǎng)絡(luò)中的 路由問題。通網(wǎng)絡(luò)的路由是通過路由表進(jìn)行的,在每個節(jié)點(diǎn)的由表中，對每個目的節(jié)點(diǎn)都列 出了與該節(jié)點(diǎn)相連的節(jié)點(diǎn)，當(dāng)有數(shù)據(jù)包到達(dá)時，通過查詢路由表可知下一個將要到達(dá)的節(jié) 點(diǎn)。網(wǎng)絡(luò)信息的分布性、動態(tài)性、隨機(jī)性和異步性與蟻群算法非常相似，都是利用局部信息 發(fā)現(xiàn)解，間接通訊方式和隨機(jī)狀態(tài)的轉(zhuǎn)換。Dorigo.Di Caro和Gambardella首先將蟻群算 法應(yīng)用于網(wǎng)絡(luò)路由問題，并稱這種算法為

24、Ant Net。蟻群算法在電力系統(tǒng)中的應(yīng)用 電力系統(tǒng)優(yōu)化是一個復(fù)雜的系統(tǒng)工程，它包括無功優(yōu) 化、經(jīng)濟(jì)負(fù)荷分配、電網(wǎng)優(yōu)化及機(jī)組最優(yōu)投人等一系列問題其中很多是高維、非凸、非線 性的優(yōu)化問題。其中，機(jī)組最優(yōu)投人問題是尋求一個周期內(nèi)各個負(fù)荷水平下機(jī)組的最優(yōu)組合 方式及開停機(jī)計(jì)劃，使運(yùn)行費(fèi)用最小。利用狀態(tài)、決策及路徑概念。將機(jī)組最優(yōu)投人問題設(shè) 計(jì)成類似旅行商問題的模式，從而可方便地利用蟻群算法來求解。還有人將蟻群算法編人水 力發(fā)電規(guī)劃能源管理軟件，可很好地節(jié)約能源。此外，對于電力系統(tǒng)中的故障檢測，蟻群算 法也表現(xiàn)出較好的應(yīng)用前景。由于故障地點(diǎn)的估計(jì)信息來自保護(hù)繼電器和電路斷路器，那么 對所有故障部分的估

25、計(jì)可以看作是一個組合優(yōu)化問題。3蟻群算法在RPP問題中的應(yīng)用3.1什么是RPP問題路徑規(guī)劃問題(Routing Planning Problems, RPP)在航線設(shè)計(jì)、管道鋪設(shè)和改善城市交 通等現(xiàn)實(shí)應(yīng)用中有著十分重要的作用。根據(jù)不同的限制條件和求解要求，RPP問題又可以細(xì) 分為最優(yōu)路徑問題(Optimal Path Problems，OPP)、旅行商問題(Travelling Salesman Problem， TSP)以及帶時間窗的旅行商問題(Travelling Salesman Problem with Time Windows TSPTW) 等多個子問題。分類如圖2所示：路徑規(guī)劃問題

26、(RPP)單目懷點(diǎn)務(wù)目標(biāo)點(diǎn)單車輛求解 多車輛求釁炒仇 典旅行商問題帶時間窗-限制的車輛路徑問題帶時間窗限制的(OPP)(TSP)旅行商問袈(VRP)車輛路徑問題 (TSPTW) (VRPTW)圖2路徑規(guī)劃問題分類3.2 TSP問題3.2.1 TSP問題的描述給定n個城市的集合0，1，2,，n-1及城市之間環(huán)游的花費(fèi)Cij (0WiWn-1, 0WjWn-1, i尹j)。TSP問題是指找到一條經(jīng)過每個城市一次且回到起點(diǎn)的 最小花費(fèi)的環(huán)游。若將每個頂點(diǎn)看成是圖上的節(jié)點(diǎn)，花費(fèi)Cij為連接頂點(diǎn)Vi、Vj邊上的權(quán)， 則TSP問題就是在一個具有n個節(jié)點(diǎn)的完全圖上找到一條花費(fèi)最小的Hamilton回路。蟻群

27、算法求解TSP問題的流程 步驟1:nc=0(nc為迭代步數(shù)或搜索次數(shù))；每條邊上 的Tj(0)=c(常數(shù))，并且ATj=0 ；放置m個螞蟻到n個城市上。步驟2:將各螞蟻的初始出 發(fā)點(diǎn)置于當(dāng)前解集TABUk(s)中;對每個螞蟻k(k=1,.,m)，按概率Pij(t)移至下一城市j；將 城市j置于TABUk(s)中。步驟3:經(jīng)過n個時刻，螞蟻k可走完所有的城市，完成一次循 環(huán)。計(jì)算每個螞蟻?zhàn)哌^的總路徑長度Lk，更新找到的最短路徑。步驟4:更新每條邊上的 信息量Tij(t+n)。步驟5:對每一條邊置ATijuO； nc=nc+1。步驟6:若nc預(yù)定的迭代次數(shù) Ncmax，則轉(zhuǎn)步驟2；否則，打印出最短

28、路徑，終止整個程序。蟻群算法求解TSP問題的源代碼clear all close allclc%初始化蟻群m=31;%蟻群中螞蟻的數(shù)量，當(dāng)m接近或等于城市個數(shù)n時，本算法可以在最少的迭代次數(shù) 內(nèi)找到最優(yōu)解C=1304 2312;3639 1315;4177 2244;3712 1399;3488 1535;3326 1556;3238 1229;4196 1004; 4312 790;4386 570;3007 1970;2562 1756;2788 1491;2381 1676;1332 695;3715 1678; 3918 2179;4061 2370;3780 2212;3676 25

29、78;4029 2838;4263 2931;3429 1908;3507 2367; 3394 2643;3439 3201;2935 3240;3140 3550;2545 2357;2778 2826;2370 2975;% 城市的坐標(biāo)矩陣Nc_max=200;%最大循環(huán)次數(shù)，即算法迭代的次數(shù)，亦即螞蟻出動的撥數(shù)(每撥螞蟻的數(shù)量 當(dāng)然都是m)alpha=1;%螞蟻在運(yùn)動過程中所積累信息(即信息素)在螞蟻選擇路徑時的相對重要程度， alpha過大時，算法迭代到一定代數(shù)后將出現(xiàn)停滯現(xiàn)象beta=5;%啟發(fā)式因子在螞蟻選擇路徑時的相對重要程度rho=0.5;%0rho1,表示路徑上信息素的衰減

30、系數(shù)(亦稱揮發(fā)系數(shù)、蒸發(fā)系數(shù))，1-rho表示信 息素的持久性系數(shù)Q=100;%螞蟻釋放的信息素量，對本算法的性能影響不大%變量初始化n=size(C,1);%表示TSP問題的規(guī)模，亦即城市的數(shù)量D=ones(n,n);%表示城市完全地圖的賦權(quán)鄰接矩陣，記錄城市之間的距離for i=1:nfor j=1:nif ijD(i,j)=sqrt(C(i,1)-C(j,1)A2+(C(i,2)-C(j,2)A2);endD(j,i)=D(i,j);endendeta=1./D;%啟發(fā)式因子，這里設(shè)為城市之間距離的倒數(shù)pheromone=ones(n,n);%信息素矩陣，這里假設(shè)任何兩個城市之間路徑上的

31、初始信息素都為1 tabu_list=zeros(m,n);%禁忌表，記錄螞蟻已經(jīng)走過的城市，螞蟻在本次循環(huán)中不能再經(jīng)過這 些城市。當(dāng)本次循環(huán)結(jié)束后，禁忌表被用來計(jì)算螞蟻當(dāng)前所建立的解決方案，即經(jīng)過的路徑 和路徑的長度Nc=0;%循環(huán)次數(shù)計(jì)數(shù)器routh_best=zeros(Nc_max,n);% 各次循環(huán)的最短路徑length_best=ones(Nc_max,1);%各次循環(huán)最短路徑的長度length_average=ones(Nc_max,1);%各次循環(huán)所有路徑的平均長度while Ncq0for k=1:length(city_remained)probability(k)=(ph

32、eromone(city_visited(end),city_remained(k)Aalpha*(eta(city_visited(end),city _remained(k)Abeta;position=find(probability=max(probability);to_visit=city_remained(position(1);endelsefor k=1:length(city_remained)probability(k)=(pheromone(city_visited(end),city_remained(k)Aalpha*(eta(city_visited(end),c

33、ity _remained(k)Abeta;endprobability=probability/sum(probability);pcum=cumsum(probability);select=find(pcum=rand);to_visit=city_remained(select(1);end tabu_list(i,j)=to_visit;rvf “%*endendif Nc0tabu_list(1,:)=routh_best(Nc,:);%將上一代的最優(yōu)路徑(最優(yōu)解)保留下來，保證上 一代中的最適應(yīng)個體的信息不會丟失end%記錄本次循環(huán)的最佳路線total_length=zeros(

34、m,1);%m只螞蟻在本次循環(huán)中分別所走過的路徑長度for i=1:mr=tabu_list(i,:);%取出第i只螞蟻在本次循環(huán)中所走的路徑for j=1:(n-1)total_length(i)=total_length(i)+D(r(j),r(j+1);%第 i 只螞蟻本次循環(huán)中從起點(diǎn)城市 到終點(diǎn)城市所走過的路徑長度endtotal_length(i)=total_length(i)+D(r(1),r(n);%最終得到第 i 只螞蟻在本次循環(huán)中所走 過的路徑長度endlength_best(Nc+1)=min(total_length);%把m只螞蟻在本次循環(huán)中所走路徑長度的最小值 作為

35、本次循環(huán)中最短路徑的長度position=find(total_length=length_best(Nc+1);%找 到最短路徑的位置，即最短路徑是第 幾只螞蟻或哪幾只螞蟻?zhàn)叱鰜淼膔outh_best(Nc+1,:)=tabu_list(position (1),:);%把第一個走出最短路徑的螞蟻在本次循環(huán)中 所走的路徑作為本次循環(huán)中的最優(yōu)路徑length_average(Nc+1)=mean(total_length);%計(jì)算本次循環(huán)中m只螞蟻所走路徑的平均長 度Nc=Nc+1%更新信息素delta_pheromone=zeros(n,n);for i=1:mfor j=1:(n-1)de

36、lta_pheromone(tabu_list(i,j),tabu_list(i,j+1)=delta_pheromone(tabu_list(i,j),tabu_list(i,j+1)+Q /total_length(i);%total_length(i)為第i只螞蟻在本次循環(huán)中所走過的路徑長度(蟻周系統(tǒng)區(qū)別 于蟻密系統(tǒng)和蟻量系統(tǒng)的地方)enddelta_pheromone(tabu_list(i,n),tabu_list(i,1)=delta_pheromone(tabu_list(i,n),tabu_list(i,1)+Q/tot al_length(i);%至此把第i只螞蟻在本次循環(huán)中

37、在所有路徑上釋放的信息素已經(jīng)累加上去end%至此把m只螞蟻在本次循環(huán)中在所有路徑上釋放的信息素已經(jīng)累加上去pheromone=(1-rho).*pheromone+delta_pheromone;%本 次循環(huán)后所有路徑上的信息素%禁忌表清零，準(zhǔn)備下一次循環(huán)，螞蟻在下一次循環(huán)中又可以自由地進(jìn)行選擇 tabu_list=zeros(m,n);end%輸出結(jié)果，繪制圖形position=find(length_best=min(length_best);shortest_path=routh_best(position(1),:)shortest_length=length_best(positio

38、n(1)%繪制最短路徑figure(1)set(gcf,Name,Ant Colony OptimizationFigure of shortest_path,Color,r)N=length(shortest_path);scatter(C(:,1),C(:,2),50,filled);hold onplot(C(shortest_path(1),1),C(shortest_path(N),1),C(shortest_path(1),2),C(shortest_path(N),2)set(gca,Color,g)hold onfor i=2:Nplot(C(shortest_path(i-1

39、),1),C(shortest_path(i),1),C(shortest_path(i-1),2),C(shortest_path(i),2)hold onend%繪制每次循環(huán)最短路徑長度和平均路徑長度figure(2)set(gcf,Name,Ant Colony OptimizationFigure of length_best and length_average,Color,r)plot(length_best,r)set(gca,Color,g)hold onplot(length_average,k)運(yùn)行結(jié)果(a)(b)(c)圖3運(yùn)行結(jié)果圖3 （a）顯示31個城市最短路徑的走法；

40、圖3 （b）顯示每次搜索時的單次路徑長度的平 均值（上面的曲線）以及全局最短路徑（下面的曲線）；圖3（c）顯示最短路徑為15772。3.3 OPP問題3.3.1 OPP問題的描述 OPP問題是以一個事先指定好的節(jié)點(diǎn)為目標(biāo)，螞蟻只需要到達(dá)該目 標(biāo)即算一次搜索完成（如圖4所示）。但是螞蟻又無法忽略掉全部的“無用”節(jié)點(diǎn)，它必然要 途徑一些節(jié)點(diǎn)作為過渡才能到達(dá)目標(biāo)節(jié)點(diǎn)。因此在OPP問題的路網(wǎng)中，對螞蟻而言存在著目 標(biāo)節(jié)點(diǎn)（黑色節(jié)點(diǎn)）、過渡節(jié)點(diǎn)（灰色節(jié)點(diǎn)）以及“無用”節(jié)點(diǎn)（白色節(jié)點(diǎn)）而如何讓螞蟻 能夠清楚地分辨出三種節(jié)點(diǎn)之間的區(qū)別，是提高算法效率，提升最終解質(zhì)量的關(guān)鍵所在。圖4最優(yōu)路徑問題示意圖蟻群算法

41、求解OPP問題的流程 當(dāng)以用時最少，即最快到達(dá)目的地點(diǎn)為求解目標(biāo) 時，OPP問題可描述為：設(shè)有N個節(jié)點(diǎn)C=C1,C2,C3Cn，現(xiàn)任意選取一個出發(fā)點(diǎn)Co 和一個目標(biāo)點(diǎn)Cd，(Co, CdC)，求一條以Co為起點(diǎn)，Cd為終點(diǎn)的通路 Co, C1,C2, Cd，使得該通路的刃tR,匕2)為最小，其中d為該通路所包含的節(jié)點(diǎn)個數(shù)，t(Ck-1,Ck)為從節(jié) k-1點(diǎn)Ck-1至節(jié)點(diǎn)Ck所花費(fèi)的時間。蟻群算法求解OPP問題的源代碼function varargout = antinface(varargin)% ANTINFACE M-file for antinface.fig% ANTINFACE,

42、by itself, creates a new ANTINFACE or raises the existing% singleton*.% H = ANTINFACE returns the handle to a new ANTINFACE or the handle to %the existing singleton*.%ANTINFACE(CALLBACK,hObject,eventData,handles,.) calls the local% function named CALLBACK in ANTINFACE.M with the given input argument

43、s.% ANTINFACE(Property,Value,.) creates a new ANTINFACE or raises the% existing singleton*. Starting from the left, property value pairs are% applied to the GUI before antinface_OpeningFcn gets called. An% unrecognized property name or invalid value makes property application% stop. All inputs are p

44、assed to antinface_OpeningFcn via varargin.% *See GUI Options on GUIDEs Tools menu. Choose GUI allows only one% instance to run (singleton).% See also: GUIDE, GUIDATA, GUIHANDLES% Edit the above text to modify the response to help antinface% Last Modified by GUIDE v2.5 02-Jun-2008 10:29:35% Begin in

45、itialization code - DO NOT EDITgui_Singleton = 1;gui_State = struct(gui_Name, mfilename, .gui_Singleton, gui_Singleton, .gui_OpeningFcn, antinface_OpeningFcn, .gui_OutputFcn, antinface_OutputFcn, .gui_LayoutFcn,.gui_Callback, );if nargin & ischar(varargin1)gui_State.gui_Callback = str2func(varargin1

46、);endif nargoutvarargout1:nargout = gui_mainfcn(gui_State, varargin:);elsegui_mainfcn(gui_State, varargin:);end% End initialization code - DO NOT EDIT% - Executes just before antinface is made visible.function antinface_OpeningFcn(hObject, eventdata, handles, varargin)% This function has no output a

47、rgs, see OutputFcn.% hObject handle to figure% eventdata reserved - to be defined in a future version of MATLAB% handles structure with handles and user state (see GUIDATA)% varargin command line arguments to antinface (see VARARGIN)% Choose default command line output for antinface handles.output =

48、 hObject;% Update handles structureguidata(hObject, handles);h=waitbar(0,請等待.);for i=1:100waitbar(i/100);enddelete(h);% UIWAIT makes antinface wait for user response (see UIRESUME) % uiwait(handles.handles);% - Outputs from this function are returned to the command line. function varargout = antinfa

49、ce_OutputFcn(hObject, eventdata, handles) % varargout cell array for returning output args (see VARARGOUT);% hObject handle to figure% eventdata reserved - to be defined in a future version of MATLAB% handles structure with handles and user state (see GUIDATA)% Get default command line output from h

50、andles structure varargout1 = handles.output;function edit_initao_Callback(hObject, eventdata, handles)% hObject handle to edit_initao (see GCBO)% eventdata reserved - to be defined in a future version of MATLAB% handles structure with handles and user state (see GUIDATA)% Hints: get(hObject,String)

51、 returns contents of edit_initao as text%str2double(get(hObject,String) returns contents of edit_initao as a double% - Executes during object creation, after setting all properties.function edit_initao_CreateFcn(hObject, eventdata, handles)% hObject handle to edit_initao (see GCBO)% eventdata reserv

52、ed - to be defined in a future version of MATLAB% handles empty - handles not created until after all CreateFcns called% Hint: edit controls usually have a white background on Windows.% See ISPC and COMPUTER.if ispc & isequal(get(hObject,BackgroundColor), get(0,defaultUicontrolBackgroundColor) set(h

53、Object,BackgroundColor,white);end function edit_q_Callback(hObject, eventdata, handles)% hObject handle to edit_q (see GCBO)% eventdata reserved - to be defined in a future version of MATLAB% handles structure with handles and user state (see GUIDATA)% Hints: get(hObject,String) returns contents of

54、edit_q as text%str2double(get(hObject,String) returns contents of edit_q as a double% - Executes during object creation, after setting all properties.function edit_q_CreateFcn(hObject, eventdata, handles)% hObject handle to edit_q (see GCBO)% eventdata reserved - to be defined in a future version of

55、 MATLAB% handles empty - handles not created until after all CreateFcns called% Hint: edit controls usually have a white background on Windows.% See ISPC and COMPUTER.if ispc & isequal(get(hObject,BackgroundColor), get(0,defaultUicontrolBackgroundColor) set(hObject,BackgroundColor,white);end functio

56、n edit_alpha_Callback(hObject, eventdata, handles)% hObject handle to edit_alpha (see GCBO)% eventdata reserved - to be defined in a future version of MATLAB% handles structure with handles and user state (see GUIDATA)% Hints: get(hObject,String) returns contents of edit_alpha as text%str2double(get

57、(hObject,String) returns contents of edit_alpha as a double% - Executes during object creation, after setting all properties.function edit_alpha_CreateFcn(hObject, eventdata, handles)% hObject handle to edit_alpha (see GCBO)% eventdata reserved - to be defined in a future version of MATLAB% handles

58、empty - handles not created until after all CreateFcns called% Hint: edit controls usually have a white background on Windows.% See ISPC and COMPUTER.if ispc & isequal(get(hObject,BackgroundColor), get(0,defaultUicontrolBackgroundColor) set(hObject,BackgroundColor,white);end function edit_rou_Callba

59、ck(hObject, eventdata, handles)% hObject handle to edit_rou (see GCBO)% eventdata reserved - to be defined in a future version of MATLAB% handles structure with handles and user state (see GUIDATA)% Hints: get(hObject,String) returns contents of edit_rou as text%str2double(get(hObject,String) return

60、s contents of edit_rou as a double% - Executes during object creation, after setting all properties.function edit_rou_CreateFcn(hObject, eventdata, handles)% hObject handle to edit_rou (see GCBO)% eventdata reserved - to be defined in a future version of MATLAB% handles empty - handles not created u