蟻群算法國防科技大學理學院數(shù)學系成禮智2011年夏季學期數(shù)學建模競賽講座1蟻群算法國防科技大學理學院數(shù)學系1

蟻群優(yōu)化算法概述蟻群優(yōu)化算法概念算法模型和收斂性分析算法實現(xiàn)的技術問題應用參考資料2蟻群優(yōu)化算法概述2

1蟻群優(yōu)化算法概述1.1起源1.2應用領域1.3研究背景1.4研究現(xiàn)狀1.5應用現(xiàn)狀31蟻群優(yōu)化算法概述1.1起源3

1.1蟻群優(yōu)化算法起源20世紀90年代意大利學者M．Dorigo，V．Maniezzo，A．Colorni等從生物進化的機制中受到啟發(fā)，通過模擬自然界螞蟻搜索路徑的行為，提出來一種新型的模擬進化算法——蟻群算法，是群智能理論研究領域的一種主要算法。用該方法求解TSP問題、分配問題、job-shop調(diào)度問題，取得了較好的試驗結果．雖然研究時間不長，但是現(xiàn)在的研究顯示出，蟻群算法在求解復雜優(yōu)化問題（特別是離散優(yōu)化問題）方面有一定優(yōu)勢，表明它是一種有發(fā)展前景的算法．41.1蟻群優(yōu)化算法起源

1.2蟻群優(yōu)化算法應用領域

蟻群算法是一種群智能方法，能夠被用于解決大多數(shù)優(yōu)化問題或者能夠轉(zhuǎn)化為優(yōu)化求解的問題?，F(xiàn)在其應用領域已擴展到多目標優(yōu)化、數(shù)據(jù)分類、數(shù)據(jù)聚類、模式識別、電信管理、生物系統(tǒng)建模、流程規(guī)劃、信號處理、機器人控制、決策支持以及仿真和系統(tǒng)辯識等方面，群智能理論和方法為解決這類應用問題提供了新的途徑。51.2蟻群優(yōu)化算法應用領域蟻群算法是一

1.3蟻群優(yōu)化算法研究背景

群智能理論研究領域有兩種主要的算法：蟻群算法(AntColonyOptimization,ACO)和微粒群（或稱為粒子群）算法（ParticleSwarmOptimization,PSO）。前者是對螞蟻群落食物采集過程的模擬，已成功應用于許多離散優(yōu)化問題。微粒群算法也是起源于對簡單社會系統(tǒng)的模擬，最初是模擬鳥群覓食的過程，但后來發(fā)現(xiàn)它是一種很好的優(yōu)化工具。

61.3蟻群優(yōu)化算法研究背景

1.3蟻群優(yōu)化算法研究背景

與大多數(shù)基于梯度的應用優(yōu)化算法不同，群智能依靠的是概率搜索算法。雖然概率搜索算法通常要采用較多的評價函數(shù)，但是與梯度方法及傳統(tǒng)的演化算法相比，其優(yōu)點還是顯著的，主要表現(xiàn)在以下幾個方面：1無集中控制約束，不會因個別個體的故障影響整個問題的求解，確保了系統(tǒng)具備更強的魯棒性2以非直接的信息交流方式確保了系統(tǒng)的擴展性3并行分布式算法模型，可充分利用多處理器4對問題定義的連續(xù)性無特殊要求5算法實現(xiàn)簡單71.3蟻群優(yōu)化算法研究背景與大多數(shù)基于梯

1.3蟻群優(yōu)化算法研究背景

群智能方法易于實現(xiàn)，算法中僅涉及各種基本的數(shù)學操作，其數(shù)據(jù)處理過程對CPU和內(nèi)存的要求也不高。而且，這種方法只需目標函數(shù)的輸出值，而無需其梯度信息。已完成的群智能理論和應用方法研究證明群智能方法是一種能夠有效解決大多數(shù)全局優(yōu)化問題的新方法。更為重要是，群智能潛在的并行性和分布式特點為處理大量的以數(shù)據(jù)庫形式存在的數(shù)據(jù)提供了技術保證。無論是從理論研究還是應用研究的角度分析，群智能理論及其應用研究都是具有重要學術意義和現(xiàn)實價值的。81.3蟻群優(yōu)化算法研究背景群智能

1.4蟻群優(yōu)化算法研究現(xiàn)狀90年代Dorigo最早提出了蟻群優(yōu)化算法---螞蟻系統(tǒng)（AntSystem,AS）并將其應用于解決計算機算法學中經(jīng)典的旅行商問題（TSP）。從螞蟻系統(tǒng)開始，基本的蟻群算法得到了不斷的發(fā)展和完善，并在TSP以及許多實際優(yōu)化問題求解中進一步得到了驗證。這些AS改進版本的一個共同點就是增強了螞蟻搜索過程中對最優(yōu)解的探索能力，它們之間的差異僅在于搜索控制策略方面。而且，取得了最佳結果的ACO是通過引入局部搜索算法實現(xiàn)的，這實際上是一些結合了標準局域搜索算法的混合型概率搜索算法，有利于提高蟻群各級系統(tǒng)在優(yōu)化問題中的求解質(zhì)量。91.4蟻群優(yōu)化算法研究現(xiàn)狀90

1.4蟻群優(yōu)化算法研究現(xiàn)狀

M.Dorigo

最初提出的AS（Ant-System）有三種版本：Ant-density(蟻密)、Ant-quantity（蟻量）和Ant-cycle（蟻周）。在Ant-density和Ant-quantity中螞蟻在兩個位置節(jié)點間每移動一次后即更新信息素，而在Ant-cycle中當所有的螞蟻都完成了自己的行程后才對信息素進行更新，而且每個螞蟻所釋放的信息素被表達為反映相應行程質(zhì)量的函數(shù)。通過與其它各種通用的啟發(fā)式算法相比，在不大于75城市的TSP中，這三種基本算法的求解能力還是比較理想的，但是當問題規(guī)模擴展時，AS的解題能力大幅度下降。對此，后面的研究者提出了多種不同的改進蟻群算法。

101.4蟻群優(yōu)化算法研究現(xiàn)狀

