改進(jìn)的蟻群算法在移動(dòng)Agent路徑選擇中的應(yīng)用研究

1、河北科技大學(xué) 2010 年研究生考試試卷學(xué)號(hào)：20081041 姓名：徐韓 學(xué)院：信息學(xué)院 專業(yè)及研究方向：通信與信息系統(tǒng) 網(wǎng)絡(luò)管理技術(shù) 考試科目：智能優(yōu)化算法及其應(yīng)用 考試時(shí)間： 2010-5-20 學(xué)時(shí)及學(xué)分： 36 學(xué)時(shí) 2 學(xué)分 2010 年 6 月 3 日摘要移動(dòng)Agent遷移過(guò)程中路徑選擇的一個(gè)經(jīng)典的、代表問(wèn)題旅行Agent問(wèn)題(TAP)，是一個(gè)復(fù)雜的組合優(yōu)化問(wèn)題。蟻群算法(ant colony algorithm)作為一種新的生物進(jìn)化算法，具有并行、正反饋和啟發(fā)式搜索等特點(diǎn)，在求解該問(wèn)題上具有一定的優(yōu)勢(shì)，但搜索時(shí)間長(zhǎng)，易陷入局部最優(yōu)是其突出缺點(diǎn)。本文結(jié)合現(xiàn)有的蟻群算法和移動(dòng)Age

2、nt本身的特點(diǎn)，提出了基于任務(wù)權(quán)重和算法迭代次數(shù)來(lái)修改路徑上信息素更新規(guī)則和信息素?fù)]發(fā)系數(shù)這兩種新方法，來(lái)更好的提高蟻群算法的求解性能。關(guān)鍵詞：移動(dòng)Agent，蟻群算法，任務(wù)權(quán)重一 移動(dòng)Agent路徑選擇問(wèn)題的概述近年來(lái)，隨著人工智能和網(wǎng)絡(luò)技術(shù)的飛速發(fā)展，國(guó)內(nèi)外眾多的研究學(xué)者對(duì)移動(dòng)Agent技術(shù)的研究和發(fā)展也更加關(guān)注。移動(dòng)Agent技術(shù)的遷移策略是該技術(shù)的基礎(chǔ)技術(shù)核心，而移動(dòng)Agent路徑選擇問(wèn)題，正是移動(dòng)Agent遷移策略的主要研究對(duì)象，所以求解移動(dòng)Agent路徑選擇問(wèn)題具有重要的意義。移動(dòng)Agent的遷移策略，受到了學(xué)術(shù)界和工業(yè)界廣泛的關(guān)注，并進(jìn)行了大量探索和研究，取得了一定的成績(jī)。旅行A

3、gent問(wèn)題(TAP)是移動(dòng)Agent路徑選擇問(wèn)題中的一個(gè)經(jīng)典例子。該問(wèn)題是根據(jù)移動(dòng)Agent的任務(wù)、網(wǎng)絡(luò)的軟硬件環(huán)境和其他約束條件為移動(dòng)Agent規(guī)劃出最佳的遷移路徑。很多研究學(xué)者對(duì)該問(wèn)題都進(jìn)行了大量的研究和實(shí)驗(yàn)，提出了很多有效的方法和思想，如遺傳算法，模擬退化算法等等，在該問(wèn)題上取得的一定的效果。旅行Agent問(wèn)題(TAP)是一個(gè)NP完全問(wèn)題，其時(shí)間度、空間復(fù)雜度都高，這就要求求解該問(wèn)題的方法一般需要具備自適應(yīng)、自學(xué)習(xí)、分布式、并行化等特點(diǎn)。蟻群算法是意大利學(xué)者Dorigo等人在20世紀(jì)90年代，首先提出的一種基于種群的啟發(fā)式仿生算法。該算法不僅僅具有以上特征，而且還具有正反饋、引入與問(wèn)題

