第五章蟻群優(yōu)化算法5.1介紹蟻群優(yōu)化(ACO)是群體智能的一部分，它模仿螞蟻的合作行為來解決復(fù)雜的組合優(yōu)化問題。它的概念是由MarcoDorigo［1］和他的同事提出的，當(dāng)他們觀察到這些生物在尋找食物時所采用的相互交流和自我組織的合作方式時，他們感到很驚訝。他們提出了執(zhí)行這些策略的想法，為不同領(lǐng)域的復(fù)雜優(yōu)化問題提供了解決方案，并獲得了廣泛的歡迎［1,2］。蟻群算法是一組被稱為人工螞蟻的軟件代理，它們?yōu)樘囟ǖ膬?yōu)化問題尋找好的解決方案。蟻群算法是通過將問題映射成一個加權(quán)圖來實現(xiàn)的，在加權(quán)圖中，螞蟻沿著邊緣移動，尋找最佳路徑。蟻群研究(實際上是真正的螞蟻)始于1959年，當(dāng)時皮埃爾?保羅?格拉斯(PierrePaulGrasse)發(fā)明了“協(xié)同”理論，解釋了白蟻的筑巢行為。之后于1983年Deneubourg和他的同事們⑶對螞蟻的集體行為進行了研究。1988年，Mayson和Manderick發(fā)表了一篇關(guān)于螞蟻的自組織行為的文章。最終在1989年，Goss,Aron,Deneubour,andPasteelson在其研究工作(阿根廷螞蟻的集體行為)中提出了蟻群算法的基本思想［4］，同年，Ebling及其同事提出了一食物定位模型。1992年，MarcoDorigo(Dorigo,1992)在其博士論文中提出了螞蟻系統(tǒng)(AntSystem)［1］。一些研究人員將這些算法擴展到各個研究領(lǐng)域的應(yīng)用中，Appleby和英國電信主管發(fā)表了第一個在電信網(wǎng)絡(luò)中的應(yīng)用，后來Schoonderwoerd和他的同事在1997年對其進行了改進。在2002年，它被應(yīng)用于貝葉斯網(wǎng)絡(luò)中的調(diào)度問題。蟻群算法的設(shè)計是基于螞蟻搜索巢穴和食物位置之間短路徑的能力，這可能會因螞蟻的種類而有所不同。近年來，研究人員對蟻群算法的應(yīng)用結(jié)果進行了研究，結(jié)果表明，所使用的大多數(shù)人工螞蟻并不能提供最好的解決方案，而精英蟻群通過重復(fù)的交換技術(shù)提供了最好的解決方案。他們進一步指出，如果考慮相同的參數(shù)，混合和交換方法的性能優(yōu)于蟻群系統(tǒng)(ACS)。基于這一理論，研究人員提出了一種專門的蟻群優(yōu)化方法，可以模擬特定種類的螞蟻，如黑蟻(Lasiusniger或Irodomyrexhumilis)，著名的阿根廷螞蟻。5.2人工螞蟻的概念自然生物的合作行為常常被證明是解決現(xiàn)實生活中各種復(fù)雜問題的一個很好的方法。生物的協(xié)作行為吸引了研究人員將它們的智能融入人工智能中，共同努力解決不同領(lǐng)域的各種復(fù)雜問題。5.2.1真實螞蟻如何工作像螞蟻這樣的微小自然生物可以共同工作來完成復(fù)雜的任務(wù)。這種群居行為是基于螞蟻在運動時分泌的一種特殊化學(xué)物質(zhì)——信息素。這些信息素吸引其他螞蟻通過相同的路徑，這就證明了為什么螞蟻總是在群體中交流，蟻丘是如何形成的，以及它們?nèi)绾文軌蛲ㄟ^相互交流策略實現(xiàn)復(fù)雜的結(jié)構(gòu)。信息素在螞蟻之間完成各種集體任務(wù)的信息交換中發(fā)揮著重要的作用；對我們來說理解信息素的工作原理以及它們?nèi)绾螏椭浵佌业绞澄镌吹淖疃搪窂阶兊梅浅Ｖ匾?.2.2螞蟻如何優(yōu)化食物搜索食物搜索過程大致可以分為三個階段。螞蟻開始尋找目標(biāo)時，會在朝隨機的方向搜索食物。這些螞蟻以混亂的方式四處游走，最終當(dāng)疲憊不堪時就返回巢穴進食和休息。然而，當(dāng)它們漫步時，如果其中一只遇到了食物來源，它會帶著一小塊食物回到巢穴，并留下信息素軌跡，這種信息素可以作為其他螞蟻是否有食物的指示。因此，螞蟻會沿著信息素軌跡，留下更多的信息素。然而，考慮到螞蟻可以選擇多種路徑到達食物源，螞蟻的初始移動在本質(zhì)上是有些混亂的，有許多路徑連接著巢穴和食物，螞蟻通常選擇信息素更強的路徑。信息素隨著時間的推移而蒸發(fā)，從而到達食物源最短的路徑具有最強的信息素；螞蟻慢慢地向這條路線靠攏，使之成為最優(yōu)路線，后來形成了蟻群（Fogel等，1966）。5.2.3什么是人工螞蟻人工螞蟻不過是一種模擬代理，它模仿真實螞蟻的一些行為特征，以解決復(fù)雜的現(xiàn)實問題。根據(jù)計算機科學(xué)，它們代表了來自真實螞蟻行為的多智能體技術(shù)。這個概念是建立在這樣一個理念之上的：智能可以是許多微小物體的集體努力。這種智能個體的環(huán)境網(wǎng)絡(luò)目前是未來技術(shù)的愿景，有望超越目前基于人腦的集中式系統(tǒng)［5］。人工螞蟻有著雙重特性，一方面，它們是真實螞蟻行為特征的一種抽象，將螞蟻覓食行為中最關(guān)鍵的部分賦予人工螞蟻；另一方面，人工螞蟻是為了解決實際的工程優(yōu)化問題，所以人工螞蟻也具備了一些真實螞蟻所不具備的本領(lǐng)以增強算法的優(yōu)化效果。5.2.3.1相同相互合作的個體：每個人工螞蟻都是一個可行解，高質(zhì)量的解是整個蟻群合作的結(jié)果；共同的任務(wù)：尋找起點（蟻穴）到終點（食物源）之間的最短路徑（最小代價）；信息素-間接通訊：人工蟻群算法中信息素軌跡是通過狀態(tài)變量來比表示。狀態(tài)變量用一個nxn維信息素矩陣來表示，其中n表示問題的規(guī)模，矩陣中的元素表示在節(jié)點i選擇節(jié)點j作為移動方向的期望值。初始化矩陣中每一個元素（如0），隨著螞蟻在所經(jīng)過的路徑上釋放信息素的增多，矩陣中的對應(yīng)元素也隨之改變，人工蟻群算法就是通過修改矩陣中的元素的數(shù)值，來模擬自然界中信息素軌跡的更新過程。正反饋：當(dāng)一些路徑上通過的螞蟻越來越多，其留下的信息素軌跡也越來越多，使得信息素的強度增大。根據(jù)螞蟻傾向于選擇信息素強度大的路徑的特點，后來的螞蟻選擇該路徑的概率也越高，從而增加了該路徑的信息素強度，這種選擇過程被稱為自催化過程。自催化過程利用信息作為反饋，通過對系統(tǒng)演化過程中較優(yōu)解的自增強作用，使得問題的解向著全局最優(yōu)的方向不斷進化，最終能夠有效獲得相對較優(yōu)的解。正反饋在基于群體的優(yōu)化算法中是一個強有力的機制。信息素的揮發(fā)：揮發(fā)機制可以使螞蟻逐漸忘記過去，不受過去經(jīng)驗的過分約束，有利于指引螞蟻向著新的方向進行搜索，避免早熟收斂。不預(yù)測未來狀態(tài)概率的狀態(tài)轉(zhuǎn)移策略：只充分利用局部信息，并沒有利用前瞻性預(yù)測未來的狀態(tài)。5.2.3.2不同人工螞蟻生活在離散的世界中，它們的移動實質(zhì)上是由一個離散狀態(tài)到另一個離散狀態(tài)的躍遷；人工螞蟻內(nèi)部有一個內(nèi)部的狀態(tài)，這個私有的狀態(tài)記憶了螞蟻過去的行為；人工螞蟻釋放一定量的信息素，它是螞蟻所建立的問題解決方案優(yōu)劣程度的函數(shù)；人工螞蟻釋放信息素的時間可以視情況而定，而真實螞蟻是在移動的同時釋放信息素，人工螞蟻可以在建立了一個可行的解決方案后再進行信息素的更新；5.3螞蟻系統(tǒng)螞蟻系統(tǒng)是提出的第一個ACO算法[6],可以以旅行商問題為例說明該算法。在ACO仿真中，每只螞蟻都要從一個城市到另一個城市，在螞蟻完成它們的旅程后，蟻群算法會在它們的路徑上儲存信息素。信息素不僅沉積,而且蒸發(fā)。一只螞蟻從現(xiàn)在的城市到另一個城市旅行的概率與城市間信息素的數(shù)量成正比。螞蟻也被認(rèn)為對問題有一定的了解,可以幫助它們在旅途中做出決定。它們知道從現(xiàn)在的城市到其他城市的距離,更有可能去一個近的城市而不是一個遙遠的城市,因為算法的目標(biāo)是找到最短路徑。螞蟻系統(tǒng)算法如下所示。n：城市數(shù)量a,卩：信息素和啟發(fā)式信息的相對重要性Q：信息素釋放量P：揮發(fā)率Tj對于iW[l,n]且je[1,n],值為t0（城市i和j之間的初始信息素）dj城市i和j之間的距離（ie[1,n]且je[1,n]）while（終止條件不滿足）forq=1ton-1for每一只螞蟻ke[1,N]為每只螞蟻ke[1,N]初始化開始城市ck1為螞蟻ke[1,N]初始化已訪問城市集合：Ck—{ck1}for每一個城市je[1,n]且j$Ck計算概率：p..（k）J（T.a/d..卩）/（vvvv ）□j iJiJ 為塞為"nextj螞蟻k以概率piJ（k）去到城市J使用ck+1表示上一行中選擇的城市k,+1C—CU{c}kk k，q+1next螞蟻nextqLk—由螞蟻k(k$[l,N])構(gòu)建的總路徑長度for每一個城市i(ie[1,n])和每一個城市j(je[1,n])for每一只螞蟻ke[1,N]if螞蟻k從城市i去到城市jelseendifnext螞蟻next城市對next代從算法中可以看出每只螞蟻從城市i去到城市j的概率與這些城市之間路徑上信息素的數(shù)量成正比，與這些城市之間的距離成反比。比率a/p確定信息素信息相對于距離信息在決定去哪個城市旅行時的重要性。當(dāng)一只螞蟻從一個城市i移動到另一個城市j時，這條路徑上的信息素的數(shù)量與螞蟻解的質(zhì)量成正比(也就是說，與螞蟻的總旅行距離成反比)。5.4三種模型5.4.1蟻密系統(tǒng)模型該模型中，一只螞蟻經(jīng)過路徑（i,j）上釋放的信息素量為常數(shù)Q,即螞蟻經(jīng)過路徑（，）否則蟻量系統(tǒng)模型該模型中，一只螞蟻經(jīng)過路徑（i,j）上釋放的信息素量為常數(shù)Q/djj,即螞蟻經(jīng)過路徑（，）否則可以看出，在蟻量模型中，信息素軌跡強度的增加與dij成反比，因此段路徑對螞蟻更有吸引力。蟻周系統(tǒng)模型該模型與前兩種模型的區(qū)別在于螞蟻k完成一次循環(huán)后才會更新信息素，其更新公式如下：螞蟻經(jīng)過路徑（，）否則在蟻密模型和蟻量模型中，螞蟻在建立方案的同時釋放信息素，利用的是局部信息，而蟻周模型是在螞蟻已經(jīng)建立了完整的軌跡后再釋放信息素，利用的是整體信息。5.5改進的蟻群優(yōu)化算法5.5.1帶精英策略的螞蟻系統(tǒng)帶精英策略的螞蟻系統(tǒng)（AntSystemwithelitiststrategy，ASelite），為了使當(dāng)前的最優(yōu)解在下一循環(huán)中對螞蟻更有吸引力，在每次循環(huán)后給予最優(yōu)解以額外的信息素，這個最優(yōu)解就是全局最優(yōu)解，找到該解的螞蟻為精英螞蟻，信息素更新公式如下：表示第k個螞蟻經(jīng)過ij，是精英解的個數(shù)。5.5.2基于優(yōu)化排序的螞蟻系統(tǒng)和螞蟻系統(tǒng)一樣，帶精英策略的螞蟻系統(tǒng)有一個缺點：若在進化過程中，解的總質(zhì)量提高了，解元素之間的差異減少了，導(dǎo)致選擇概率的差異隨之減小，使得搜索過程不會集中在到目前為止所找出的最優(yōu)解附近，從而阻止了對更優(yōu)解的進一步搜索。當(dāng)路徑長度變得非常接近，特別是當(dāng)很多螞蟻沿著局部極優(yōu)的路徑行進時，則對短路徑的增強作用被削弱了。受遺傳算法中采用排序選擇機制解決選擇壓力的啟發(fā)，將排序的概念應(yīng)用到螞蟻系統(tǒng)中，就有了基于優(yōu)先排序的螞蟻系統(tǒng)（Rank-BsedVersionofAntSystem,ASrank）。具體過程如下：當(dāng)每只螞蟻都生成一條路徑后，螞蟻按照路徑長度排序（L1<L2<^<Lm）,螞蟻對信息素軌跡更新的貢獻根據(jù)該螞蟻的排名的位次進行加權(quán)。此外只考慮w只最好的螞蟻，為目前為止所找出的最優(yōu)路徑上軌跡貢獻的權(quán)值，前只螞蟻中的各只所經(jīng)歷的邊獲得一定量的信息素，其正比于該螞蟻的排名位次。此外，到目前為止找出最優(yōu)路徑的螞蟻所經(jīng)過的邊也將獲得額外的信息素（這相當(dāng)于帶有精英策略的螞蟻系統(tǒng)中精英螞蟻的更新），所以有如下的更新：是只螞蟻根據(jù)排名對信息素軌跡的更新：第只螞蟻經(jīng)過路徑（，）否則最優(yōu)螞蟻經(jīng)過路徑（，）否則5.5.3蟻群系統(tǒng)蟻群系統(tǒng)（AntColonySystem,ACS）［7］是由Dorigo和Gambardella在1996年提出的，用于改善螞蟻系統(tǒng)的性能。蟻群系統(tǒng)在螞蟻系統(tǒng)的基礎(chǔ)上主要做了三個方面的改進：（1）狀態(tài)轉(zhuǎn)移規(guī)則為更好更合理地利用新路徑和利用關(guān)于問題的先驗知識提供了方法。蟻群系統(tǒng)使用雙重決策：既可以利用關(guān)于問題的先驗知識和以信息素形式存儲的已經(jīng)獲得信息，又可以進行有向性的探索。通過調(diào)節(jié)參數(shù)q0,可以調(diào)節(jié)探索新路徑的程度和是否使螞蟻的搜索活動集中于最優(yōu)解的空間鄰域內(nèi)。（2） 全局更新規(guī)則只應(yīng)用于最優(yōu)的螞蟻路徑上在蟻群系統(tǒng)中,每次循環(huán)后只對最優(yōu)螞蟻經(jīng)歷的路徑進行信息素的增強,其他路徑由于揮發(fā)機制信息素會逐漸減少,這就增大了最優(yōu)路徑和最差路徑在信息素上的差異,使得螞蟻更傾向于選擇最優(yōu)路徑中的邊,從而使得其搜索行為能夠很快地集中造最優(yōu)路徑附近,提高了算法的搜索效率。（3） 建立問題解決方案的過程中,應(yīng)用局部信息素更新規(guī)則螞蟻在構(gòu)造路徑的同時進行局部更新,類似于蟻密和蟻量模型中的局部更新,而在每次循環(huán)后再對路徑進行一次全局的更新。5.5.3.1蟻群系統(tǒng)狀態(tài)轉(zhuǎn)移規(guī)則蟻群系統(tǒng)在構(gòu)造候選解時使用了偽隨機比例規(guī)則，位于節(jié)點i的螞蟻通過下式確定選擇下一個城市j的概率：為［0,1］內(nèi)均勻分布的隨機數(shù)。5.5.3.2蟻群系統(tǒng)全局更新規(guī)則在蟻群系統(tǒng)中，只有全局最優(yōu)的螞蟻才被允許釋放信息素，這種選擇以及偽隨機比例規(guī)則，其目的都是為了使搜素過程更具有指導(dǎo)性：螞蟻的搜索主要集中在當(dāng)前循環(huán)為止所找出的最好路徑的鄰域內(nèi)。全局更新如下：最優(yōu)螞蟻經(jīng)過路徑(，)

