5.1 介紹

蟻群優(yōu)化(ACO)是群體智能的一部分，它模仿螞蟻的合作行為來解決復(fù)雜的組合優(yōu)化問題。它的概念是由Marco Dorigo[1]和他的同事提出的，當(dāng)他們觀察到這些生物在尋找食物時(shí)所采用的相互交流和自我組織的合作方式時(shí)，他們感到很驚訝。他們提出了執(zhí)行這些策略的想法，為不同領(lǐng)域的復(fù)雜優(yōu)化問題提供了解決方案，并獲得了廣泛的歡迎[1, 2]。

蟻群算法是一組被稱為人工螞蟻的軟件代理，它們?yōu)樘囟ǖ膬?yōu)化問題尋找好的解決方案。蟻群算法是通過將問題映射成一個(gè)加權(quán)圖來實(shí)現(xiàn)的，在加權(quán)圖中，螞蟻沿著邊緣移動(dòng)，尋找最佳路徑。

蟻群研究(實(shí)際上是真正的螞蟻)始于1959年，當(dāng)時(shí)皮埃爾?保羅?格拉斯(Pierre Paul Grasse)發(fā)明了“協(xié)同”理論，解釋了白蟻的筑巢行為。之后于1983年Deneubourg和他的同事們[3]對螞蟻的集體行為進(jìn)行了研究。1988年，Mayson和Manderick發(fā)表了一篇關(guān)于螞蟻的自組織行為的文章。最終在1989年，Goss, Aron, Deneubour, and Pasteelson在其研究工作（阿根廷螞蟻的集體行為）中提出了蟻群算法的基本思想[4]，同年，Ebling及其同事提出了一食物定位模型。1992年，Marco Dorigo(Dorigo, 1992)在其博士論文中提出了螞蟻系統(tǒng)（Ant System）[1]。一些研究人員將這些算法擴(kuò)展到各個(gè)研究領(lǐng)域的應(yīng)用中，Appleby和英國電信主管發(fā)表了第一個(gè)在電信網(wǎng)絡(luò)中的應(yīng)用，后來Schoonderwoerd和他的同事在1997年對其進(jìn)行了改進(jìn)。在2002年，它被應(yīng)用于貝葉斯網(wǎng)絡(luò)中的調(diào)度問題。

蟻群算法的設(shè)計(jì)是基于螞蟻搜索巢穴和食物位置之間短路徑的能力，這可能會因螞蟻的種類而有所不同。近年來，研究人員對蟻群算法的應(yīng)用結(jié)果進(jìn)行了研究，結(jié)果表明，所使用的大多數(shù)人工螞蟻并不能提供最好的解決方案，而精英蟻群通過重復(fù)的交換技術(shù)提供了最好的解決方案。他們進(jìn)一步指出，如果考慮相同的參數(shù)，混合和交換方法的性能優(yōu)于蟻群系統(tǒng)(ACS)。

基于這一理論，研究人員提出了一種專門的蟻群優(yōu)化方法，可以模擬特定種類的螞蟻，如黑蟻（Lasius niger或Irodomyrex humilis），著名的阿根廷螞蟻。

5.2 人工螞蟻的概念

自然生物的合作行為常常被證明是解決現(xiàn)實(shí)生活中各種復(fù)雜問題的一個(gè)很好的方法。生物的協(xié)作行為吸引了研究人員將它們的智能融入人工智能中，共同努力解決不同領(lǐng)域的各種復(fù)雜問題。

5.2.1 真實(shí)螞蟻如何工作

像螞蟻這樣的微小自然生物可以共同工作來完成復(fù)雜的任務(wù)。這種群居行為是基于螞蟻在運(yùn)動(dòng)時(shí)分泌的一種特殊化學(xué)物質(zhì)——信息素。這些信息素吸引其他螞蟻通過相同的路徑，這就證明了為什么螞蟻總是在群體中交流，蟻丘是如何形成的，以及它們?nèi)绾文軌蛲ㄟ^相互交流策略實(shí)現(xiàn)復(fù)雜的結(jié)構(gòu)。

信息素在螞蟻之間完成各種集體任務(wù)的信息交換中發(fā)揮著重要的作用；對我們來說，理解信息素的工作原理以及它們?nèi)绾螏椭浵佌业绞澄镌吹淖疃搪窂阶兊梅浅Ｖ匾?/p>

