ACO算法及應用

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