4、相關(guān)領(lǐng)域的知識(shí)等特點(diǎn)，所以蟻群算法求解該問(wèn)題是非常合適。蟻群算法在求解該問(wèn)題上具有很強(qiáng)的優(yōu)勢(shì)，但是隨著問(wèn)題規(guī)模的增大和一些不確定性因素的存在，它會(huì)表現(xiàn)出全局搜索能力不強(qiáng)，易于陷入局部最優(yōu)等缺陷，因此，本文在基本蟻群算法的基礎(chǔ)上，理解和掌握現(xiàn)有的其他改進(jìn)思想和方法，提出了基于任務(wù)權(quán)重和算法迭代次數(shù)的自適應(yīng)蟻群算法來(lái)求解該問(wèn)題，對(duì)仿真實(shí)驗(yàn)結(jié)果進(jìn)行了分析和比較。實(shí)驗(yàn)結(jié)果表明，本文兩種改進(jìn)方法使該算法的性能有了一定的提高。1.2蟻群算法蟻群算法的研究背景在當(dāng)今社會(huì)中，隨著人工智能(AI)和網(wǎng)絡(luò)技術(shù)的飛速發(fā)展，科學(xué)技術(shù)與其他的多種學(xué)科相互交叉，相互滲透和融合，不僅給人們的生活、學(xué)習(xí)和工作等方面帶了便利，

5、而且也從根本上改變了人類的生活和生產(chǎn)。與此同時(shí)，隨著人類生活空間的不斷擴(kuò)大和對(duì)世界認(rèn)識(shí)水平的不斷提高，人們又對(duì)科學(xué)技術(shù)的發(fā)展提出了更高、更多的要求，期待著更多的研究學(xué)者對(duì)它進(jìn)行不斷的研究和提高，其中高效的優(yōu)化技術(shù)和智能計(jì)算的要求也進(jìn)一步的迫切需求。為了提高優(yōu)化技術(shù)水平和智能計(jì)算的發(fā)展，近些年來(lái)有很多的研究學(xué)者，特別是在生物方面的研究專家和學(xué)者，通過(guò)對(duì)大自然中很多生物的生活現(xiàn)象和規(guī)律進(jìn)行了大量的研究和探討，提出了很多的群體智能算法。它們是一種基于生物信息系統(tǒng)的智能仿生算法，學(xué)者們是對(duì)社會(huì)性昆蟲相互合作進(jìn)行工作的研究，從生物進(jìn)化和仿生學(xué)角度受到啟發(fā)而提出的。眾所周知，社會(huì)性昆蟲如蜜蜂，螞蟻等，雖然

6、其單個(gè)個(gè)體的力量很小，行為方式很簡(jiǎn)單、隨機(jī)，但是它們卻可以憑借集體的力量進(jìn)行一些復(fù)雜的社會(huì)性活動(dòng)，來(lái)更好的完成單個(gè)個(gè)體很難甚至不能完成的行為或活動(dòng)，如它們可以通過(guò)社會(huì)分工等方式來(lái)更快的找到食物，共同的建造巢穴和防止外敵入侵等等。這種群體所表現(xiàn)出來(lái)的“智能”，就可以稱之為群體智能5(Swarm Intelligence SI)。群體智能中的群體(Swarm)是指“一組相互之間可以進(jìn)行間接通信(Stigmergy)的主體，這組主體能夠合作進(jìn)行分布式問(wèn)題求解”。而所謂群體智能是指“無(wú)智能的主體通過(guò)合作表現(xiàn)出智能行為的特性”。群體智能在沒(méi)有集中控制并且不提供全局模型的前提下，為尋找復(fù)雜的分布式問(wèn)題的解

7、決方案提供了基礎(chǔ)。在很多專家和研究學(xué)者的共同努力下，有很多的群體智能算法得以提出并有了很好的發(fā)展和應(yīng)用。雖然有些智能算法有了成熟的理論基礎(chǔ)，但是把它們能夠很好的應(yīng)用到現(xiàn)實(shí)生活中還有一定的差距，需要我們共同的參與，進(jìn)行不斷的探索、嘗試和研究。蟻群算法正是群體智能算法中的一個(gè)重要分支。在對(duì)一些生物昆蟲，如蜜蜂、螞蟻等進(jìn)行大量的觀察和研究后，生物學(xué)家發(fā)現(xiàn)了像螞蟻這樣弱小的昆蟲，在覓食的時(shí)候，通過(guò)群體的力量，經(jīng)過(guò)多次的探索和尋找，最終能夠找得到一條從巢穴到食物源的最短路徑。為了進(jìn)一步的研究，生物學(xué)家就在螞蟻尋找食物的路徑上，設(shè)置一些障礙物來(lái)影響螞蟻尋找路徑，經(jīng)過(guò)一段時(shí)間的搜尋，最終螞蟻還是找到了從巢穴

