分數(shù): 任課教師簽字： 華北電力大學研究生結(jié)課作業(yè)學年學期：2010學年第二學期課程名稱：人工智能與知識工程號：題目：蟻群算法概述提交時間：2011/4/13蟻群算法概述摘要:群智能算法是一種新興的人工智能方法，已成為越來越多研究者的關(guān)注焦點。蟻群算法是群智能算法的一個重要的分支，是意大利學者M.Dorigo通過模擬蟻群覓食行為提出的［1］。本文首先介紹了群智能的概念及特點，然后詳細介紹基本蟻群算法的原理及其優(yōu)缺點。在此基礎上又介紹了五種針對基本蟻群算法的改進算法，最后針對蟻群算法的應用做了簡要的介紹。關(guān)鍵詞】群智能；蟻群算法；改進算法Abstract:Swarmintelligenceisanewlydevelopingmethodinthefieldofartificialintelligence.Ithasbecomethefocusofmoreandmoreresearchers.AntcolonyalgorithmisanimportantbranchofSwarmintelligentalgorithm.ItwasproposedbyanItalianscholarM.Dorigothroughsimulatingtheforagingbehaviorsofantcolony.Thispaperfirstintroducedtheconceptandcharacteristicofswarmintelligence,andthenintroducedtheprincipleofbasicantcolonyalgorithmandtheiradvantagesanddisadvantages.Onthisbasis,Iintroducefiveimprovedalgorithmsofbasicantcolonyalgorithmandtheapplicationofantcolonyalgorithm.【Keywords】Swarmintelligence;Antcolonyalgorithm;Improvedalgorithm目錄TOC\o"1-5"\h\z\o"CurrentDocument"目錄 3\o"CurrentDocument"1緒論 4\o"CurrentDocument"群智能的概念 4\o"CurrentDocument"群智能的特點 4\o"CurrentDocument"蟻群算法的基本思想 4\o"CurrentDocument"2蟻群算法概述 5\o"CurrentDocument"蟻群算法基本原理 5\o"CurrentDocument"蟻群算法的優(yōu)點與不足 7\o"CurrentDocument"本章小結(jié) 7\o"CurrentDocument"3改進的蟻群優(yōu)化算法 8\o"CurrentDocument"3.1 帶精英策略的蟻群算法 8\o"CurrentDocument"基于優(yōu)化排序的螞蟻系統(tǒng) 8\o"CurrentDocument"蟻群系統(tǒng) 8\o"CurrentDocument"最大-最小螞蟻系統(tǒng) 9\o"CurrentDocument"最優(yōu)-最差螞蟻系統(tǒng) 9\o"CurrentDocument"4蟻群優(yōu)化算法的應用 10\o"CurrentDocument"參考文獻 101緒論仿生優(yōu)化算法是人工智能研究領(lǐng)域的一個重要的分支，其中包括模擬生物界中自然選擇和遺傳機制的遺傳算法、模擬螞蟻群體覓食行為的蟻群算法以及模擬鳥類群體捕食行為的粒子群算法等。群智能的概念螞蟻、蜜蜂和鳥類等社會性的群居動物可以通過分工協(xié)作完成諸如發(fā)現(xiàn)新的食物源、建筑龐大復雜的巢穴、跨越幾千公里遷徙到指定地區(qū)等復雜的任務。通過對這些動物的研究產(chǎn)生了群智能的概念。群智能指的就是“無智能的主體通過合作表現(xiàn)出智能行為的特性”［2］，是一種基于生物群體行為規(guī)律的計算技術(shù)。群智能的特點群智能有如下特點和優(yōu)點［2］：群體中相互合作的個體是分布的(Distributed)，這樣更能夠適應當前網(wǎng)絡環(huán)境下的工作狀態(tài)。沒有中心的控制與數(shù)據(jù)，這樣的系統(tǒng)更具有魯棒性(Robust)，不會由于某一個或者某幾個個體的故障而影響整個問題的求解。可以不通過個體之間直接通信，而是通過非直接通信進行合作，這樣的系統(tǒng)具有更好的可擴充性(Scalability)。由于系統(tǒng)中個體的增加而增加的系統(tǒng)通信開銷在這里是十分小的，系統(tǒng)中每個個體的能力十分簡單，這樣每個個體的執(zhí)行時間比較短，并且實現(xiàn)也比較簡單，具有簡單性(Simplicity)。蟻群算法的基本思想現(xiàn)實生活中單個螞蟻的能力和智力非常簡單，但它們能通過相互協(xié)調(diào)、分工、合作來完成筑巢、覓食、遷徙、清掃蟻穴等復雜行為，尤其是螞蟻有能力在沒有任何可見提示的條件下找到從蟻穴到食物源的最短路徑，并且能隨環(huán)境的變化而變化地搜索新的路徑，產(chǎn)生新的選擇。這是因為螞蟻在其走過的路上會分泌一種信息素，其他的螞蟻能夠感知這種物質(zhì)的存在和強度，并以此指導自己的運動方向，使其傾向于朝著信息素強度高的方向移動。蟻群算法就是從自然界中真實螞蟻覓食的群體行為中得到啟發(fā)而提出的。在蟻群算法中，為了實現(xiàn)對真實螞蟻的抽象，提出了人工蟻的概念。人工蟻和真實螞蟻有如下相同點：人工蟻和螞蟻一樣，是一群相互合作的個體，每個螞蟻都能建立一種解決方案，整個蟻群相互合作在全局范圍內(nèi)找出問題的較優(yōu)的解決方案。人工蟻和真實螞蟻有著公共的任務，尋找最優(yōu)路徑。人工蟻和真實螞蟻一樣也通過使用信息素進行間接通訊。人工蟻和真實螞蟻的覓食行為都是一種正反饋過程。

