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