5.2.2 螞蟻如何優(yōu)化食物搜索

食物搜索過程大致可以分為三個(gè)階段。螞蟻開始尋找目標(biāo)時(shí)，會在朝隨機(jī)的方向搜索食物。這些螞蟻以混亂的方式四處游走，最終當(dāng)疲憊不堪時(shí)就返回巢穴進(jìn)食和休息。然而，當(dāng)它們漫步時(shí)，如果其中一只遇到了食物來源，它會帶著一小塊食物回到巢穴，并留下信息素軌跡，這種信息素可以作為其他螞蟻是否有食物的指示。因此，螞蟻會沿著信息素軌跡，留下更多的信息素。然而，考慮到螞蟻可以選擇多種路徑到達(dá)食物源，螞蟻的初始移動(dòng)在本質(zhì)上是有些混亂的，有許多路徑連接著巢穴和食物，螞蟻通常選擇信息素更強(qiáng)的路徑。信息素隨著時(shí)間的推移而蒸發(fā)，從而到達(dá)食物源最短的路徑具有最強(qiáng)的信息素；螞蟻慢慢地向這條路線靠攏，使之成為最優(yōu)路線，后來形成了蟻群(Fogel等，1966)。

5.2.3 什么是人工螞蟻

人工螞蟻不過是一種模擬代理，它模仿真實(shí)螞蟻的一些行為特征，以解決復(fù)雜的現(xiàn)實(shí)問題。根據(jù)計(jì)算機(jī)科學(xué)，它們代表了來自真實(shí)螞蟻行為的多智能體技術(shù)。這個(gè)概念是建立在這樣一個(gè)理念之上的：智能可以是許多微小物體的集體努力。這種智能個(gè)體的環(huán)境網(wǎng)絡(luò)目前是未來技術(shù)的愿景，有望超越目前基于人腦的集中式系統(tǒng)[5]。

人工螞蟻有著雙重特性，一方面，它們是真實(shí)螞蟻行為特征的一種抽象，將螞蟻覓食行為中最關(guān)鍵的部分賦予人工螞蟻；另一方面，人工螞蟻是為了解決實(shí)際的工程優(yōu)化問題，所以人工螞蟻也具備了一些真實(shí)螞蟻所不具備的本領(lǐng)以增強(qiáng)算法的優(yōu)化效果。

5.2.3.1 相同

• 
  

• 相互合作的個(gè)體：每個(gè)人工螞蟻都是一個(gè)可行解，高質(zhì)量的解是整個(gè)蟻群合作的結(jié)果；

• 
  

• 共同的任務(wù)：尋找起點(diǎn)（蟻穴）到終點(diǎn)（食物源）之間的最短路徑（最小代價(jià)）；

• 
  

• 信息素-間接通訊：人工蟻群算法中信息素軌跡是通過狀態(tài)變量來比表示。狀態(tài)變量用一個(gè)nxn維信息素矩陣來表示，其中n表示問題的規(guī)模，矩陣中的元素rij表示在節(jié)點(diǎn)i選擇節(jié)點(diǎn)j作為移動(dòng)方向的期望值。初始化矩陣中每一個(gè)元素（如0），隨著螞蟻在所經(jīng)過的路徑上釋放信息素的增多，矩陣中的對應(yīng)元素也隨之改變，人工蟻群算法就是通過修改矩陣中的元素的數(shù)值，來模擬自然界中信息素軌跡的更新過程。

• 
  

• 正反饋：當(dāng)一些路徑上通過的螞蟻越來越多，其留下的信息素軌跡也越來越多，使得信息素的強(qiáng)度增大。根據(jù)螞蟻傾向于選擇信息素強(qiáng)度大的路徑的特點(diǎn)，后來的螞蟻選擇該路徑的概率也越高，從而增加了該路徑的信息素強(qiáng)度，這種選擇過程被稱為自催化過程。自催化過程利用信息作為反饋，通過對系統(tǒng)演化過程中較優(yōu)解的自增強(qiáng)作用，使得問題的解向著全局最優(yōu)的方向不斷進(jìn)化，最終能夠有效獲得相對較優(yōu)的解。正反饋在基于群體的優(yōu)化算法中是一個(gè)強(qiáng)有力的機(jī)制。