在蟻群算法中存在一種信息素的揮發(fā)機制，類似于真實世界中的情況,不預測未來狀態(tài)概率的狀態(tài)轉(zhuǎn)移策略。人工蟻的策略是充分利用了局部信息，而沒有前瞻性的預測未來的狀態(tài)。圖1：二元橋?qū)嶒灣跏紶顟B(tài)圖2：二元橋?qū)嶒灲Y(jié)束狀態(tài)2蟻群算法概述下面詳細介紹蟻群算法原理及其優(yōu)缺點。2.1蟻群算法基本原理蟻群算法⑶可以表述如下：初始時刻，各條路徑上的信息素量相等，設I/O)=C(C為常數(shù))，螞蟻k(k=1,2,3,…,m)在運動過程中根據(jù)各條路徑上的信息

量決定轉(zhuǎn)移方向。螞蟻系統(tǒng)所使用的轉(zhuǎn)移規(guī)則被稱為隨機比例規(guī)則，在時刻t，螞蟻k從城市i選擇城市j的轉(zhuǎn)移概率pk(t)為:ijpk(pk(t)=ij力(t)r?「耳(t)『-ij_r qijr ,ify Lt(t)ia-Ln Jpis issGJk(i)0, otherwiseGJk(i)(2.1)其中，Jk(i)={1,2,……,n}-tabuk表示螞蟻k下一步允許選擇的城市。列表tabuk記錄了螞蟻k在本次迭代中已經(jīng)走過的城市，不允許該螞蟻在本次循環(huán)中再經(jīng)過這些城市。當所有n座城市都加入到tabuk中時，螞蟻k便完成了一次周游，此時螞蟻k所走過的路徑便是TSP問題的一個可行解。(2.1)式中的Jj是一個啟發(fā)式因子，被稱為能見度因子。在AS算法中，幾^通常取城市i與城市j之間距離的倒數(shù)。a和B分別反映了在螞蟻的運動過程中已積累的信息和啟發(fā)信息的相對重要程度。當所有螞蟻完成一次周游后，各路徑上的信息素根據(jù)(2.2)式更新。t0+n)=(1_p)*t(t)+At (2.2)ij ij ij(2.3)At= ym Atk(2.3)ij ijk=1其中P(0<P<1)表示路徑上信息素的揮發(fā)系數(shù)，1-P表示信息素的持久系數(shù);△tij表示本次迭代邊(ij)上信息素的增量。Atkij表示第k只螞蟻在本次迭代中留在邊(ij)上的信息素量。如果螞蟻k沒有經(jīng)過邊(ij),則ATkij的值為0?！鱰kij表示為：Atk=2LAtk=2Lij若螞蟻k在本次周游中經(jīng)過邊ijK0,否則(2.4)其中，Q為正常數(shù)，Lk表示第k只螞蟻在本次周游中所走過路徑的長度。M.Dorigo提出了3種AS算法的模型［4］，式(2.4)稱為蟻周系統(tǒng)，另兩個模型分別稱為蟻量系統(tǒng)和蟻密系統(tǒng)，其差別主要在(2.4)式，即在蟻量系統(tǒng)模型中為：Atkijdij0,在蟻密系統(tǒng)模型中為：AtAtkijdij0,在蟻密系統(tǒng)模型中為：Atkij螞蟻k在時刻t和t+1經(jīng)過邊ij否則螞蟻k在時刻t和t+1經(jīng)過邊ij否則(2.5)(2.6)AS算法實際上是正反饋原理和啟發(fā)式算法相結(jié)合的一種算法。在選擇路徑時，螞蟻不僅利用了路徑上的信息素，而且用到了城市間距離的倒數(shù)作為啟發(fā)式因子。實驗結(jié)果表明，蟻周系統(tǒng)模型比蟻量系統(tǒng)和蟻密系統(tǒng)模型有更好的性能。這是因為蟻周系統(tǒng)型利用全局信息更新路徑上的信息素量，而蟻量系統(tǒng)和蟻密系統(tǒng)模型使用局部信息。AS算法的時間復雜度為0(NC*n2*m)，算法的空間復雜度為S(n)=0(n2)+0(n*m)，其中NC表示迭代的次數(shù)，n為城市數(shù)，m為螞蟻的數(shù)目。2.2蟻群算法的優(yōu)點與不足眾多研究已經(jīng)證明AS算法具有很強的發(fā)現(xiàn)較好解的能力，這是因為該算法不僅利用了正反饋原理，在一定程度上可以加快進化過程，而且是一種本質(zhì)上并行的算法。它有如下優(yōu)點［5］：較強的魯棒性：對蟻群算法模型稍加修改，便可以應用于其它問題。分布式計算：蟻群算法是一種基于種群的進化算法，具有本質(zhì)的并行性，易于實現(xiàn)。易于與其他方法結(jié)合：蟻群算法很容易與多種啟發(fā)式算法結(jié)合，以改善算法的性能。同時它也存在一些缺陷：限于局部最優(yōu)解，從算法解的性質(zhì)而言，蟻群算法也是在尋找一個比較好的局部最優(yōu)解，而不是強求是全局最優(yōu)解。工作過程的中間停滯問題，和算法開始時收斂速度快一樣，在算法工作過程當中，迭代到一定次數(shù)后，螞蟻也可能在某個或某些局部最優(yōu)解的鄰域附近產(chǎn)生停滯。較長的搜索時間，盡管和其他算法相比，蟻群算法在迭代次數(shù)和解的質(zhì)量上都有一定的優(yōu)勢，但對于目前計算機網(wǎng)絡的實際情況，還是需要較長的搜索時間。雖然計算機計算速度的提高和蟻群算法的并行性在一定程度上可以緩解這一問題，但是對于大規(guī)模復雜的計算機網(wǎng)絡，這還是一個很大的障礙?；鞠伻核惴ㄔ诮鉀Q一些小規(guī)模的TSP問題時的表現(xiàn)尚可令人滿意。但是隨著問題規(guī)模的增大，螞蟻系統(tǒng)難以在可接受的循環(huán)次數(shù)內(nèi)找到最優(yōu)解。本章小結(jié)本章主要介紹了蟻群算法基本思想?；鞠伻核惴ㄔ诮鉀Q一些小規(guī)模的TSP問題時的表現(xiàn)尚可令人滿意。但是隨著問題規(guī)模的增大，螞蟻系統(tǒng)難以在可接受的循環(huán)次數(shù)內(nèi)找到最優(yōu)解。針對基本蟻群算法的這些不足，研究者進行了大量的