1.5蟻群優(yōu)化算法應用現(xiàn)狀

隨著群智能理論和應用算法研究的不斷發(fā)展，研究者已嘗試著將其用于各種工程優(yōu)化問題，并取得了意想不到的收獲。多種研究表明，群智能在離散求解空間和連續(xù)求解空間中均表現(xiàn)出良好的搜索效果，并在組合優(yōu)化問題中表現(xiàn)突出。蟻群優(yōu)化算法并不是旅行商問題的最佳解決方法，但是它卻為解決組合優(yōu)化問題提供了新思路，并很快被應用到其它組合優(yōu)化問題中。比較典型的應用研究包括：網(wǎng)絡路由優(yōu)化、數(shù)據(jù)挖掘以及一些經(jīng)典的組合優(yōu)化問題。111.5蟻群優(yōu)化算法應用現(xiàn)狀

1.5蟻群優(yōu)化算法應用現(xiàn)狀

蟻群算法在電信路由優(yōu)化中已取得了一定的應用成果。HP公司和英國電信公司在90年代中后期都開展了這方面的研究，設計了蟻群路由算法（AntColonyRouting,ACR）。每只螞蟻就像蟻群優(yōu)化算法中一樣，根據(jù)它在網(wǎng)絡上的經(jīng)驗與性能，動態(tài)更新路由表項。如果一只螞蟻因為經(jīng)過了網(wǎng)絡中堵塞的路由而導致了比較大的延遲，那么就對該表項做較大的增強。同時根據(jù)信息素揮發(fā)機制實現(xiàn)系統(tǒng)的信息更新，從而拋棄過期的路由信息。這樣，在當前最優(yōu)路由出現(xiàn)擁堵現(xiàn)象時，ACR算法就能迅速的搜尋另一條可替代的最優(yōu)路徑，從而提高網(wǎng)絡的均衡性、負荷量和利用率。目前這方面的應用研究仍在升溫，因為通信網(wǎng)絡的分布式信息結構、非穩(wěn)定隨機動態(tài)特性以及網(wǎng)絡狀態(tài)的異步演化與ACO的算法本質(zhì)和特性非常相似。121.5蟻群優(yōu)化算法應用現(xiàn)狀蟻群算法在

1.5蟻群優(yōu)化算法應用現(xiàn)狀

ACO還在許多經(jīng)典組合優(yōu)化問題中獲得了成功的應用，如二次規(guī)劃問題（QAP）、機器人路徑規(guī)劃、作業(yè)流程規(guī)劃、圖著色（GraphColoring）等問題。經(jīng)過多年的發(fā)展，ACO已成為能夠有效解決實際二次規(guī)劃問題的幾種重要算法之一。AS在作業(yè)流程計劃（Job-shopScheduling）問題中的應用實例已經(jīng)出現(xiàn)，這說明了AS在此領域的應用潛力。利用MAX-MINAS解決PAQ也取得了比較理想的效果，并通過實驗中的計算數(shù)據(jù)證明采用該方法處理PAQ比較早的SA算法更好，且與禁忌搜索算法性能相當。利用ACO實現(xiàn)對生產(chǎn)流程和特料管理的綜合優(yōu)化，并通過與遺傳、模擬退火和禁忌搜索算法的比較證明了ACO的工程應用價值。131.5蟻群優(yōu)化算法應用現(xiàn)狀

1.5蟻群優(yōu)化算法應用現(xiàn)狀

許多研究者將ACO用于了武器攻擊目標分配和優(yōu)化問題、車輛運行路徑規(guī)劃、區(qū)域性無線電頻率自動分配、Bayesiannetworks的訓練和集合覆蓋等應用優(yōu)化問題。Costa和Herz還提出了一種AS在規(guī)劃問題方面的擴展應用——圖著色問題，并取得了可與其他啟發(fā)式算法相比的效果。141.5蟻群優(yōu)化算法應用現(xiàn)狀許

2蟻群優(yōu)化算法概念

2.1蟻群算法原理2.2簡化的螞蟻尋食過程2.3自然蟻群與人工蟻群算法2.4蟻群算法與TSP問題2.5初始的蟻群優(yōu)化算法—基于圖的蟻群系統(tǒng)（GBAS）2.6一般蟻群算法的框架152蟻群優(yōu)化算法概念 2.1蟻群算法原理15

2.1蟻群算法原理

蟻群算法是對自然界螞蟻的尋徑方式進行模似而得出的一種仿生算法。螞蟻在運動過程中，能夠在它所經(jīng)過的路徑上留下一種稱之為外激素(pheromone)的物質(zhì)進行信息傳遞，而且螞蟻在運動過程中能夠感知這種物質(zhì)，并以此指導自己的運動方向，因此由大量螞蟻組成的蟻群集體行為便表現(xiàn)出一種信息正反饋現(xiàn)象：某一路徑上走過的螞蟻越多，則后來者選擇該路徑的概率就越大。為了說明蟻群算法的原理，先簡要介紹一下螞蟻搜尋食物的具體過程。在蟻群尋找食物時，它們總能找到一條從食物到巢穴之間的最優(yōu)路徑。這是因為螞蟻在尋找路徑時會在路徑上釋放出一種特殊的信息素。當它們碰到一個還沒有走過的路口時．就隨機地挑選一條路徑前行。與此同時釋放出與路徑長度有關的信息素。路徑越長，釋放的激索濃度越低.當后來的螞蟻再次碰到這個路口的時候．選擇激素濃度較高路徑概率就會相對較大。這樣形成一個正反饋。最優(yōu)路徑上的激索濃度越來越大．而其它的路徑上激素濃度卻會隨著時間的流逝而消減。最終整個蟻群會找出最優(yōu)路徑。162.1蟻群算法原理蟻群算法

螞蟻覓食機理17螞蟻覓食機理17

其基本原理如下圖：上圖表示螞蟻覓食的線路，A為蟻穴,B為食源，從到有兩條線路可走，是長路徑，是短路徑.螞蟻走過一條路線以后，在地面上會留下信息素氣味，后來螞蟻就是根據(jù)留在地面上這種氣味的強度選擇移動的方向.18其基本原理如下圖：18