8、到食物源的最短路徑。經(jīng)過(guò)各種實(shí)驗(yàn)，生物學(xué)家進(jìn)一步的研究表明，螞蟻在尋找食物的探索過(guò)程中，會(huì)在所經(jīng)過(guò)的路徑上釋放一種揮發(fā)的化學(xué)物質(zhì)，這種特殊的物質(zhì)被稱之為信息素(Pheromone)。信息素可以沉積在路徑上，并隨著時(shí)間逐步的揮發(fā)。當(dāng)螞蟻選擇路徑的時(shí)候，它們傾向于沿著信息素氣味較濃的路徑上前進(jìn)。因此信息素可以引導(dǎo)螞蟻來(lái)更快的，更有可能的找到離巢穴最近的食物。實(shí)驗(yàn)結(jié)果表明，正是這種特殊的物質(zhì)，能夠使螞蟻找到從巢穴通向食物的最短路徑。也可以說(shuō)，當(dāng)螞蟻的巢穴和食物之間存在較多路徑時(shí)，整個(gè)蟻群可以通過(guò)搜索各個(gè)個(gè)體螞蟻留下的信息素的痕跡來(lái)找到往返于蟻穴和食物之間的最短的路徑。蟻群算法的歷史和科學(xué)意義蟻群算法

9、（ant colony algorithm）是由意大利學(xué)者M(jìn).Dorigo等在20世紀(jì)90年代初期研究螞蟻尋找從巢穴到食物源的路徑時(shí)，從生物進(jìn)化的機(jī)制中受到啟發(fā)，提出了一種新型的模擬進(jìn)化算法。該算法具有穩(wěn)健性（魯棒性）、正反饋性和分布式計(jì)算等優(yōu)點(diǎn)，在求解復(fù)雜的組合優(yōu)化問(wèn)題上有更強(qiáng)的優(yōu)勢(shì)，在分配問(wèn)題、Job-shop調(diào)度等問(wèn)題上，都有了較好的實(shí)驗(yàn)結(jié)果。在求解計(jì)算機(jī)算法中經(jīng)典的“旅行商問(wèn)題 (Traveling SalesmanProblem.TSP)”時(shí)，眾多的研究學(xué)者根據(jù)算法基本原理，在算法中設(shè)計(jì)出了虛擬的“螞蟻”來(lái)搜索不同的路線，還有虛擬的“信息素”，它會(huì)隨著時(shí)間逐漸的消失。當(dāng)每只螞蟻每次隨

10、機(jī)選擇要走的路徑，它們會(huì)盡可能的傾向于選擇路徑較短、信心素濃度較高的路徑，根據(jù)“信息量較濃的路線更近”的原則，即可選擇出最佳的路徑。由于該算法利用了正反饋的機(jī)制，使得較短的路徑能夠有較大的機(jī)會(huì)得到選擇，并且采用了概率算法，來(lái)選擇下一步要走的路徑，所以它能夠不局限于局部最優(yōu)解。雖然對(duì)蟻群算法的研究時(shí)間并不長(zhǎng)，遠(yuǎn)不如像遺傳算法，模擬退火等算法那樣形成系統(tǒng)的分析方法和堅(jiān)實(shí)的數(shù)學(xué)基礎(chǔ)和理論基礎(chǔ)，但是它的提出，能夠?yàn)榻鉀Q一些復(fù)雜的系統(tǒng)優(yōu)化問(wèn)題提供了一種新的，更好的求解算法，特別是在求解離散型組合優(yōu)化的問(wèn)題上，蟻群算法表現(xiàn)出了其他進(jìn)化算法無(wú)法比擬的優(yōu)越性。蟻群算法不僅具有魯棒性、分布式計(jì)算、正反饋性、易于