否則5.5.3.3蟻群系統(tǒng)局部更新規(guī)則由實驗發(fā)現(xiàn)，設(shè)置 可以產(chǎn)生好的結(jié)果，其中n是城市的數(shù)量，Lnn是由最近的鄰域啟發(fā)產(chǎn)生的一個路徑長度。局部更新規(guī)則的應(yīng)用使得相應(yīng)的信息素軌跡減少，可以有效避免螞蟻收斂到同一路徑。5.5.4最大-最小螞蟻系統(tǒng)最大-最小螞蟻系統(tǒng)(Max-minAntSystem，MMAS)是對標(biāo)準(zhǔn)螞蟻系統(tǒng)算法的一個簡單修改［8,9］。它有兩個主要特點。首先，每一代最好的螞蟻才能增加信息素，這就減少了開發(fā)并增加了對已知的開采。其次，信息素的量是上下有界的，這起到有相反的作用，也就是說，它增加了探索，因為即使是最糟糕的旅行也保留了非零數(shù)量的信息素，即使是最好的旅行也無法獲得如此多的信息素，以至于完全控制了螞蟻的決策。最優(yōu)螞蟻經(jīng)過路徑(，)否則若一條路徑的信息素軌跡明顯高于其他路徑，停滯現(xiàn)象就會發(fā)生，因為在這種情況下螞蟻更傾向于選擇該路徑，正反饋機制使得該路徑的信息素進一步增強，從而螞蟻將重復(fù)地建立同一個解，對搜索空間的探索停止。因此最大-最小螞蟻系統(tǒng)對信息素軌跡的最大值和最小值分別施加了和限制，從而有5.5.5最優(yōu)-最差螞蟻系統(tǒng)鑒于螞蟻系統(tǒng)搜索效率低和質(zhì)量差的缺點，提出了一種最優(yōu)-最差螞蟻系統(tǒng)(Best-WorstAntSystem，BWAS)。該算法的思想是對最優(yōu)解進行更大限度的增強，而對最差解進行削弱，使得屬于最優(yōu)路徑的邊與屬于最差路徑的邊之間的信息素差異進一步增大，從而使螞蟻的搜索行為更集中于最優(yōu)的附近。該算法主要修改了蟻群系統(tǒng)中的全局更新，當(dāng)所有螞蟻完成一次循環(huán)后，增加對最差螞蟻所經(jīng)歷路徑的信息素的更新。若（i,j）為最差螞蟻路徑中的一條邊，且不是最優(yōu)螞蟻路徑中的邊，則該路徑的信息素按如下調(diào)整：參考文獻Dorigo,M.,Optimization,LearningandNaturalAlgorithms(inItalian),inDipartimentodiElettronicaeInformazione.1992,PolitecnicodiMilano:Milan,Italy.H.Papadimitriou,C.andK.Steiglitz,CombinatorialOptimization:AlgorithmsandComplexity.Vol.32.1982.Deneubourg,J.-L.,etal.,Thedynamicsofcollectivesortingrobot-likeantsandant-likerobots.1990.356-363.Deneubourg,J.L.,etal.,Theself-organizingexploratorypatternoftheargentineant.JournalofInsectBehavior,1990.3(2):p.159-168.Lopez-Ibanez,M.,T.Stutzle,andM.Dorigo,AntColonyOptimization:AComponent-WiseOverview,inHandbookofHeuristics,R.Marti,P.Panos,andM.G.C.Resende,Editors.2016,SpringerInternationalPublishing:Cham.p.1-37.Dorig