• 
  

• 信息素的揮發(fā)：揮發(fā)機(jī)制可以使螞蟻逐漸忘記過去，不受過去經(jīng)驗(yàn)的過分約束，有利于指引螞蟻向著新的方向進(jìn)行搜索，避免早熟收斂。

• 
  

• 不預(yù)測未來狀態(tài)概率的狀態(tài)轉(zhuǎn)移策略：只充分利用局部信息，并沒有利用前瞻性預(yù)測未來的狀態(tài)。

5.2.3.2 不同

• 
  

• 人工螞蟻生活在離散的世界中，它們的移動(dòng)實(shí)質(zhì)上是由一個(gè)離散狀態(tài)到另一個(gè)離散狀態(tài)的躍遷；

• 
  

• 人工螞蟻內(nèi)部有一個(gè)內(nèi)部的狀態(tài)，這個(gè)私有的狀態(tài)記憶了螞蟻過去的行為；

• 
  

• 人工螞蟻釋放一定量的信息素，它是螞蟻所建立的問題解決方案優(yōu)劣程度的函數(shù)；

• 
  

• 人工螞蟻釋放信息素的時(shí)間可以視情況而定，而真實(shí)螞蟻是在移動(dòng)的同時(shí)釋放信息素，人工螞蟻可以在建立了一個(gè)可行的解決方案后再進(jìn)行信息素的更新；

5.3 螞蟻系統(tǒng)

螞蟻系統(tǒng)是提出的第一個(gè)ACO算法[6]，可以以旅行商問題為例說明該算法。在ACO仿真中，每只螞蟻都要從一個(gè)城市到另一個(gè)城市，在螞蟻完成它們的旅程后，蟻群算法會在它們的路徑上儲存信息素。信息素不僅沉積，而且蒸發(fā)。一只螞蟻從現(xiàn)在的城市到另一個(gè)城市旅行的概率與城市間信息素的數(shù)量成正比。螞蟻也被認(rèn)為對問題有一定的了解，可以幫助它們在旅途中做出決定。它們知道從現(xiàn)在的城市到其他城市的距離，更有可能去一個(gè)近的城市而不是一個(gè)遙遠(yuǎn)的城市，因?yàn)樗惴ǖ哪繕?biāo)是找到最短路徑。螞蟻系統(tǒng)算法如下所示。

從算法中可以看出每只螞蟻從城市i去到城市j的概率與這些城市之間路徑上信息素的數(shù)量成正比，與這些城市之間的距離成反比。比率α/β確定信息素信息相對于距離信息在決定去哪個(gè)城市旅行時(shí)的重要性。當(dāng)一只螞蟻從一個(gè)城市i移動(dòng)到另一個(gè)城市j時(shí)，這條路徑上的信息素的數(shù)量與螞蟻解的質(zhì)量成正比(也就是說，與螞蟻的總旅行距離成反比)。

5.4 三種模型

5.4.1 蟻密系統(tǒng)模型

該模型中，一只螞蟻經(jīng)過路徑（i，j）上釋放的信息素量為常數(shù)Q，即

5.4.2 蟻量系統(tǒng)模型

該模型中，一只螞蟻經(jīng)過路徑（i，j）上釋放的信息素量為常數(shù)Q/dij，即

可以看出，在蟻量模型中，信息素軌跡強(qiáng)度的增加與dij成反比，因此段路徑對螞蟻更有吸引力。

5.4.3 蟻周系統(tǒng)模型

該模型與前兩種模型的區(qū)別在于螞蟻k完成一次循環(huán)后才會更新信息素，其更新公式如下：

在蟻密模型和蟻量模型中，螞蟻在建立方案的同時(shí)釋放信息素，利用的是局部信息，而蟻周模型是在螞蟻已經(jīng)建立了完整的軌跡后再釋放信息素，利用的是整體信息。

5.5 改進(jìn)的蟻群優(yōu)化算法

5.5.1 帶精英策略的螞蟻系統(tǒng)