11、和其他的智能算法相結(jié)合的特點(diǎn)，而且還能夠智能搜索、全局優(yōu)化等優(yōu)勢(shì)。該算法已經(jīng)引起了眾多專家和學(xué)者的注意，現(xiàn)在正被越來(lái)越多的研究者關(guān)注和探討，算法的理論得到不斷的完善，應(yīng)用范圍也普及到許多的科學(xué)技術(shù)及工程領(lǐng)域，是一種有良好發(fā)展前景的模擬進(jìn)化算法。1.3移動(dòng)Agent技術(shù)移動(dòng)Agent的簡(jiǎn)介20世紀(jì)90年代初，由General Magic公司在推出系統(tǒng)TeleScript時(shí)提出了移動(dòng)Agetn的概念。移動(dòng)Agent是一個(gè)能在異構(gòu)的網(wǎng)絡(luò)中，自主的從一臺(tái)主機(jī)遷移到另一臺(tái)主機(jī)，并可與其他Agent或主機(jī)上的資源交互的實(shí)體，實(shí)際上它是分布式計(jì)算機(jī)技術(shù)與Agen技術(shù)的相互結(jié)合的產(chǎn)物。傳統(tǒng)的服務(wù)器和RPC客戶

12、之間的交互需要連續(xù)的通信，但是移動(dòng)的Agent可以遷移到目標(biāo)服務(wù)器上，與之本地進(jìn)行高速通信，這種本地通信節(jié)省了網(wǎng)絡(luò)資源。移動(dòng)Agent遷移的內(nèi)容包括其代碼和運(yùn)行的狀態(tài)。運(yùn)行的狀態(tài)可分為數(shù)據(jù)和執(zhí)行這兩種狀態(tài)：數(shù)據(jù)狀態(tài)是指與移動(dòng)Agent運(yùn)行情況相關(guān)的數(shù)據(jù)堆內(nèi)容；執(zhí)行的狀態(tài)是指移動(dòng)Agent當(dāng)前運(yùn)行時(shí)的狀態(tài)和情況。如運(yùn)行棧內(nèi)容、程序計(jì)數(shù)器等。移動(dòng)Agent與遠(yuǎn)程執(zhí)行不同，移動(dòng)Agent可以能夠不斷的從一個(gè)網(wǎng)絡(luò)主機(jī)遷移到另一個(gè)主機(jī)，能夠根據(jù)自己的需要自主的進(jìn)行移動(dòng)。移動(dòng)Agent也不同進(jìn)程遷移，一般來(lái)說(shuō)，進(jìn)程遷移的系統(tǒng)不允許進(jìn)程遷移到哪里和選擇什么時(shí)候，而移動(dòng)Agent可以帶有狀態(tài)，所以，移動(dòng)Age

13、nt可以根據(jù)應(yīng)用的需要隨時(shí)可以移動(dòng)到它想去的地方。移動(dòng)Agent與Applet存在差異，Applet只能從服務(wù)器向客戶端單方向的移動(dòng)，然而移動(dòng)Agent卻可以在服務(wù)器和客戶之間進(jìn)行自由雙向的移動(dòng)。移動(dòng)Agent還有很多的優(yōu)點(diǎn)，移動(dòng)Agent技術(shù)通過(guò)將服務(wù)請(qǐng)求Agent狀態(tài)遷移到目標(biāo)服務(wù)器端執(zhí)行，所以Agent可以較少通過(guò)網(wǎng)絡(luò)傳輸這一中間環(huán)節(jié)，而直接面對(duì)要訪問(wèn)的服務(wù)器資源，從而有效的避免了大量數(shù)據(jù)的網(wǎng)絡(luò)傳輸，大幅度的降低了系統(tǒng)對(duì)網(wǎng)絡(luò)帶寬的依賴。移動(dòng)Agent可以不需要統(tǒng)一調(diào)度，經(jīng)過(guò)用戶創(chuàng)建的Agent可以異步的在不同的結(jié)點(diǎn)上工作，等到任務(wù)完成后再將相應(yīng)的結(jié)果傳送給用戶。為了完成某項(xiàng)復(fù)雜的任務(wù)，用

