2007年第2期職業(yè)圈No.2,2007(總第54期)ZHIYE QUAN(Cumulatively No. 54)ACO算法及應用黃聞嫻(溫州大學甌江學院,浙江溫州325000)【摘要】AC0算法是一種新型模擬進化算法,為求解復雜一種新型模擬進化算法,研究表明該算法具有并行性,魯棒的組合優(yōu)化問題提供了一種新的思路和方法.文章對AC0算性等優(yōu)良性質(zhì),為解決許多優(yōu)化問題提供了新的方向。法理論做簡要的綜逑,并介紹其在實際問題中的應用,最后對AC0算法仍需要解決的問題和未來的發(fā)展方向進行了探討AC0算法理論【關鍵詞】AC0算法;組合優(yōu)化;人工蟻群對于螞蟻這類群居昆蟲,其單個螞蟻的行為極其簡單【中圖分類號】TP301【文獻標識】A但由這些簡單的個體組成的蟻群群體卻表現(xiàn)出極其復雜的行【文章編號】1671-5969(2007)02-0127-02為,能夠完成復雜的任務。蟻群會很快找到蟻穴到食物處的最短路徑。此外,蟻群還能夠適應環(huán)境的變化,當蟻群運動當今科學技術正處于多學科相互交叉和融合的時代。隨路線上突然出現(xiàn)障礙物時,螞蟻能夠很快地重新找到最優(yōu)路著人們認識與改進世界范圍的擴大,人們對科學技術提出了徑更高更新的要求,單一領城的研究已經(jīng)無法滿足人們改造世仿生學家通過大量的觀察研究發(fā)現(xiàn),螞蟻在尋找食物或界的需求,人類面臨的許多復雜課題都需要通過交叉學科研回穴的路徑中,會在它們經(jīng)過的地方留下一些“信息素”,用究才能夠得到解決。隨著科技和經(jīng)濟的高速發(fā)展,人們對高以與群體中的其他螞蟻進行信息的交流。媽蟻在運動的過程效的優(yōu)化技術和智能計算的要求日益迫切。中能感知這些物質(zhì),并以此來指導自己的運動方向。具體表優(yōu)化技術是一種以數(shù)學為基礎,用于求解各種工程問題現(xiàn)在螞蟻以相對較高的概率選擇信息素濃度較高的路徑,而優(yōu)化解的應用技術。作為一個重要的學科分支,一直受到人后到者留下的信息素會對原有的信息素進行加強。這樣,蟻們的廣泛重視,并在諸多工程領域得到迅速推廣和應用,如群的集體行為便表現(xiàn)出一種信息正反饋現(xiàn)象:某一路徑上走系統(tǒng)控制、人工智能、模式識別、生產(chǎn)調(diào)度、VLSI技術、多過的螞蟻越多,在該路徑上留下的信息素濃度也越高,后來代理機器人之間的任務協(xié)調(diào)和計算機并行處理等。鑒于實際的螞蟻選擇該路徑的概率就越大。螞蟻個體間就是通過這種工程問題的復雜性、約束性、非線性、建模困難等特點,尋信息的交流達到搜索食物的目的。找一種適合于大規(guī)模并行且具有智能特征的優(yōu)化算法已成為20世紀90年代,意大利學者正是充分利用了螞蟻搜索食有關學科的一個主要研究目標和引人注目的研究方向。物的過程與著名的旅行商問題之間的相似性,最早提出了蟻目前,除了已得到公認的遺傳算法,模擬退火算法、禁群算法。不同的蟻群算法模型的定義雖然在一定程度上受到忌搜索法、人工神經(jīng)網(wǎng)絡等進化算法,近幾年提出的蟻群算問題結構化的影響,但就求解組合優(yōu)化問題而言,所有的蟻法正開始嶄露頭角,為復雜困難的系統(tǒng)優(yōu)化問題提供了新的群算法都是以 Macro dorigo針對TSP問題提出的基本蟻群具有競爭力的求解算法,應用范圍也開始遍及到許多科學技算法為基礎。因此,下面先簡要地介紹用于TSP問題求解的術及工程領域蟻群算法。、群集智能為模擬實際螞蟻的行為,首先引入如下記號,設m是蟻群仿生學是人類一直使用的方法,如模仿海豚皮而構造的中螞蟻的數(shù)量d(=1,2,…,n表示城市和之間的距離,海豚皮游泳衣”模仿人眼視網(wǎng)膜工作原理,制成的生物r()表示在時刻城市和之間的路徑上殘留的信息量來電子位置傳遞器”,模擬活細胞生化過程及其調(diào)控機制研制模擬實際螞蟻的信息素濃度。的人工模擬線粒體膜,葉綠體膜的人造能量轉換膜等。群居在初始化的時候,m個螞蟻被放置在不同的城市上,賦予昆蟲以集體的力量,進行覓食、御敵、筑巢等。這種群體所每條邊上的信息量為r』0,每個螞蟻k的tbu的第一個元表現(xiàn)出來的“智能”,就稱之為群體智能。如蜜蜂采蜜、筑巢、素賦值為它所在的城市。螞蟻覓食、筑巢等。從群居昆蟲相互合作進行工作中,得到用g()表示在時刻螞蟻k由城市i轉移到城市j的概率,啟迪,研究其中的原理,以此原理來設計新的求解問題的算則法。這是仿生學的另一重要領域,它是受自然界規(guī)律的啟迪根據(jù)其原理,模仿設計求解問題的算法。如人工神經(jīng)網(wǎng)絡技中國煤化工術、遺傳算法、進化規(guī)劃、模擬退火技術和群集智能技術等。CNMHG(1)AC蟻群優(yōu)化算法亦屬于這一領城,它是近幾年發(fā)展起來的其中 allowed表示螞蟻k下一步允許走過的城市的集合127它隨螞蟻k的行進過程而動態(tài)改變;信息量r1)隨時間的推信息,并且使用這些信息來修改問題的表現(xiàn)形式正如其它螞移會逐步衰減用l—p表示它的衰減程度;α,B分別表示螞蟻所看到的那樣。螞蟻既能共同的行動又能獨立的工作,顯示蟻在運動過程中所積累的信息量及啟發(fā)式因子在螞蟻選擇路出了一種相互協(xié)作的行為,它們之間不使用直接通訊,而使用徑中所起的不同作用;n()為由城市轉移到城市的期望程信息激素指導著媽蟻間的信息交換。螞蟻使用一種結構上的度,可根據(jù)某種啟發(fā)算法而定貪婪啟發(fā)式搜索可行解。根據(jù)問題的約束條件列出了一個解經(jīng)過n個時刻,螞蟻k走完所有的城市,完成一次循環(huán)。此作為經(jīng)過問題狀態(tài)的最小代價(最短路徑)每只螞蟻都能夠找時,要根據(jù)下式對各路徑上的信息量作更新:出一個解,但可能是較差解。蟻群中的個體同時建立了很多不(+)=pt1;·A同的解決方案找出高質(zhì)量的解是群體中的所有個體之間全局性的相互協(xié)作的結果。只要我們擅于利用問題與蟻群算法之間的相似性,模擬出人工螞蟻來幫助解決間題,那么蟻群算法的應用范圍將是△rk表示媽蟻k在本次循環(huán)中在城市i和城市之間留廣闊的下的信息量,其計算方法根據(jù)計算模型而定,在最常用的五、AC0算法在組合優(yōu)化中的應用antcyclesystem模型中ACO蟻群算法主要用于求解不同的組合優(yōu)化問題,一類t,{QA,若氨運本次環(huán)中壁過市和市應用于靜態(tài)組合優(yōu)化問題,另一類用于動態(tài)組合優(yōu)化問題。靜態(tài)問題指一次性給出問題的特征,在解決問題過程中,問題其中Q為常數(shù)L為螞蟻k在本次循環(huán)中所走路徑的長的特征不再改變。這類問題的范例就是經(jīng)典旅行商問題度(TSP);動態(tài)問題被定義為一些量的函數(shù),這些量的值由隱含系三、AC0算法流程統(tǒng)動態(tài)設置。因此,問題在運行時間內(nèi)是變化的,而優(yōu)化算法步驟lnc=0(nc為迭代步數(shù)或搜索次數(shù));每條邊上的須在線適應不斷變化的環(huán)境。這類問題的典型例子是網(wǎng)絡路r小Oc(常數(shù),并且△r0,放置m個螞蟻到n個城市上由問題步驟2將各媽蟻的初始出發(fā)點置于當前解集 tabuk(s)目前,在靜態(tài)組合優(yōu)化問題中,蟻群算法主要用于解決中:對每個螞蟻k(k=1,…,m),按概率p移至下一城市j將城旅行商問題,二次分配問題,車間任務調(diào)度問題,車輛路線市j置于tabu,(s)中問題,圖著色問題,有序排列問題等。步驟3經(jīng)過n個時刻,螞蟻k可走完所有的城市,完成在動態(tài)組合優(yōu)化問題中,主要應用于有向連接的網(wǎng)絡路次循環(huán)計箅每個螞蟻走過的總路徑長度L,更新找到的最短由和無向連接的網(wǎng)絡路由等。研究表明,用蟻群算法研究解路徑?jīng)Q包含帶寬、延時、延時抖動、包丟失率和最小花費等約束步驟4更新每條邊上的信息量rt+n)條件在內(nèi)的QS組播路由問題,效果優(yōu)于模擬退火算法及遺步驟5對每一條邊置△r:=0,nc=nc+1傳算法。步驟6若nc<預定的選代次數(shù) NCMAX,則轉步驟2;否另外,蟻群箅法在其他領域也得到了應用,如在解決管則打印出最短路徑,終止整個程序。線敷設問題,機構同構判定問題,開關合布線問題等都取得四、人工螞蟻了令人滿意的結果人們利用蟻群優(yōu)化算法解決實際問題的過程實際上是利六、結語用問題與真實螞蟻覓食過程的相似性,把問題抽象為真實螞ACO蟻群算法是一種新的仿生啟發(fā)式優(yōu)化算法,剛剛問蟻覓食的過程。這樣,人們便抽象出許許多多的“人工螞蟻”世幾年,其理論還十分不完善,存在著搜索時間較長,在算來幫助我們解決實際問題。法模型、收斂性及理論依據(jù)方面還有許多工作有待進一步深人工螞蟻吸收了螞蟻群體行為的典型特征:一是能覺察研究。但其在解決組合優(yōu)化問題中的優(yōu)越性也是顯著的小范圍區(qū)域內(nèi)狀況,并判斷出是否有食物或其他同類的信息它具有較強的魯棒性、通用性、并行搜索等優(yōu)點素軌跡;二是能釋放自己的信息素:三是所遺留的信息素量對ACO算法的研究才剛剛起步,需要解決的問題還有很會隨時間而逐步減少多很多,但這是一種用途廣泛且高效的算法,值得我們?nèi)ド钗浵佀惴ㄍㄟ^候選解組織群體的進化過程來尋求最優(yōu)解,人地研究和優(yōu)化其算法。相信日后會在更多的領域用到“人這一過程包括適應階段和協(xié)作階段。在適應階段,各候選解根工螞蟻”!據(jù)積累的信息不斷調(diào)整自身的結構;在協(xié)作階段各候選解間通過信息交流,以便產(chǎn)生性能更好的解。在蟻群算法中,一個有【參考文獻】限規(guī)模的人工蟻群體,通過相互協(xié)作搜索用于解決優(yōu)化問題的[1]宋雪梅,蟻群算法及其應用【D].河北理工學院學報較優(yōu)解。每只螞蟻根據(jù)問題依賴的準則,從被選的初始狀態(tài)出2006發(fā)建立一個可行解或是解的一個組成部分。在建立螞蟻自己2]李士勇,蟻群優(yōu)化算法及其應用研究進展[D],哈爾濱工中國煤化工的解決方案中,每只螞蟻都搜集關于問題拓征和其自身行為的CNMHG-128