2.2蟻群覓食中的簡單規(guī)則

每只螞蟻只關心很小范圍內(nèi)的局部信息，而且根據(jù)這些局部信息利用幾條簡單的規(guī)則進行決策。（1）范圍：螞蟻觀察到的范圍是一個方格世界速度半徑（一般是3），移動的距離在這個方格范圍之內(nèi).（2）環(huán)境：螞蟻所在的環(huán)境是一個虛擬世界，有障礙物、別的螞蟻、信息素。信息素有兩種，一種是找到食物的螞蟻灑下的食物信息素，一種是找到窩的螞蟻灑下的窩的信息素.每個螞蟻都僅僅能感知它范圍內(nèi)的環(huán)境信息.環(huán)境以一定的速率讓信息素消失.（3）覓食規(guī)則：直接奔食物或看是否有信息素，并且朝信息素多的地方走，還會以小概率犯錯誤，從而并不總是往信息素最多的點移動.192.2蟻群覓食中的簡單規(guī)則19

（4）移動規(guī)則：每只螞蟻都朝向信息素最多的方向移，當周圍沒有信息素指引的時候，螞蟻會按照原來運動的方向慣性的運動下去，在運動的方向有一個隨機的小的擾動.為了防止螞蟻原地轉(zhuǎn)圈，它會記住最近剛走過了哪些點，如果發(fā)現(xiàn)要走的下一點已經(jīng)在最近走過了，它就會盡量避開.（5）避障規(guī)則：如果螞蟻要移動的方向有障礙物擋住，它會隨機的選擇另一個方向，并且有信息素指引的話，它會按照覓食的規(guī)則行為.（6）播撒信息素規(guī)則：每只螞蟻在剛找到食物或者窩的時候散發(fā)的信息素最多，并隨著它走的距離越遠，播撒的信息素越來越少.20（4）移動規(guī)則：每只螞蟻都朝向信息素最多的方向

2.3自然蟻群與人工蟻群人工蟻是自然蟻群的抽象：(1)人工蟻與真實蟻一樣，通過相互協(xié)調(diào)與合作從而有可能找到全局最優(yōu)方案，而每只人工蟻的單獨行動只可能找到局部最優(yōu)解.(2)人工蟻和真實蟻一樣，都要尋找一個從源節(jié)點（巢穴）到目的節(jié)點（食物源）之間的最短路徑（或最小代價），人工螞蟻與真實螞蟻一樣都不能跳躍，必須在相鄰節(jié)點之間移動，直至遍歷所有可能路徑，為了減少計算復雜度并尋找出最短路徑，需要記錄當前路徑.(3)人工蟻與真實蟻一樣都通過使用信息素進行間接通信真實螞蟻在經(jīng)過的路徑上留下信息素，人工蟻則不斷修改更新在其所經(jīng)過的路徑上存儲的信息，是一種模擬自然界中的信息素軌跡更新的過程.212.3自然蟻群與人工蟻群21

(4)人工蟻利用真實蟻覓食行為中的自催化機制—正反饋當一些路徑上通過的螞蟻越來越多時，路徑上留下的信息素軌跡也越來越多，使得信息素強度變大，根據(jù)螞蟻群傾向于選擇信息強度大的特點，后來的螞蟻選擇該路徑的概率也越高，從而增加了該路徑的信息素強度（自催化過程），自催化機制利用信息素作為反饋，通過對系統(tǒng)演化過程中較優(yōu)解的增強作用，使得問題的解向著全局最優(yōu)的方向逐步接近.(5)信息素的揮發(fā)機制在蟻群算法中設置一種揮發(fā)機制，類似于真實信息素的揮發(fā)，這種機制需要螞蟻忘記過去，不受過去經(jīng)驗的過分約束，有利于指引螞蟻朝著新的方向搜索，避免早熟收斂.(6)利用當前信息進行路徑選擇的隨機選擇策略人工蟻與真實蟻都是利用概率選擇策略實現(xiàn)一個節(jié)點到相鄰節(jié)點的移動，選擇策略只利用當前的信息去預測未來的情況，而不能利用未來的信息，因此，人工蟻與真實蟻所使用的選擇策略在時間和空間上都具有局部特性.22(4)人工蟻利用真實蟻覓食行為中的自催化

人工蟻具備一些真實蟻所不具備的特征，主要體現(xiàn)在下列五個方面：(1)人工蟻存在于離散空間中，它們的移動實質(zhì)上是有一個離散狀態(tài)到另一個離散狀態(tài)的轉(zhuǎn)移；(2)人工蟻具有一個記錄其過去自身行為的內(nèi)在狀態(tài)（記憶特性）；(3)人工蟻存在于與時間無關聯(lián)的環(huán)境之中；(4)人工蟻并非完全盲從，它受到問題特征的啟發(fā)，例如，有的問題中人工螞蟻產(chǎn)生一個解后改變信息量，而在有的問題中人工螞蟻每做一次選擇便改變信息量；(5)為了提升人工蟻系統(tǒng)的性能，改進算法效率，人工蟻可增加一些性能，如預測未來、局部優(yōu)化、回溯等.23人工蟻具備一些真實蟻所不具備的特征，主要體現(xiàn)2.3蟻群算法與TSP問題

2.3.1蟻群算法模型的建立

（1）螞蟻個體的抽象:抽象出能夠為建立模型起作用的真實蟻群的機理，摒棄與建立模型算法無關的因素.（2）問題空間的描述:螞蟻軌跡可以看成二維平面上的活動，其活動過程為一個狀態(tài)到另一個狀態(tài)的遷移，利用蟻群算法求解的采用圖論語言來描述就顯得非常自然，另一方面，在實際問題中的許多應用問題可以通過圖的語言來描述，這就使得蟻群算法的廣泛應用成為可能.（3）尋找路徑的抽象:把真實螞蟻的覓食過程抽象成算法中解的構造過程，將信息素抽象成存在于圖邊上的軌跡，信息素的大小可以通過設置權重來體現(xiàn)，并根據(jù)權重的值決定走向下一個節(jié)點的概率.用任何兩個節(jié)點分別表示螞蟻的巢穴（初始節(jié)點）和食物源（終止節(jié)點），人工螞蟻按照一定的狀態(tài)轉(zhuǎn)移概率從初始節(jié)點移動到鄰近的節(jié)點，以此類推，最終選擇行走到目標節(jié)點，從而得到問題的一個可行解.242.3蟻群算法與TSP問題2.3.1蟻群算法模型的