14、戶可以創(chuàng)建多個(gè)Agent，同時(shí)在一個(gè)或若干個(gè)主機(jī)或服務(wù)器上運(yùn)行，形成并行的求解能力。此外，它還有很好的自治性和智能路由等特性。gent的歷史意義及應(yīng)用Agent是人工智能領(lǐng)域中的一部分。簡(jiǎn)單的說(shuō)，Agent是指模擬人類行為與關(guān)系、具有一定智能，并能夠自主運(yùn)行和提供相應(yīng)服務(wù)的實(shí)體。Agent與現(xiàn)在流行的軟件實(shí)體(如對(duì)象、構(gòu)件)相比，粒度較大，自主性強(qiáng)，智能化較高。隨著現(xiàn)代網(wǎng)絡(luò)技術(shù)的發(fā)展，我們可以讓Agent在網(wǎng)絡(luò)中移動(dòng)并執(zhí)行，完成某些功能，把任務(wù)的結(jié)果帶回來(lái)。這就是移動(dòng)Agent(MobileAgent)的思想。Agent技術(shù)的誕生和發(fā)展是人工智能技術(shù)(AI)和網(wǎng)絡(luò)技術(shù)發(fā)展的必然結(jié)果。隨著人工智

15、能和計(jì)算機(jī)技術(shù)的發(fā)展以及萬(wàn)維網(wǎng)(WWW，World Wide Web)和互聯(lián)網(wǎng)(Internet)的出現(xiàn)及發(fā)展，集中式的系統(tǒng)已經(jīng)不能很好的適應(yīng)科學(xué)技術(shù)的發(fā)展需要。針對(duì)這樣的情況，分布式處理等技術(shù)(包括分布式人工智能)和并行計(jì)算應(yīng)運(yùn)而生，并在過(guò)去的20多年中飛速的發(fā)展。近10年來(lái)，Agent技術(shù)和多Agent系統(tǒng)與人工智能領(lǐng)域有著密切的關(guān)系，它們的研究成為分布式人工智能研究的一個(gè)熱點(diǎn)。網(wǎng)絡(luò)化和智能化的發(fā)展促進(jìn)了Agent技術(shù)和多Agent系統(tǒng)的發(fā)展。Agent技術(shù)在不斷的發(fā)展，同時(shí)可以應(yīng)用到電子商務(wù)、智能決策、空襲目標(biāo)模型系統(tǒng)和遠(yuǎn)程教育等方面，顯示出Agent技術(shù)的優(yōu)越性，能夠更好的為我們提供便

16、利，具有很好的研究和發(fā)展前景。二 基本蟻群算法及其應(yīng)用蟻群算法(ant colony algorithm)又稱為人工蟻群算法，是受到真實(shí)螞蟻行為研究的啟發(fā)而提出來(lái)的，是一種模擬進(jìn)化算法。該算法具有穩(wěn)健性(魯棒性)、正反饋性和分布式計(jì)算等優(yōu)點(diǎn)，在求解復(fù)雜的組合優(yōu)化問(wèn)題上有其優(yōu)勢(shì)，該方法求解二次分配問(wèn)題、TSP問(wèn)題和作業(yè)調(diào)度等問(wèn)題，取得了較好的成果。該算法已經(jīng)顯示出它在求解復(fù)雜優(yōu)化問(wèn)題，特別是離散優(yōu)化問(wèn)題方面的優(yōu)勢(shì)，是一種很有發(fā)展前景的智能計(jì)算方法。2.1蟻群算法的基本原理20世紀(jì)90年代初期，意大利學(xué)者M(jìn).Dorigo等人從生物進(jìn)化和仿生學(xué)角度出發(fā)，研究螞蟻尋找路徑的自然行為，通過(guò)大量的觀察和研

17、究，提出了蟻群算法20-22。為了更好的說(shuō)明蟻群算法的基本原理，針對(duì)蟻群搜索食物的過(guò)程進(jìn)行分析。像蜜蜂、飛蛾、螞蟻等群居昆蟲，盡管單個(gè)昆蟲的行為很簡(jiǎn)單，但正是由這些簡(jiǎn)單的個(gè)體所組成的群體，卻能表現(xiàn)出復(fù)雜的行為。螞蟻這類群居的昆蟲，盡管沒(méi)有視覺(jué)，經(jīng)過(guò)一段時(shí)間后，卻能找到由蟻穴到食物源的最優(yōu)路徑，原因是什么呢？國(guó)內(nèi)外的仿生學(xué)家經(jīng)過(guò)大量細(xì)致的觀察研究后發(fā)現(xiàn)，螞蟻個(gè)體之間是通過(guò)一種稱之為信息素(pheromone)的特殊物質(zhì)進(jìn)行信息傳遞和交流。在搜索較好路徑的過(guò)程中，螞蟻能夠在它所經(jīng)過(guò)的路徑上留下該物質(zhì)，而且其他螞蟻在運(yùn)動(dòng)過(guò)程中能夠感知這種物質(zhì)，并以此確定自己的運(yùn)動(dòng)方向。所以，這些大量的螞蟻組成的蟻群

