改進的蟻群算法在移動Agent路徑選擇中的應用研究

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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