帶精英策略的螞蟻系統(tǒng)（Ant System with elitist strategy，ASelite），為了使當(dāng)前的最優(yōu)解在下一循環(huán)中對螞蟻更有吸引力，在每次循環(huán)后給予最優(yōu)解以額外的信息素，這個(gè)最優(yōu)解就是全局最優(yōu)解，找到該解的螞蟻為精英螞蟻，信息素更新公式如下：

δij(k)表示第k個(gè)螞蟻經(jīng)過ij，σ是精英解的個(gè)數(shù)。

5.5.2 基于優(yōu)化排序的螞蟻系統(tǒng)

和螞蟻系統(tǒng)一樣，帶精英策略的螞蟻系統(tǒng)有一個(gè)缺點(diǎn)：若在進(jìn)化過程中，解的總質(zhì)量提高了，解元素之間的差異減少了，導(dǎo)致選擇概率的差異隨之減小，使得搜索過程不會集中在到目前為止所找出的最優(yōu)解附近，從而阻止了對更優(yōu)解的進(jìn)一步搜索。當(dāng)路徑長度變得非常接近，特別是當(dāng)很多螞蟻沿著局部極優(yōu)的路徑行進(jìn)時(shí)，則對短路徑的增強(qiáng)作用被削弱了。

受遺傳算法中采用排序選擇機(jī)制解決選擇壓力的啟發(fā)，將排序的概念應(yīng)用到螞蟻系統(tǒng)中，就有了基于優(yōu)先排序的螞蟻系統(tǒng)（Rank-Bsed Version of Ant System，ASrank）。具體過程如下：當(dāng)每只螞蟻都生成一條路徑后，螞蟻按照路徑長度排序（L1≤L2≤┈≤Lm），螞蟻對信息素軌跡更新的貢獻(xiàn)根據(jù)該螞蟻的排名μ的位次進(jìn)行加權(quán)。此外只考慮w只最好的螞蟻，σ為目前為止所找出的最優(yōu)路徑上軌跡貢獻(xiàn)的權(quán)值，前σ-1只螞蟻中的各只所經(jīng)歷的邊獲得一定量的信息素，其正比于該螞蟻的排名位次。此外，到目前為止找出最優(yōu)路徑的螞蟻所經(jīng)過的邊也將獲得額外的信息素（這相當(dāng)于帶有精英策略的螞蟻系統(tǒng)中精英螞蟻的更新），所以有如下的更新：

是σ-1只螞蟻根據(jù)排名對信息素軌跡的更新：

5.5.3 蟻群系統(tǒng)

蟻群系統(tǒng)（Ant Colony System，ACS）[7]是由Dorigo和Gambardella在1996年提出的，用于改善螞蟻系統(tǒng)的性能。蟻群系統(tǒng)在螞蟻系統(tǒng)的基礎(chǔ)上主要做了三個(gè)方面的改進(jìn)：
（1）狀態(tài)轉(zhuǎn)移規(guī)則為更好更合理地利用新路徑和利用關(guān)于問題的先驗(yàn)知識提供了方法。

蟻群系統(tǒng)使用雙重決策：既可以利用關(guān)于問題的先驗(yàn)知識和以信息素形式存儲的已經(jīng)獲得信息，又可以進(jìn)行有向性的探索。通過調(diào)節(jié)參數(shù)q0，可以調(diào)節(jié)探索新路徑的程度和是否使螞蟻的搜索活動(dòng)集中于最優(yōu)解的空間鄰域內(nèi)。

（2）全局更新規(guī)則只應(yīng)用于最優(yōu)的螞蟻路徑上

在蟻群系統(tǒng)中，每次循環(huán)后只對最優(yōu)螞蟻經(jīng)歷的路徑進(jìn)行信息素的增強(qiáng)，其他路徑由于揮發(fā)機(jī)制信息素會逐漸減少，這就增大了最優(yōu)路徑和最差路徑在信息素上的差異，使得螞蟻更傾向于選擇最優(yōu)路徑中的邊，從而使得其搜索行為能夠很快地集中造最優(yōu)路徑附近，提高了算法的搜索效率。

（3）建立問題解決方案的過程中，應(yīng)用局部信息素更新規(guī)則

螞蟻在構(gòu)造路徑的同時(shí)進(jìn)行局部更新，類似于蟻密和蟻量模型中的局部更新，而在每次循環(huán)后再對路徑進(jìn)行一次全局的更新。