（4）信息素揮發(fā)的抽象:自然界中真實螞蟻在所經(jīng)過的路徑上會連續(xù)不斷的留下信息素，而信息素也會隨著時間的推移連續(xù)不斷的揮發(fā)，在人工蟻群算法中，螞蟻完成從某一節(jié)點到相鄰節(jié)點的一次移動后（相應于經(jīng)過一個時間單位），進行一次信息素揮發(fā)，這有利于避免陷入局部最優(yōu)的陷阱.（5）啟發(fā)因子的引入:為了設計有效的蟻群算法，在決定螞蟻行走方向的狀態(tài)轉(zhuǎn)移概率時，引入一個隨機搜索的過程，即引入一個啟發(fā)因子，根據(jù)所求問題空間的具體特征，給蟻群算法一個初始的引導，從而極大的增加算法的有效性，從而使蟻群算法的有效應用成為可能.25（4）信息素揮發(fā)的抽象:自然界中真實螞蟻在

2.3.2旅行商問題（ＴＳＰ）與蟻群算法

TSP問題描述如下：設有n個城市，用數(shù)碼1,,n代表.城市和城市之間的距離為．TSP問題是要找遍訪每個域市恰好一次的一條回路，且其路徑總長度為最短.圖論模型：給定圖，其中V為頂點集，A為各定點相互連接組成的邊集，已知各頂點間的連接距離，要求確定一條最短的Hamilton回路，即遍歷所有頂點當且僅當一次的最短回路.

Hamilton回路：經(jīng)過圖（有向圖或無向圖）中所有頂點一次且僅一次的通路。262.3.2旅行商問題（ＴＳＰ）與蟻群算法26

TSP問題表示為一個N個城市的有向圖G=（N，A），其中 城市之間距離目標函數(shù)為其中為城市1,2，…n的一個排列，。27TSP問題表示為一個N個城市的有向圖G=（N，A），

以TSP為例，基本蟻群算法的具體實現(xiàn)步驟描述如下：

（1）參數(shù)初始化（2）循環(huán)（3）螞蟻個體根據(jù)狀態(tài)轉(zhuǎn)移概率公式計算的概率選擇沿元素（城市）j前進，（4）修改禁忌指針表，即將選擇好之后的螞蟻移動到新的元素（城市），并將該元素（城市）移到該螞蟻個體的禁忌表中；（5）信息素更新的計算（6）紀錄到目前為止的最短路徑，如果，則計算終止，循環(huán)結束并輸出計算結果，否則，清空禁忌表并返回步驟（2）.整個計算過程所耗的空間復雜度為.28以TSP為例，基本蟻群算法的具體實現(xiàn)步驟描述如下：28

例2：0-1背包問題的解順序表達形式與算法實現(xiàn)。設有一個容積為b的背包，n個尺寸分別為，價值分別為的物品，0-1背包問題的數(shù)學模型為：假設其解的順序表達形式為，其中為的一個排列。29例2：0-1背包問題的解順序表達形式與算法實現(xiàn)。設

建立有向圖，其中A中共有條弧。初始信息素痕跡定義為。設第s只螞蟻第k步所走的路線為，表示螞蟻從0點出發(fā)，順序到達。第步按TSP算法的轉(zhuǎn)移概率公式行走選擇。若則，否則，此螞蟻不再繼續(xù)行走，退回起點。30建立有向圖，其中

對蟻群重復以上過程，比較m只螞蟻的裝包值 并記憶具有最大裝包值的螞蟻為t。把AS算法中步驟3中的改為，若滿足此條件則替換當前最好解為，對W上的弧進行信息素的加強，其他弧進行信息素的揮發(fā)。算法中記錄了三個信息：信息素痕跡；行走路線；和問題的約束條件 ，以確定是否將加入。31對蟻群重復以上過程，比較m只螞蟻的裝

算法中需要記憶的信息有三部分。第一部分信息是存在每個節(jié)點路由表數(shù)據(jù)結構，由此決定的的轉(zhuǎn)移概率為其中T可以看成節(jié)點i的鄰域。32算法中需要記憶的信息有三部分。32

第二部分需要記憶的信息是每個螞蟻的記憶表中存儲著的自身的歷史信息，這一部分主要由算法的中的記憶，表示螞蟻已經(jīng)行走過的節(jié)點。第三部分為問題的約束條件。在GBAS中，T集合表示滿足約束條件的候選集，在背包問題的蟻群算法中由判別條件， 實現(xiàn)記憶功能。33第二部分需要記憶的信息是每個螞蟻的記憶表中

基于最大-最小蟻群算法的指派問題求解

一、指派問題模型有個人和個任務，已知第個人做第個任務的費用為，要求確定人和任務之間的一一對應的指派方案，使完成這些任務的總費用最少。數(shù)學模型：34基于最大-最小蟻群算法的指派問題求解

一、指派問

在改進的蟻群算法之最大–最小蟻群系統(tǒng)（Max-MinAntSystem）

MMAS系統(tǒng)

中每次只對迭代最優(yōu)螞蟻或到目前為止全局最優(yōu)的螞蟻進行信息素更新（不是像螞蟻系統(tǒng)對所有走過路徑進行信息素更新）；每個解的元素上的信息素軌跡量值域限制在區(qū)間內(nèi)（不同于螞蟻系統(tǒng)中信息素軌跡量不被限制，使得一些路徑上軌跡量遠高于其它邊導致搜素停滯）；精心設計信息素初始化值，以保證更容易探索新的解（螞蟻系統(tǒng)中沒有考慮該因素導致算法收斂性較差）；引入信息素軌跡的平滑機制，以增加探索新解的能力，加快算法的收斂速度以及提高算法的數(shù)值穩(wěn)定性。（MMAS系統(tǒng)1996年由MLuca與Cambradella等人提出）35在改進的蟻群算法之最大–最小蟻群系統(tǒng)（Max