改進工作。3改進的蟻群優(yōu)化算法面對目前最流行的幾種蟻群算法進行性能比較分析。3.1帶精英策略的蟻群算法在蟻群算法中所謂的精英策略［3］指的是，在每次迭代之后給予最優(yōu)解以額外的信息量。與AS算法相比，ASelite算法在信息素更新時加強了對全局最優(yōu)解的利用,其信息素更新策略為：T(t+1)=(l—p)*T(t)T(t+1)=(l—p)*T(t)+AC+T*ijijijijPG(0,1)AT二ijmLTkijk=1Atk=<ij0,如果螞蟻k經(jīng)過邊ij否則(3.1)(3.2)(3.3)AT*ijLgb0,如果邊(ij)是當前最優(yōu)解的一部分否則(3.4)其中△T*ij為精英螞蟻在邊(i,j)上增加的信息素量，。為精英螞蟻數(shù)，Lgb為全局最優(yōu)解。3.2基于優(yōu)化排序的螞蟻系統(tǒng)基于排序的螞蟻系統(tǒng)(Rank-basedVersionofAntSystem簡稱RAS)是BerndBullnheimer⑺等提出的AS的又一擴展算法。RAS在每次迭代完成后，螞蟻所經(jīng)路徑將按從小到大的順序排列，即L1(t)WL2(t) WLm(t)，并根據(jù)路徑長度賦予不同的權(quán)重，路徑長度越短權(quán)重越大。全局最優(yōu)解的權(quán)重為w,第r個最優(yōu)解的權(quán)重為max{0,w-r}，按(3.5)式更新各路徑上的信息素：t(t+1)二(1-p)-t(t)+L=1(w-r)-Atr(t)+w-Atgb(t) Pe(0,1) (3.5)ijijijijr=1其中，△T\j(t)=1/Lr(t)，^Tgbij(t)=1/Lgb蟻群系統(tǒng)蟻群系統(tǒng)⑹在基本蟻群算法的基礎上做了如下三個方面的修改：狀態(tài)轉(zhuǎn)移規(guī)則為更好更合理的探索新路徑和利用先驗知識提供了方法。在基本蟻群算法中，螞蟻完全依賴概率進行路徑選擇，使用的是隨機比例規(guī)則，蟻群系統(tǒng)使用了不同的決策規(guī)則，稱之為偽隨機比例規(guī)則。這個決策規(guī)則具有雙重功率。決策規(guī)則既可以利用關(guān)于問題的先驗知識，也可以有傾向性的搜索。瓦槪法心⑴嘰］%ifJ= nthcrvvise ,八其中J是根據(jù)2.1式計算出來的。參數(shù)q的大小決定了利用先驗知識和探索新0路徑之間的相對重要性。每當螞蟻要選擇下一個城市時，它就選取一個隨機數(shù)0<=q<=1，如果q<=q，則根據(jù)先驗知識(式3.6)來選擇最好的邊，否則就按照3.1式概率的選擇一條邊。全局更新規(guī)則只應用于最優(yōu)的螞蟻路徑上。t(r,s)=(1-a)*t(r,s)+a*At(r,s)(3.7)其中如果(r,s)屬于全局最優(yōu)路徑At(r,s)=l/Lgb，否則為0。其中a為信息素揮發(fā)參數(shù)。Lgb為目前為止找到的全局最優(yōu)路徑。這里的Lgb也可以用Lib替代，前者是全局最優(yōu)，后者是迭代最優(yōu)。在建立問題解決方案的過程中，應用局部信息素更新規(guī)則。局部信息素更新利用的也是3.6式的規(guī)則。局部更新規(guī)則使得相應的信息素逐漸減少，可以有效的避免螞蟻收斂到同一路徑。3.4最大-最小螞蟻系統(tǒng)蟻群算法將螞蟻的搜索行為集中到最優(yōu)解的附近可以提高解的質(zhì)量和收斂速度，從而改進算法的性能。但是這種搜索方式會使早熟收斂行為更容易發(fā)生。最大-最小螞蟻系統(tǒng)⑻可以有效避免早熟收斂的發(fā)生。MMAS和AS的區(qū)別在于以下三個方面：在每次循環(huán)結(jié)束之后，只有一只螞蟻進行信息素的更新，這只螞蟻就是全局最優(yōu)螞蟻或是迭代最優(yōu)螞蟻。為了避免搜索的停滯，每個解上的信息量的值域范圍被限制在［t,t］范圍內(nèi)。這樣就可以有效的避免某條路徑上的信息量遠大于或遠小于其余路徑情況的發(fā)生，使得所有的螞蟻都集中到同一條路徑上，從而使算法不再擴散，加快收斂速度。信息素的初始值被設為其取值上限，這樣有助于增加算法初始階段的搜索能力。3.5最優(yōu)-最差螞蟻系統(tǒng)在前述蟻群算法中，路徑上的初始信息量是相同的，蟻群創(chuàng)建的第一條路徑所獲得的信息主要是城市間的距離信息。此時的蟻群算法等價于貪婪算法。這就會對以后的循環(huán)產(chǎn)生誤導。最優(yōu)-最差蟻群算法⑼對最優(yōu)解進行了更大限度的增強，而對最弱解進行了削弱。使得最優(yōu)和最差路徑的邊之間的路徑信息量差異進一步增大。該算法主要是修改了蟻群算法中的全局更新公式，當一次迭代結(jié)束，對最差螞蟻所經(jīng)過的路徑進行信息素的更新。t(r,s)=(1-a)*t(r,s)-￡*L/Lworstbest(3.7)4蟻群優(yōu)化算法的應用蟻群算法最初被用于解決旅行商(TSP)問題。自從在著名的旅行商問題和工件排序問題上取得成效，已經(jīng)滲透到其他領(lǐng)域內(nèi)。其中最成功的是其在組合優(yōu)化問題中的應用，可以將這些應用分為兩類：一類是靜態(tài)組合優(yōu)化問題，其典型代表是TSP、QAP、車間調(diào)度問題、車輛路由問題等；另一類應用于動態(tài)組合優(yōu)化問題，例如網(wǎng)絡路由問題。參考文獻段海濱，王道波，于秀芬.蟻群算法的研究現(xiàn)狀及其展望[J].中國工程科學，2007,9(2):98-102秦玲.蟻群算法的改進與應用[D].揚州大學碩士論文,2004M.Dorigo，V.Maniezzo，andA.Colorni.TheAntSystem:Optimizationbycolonyofcooperatingagents[J].IEEE