5.5.3.1 蟻群系統(tǒng)狀態(tài)轉(zhuǎn)移規(guī)則

蟻群系統(tǒng)在構(gòu)造候選解時(shí)使用了偽隨機(jī)比例規(guī)則，位于節(jié)點(diǎn)i的螞蟻通過下式確定選擇下一個(gè)城市j的概率：

r為[0,1]內(nèi)均勻分布的隨機(jī)數(shù)。

5.5.3.2 蟻群系統(tǒng)全局更新規(guī)則

在蟻群系統(tǒng)中，只有全局最優(yōu)的螞蟻才被允許釋放信息素，這種選擇以及偽隨機(jī)比例規(guī)則，其目的都是為了使搜素過程更具有指導(dǎo)性：螞蟻的搜索主要集中在當(dāng)前循環(huán)為止所找出的最好路徑的鄰域內(nèi)。全局更新如下：

5.5.3.3 蟻群系統(tǒng)局部更新規(guī)則

由實(shí)驗(yàn)發(fā)現(xiàn)，設(shè)置τ_0=(nL_nn )^(-1)可以產(chǎn)生好的結(jié)果，其中n是城市的數(shù)量，Lnn是由最近的鄰域啟發(fā)產(chǎn)生的一個(gè)路徑長度。局部更新規(guī)則的應(yīng)用使得相應(yīng)的信息素軌跡減少，可以有效避免螞蟻收斂到同一路徑。

5.5.4 最大-最小螞蟻系統(tǒng)

最大-最小螞蟻系統(tǒng)（Max-min Ant System，MMAS）是對標(biāo)準(zhǔn)螞蟻系統(tǒng)算法的一個(gè)簡單修改[8, 9]。它有兩個(gè)主要特點(diǎn)。首先，每一代最好的螞蟻才能增加信息素，這就減少了開發(fā)并增加了對已知的開采。其次，信息素的量是上下有界的，這起到有相反的作用，也就是說，它增加了探索，因?yàn)榧词故亲钤愀獾穆眯幸脖Ａ袅朔橇銛?shù)量的信息素，即使是最好的旅行也無法獲得如此多的信息素，以至于完全控制了螞蟻的決策。

若一條路徑的信息素軌跡明顯高于其他路徑，停滯現(xiàn)象就會發(fā)生，因?yàn)樵谶@種情況下螞蟻更傾向于選擇該路徑，正反饋機(jī)制使得該路徑的信息素進(jìn)一步增強(qiáng)，從而螞蟻將重復(fù)地建立同一個(gè)解，對搜索空間的探索停止。因此最大-最小螞蟻系統(tǒng)對信息素軌跡的最大值和最小值分別施加了τ_min和τ_max限制，從而有

5.5.5 最優(yōu)-最差螞蟻系統(tǒng)

鑒于螞蟻系統(tǒng)搜索效率低和質(zhì)量差的缺點(diǎn)，提出了一種最優(yōu)-最差螞蟻系統(tǒng)（Best-Worst Ant System，BWAS）。該算法的思想是對最優(yōu)解進(jìn)行更大限度的增強(qiáng)，而對最差解進(jìn)行削弱，使得屬于最優(yōu)路徑的邊與屬于最差路徑的邊之間的信息素差異進(jìn)一步增大，從而使螞蟻的搜索行為更集中于最優(yōu)的附近。
該算法主要修改了蟻群系統(tǒng)中的全局更新，當(dāng)所有螞蟻完成一次循環(huán)后，增加對最差螞蟻所經(jīng)歷路徑的信息素的更新。若（i，j）為最差螞蟻路徑中的一條邊，且不是最優(yōu)螞蟻路徑中的邊，則該路徑的信息素按如下調(diào)整：

5.6 代碼