改進算法描述設需要指派3個人去完成3個任務，并知道每個人完成每個任務所需的費用，則可得到一個三行三列的系數(shù)矩陣。指派問題的系數(shù)矩陣形成移動矩陣相同行的不同列之間移動，并且此列未到達過信息素集中在節(jié)點轉(zhuǎn)到下一個節(jié)點的代價為下一個節(jié)點的系數(shù)矩陣值轉(zhuǎn)移概率并非選擇最大節(jié)點，有干擾因子到達一個節(jié)點，立即進行節(jié)點信息素的更新所有螞蟻完成一次覓食，比較次優(yōu)解，全局信息素的更新改進算法模型36改進算法描述設需要指派3個人去完成3個任務，并

改進算法模型轉(zhuǎn)移概率。產(chǎn)生隨機數(shù)，如果，則根據(jù)下式，螞蟻移向概率最大的節(jié)點。否則在可選節(jié)點中隨機選擇一個。局部信息素更新。當螞蟻選擇此節(jié)點后，立即更新此節(jié)點的信息素。全局信息素更新。當所有螞蟻完成一次覓食后，得到次優(yōu)解。優(yōu)于全局最優(yōu)解，更新全局信息素。37改進算法模型轉(zhuǎn)移概率。產(chǎn)生隨機數(shù)

實驗描述實驗目的：得到信息素啟發(fā)因子，期望值啟發(fā)因子，干擾因子，螞蟻數(shù)量，局部信息素揮發(fā)系數(shù)，全局信息素的揮發(fā)系數(shù)范圍規(guī)模為10的干擾因子實驗設置及結果，10次，迭代次數(shù)不同所有實驗38實驗描述實驗目的：得到信息素啟發(fā)因子，期望值啟發(fā)因

實驗目的：驗證算法的有效性參數(shù)設置及結果--》39實驗目的：驗證算法的有效性參數(shù)設置及結果--》39

與標準蟻群算法性能對比參數(shù)設置及結果--》40與標準蟻群算法性能對比參數(shù)設置及結果--》40

另外還有兩種改進蟻群算法以及蟻群算法的應用（運輸問題的蟻群算法）見word文檔41另外還有兩種改進蟻群算法以及蟻群算法的應用（運輸問題的蟻TheEnd！BaiBai！42TheEnd！42蟻群算法國防科技大學理學院數(shù)學系成禮智2011年夏季學期數(shù)學建模競賽講座43蟻群算法國防科技大學理學院數(shù)學系1

蟻群優(yōu)化算法概述蟻群優(yōu)化算法概念算法模型和收斂性分析算法實現(xiàn)的技術問題應用參考資料44蟻群優(yōu)化算法概述2

1蟻群優(yōu)化算法概述1.1起源1.2應用領域1.3研究背景1.4研究現(xiàn)狀1.5應用現(xiàn)狀451蟻群優(yōu)化算法概述1.1起源3

1.1蟻群優(yōu)化算法起源20世紀90年代意大利學者M．Dorigo，V．Maniezzo，A．Colorni等從生物進化的機制中受到啟發(fā)，通過模擬自然界螞蟻搜索路徑的行為，提出來一種新型的模擬進化算法——蟻群算法，是群智能理論研究領域的一種主要算法。用該方法求解TSP問題、分配問題、job-shop調(diào)度問題，取得了較好的試驗結果．雖然研究時間不長，但是現(xiàn)在的研究顯示出，蟻群算法在求解復雜優(yōu)化問題（特別是離散優(yōu)化問題）方面有一定優(yōu)勢，表明它是一種有發(fā)展前景的算法．461.1蟻群優(yōu)化算法起源

1.2蟻群優(yōu)化算法應用領域

蟻群算法是一種群智能方法，能夠被用于解決大多數(shù)優(yōu)化問題或者能夠轉(zhuǎn)化為優(yōu)化求解的問題?，F(xiàn)在其應用領域已擴展到多目標優(yōu)化、數(shù)據(jù)分類、數(shù)據(jù)聚類、模式識別、電信管理、生物系統(tǒng)建模、流程規(guī)劃、信號處理、機器人控制、決策支持以及仿真和系統(tǒng)辯識等方面，群智能理論和方法為解決這類應用問題提供了新的途徑。471.2蟻群優(yōu)化算法應用領域蟻群算法是一

1.3蟻群優(yōu)化算法研究背景

群智能理論研究領域有兩種主要的算法：蟻群算法(AntColonyOptimization,ACO)和微粒群（或稱為粒子群）算法（ParticleSwarmOptimization,PSO）。前者是對螞蟻群落食物采集過程的模擬，已成功應用于許多離散優(yōu)化問題。微粒群算法也是起源于對簡單社會系統(tǒng)的模擬，最初是模擬鳥群覓食的過程，但后來發(fā)現(xiàn)它是一種很好的優(yōu)化工具。

481.3蟻群優(yōu)化算法研究背景

1.3蟻群優(yōu)化算法研究背景

與大多數(shù)基于梯度的應用優(yōu)化算法不同，群智能依靠的是概率搜索算法。雖然概率搜索算法通常要采用較多的評價函數(shù)，但是與梯度方法及傳統(tǒng)的演化算法相比，其優(yōu)點還是顯著的，主要表現(xiàn)在以下幾個方面：1無集中控制約束，不會因個別個體的故障影響整個問題的求解，確保了系統(tǒng)具備更強的魯棒性2以非直接的信息交流方式確保了系統(tǒng)的擴展性3并行分布式算法模型，可充分利用多處理器4對問題定義的連續(xù)性無特殊要求5算法實現(xiàn)簡單491.3蟻群優(yōu)化算法研究背景與大多數(shù)基于梯

1.3蟻群優(yōu)化算法研究背景