18、集體的行為便表現(xiàn)出一種信息正反饋的現(xiàn)象：某一條路徑上走過(guò)的螞蟻越多，后來(lái)螞蟻選擇該路徑的概率就越大。螞蟻個(gè)體之間就是通過(guò)這種特殊物質(zhì)進(jìn)行信息的交流，達(dá)到搜索食物的目的。本文用比較形象化的圖示，來(lái)說(shuō)明螞蟻群體的路徑搜索原理和機(jī)制。下面用M.Dorigo所舉的例子來(lái)說(shuō)明蟻群系統(tǒng)的原理。如圖2-1所示，蟻群系統(tǒng)的初始狀態(tài)。設(shè)A是螞蟻的巢穴，E是食物源，H、C是兩個(gè)繞過(guò)障礙物的節(jié)點(diǎn)。由于障礙物的存在，螞蟻只能繞過(guò)C或H由E到達(dá)A，或由A到達(dá)E。各節(jié)點(diǎn)之間的距離如圖所示。設(shè)每個(gè)時(shí)間單位，有30只螞蟻由E到達(dá)D點(diǎn)和有30只螞蟻由A到達(dá)B，螞蟻在經(jīng)過(guò)的路徑上留下的外激素為1。設(shè)外激素的停留時(shí)間為1。圖2-1

19、蟻群系統(tǒng)的初始狀態(tài)圖2-2蟻群系統(tǒng)的t=0時(shí)刻的狀態(tài)如圖2-2所示，蟻群系統(tǒng)在開始時(shí)刻的狀態(tài)。由于路徑DH，DC，BH,BC信息存在，位于D和B的螞蟻可以隨機(jī)選擇路徑。從統(tǒng)計(jì)學(xué)的角度考慮，可以認(rèn)為它們以相同的概率選擇DH，DC，BH,BC。經(jīng)過(guò)一段時(shí)間后，路徑BCD和BHD上螞蟻數(shù)目的差距越來(lái)越大，直至大多數(shù)螞蟻選擇較短的路徑BCD。圖2-3蟻群系統(tǒng)t=1時(shí)刻的狀態(tài)如圖2-3所示，蟻群系統(tǒng)在t=1時(shí)刻的狀態(tài)。此時(shí)將有20只螞蟻由D和B到達(dá)C，有10只螞蟻由D和B到達(dá)H。經(jīng)過(guò)一段時(shí)間，大量的螞蟻將會(huì)以越來(lái)越大的概率選擇路徑BCD，最終完全選擇路徑BCD，從而找到由蟻巢到食物源的最短的路徑。由此可

20、見(jiàn)，螞蟻個(gè)體之間的信息交換是一個(gè)正反饋機(jī)制的過(guò)程。在相同的時(shí)間和區(qū)域內(nèi)，較短的路徑就會(huì)有更大的機(jī)率被選擇。蟻群算法是一種隨機(jī)搜索，智能的仿生算法，與其他的進(jìn)化算法一樣，通過(guò)群體的候選解進(jìn)行進(jìn)化，來(lái)篩選出全局最優(yōu)解，此過(guò)程包括兩個(gè)階段：適應(yīng)階段與協(xié)調(diào)階段。在適應(yīng)階段中，各候選解就會(huì)根據(jù)積累的信息不斷的調(diào)整自身的結(jié)構(gòu)；在第二階段，候選解之間通過(guò)信息素的交流，希望產(chǎn)生性能更好的解。蟻群算法作為一種通用型優(yōu)化方法，與遺傳算法一樣，不需要任何先驗(yàn)知識(shí)，開始只是隨機(jī)的選擇搜索路徑，經(jīng)過(guò)一段時(shí)間對(duì)算法解的空間的“了解”，搜索變得的有規(guī)律，并發(fā)揮其正反饋的性能，直至最終取得全局最優(yōu)解。蟻群算法對(duì)搜索空間的“了