%% 該函數(shù)用于演示基于蟻群算法的三維路徑規(guī)劃算法 %% 清空環(huán)境 clc clear %% 數(shù)據(jù)初始化 %下載數(shù)據(jù) load ?HeightData HeightData %網(wǎng)格劃分 LevelGrid=10; PortGrid=21; %起點(diǎn)終點(diǎn)網(wǎng)格點(diǎn) starty=10;starth=4; endy=8;endh=5; m=1; %算法參數(shù) PopNumber=10; ? ? ? ? %種群個(gè)數(shù) BestFitness=[]; ? ?%最佳個(gè)體 %初始信息素 pheromone=ones(21,21,21); %% 初始搜索路徑 [path,pheromone]=searchpath(PopNumber,LevelGrid,PortGrid,pheromone, ... ? ?HeightData,starty,starth,endy,endh); fitness=CacuFit(path); ? ? ? ? ? ? ? ? ? ? ? ? ?%適應(yīng)度計(jì)算 [bestfitness,bestindex]=min(fitness); ? ? ? ? ? %最佳適應(yīng)度 bestpath=path(bestindex,:); ? ? ? ? ? ? ? ? ? ? %最佳路徑 BestFitness=[BestFitness;bestfitness]; ? ? ? ? ?%適應(yīng)度值記錄 %% 信息素更新 rou=0.2; cfit=100/bestfitness; for i=2:PortGrid-1 ? ?pheromone(i,bestpath(i*2-1),bestpath(i*2))= ... ? ? ? ?(1-rou)*pheromone(i,bestpath(i*2-1),bestpath(i*2))+rou*cfit; end ? ? %% 循環(huán)尋找最優(yōu)路徑 for kk=1:100 ? ? ? ?%% 路徑搜索 ? ?[path,pheromone]=searchpath(PopNumber,LevelGrid,PortGrid,... ? ? ? ?pheromone,HeightData,starty,starth,endy,endh); ? ? ? ?%% 適應(yīng)度值計(jì)算更新 ? ?fitness=CacuFit(path); ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?[newbestfitness,newbestindex]=min(fitness); ? ? ? ?if newbestfitness<bestfitness ? ? ? ?bestfitness=newbestfitness; ? ? ? ?bestpath=path(newbestindex,:); ? ?end ? ?BestFitness=[BestFitness;bestfitness]; ? ? ? ?%% 更新信息素 ? ?cfit=100/bestfitness; ? ?for i=2:PortGrid-1 ? ? ? ?pheromone(i,bestpath(i*2-1),bestpath(i*2))=(1-rou)* ... ? ? ? ? ? ?pheromone(i,bestpath(i*2-1),bestpath(i*2))+rou*cfit; ? ?end end %% 最佳路徑 for i=1:21 ? ?a(i,1)=bestpath(i*2-1); ? ?a(i,2)=bestpath(i*2); end figure(1) x=1:21; y=1:21; [x1,y1]=meshgrid(x,y); mesh(x1,y1,HeightData) axis([1,21,1,21,0,2000]) hold on k=1:21; plot3(k(1)',a(1,1)',a(1,2)'*200,'--o','LineWidth',2,... ? ? ? ? ? ? ? ? ? ? ? 'MarkerEdgeColor','k',... ? ? ? ? ? ? ? ? ? ? ? 'MarkerFaceColor','g',... ? ? ? ? ? ? ? ? ? ? ? 'MarkerSize',10) plot3(k(21)',a(21,1)',a(21,2)'*200,'--o','LineWidth',2,... ? ? ? ? ? ? ? ? ? ? ? 'MarkerEdgeColor','k',... ? ? ? ? ? ? ? ? ? ? ? 'MarkerFaceColor','g',... ? ? ? ? ? ? ? ? ? ? ? 'MarkerSize',10) ? ? ? ? ? ? ? ? ? text(k(1)',a(1,1)',a(1,2)'*200,'S'); text(k(21)',a(21,1)',a(21,2)'*200,'T'); xlabel('km','fontsize',12); ylabel('km','fontsize',12); zlabel('m','fontsize',12); title('三維路徑規(guī)劃空間','fontsize',12) set(gcf, 'Renderer', 'ZBuffer') hold on plot3(k',a(:,1)',a(:,2)'*200,'--o') %% 適應(yīng)度變化 figure(2) plot(BestFitness) title('最佳個(gè)體適應(yīng)度變化趨勢') xlabel('迭代次數(shù)') ylabel('適應(yīng)度值')

博主擅長優(yōu)化求解、神經(jīng)網(wǎng)絡(luò)預(yù)測、信號處理、元胞自動(dòng)機(jī)、圖像處理等多種領(lǐng)域的Matlab仿真，QQ1575304183