群智能方法易于實現(xiàn)，算法中僅涉及各種基本的數(shù)學操作，其數(shù)據(jù)處理過程對CPU和內(nèi)存的要求也不高。而且，這種方法只需目標函數(shù)的輸出值，而無需其梯度信息。已完成的群智能理論和應用方法研究證明群智能方法是一種能夠有效解決大多數(shù)全局優(yōu)化問題的新方法。更為重要是，群智能潛在的并行性和分布式特點為處理大量的以數(shù)據(jù)庫形式存在的數(shù)據(jù)提供了技術保證。無論是從理論研究還是應用研究的角度分析，群智能理論及其應用研究都是具有重要學術意義和現(xiàn)實價值的。501.3蟻群優(yōu)化算法研究背景群智能

1.4蟻群優(yōu)化算法研究現(xiàn)狀90年代Dorigo最早提出了蟻群優(yōu)化算法---螞蟻系統(tǒng)（AntSystem,AS）并將其應用于解決計算機算法學中經(jīng)典的旅行商問題（TSP）。從螞蟻系統(tǒng)開始，基本的蟻群算法得到了不斷的發(fā)展和完善，并在TSP以及許多實際優(yōu)化問題求解中進一步得到了驗證。這些AS改進版本的一個共同點就是增強了螞蟻搜索過程中對最優(yōu)解的探索能力，它們之間的差異僅在于搜索控制策略方面。而且，取得了最佳結果的ACO是通過引入局部搜索算法實現(xiàn)的，這實際上是一些結合了標準局域搜索算法的混合型概率搜索算法，有利于提高蟻群各級系統(tǒng)在優(yōu)化問題中的求解質(zhì)量。511.4蟻群優(yōu)化算法研究現(xiàn)狀90

1.4蟻群優(yōu)化算法研究現(xiàn)狀

M.Dorigo

最初提出的AS（Ant-System）有三種版本：Ant-density(蟻密)、Ant-quantity（蟻量）和Ant-cycle（蟻周）。在Ant-density和Ant-quantity中螞蟻在兩個位置節(jié)點間每移動一次后即更新信息素，而在Ant-cycle中當所有的螞蟻都完成了自己的行程后才對信息素進行更新，而且每個螞蟻所釋放的信息素被表達為反映相應行程質(zhì)量的函數(shù)。通過與其它各種通用的啟發(fā)式算法相比，在不大于75城市的TSP中，這三種基本算法的求解能力還是比較理想的，但是當問題規(guī)模擴展時，AS的解題能力大幅度下降。對此，后面的研究者提出了多種不同的改進蟻群算法。

521.4蟻群優(yōu)化算法研究現(xiàn)狀

1.5蟻群優(yōu)化算法應用現(xiàn)狀

隨著群智能理論和應用算法研究的不斷發(fā)展，研究者已嘗試著將其用于各種工程優(yōu)化問題，并取得了意想不到的收獲。多種研究表明，群智能在離散求解空間和連續(xù)求解空間中均表現(xiàn)出良好的搜索效果，并在組合優(yōu)化問題中表現(xiàn)突出。蟻群優(yōu)化算法并不是旅行商問題的最佳解決方法，但是它卻為解決組合優(yōu)化問題提供了新思路，并很快被應用到其它組合優(yōu)化問題中。比較典型的應用研究包括：網(wǎng)絡路由優(yōu)化、數(shù)據(jù)挖掘以及一些經(jīng)典的組合優(yōu)化問題。531.5蟻群優(yōu)化算法應用現(xiàn)狀

1.5蟻群優(yōu)化算法應用現(xiàn)狀

蟻群算法在電信路由優(yōu)化中已取得了一定的應用成果。HP公司和英國電信公司在90年代中后期都開展了這方面的研究，設計了蟻群路由算法（AntColonyRouting,ACR）。每只螞蟻就像蟻群優(yōu)化算法中一樣，根據(jù)它在網(wǎng)絡上的經(jīng)驗與性能，動態(tài)更新路由表項。如果一只螞蟻因為經(jīng)過了網(wǎng)絡中堵塞的路由而導致了比較大的延遲，那么就對該表項做較大的增強。同時根據(jù)信息素揮發(fā)機制實現(xiàn)系統(tǒng)的信息更新，從而拋棄過期的路由信息。這樣，在當前最優(yōu)路由出現(xiàn)擁堵現(xiàn)象時，ACR算法就能迅速的搜尋另一條可替代的最優(yōu)路徑，從而提高網(wǎng)絡的均衡性、負荷量和利用率。目前這方面的應用研究仍在升溫，因為通信網(wǎng)絡的分布式信息結構、非穩(wěn)定隨機動態(tài)特性以及網(wǎng)絡狀態(tài)的異步演化與ACO的算法本質(zhì)和特性非常相似。541.5蟻群優(yōu)化算法應用現(xiàn)狀蟻群算法在

1.5蟻群優(yōu)化算法應用現(xiàn)狀

ACO還在許多經(jīng)典組合優(yōu)化問題中獲得了成功的應用，如二次規(guī)劃問題（QAP）、機器人路徑規(guī)劃、作業(yè)流程規(guī)劃、圖著色（GraphColoring）等問題。經(jīng)過多年的發(fā)展，ACO已成為能夠有效解決實際二次規(guī)劃問題的幾種重要算法之一。AS在作業(yè)流程計劃（Job-shopScheduling）問題中的應用實例已經(jīng)出現(xiàn)，這說明了AS在此領域的應用潛力。利用MAX-MINAS解決PAQ也取得了比較理想的效果，并通過實驗中的計算數(shù)據(jù)證明采用該方法處理PAQ比較早的SA算法更好，且與禁忌搜索算法性能相當。利用ACO實現(xiàn)對生產(chǎn)流程和特料管理的綜合優(yōu)化，并通過與遺傳、模擬退火和禁忌搜索算法的比較證明了ACO的工程應用價值。551.5蟻群優(yōu)化算法應用現(xiàn)狀

1.5蟻群優(yōu)化算法應用現(xiàn)狀

許多研究者將ACO用于了武器攻擊目標分配和優(yōu)化問題、車輛運行路徑規(guī)劃、區(qū)域性無線電頻率自動分配、Bayesiannetworks的訓練和集合覆蓋等應用優(yōu)化問題。Costa和Herz還提出了一種AS在規(guī)劃問題方面的擴展應用——圖著色問題，并取得了可與其他啟發(fā)式算法相比的效果。561.5蟻群優(yōu)化算法應用現(xiàn)狀許