21、解”機(jī)制主要包括以下幾方面：(1).螞蟻的記憶。一只螞蟻搜索過(guò)的路徑，當(dāng)下次搜索時(shí)就不會(huì)再被選擇，由此可以在蟻群算法中建立tabu(禁忌）列表來(lái)存儲(chǔ)已經(jīng)訪問(wèn)的節(jié)點(diǎn)，進(jìn)行模擬。(2).螞蟻利用信息素(pheromone)進(jìn)行相互通信。螞蟻在選擇的路徑上會(huì)釋放一種叫做信息素的物質(zhì)，當(dāng)它們的同伙在進(jìn)行路徑選擇的時(shí)候，會(huì)根據(jù)留在路徑上的信息素進(jìn)行選擇，這時(shí)信息素就成為螞蟻之間進(jìn)行通信的媒介。(3).螞蟻的集群活動(dòng)。一只螞蟻的運(yùn)動(dòng)很難到達(dá)食物源，但是通過(guò)整個(gè)蟻群進(jìn)行搜索就完全不同。當(dāng)某些路徑上經(jīng)過(guò)的螞蟻越來(lái)越多的時(shí)候，在這些路徑上留下的信息素也就越來(lái)越多，導(dǎo)致信息素強(qiáng)度增大，所以，該路徑被選擇的概率隨之

22、增大，從而進(jìn)一步增大該路徑的信息素強(qiáng)度，而當(dāng)其他某些路徑上通過(guò)的螞蟻較少時(shí)，路徑上的信息素就會(huì)隨時(shí)間推移而蒸發(fā)。因此，模擬這種現(xiàn)象可利用群體的智能來(lái)建立路徑選擇機(jī)制，使蟻群算法的搜索朝向最優(yōu)解進(jìn)化。蟻群算法所利用的搜索機(jī)制呈現(xiàn)出一種正反饋或自催化特征，可將蟻群算法模型理解成增強(qiáng)型學(xué)習(xí)系統(tǒng)。步驟：nc0；(nc為迭代步數(shù))對(duì)各和進(jìn)行初始化；將m只螞蟻隨機(jī)的置于n個(gè)頂點(diǎn)上；步驟：將各個(gè)螞蟻的初始節(jié)點(diǎn)置于當(dāng)前解集中；對(duì)每只螞蟻k(k=1,2,.m)，按概率轉(zhuǎn)移至下一個(gè)頂點(diǎn)j；將頂點(diǎn)j置于當(dāng)前解集；步驟：計(jì)算各螞蟻的目標(biāo)函數(shù) (k1,2,.m)k=；記錄當(dāng)前的最好的全局最優(yōu)解；步驟：按相應(yīng)的更新方程修

23、改軌跡上的信息素強(qiáng)度；步驟：對(duì)各邊(i,j)，置，ncnc+1；步驟：若nc小于預(yù)定的迭代次數(shù)，并且沒(méi)有退化行為(即找到的都是相同的解)則轉(zhuǎn)到步驟；步驟：輸出目前最好的解。2.3蟻群算法的研究現(xiàn)狀蟻群算法的優(yōu)點(diǎn)蟻群算法的主要的優(yōu)點(diǎn)概括如下。(1).蟻群算法是一種結(jié)合了貪婪搜索算法、正反饋機(jī)制和分布式計(jì)算，具有很好的搜索較優(yōu)解能力。貪婪式搜索有助于在搜索過(guò)程中早期找出可接受的解決方案，縮短了搜索時(shí)間，正反饋能夠快速的發(fā)現(xiàn)較優(yōu)解，分布式計(jì)算避免了早熟收斂。(2).蟻群算法具有很強(qiáng)的并行性和魯棒性，對(duì)基本的蟻群算法模型稍加修改，便可應(yīng)用于其他問(wèn)題。如車輛路徑問(wèn)題、多任務(wù)目標(biāo)分配、數(shù)據(jù)挖掘等問(wèn)題。(3

24、).可以不通過(guò)個(gè)體之間直接通信，而是有效的通過(guò)信息素進(jìn)行合作，這樣的系統(tǒng)具有較好的擴(kuò)充性。由此，隨著系統(tǒng)中個(gè)體增加，系統(tǒng)開銷將非常小。(4).易于與其他的算法結(jié)合，蟻群算法很容易與人工免疫算法、遺傳算法等算法結(jié)合，以改善算法的性能。蟻群算法的幾個(gè)缺陷盡管蟻群算法具有很強(qiáng)的全局尋優(yōu)能力，在很多的領(lǐng)域中得到了廣泛的應(yīng)用，但也存在一些缺點(diǎn)。(1).一般情況下，該算法需要較長(zhǎng)的搜索時(shí)間。蟻群中各個(gè)個(gè)體的運(yùn)動(dòng)是隨機(jī)的，盡管通過(guò)信息素交換能夠朝向最優(yōu)路徑方向進(jìn)化，但是當(dāng)群體規(guī)模較大時(shí)，很難在較短的時(shí)間內(nèi)，從大量雜亂無(wú)章的路徑中，找出一條較好的路徑。這是因?yàn)樵谶M(jìn)化的初級(jí)階段，各條路徑上的信息素的差別小。通過(guò)