2蟻群優(yōu)化算法概念

2.1蟻群算法原理2.2簡化的螞蟻尋食過程2.3自然蟻群與人工蟻群算法2.4蟻群算法與TSP問題2.5初始的蟻群優(yōu)化算法—基于圖的蟻群系統(tǒng)（GBAS）2.6一般蟻群算法的框架572蟻群優(yōu)化算法概念 2.1蟻群算法原理15

2.1蟻群算法原理

蟻群算法是對自然界螞蟻的尋徑方式進行模似而得出的一種仿生算法。螞蟻在運動過程中，能夠在它所經(jīng)過的路徑上留下一種稱之為外激素(pheromone)的物質(zhì)進行信息傳遞，而且螞蟻在運動過程中能夠感知這種物質(zhì)，并以此指導自己的運動方向，因此由大量螞蟻組成的蟻群集體行為便表現(xiàn)出一種信息正反饋現(xiàn)象：某一路徑上走過的螞蟻越多，則后來者選擇該路徑的概率就越大。為了說明蟻群算法的原理，先簡要介紹一下螞蟻搜尋食物的具體過程。在蟻群尋找食物時，它們總能找到一條從食物到巢穴之間的最優(yōu)路徑。這是因為螞蟻在尋找路徑時會在路徑上釋放出一種特殊的信息素。當它們碰到一個還沒有走過的路口時．就隨機地挑選一條路徑前行。與此同時釋放出與路徑長度有關的信息素。路徑越長，釋放的激索濃度越低.當后來的螞蟻再次碰到這個路口的時候．選擇激素濃度較高路徑概率就會相對較大。這樣形成一個正反饋。最優(yōu)路徑上的激索濃度越來越大．而其它的路徑上激素濃度卻會隨著時間的流逝而消減。最終整個蟻群會找出最優(yōu)路徑。582.1蟻群算法原理蟻群算法

螞蟻覓食機理59螞蟻覓食機理17

其基本原理如下圖：上圖表示螞蟻覓食的線路，A為蟻穴,B為食源，從到有兩條線路可走，是長路徑，是短路徑.螞蟻走過一條路線以后，在地面上會留下信息素氣味，后來螞蟻就是根據(jù)留在地面上這種氣味的強度選擇移動的方向.60其基本原理如下圖：18

2.2蟻群覓食中的簡單規(guī)則

每只螞蟻只關心很小范圍內(nèi)的局部信息，而且根據(jù)這些局部信息利用幾條簡單的規(guī)則進行決策。（1）范圍：螞蟻觀察到的范圍是一個方格世界速度半徑（一般是3），移動的距離在這個方格范圍之內(nèi).（2）環(huán)境：螞蟻所在的環(huán)境是一個虛擬世界，有障礙物、別的螞蟻、信息素。信息素有兩種，一種是找到食物的螞蟻灑下的食物信息素，一種是找到窩的螞蟻灑下的窩的信息素.每個螞蟻都僅僅能感知它范圍內(nèi)的環(huán)境信息.環(huán)境以一定的速率讓信息素消失.（3）覓食規(guī)則：直接奔食物或看是否有信息素，并且朝信息素多的地方走，還會以小概率犯錯誤，從而并不總是往信息素最多的點移動.612.2蟻群覓食中的簡單規(guī)則19

（4）移動規(guī)則：每只螞蟻都朝向信息素最多的方向移，當周圍沒有信息素指引的時候，螞蟻會按照原來運動的方向慣性的運動下去，在運動的方向有一個隨機的小的擾動.為了防止螞蟻原地轉(zhuǎn)圈，它會記住最近剛走過了哪些點，如果發(fā)現(xiàn)要走的下一點已經(jīng)在最近走過了，它就會盡量避開.（5）避障規(guī)則：如果螞蟻要移動的方向有障礙物擋住，它會隨機的選擇另一個方向，并且有信息素指引的話，它會按照覓食的規(guī)則行為.（6）播撒信息素規(guī)則：每只螞蟻在剛找到食物或者窩的時候散發(fā)的信息素最多，并隨著它走的距離越遠，播撒的信息素越來越少.62（4）移動規(guī)則：每只螞蟻都朝向信息素最多的方向

2.3自然蟻群與人工蟻群人工蟻是自然蟻群的抽象：(1)人工蟻與真實蟻一樣，通過相互協(xié)調(diào)與合作從而有可能找到全局最優(yōu)方案，而每只人工蟻的單獨行動只可能找到局部最優(yōu)解.(2)人工蟻和真實蟻一樣，都要尋找一個從源節(jié)點（巢穴）到目的節(jié)點（食物源）之間的最短路徑（或最小代價），人工螞蟻與真實螞蟻一樣都不能跳躍，必須在相鄰節(jié)點之間移動，直至遍歷所有可能路徑，為了減少計算復雜度并尋找出最短路徑，需要記錄當前路徑.(3)人工蟻與真實蟻一樣都通過使用信息素進行間接通信真實螞蟻在經(jīng)過的路徑上留下信息素，人工蟻則不斷修改更新在其所經(jīng)過的路徑上存儲的信息，是一種模擬自然界中的信息素軌跡更新的過程.632.3自然蟻群與人工蟻群21

(4)人工蟻利用真實蟻覓食行為中的自催化機制—正反饋當一些路徑上通過的螞蟻越來越多時，路徑上留下的信息素軌跡也越來越多，使得信息素強度變大，根據(jù)螞蟻群傾向于選擇信息強度大的特點，后來的螞蟻選擇該路徑的概率也越高，從而增加了該路徑的信息素強度（自催化過程），自催化機制利用信息素作為反饋，通過對系統(tǒng)演化過程中較優(yōu)解的增強作用，使得問題的解向著全局最優(yōu)的方向逐步接近.(5)信息素的揮發(fā)機制在蟻群算法中設置一種揮發(fā)機制，類似于真實信息素的揮發(fā)，這種機制需要螞蟻忘記過去，不受過去經(jīng)驗的過分約束，有利于指引螞蟻朝著新的方向搜索，避免早熟收斂.(6)利用當前信息進行路徑選擇的隨機選擇策略人工蟻與真實蟻都是利用概率選擇策略實現(xiàn)一個節(jié)點到相鄰節(jié)點的移動，選擇策略只利用當前的信息去預測未來的情況，而不能利用未來的信息，因此，人工蟻與真實蟻所使用的選擇策略在時間和空間上都具有局部特性.64(4)人工蟻利用真實蟻覓食行為中的自催化

人工蟻具備一些真實蟻所不具備的特征，主要體現(xiàn)在下列五個方面：(1)人工蟻存在于離散空間中，它們的移動實質(zhì)上是有一個離散狀態(tài)到另一個離散狀態(tài)的轉(zhuǎn)移；(2)人工蟻具有一個記錄其過去自身行為的內(nèi)在狀態(tài)（記憶特性）；(3)人工蟻存在于與時間無關聯(lián)的環(huán)境之中；(4)人工蟻并非完全盲從，它受到問題特征的啟發(fā)，例如，有的問題中人工螞蟻產(chǎn)生一個解后改變信息量，而在有的問題中人工螞蟻每做一次選擇便改變信息量；(5)為了提升人工蟻系統(tǒng)的性能，改進算法效率，人工蟻可增加一些性能，如預測未來、局部優(yōu)化、回溯等.65人工蟻具備一些真實蟻所不具備的特征，主要體現(xiàn)2.3蟻群算法與TSP問題

2.3.1蟻群算法模型的建立

（1）螞蟻個體的抽象:抽象出能夠為建立模型起作用的真實蟻群的機理，摒棄與建立模型算法無關的因素.（2）問題空間的描述:螞蟻軌跡可以看成二維平面上的活動，其活動過程為一個狀態(tài)到另一個狀態(tài)的遷移，利用蟻群算法求解的采用圖論語言來描述就顯得非常自然，另一方面，在實際問題中的許多應用問題可以通過圖的語言來描述，這就使得蟻群算法的廣泛應用成為可能.（3）尋找路徑的抽象:把真實螞蟻的覓食過程抽象成算法中解的構造過程，將信息素抽象成存在于圖邊上的軌跡，信息素的大小可以通過設置權重來體現(xiàn)，并根據(jù)權重的值決定走向下一個節(jié)點的概率.用任何兩個節(jié)點分別表示螞蟻的巢穴（初始節(jié)點）和食物源（終止節(jié)點），人工螞蟻按照一定的狀態(tài)轉(zhuǎn)移概率從初始節(jié)點移動到鄰近的節(jié)點，以此類推，最終選擇行走到目標節(jié)點，從而得到問題的一個可行解.662.3蟻群算法與TSP問題2.3.1蟻群算法模型的

（4）信息素揮發(fā)的抽象:自然界中真實螞蟻在所經(jīng)過的路徑上會連續(xù)不斷的留下信息素，而信息素也會隨著時間的推移連續(xù)不斷的揮發(fā)，在人工蟻群算法中，螞蟻完成從某一節(jié)點到相鄰節(jié)點的一次移動后（相應于經(jīng)過一個時間單位），進行一次信息素揮發(fā)，這有利于避免陷入局部最優(yōu)的陷阱.（5）啟發(fā)因子的引入:為了設計有效的蟻群算法，在決定螞蟻行走方向的狀態(tài)轉(zhuǎn)移概率時，引入一個隨機搜索的過程，即引入一個啟發(fā)因子，根據(jù)所求問題空間的具體特征，給蟻群算法一個初始的引導，從而極大的增加算法的有效性，從而使蟻群算法的有效應用成為可能.67（4）信息素揮發(fā)的抽象:自然界中真實螞蟻在

2.3.2旅行商問題（ＴＳＰ）與蟻群算法

TSP問題描述如下：設有n個城市，用數(shù)碼1,,n代表.城市和城市之間的距離為．TSP問題是要找遍訪每個域市恰好一次的一條回路，且其路徑總長度為最短.圖論模型：給定圖，其中V為頂點集，A為各定點相互連接組成的邊集，已知各頂點間的連接距離，要求確定一條最短的Hamilton回路，即遍歷所有頂點當且僅當一次的最短回路.

Hamilton回路：經(jīng)過圖（有向圖或無向圖）中所有頂點一次且僅一次的通路。682.3.2旅行商問題（ＴＳＰ）與蟻群算法26

TSP問題表示為一個N個城市的有向圖G=（N，A），其中 城市之間距離目標函數(shù)為其中為城市1,2，…n的一個排列，。69TSP問題表示為一個N個城市的有向圖G=（N，A），

以TSP為例，基本蟻群算法的具體實現(xiàn)步驟描述如下：

（1）參數(shù)初始化（2）循環(huán)（3）螞蟻個體根據(jù)狀態(tài)轉(zhuǎn)移概率公式計算的概率選擇沿元素（城市）j前進，（4）修改禁忌指針表，即將選擇好之后的螞蟻移動到新的元素（城市），并將該元素（城市）移到該螞蟻個體的禁忌表中；（5）信息素更新的計算（6）紀錄到目前為止的最短路徑，如果，則計算終止，循環(huán)結束并輸出計算結果，否則，清空禁忌表并返回步驟（2）.整個計算過程所耗的空間復雜度為.70以TSP為例，基本蟻群算法的具體實現(xiàn)步驟描述如下：28

例2：0-1背包問題的解順序表達形式與算法實現(xiàn)。設有一個容積為b的背包，n個尺寸分別為，價值分別為的物品，0-1背包問題的數(shù)學模型為：假設其解的順序表達形式為，其中為的一個排列。71例2：0-1背包問題的解順序表達形式與算法實現(xiàn)。設

建立有向圖，其中A中共有條弧。初始信息素痕跡定義為。設第s只螞蟻第k步所走的路線為，表示螞蟻從0點出發(fā)，順序到達。第步按TSP算法的轉(zhuǎn)移概率公式行走選擇。若則