25、信息正反饋機(jī)制，使得較好路徑上的信息量逐漸增大，經(jīng)過(guò)較長(zhǎng)的一段時(shí)間，才使那些較好路徑上的信息量明顯高于其他路徑上的信息量，隨著這一過(guò)程的進(jìn)行，差別越來(lái)越明顯，從而最終收斂于比較好的路徑。(2).該算法容易出現(xiàn)停滯現(xiàn)象(stagnation behavior)，即搜索進(jìn)行到一定的程度后，所有的個(gè)體發(fā)現(xiàn)的解完全一致，不能對(duì)解的空間進(jìn)一步進(jìn)行搜索，不利于發(fā)現(xiàn)更好的解。對(duì)于這些問(wèn)題，已經(jīng)引起了許多研究學(xué)者的注意，并提出了很多改進(jìn)算法，比如，智能蟻群算法39-40，基于多樣信息素的蟻群算法等幾種典型的改進(jìn)算法。2.4蟻群算法的應(yīng)用隨著眾多的研究學(xué)者對(duì)蟻群算法原理的探討以及對(duì)該算法的改進(jìn)，蟻群算法的應(yīng)用也

26、不斷的深入到其他的新領(lǐng)域中。(1).車輛調(diào)度車輛調(diào)度問(wèn)題是一類復(fù)雜的組合優(yōu)化問(wèn)題，是近年來(lái)物流控制優(yōu)化中的一個(gè)研究熱點(diǎn)。該問(wèn)題可描述為：現(xiàn)已知客戶的位置坐標(biāo)和貨物需求量，一個(gè)車隊(duì)(有多個(gè)車輛)從一個(gè)配送中心出發(fā)，每個(gè)需求點(diǎn)只被一輛車訪問(wèn)，且該車所訪問(wèn)需求點(diǎn)的總需求量不能超過(guò)該車輛的負(fù)載能力，應(yīng)如何安排車輛行走路線使得總路線最短。要求每輛車運(yùn)輸完畢后回到出發(fā)點(diǎn)(供應(yīng)點(diǎn))。目前，除了一些經(jīng)典的智能算法以外，采用TSP風(fēng)格的蟻群算法同樣可以求解VRP，求解時(shí)可以將車輛模擬成螞蟻?，F(xiàn)在，國(guó)內(nèi)外很多得研究學(xué)者，在蟻群算法求解VRP方面的研究也取的了不少成果，但是模擬效果跟現(xiàn)實(shí)生活中VRP問(wèn)題的解決還有一定差距。所以，為了更好的解決該問(wèn)題，對(duì)蟻群算法的研究還有待于進(jìn)一步的深入。(2).網(wǎng)絡(luò)路由通信問(wèn)題蟻群算法M.Dorigo于1992年提出的一種組合優(yōu)化方法，被廣泛應(yīng)用于求解組合優(yōu)化問(wèn)題，特別是NP-完全問(wèn)題。蟻群算法已在通信網(wǎng)絡(luò)方面中得到了很好的應(yīng)用和發(fā)展。11隨著網(wǎng)絡(luò)技術(shù)的發(fā)展和多媒體業(yè)務(wù)的興起，對(duì)網(wǎng)絡(luò)服務(wù)質(zhì)量提出了更高的要求，Qo