蟻群算法簡述

關于蟻群算法簡述1.蟻群算法的提出算法的提出 蟻群算法（AntColonyOptimization,ACO），又稱螞蟻算法——一種用來在圖中尋找優(yōu)化路徑的機率型算法。 它由MarcoDorigo于1992年在他的博士論文“Antsystem:optimizationbyacolonyofcooperatingagents”中提出，其靈感來源于螞蟻在尋找食物過程中發(fā)現路徑的行為。最早用于解決著名的旅行商問題(TSP,travelingsalesmanproblem)。第2頁,共36頁，2024年2月25日，星期天1.蟻群算法的提出概念原型 各個螞蟻在沒有事先告訴他們食物在什么地方的前提下開始尋找食物。 當一只找到食物以后，它會向環(huán)境釋放一種揮發(fā)性分泌物pheromone(稱為信息素,該物質隨著時間的推移會逐漸揮發(fā)消失，信息素濃度的大小表征路徑的遠近)來實現的，吸引其他的螞蟻過來，這樣越來越多的螞蟻會找到食物。 有些螞蟻并沒有象其它螞蟻一樣總重復同樣的路，他們會另辟蹊徑，如果另開辟的道路比原來的其他道路更短，那么，漸漸地，更多的螞蟻被吸引到這條較短的路上來。 最后，經過一段時間運行，就可能會出現一條最短的路徑被大多數螞蟻重復著。第3頁,共36頁，2024年2月25日，星期天1.蟻群算法的提出基本原理

蟻群算法是對自然界螞蟻的尋徑方式進行模似而得出的一種仿生算法。螞蟻在運動過程中，能夠在它所經過的路徑上留下一種稱之為外激素(pheromone)的物質進行信息傳遞，而且螞蟻在運動過程中能夠感知這種物質，并以此指導自己的運動方向，因此由大量螞蟻組成的蟻群集體行為便表現出一種信息正反饋現象：某一路徑上走過的螞蟻越多，則后來者選擇該路徑的概率就越大。第4頁,共36頁，2024年2月25日，星期天1.蟻群算法的提出簡化的螞蟻尋食過程

螞蟻從A點出發(fā)，速度相同，食物在D點，可能隨機選擇路線ABD或ACD。假設初始時每條分配路線一只螞蟻，每個時間單位行走一步，本圖為經過9個時間單位時的情形：走ABD的螞蟻到達終點，而走ACD的螞蟻剛好走到C點，為一半路程。第5頁,共36頁，2024年2月25日，星期天1.蟻群算法的提出

本圖為從開始算起，經過18個時間單位時的情形：走ABD的螞蟻到達終點后得到食物又返回了起點A，而走ACD的螞蟻剛好走到D點。第6頁,共36頁，2024年2月25日，星期天1.蟻群算法的提出

假設螞蟻每經過一處所留下的信息素為一個單位，則經過36個時間單位后，所有開始一起出發(fā)的螞蟻都經過不同路徑從D點取得了食物，此時ABD的路線往返了2趟，每一處的信息素為4個單位，而ACD的路線往返了一趟，每一處的信息素為2個單位，其比值為2：1。尋找食物的過程繼續(xù)進行，則按信息素的指導，蟻群在ABD路線上增派一只螞蟻（共2只），而ACD路線上仍然為一只螞蟻。再經過36個時間單位后，兩條線路上的信息素單位積累為12和4，比值為3：1。若按以上規(guī)則繼續(xù)，蟻群在ABD路線上再增派一只螞蟻（共3只），而ACD路線上仍然為一只螞蟻。再經過36個時間單位后，兩條線路上的信息素單位積累為24和6，比值為4：1。若繼續(xù)進行，則按信息素的指導，最終所有的螞蟻會放棄ACD路線，而都選擇ABD路線。這也就是前面所提到的正反饋效應。第7頁,共36頁，2024年2月25日，星期天1.蟻群算法的提出人工蟻群算法 基于以上蟻群尋找食物時的最優(yōu)路徑選擇問題，可以構造人工蟻群，來解決最優(yōu)化問題，如TSP問題。 人工蟻群中把具有簡單功能的工作單元看作螞蟻。二者的相似之處在于都是優(yōu)先選擇信息素濃度大的路徑。較短路徑的信息素濃度高，所以能夠最終被所有螞蟻選擇，也就是最終的優(yōu)化結果。 兩者的區(qū)別在于人工蟻群有一定的記憶能力，能夠記憶已經訪問過的節(jié)點。同時，人工蟻群再選擇下一條路徑的時候是按一定算法規(guī)律有意識地尋找最短路徑，而不是盲目的。例如在TSP問題中，可以預先知道當前城市到下一個目的地的距離。第8頁,共36頁，2024年2月25日，星期天1.蟻群算法的提出1)標有距離的路徑圖2)在0時刻，路徑上沒有信息素累積，螞蟻選擇路徑為任意3)在1時刻，路徑上信息素堆積，短邊信息素多與長邊，所以螞蟻更傾向于選擇ABCDE第9頁,共36頁，2024年2月25日，星期天2.蟻群算法的特征

蟻群算法采用了分布式正反饋并行計算機制,易于與其他方法結合,并具有較強的魯棒性。（1）其原理是一種正反饋機制或稱增強型學習系統(tǒng)；它通過信息素的不斷更新達到最終收斂于最優(yōu)路徑上；（2）它是一種通用型隨機優(yōu)化方法；但人工螞蟻決不是對實際螞蟻的一種簡單模擬，它融進了人類的智能；（3）它是一種分布式的優(yōu)化方法；不僅適合目前的串行計算機，而且適合未來的并行計算機；（4）它是一種全局優(yōu)化的方法；不僅可用于求解單目標優(yōu)化問題，而且可用于求解多目標優(yōu)化問題；（5）它是一種啟發(fā)式算法；計算復雜性為O(NC*m*n2)，其中NC是迭代次數，m是螞蟻數目，n是目的節(jié)點數目。第10頁,共36頁，2024年2月25日，星期天2.蟻群算法的特征下面是對蟻群算法的進行過程中采用的規(guī)則進行的一些說明。范圍 螞蟻觀察到的范圍是一個方格世界，螞蟻有一個參數為速度半徑（一般是3），那么它能觀察到的范圍就是3*3個方格世界，并且能移動的距離也在這個范圍之內。環(huán)境 螞蟻所在的環(huán)境是一個虛擬的世界，其中有障礙物，有別的螞蟻，還有信息素，信息素有兩種，一種是找到食物的螞蟻灑下的食物信息素，一種是找到窩的螞蟻灑下的窩的信息素。每個螞蟻都僅僅能感知它范圍內的環(huán)境信息。環(huán)境以一定的速率讓信息素消失。覓食規(guī)則 在每只螞蟻能感知的范圍內尋找是否有食物，如果有就直接過去。否則看是否有信息素，并且比較在能感知的范圍內哪一點的信息素最多，這樣，它就朝信息素多的地方走，并且每只螞蟻都會以小概率犯錯誤，從而并不是往信息素最多的點移動。螞蟻找窩的規(guī)則和上面一樣，只不過它對窩的信息素做出反應，而對食物信息素沒反應。第11頁,共36頁，2024年2月25日，星期天2.蟻群算法的特征移動規(guī)則 每只螞蟻都朝向信息素最多的方向移，并且，當周圍沒有信息素指引的時候，螞蟻會按照自己原來運動的方向慣性的運動下去，并且，在運動的方向有一個隨機的小的擾動。為了防止螞蟻原地轉圈，它會記住剛才走過了哪些點，如果發(fā)現要走的下一點已經在之前走過了，它就會盡量避開。避障規(guī)則 如果螞蟻要移動的方向有障礙物擋住，它會隨機的選擇另一個方向，并且有信息素指引的話，它會按照覓食的規(guī)則行為。信息素規(guī)則 每只螞蟻在剛找到食物或者窩的時候撒發(fā)的信息素最多，并隨著它走遠的距離，播撒的信息素越來越少。 根據這幾條規(guī)則，螞蟻之間并沒有直接的關系，但是每只螞蟻都和環(huán)境發(fā)生交互，而通過信息素這個紐帶，實際上把各個螞蟻之間關聯(lián)起來了。比如，當一只螞蟻找到了食物，它并沒有直接告訴其它螞蟻這兒有食物，而是向環(huán)境播撒信息素，當其它的螞蟻經過它附近的時候，就會感覺到信息素的存在，進而根據信息素的指引找到了食物。第12頁,共36頁，2024年2月25日，星期天2.蟻群算法的特征基本蟻群算法流程圖（詳細）1.在初始狀態(tài)下，一群螞蟻外出，此時沒有信息素，那么各自會隨機的選擇一條路徑。

2.在下一個狀態(tài)，每只螞蟻到達了不同的點，從初始點到這些點之間留下了信息素，螞蟻繼續(xù)走，已經到達目標的螞蟻開始返回，與此同時，下一批螞蟻出動，它們都會按照各條路徑上信息素的多少選擇路線(selection)，更傾向于選擇信息素多的路徑走（當然也有隨機性）。

3.又到了再下一個狀態(tài)，剛剛沒有螞蟻經過的路線上的信息素不同程度的揮發(fā)掉了(evaporation)，而剛剛經過了螞蟻的路線信息素增強(reinforcement)。然后又出動一批螞蟻，重復第2個步驟。

每個狀態(tài)到下一個狀態(tài)的變化稱為一次迭代，在迭代多次過后，就會有某一條路徑上的信息素明顯多于其它路徑，這通常就是一條最優(yōu)路徑。第13頁,共36頁，2024年2月25日，星期天3.蟻群算法的數學模型一般蟻群算法的框架主要有三個組成部分：蟻群的活動；信息素的揮發(fā)；信息素的增強；主要體現在轉移概率公式和信息素更新公式。第14頁,共36頁，2024年2月25日，星期天3.蟻群算法的數學模型蟻群算法數學模型 在路徑搜索過程中，螞蟻會根據路徑上信息素的多少及距離啟發(fā)信息進行節(jié)點間的轉移。螞蟻ｋ在ｔ時刻由節(jié)點ｉ轉移到節(jié)點ｊ的狀態(tài)轉移概率如式所示：第15頁,共36頁，2024年2月25日，星期天3.蟻群算法的數學模型

另外，為了避免殘留信息素過多引起殘留信息淹沒啟發(fā)信息,在每只螞蟻走完一步或者完成對所有n個元素的遍歷后,要對殘留信息進行更新處理。由此,t+n時刻在路徑(i,j)上的信息量可按如下規(guī)則進行調整其更新規(guī)則如下式所示：

由于信息素更新策略的不同,以及城市規(guī)模取值在適當范圍時，全局搜索能使之得到更優(yōu)的解，因此采用全局信息素更新規(guī)則，形式如下：

式中，Q表示螞蟻循環(huán)一周，且在一定程度上影響算法收斂速度的信息素總量；Lk表示本次循環(huán)中，螞蟻k所走路段的長度。第16頁,共36頁，2024年2月25日，星期天3.蟻群算法的數學模型蟻群的規(guī)模和停止規(guī)則蟻群大小:

一般情況下蟻群中螞蟻的個數不超過TSP圖中節(jié)點的個數。終止條件:1給定一個外循環(huán)的最大數目，表明已經有足夠的螞蟻工作；

2當前最優(yōu)解連續(xù)K次相同而停止，其中K是一個給定的整數，表示算法已經收斂，不再需要繼續(xù)；

3目標值控制規(guī)則，給定優(yōu)化問題（目標最小化）的一個下界和一個誤差值，當算法得到的目標值同下界之差小于給定的誤差值時，算法終止。第17頁,共36頁，2024年2月25日，星期天4.蟻群算法的模型類型

根據信息素更新策略的不同,M.Dorigo曾提出3種不同的基本蟻群算法模型,其差別在于Δτkij(t)求法的不同,即:Ant-Cycle模型Ant-Quantity模型Ant-Density模型 其中Ant-antity模型和Ant-Density模型利用的是局部信息;而Ant-Cycle模型利用的是整體信息,在求解TSP時性能較好,因此通常采用Ant-Cycle模型作為蟻群算法的基本模型。第18頁,共36頁，2024年2月25日，星期天4.蟻群算法的模型類型Ant-Cycle模型式中，Q表示信息素強度，它在一定程度上影響算法的收斂速度；Lk表示第k只螞蟻在本次循環(huán)中所走路徑的總長度。第19頁,共36頁，2024年2月25日，星期天4.蟻群算法的模型類型Ant-Quantity模型

Ant-Density模型第20頁,共36頁，2024年2月25日，星期天4.蟻群算法的模型類型區(qū)別 后兩個式子中利用的是局部信息，即螞蟻完成一步后更新路徑上的信息素；而第一個式中利用的是全局信息，即螞蟻完成一個循環(huán)后更新所有路徑上的信息素，在求解TSP時性能較好，因此通常采用第一個模型作為蟻群算法的基本模型。第21頁,共36頁，2024年2月25日，星期天4.蟻群算法的模型類型下面是一些最常用的變異蟻群算法1.精英螞蟻系統(tǒng) 全局最優(yōu)解決方案在每個迭代以及其他所有的螞蟻的沉積信息素。2.最大最小螞蟻系統(tǒng)（MMAS） 添加的最大和最小的信息素量[τmax，τmin]，只有全局最佳或迭代最好的巡邏沉積的信息素。所有的邊緣都被初始化為τmax并且當接近停滯時重新初始化為τmax。3.蟻群系統(tǒng) 蟻群系統(tǒng)已被提出。4.基于排序的螞蟻系統(tǒng)（ASrank） 所有解決方案都根據其長度排名。然后為每個解決方案衡量信息素的沉積量，最短路徑相比較長路徑的解沉積了更多的信息素。5.連續(xù)正交蟻群（COAC）

COAC的信息素沉積機制能使螞蟻協(xié)作而有效地尋解。利用正交設計方法，在可行域的螞蟻可以使用增大的全局搜索能力和精度，快速、高效地探索他們選擇的區(qū)域。正交設計方法和自適應半徑調整方法也可推廣到其他優(yōu)化算法中，在解決實際問題施展更大的威力。第22頁,共36頁，2024年2月25日，星期天5.蟻群算法的優(yōu)缺點蟻群算法的優(yōu)點：蟻群算法與其他啟發(fā)式算法相比，在求解性能上，具有很強的魯棒性（對基本蟻群算法模型稍加修改，便可以應用于其他問題）和搜索較好解的能力。蟻群算法是一種基于種群的進化算法，具有本質并行性，易于并行實現。蟻群算法很容易與多種啟發(fā)式算法結合，以改善算法性能。第23頁,共36頁，2024年2月25日，星期天5.蟻群算法的優(yōu)缺點蟻群算法存在的問題：TSP問題是一類經典的組合優(yōu)化問題，即在給定城市個數和各城市之間距離的條件下，找到一條遍歷所有城市且每個城市只能訪問一次的總路程最短的路線。蟻群算法在TSP問題應用中取得了良好的效果，但是也存在一些不足：（1）如果參數設置不當，導致求解速度很慢且所得解的質量特別差。（2）基本蟻群算法計算量大，求解所需時間較長。（3）基本蟻群算法中理論上要求所有的螞蟻選擇同一路線，該線路即為所求的最優(yōu)線路；但在實際計算中，在給定一定循環(huán)數的條件下很難達到這種情況。 另一方面，在其它的實際應用中，如圖像處理中尋求最優(yōu)模板問題，我們并不要求所有的螞蟻都找到最優(yōu)模板，而只需要一只找到最優(yōu)模板即可。如果要求所有的螞蟻都找到最優(yōu)模板，反而影響了計算效率。 蟻群算法收斂速度慢、易陷入局部最優(yōu)。蟻群算法中初始信息素匱乏。

蟻群算法一般需要較長的搜索時間，其復雜度可以反映這一點；而且該方法容易出現停滯現象，即搜索進行到一定程度后，所有個體發(fā)現的解完全一致，不能對解空間進一步進行搜索，不利于發(fā)現更好的解。第24頁,共36頁，2024年2月25日，星期天6.蟻群算法所解決的問題調度問題車間作業(yè)調度問題（JSP）開放式車間調度問題（OSP）排列流水車間問題（PFSP）單機總延遲時間問題（SMTTP）單機總加權延遲問題（SMTWTP）資源受限項目調度問題（RCPSP）車間組調度問題（GSP）附帶依賴安裝時間順序的單機總延遲問題（SMTTPDST）附帶順序相依設置/轉換時間的多階段流水車間調度問題（MFSP）車輛路徑問題限量車輛路徑問題（CVRP）多站車輛路徑問題（MDVRP）周期車輛路徑問題（PVRP）分批配送車輛路徑問題（SDVRP）隨機車輛路徑問題（SVRP）裝貨配送的車輛路徑問題（VRPPD）帶有時間窗的車輛路徑問題（VRPTW）依賴時間的時間窗車輛路徑問題（TDVRPTW）帶時間窗和復合服務員工的車輛路徑問題（VRPTWMS）第25頁,共36頁，2024年2月25日，星期天6.蟻群算法所解決的問題分配問題二次分配問題（QAP）廣義分配問題（GAP）頻率分配問題（FAP）冗余分配問題（RAP）設置問題覆蓋設置問題（SCP）分區(qū)設置問題（SPP）約束重量的樹圖劃分問題（WCGTPP）加權弧L-基數樹問題（AWlCTP）多背包問題（MKP）最大獨立集問題（MIS）其他面向關系的網絡路由無連接網絡路由數據挖掘項目調度中的貼現現金流分布式信息檢索網格工作流調度問題圖像處理系統(tǒng)識別蛋白質折疊電子電路設計第26頁,共36頁，2024年2月25日，星期天6.蟻群算法所解決的問題

蟻群優(yōu)化算法已應用于許多組合優(yōu)化問題，包括蛋白質折疊或路由車輛的二次分配問題，很多派生的方法已經應用于實變量動力學問題，隨機問題，多目標并行的實現。它也被用于產生貨郎擔問題的擬最優(yōu)解。在圖表動態(tài)變化的情況下解決相似問題時，他們相比模擬退火和遺傳算法方法有優(yōu)勢；蟻群算法可以連續(xù)運行并適應實時變化。這在網絡路由和城市交通系統(tǒng)中是有利的。 第一蟻群優(yōu)化算法被稱為“螞蟻系統(tǒng)”，它旨在解決貨郎擔問題，其目標是要找到一系列城市的最短遍歷路線?？傮w算法相對簡單，它基于一組螞蟻，每只完成一次城市間的遍歷。在每個階段，螞蟻根據一些規(guī)則選擇從一個城市移動到另一個：它必須訪問每個城市一次;一個越遠的城市被選中的機會越少（能見度更低）;在兩個城市邊際的一邊形成的信息素越濃烈，這邊被選擇的概率越大;如果路程短的話，已經完成旅程的螞蟻會在所有走過的路徑上沉積更多信息素，每次迭代后，信息素軌跡揮發(fā)。第27頁,共36頁，2024年2月25日，星期天6.蟻群算法所解決的問題在實驗和應用中，蟻群算法有他的優(yōu)勢也有自己的劣勢，但若與其他方法相結合，也能對解決問題的可行性和有效性有一定的幫助。下面列出與蟻群算法相關的方法遺傳算法（GA）支持一系列的解決方案。解的合并或突變增加了解集，其中質量低劣的解被丟棄，尋找高級解決方案的過程模仿了這一演變。模擬退火（SA）是一個全局優(yōu)化相關??的通過產生當前解的相鄰解來遍歷搜索空間的技術。高級的相鄰解總是可接受的。低級的相鄰解可能會根據基于質量和溫度參數德差異的概率被接受。溫度參數隨著算法的進程被修改以改變搜索的性質。反作用搜索優(yōu)化的重點在于將機器學習與優(yōu)化的結合，加入內部反饋回路以根據問題、根據實例、根據當前解的附近情況的特點自動調整算法的自由參數。禁忌搜索（TS）類似于模擬退火，他們都是通過測試獨立解的突變來遍歷解空間的。而模擬退火算法對于一個獨立解只生成一個突變，禁忌搜索會產生許多變異解并且移動到產生的解中的符合度最低的一個。為了防止循環(huán)并且促進在解空間中的更大進展，由部分或完整的解組建維系了一個禁忌列表。移動到元素包含于禁忌列表的解是禁止，禁忌列表隨著解遍歷解空間的過程而不斷更新。人工免疫系統(tǒng)（AIS）算法仿照了脊椎動物的免疫系統(tǒng)。粒子群優(yōu)化（PSO），群智能方法引力搜索算法（GSA），群智能方法蟻群聚類方法（ACCM中），這個方法利用了聚類方法擴展了蟻群優(yōu)化。隨機傳播搜索（SDS），基于代理的概率全局搜索和優(yōu)化技術，最適合于將目標函數分解成多個獨立的分布函數的優(yōu)化問題。第28頁,共36頁，2024年2月25日，星期天7.蟻群算法的應用應用領域 蟻群算法能夠被用于解決大多數優(yōu)化問題或者能夠轉化為優(yōu)化求解的問題。 現在其應用領域已擴展到多目標優(yōu)化、數據分類、數據聚類、模式識別、電信QoS管理、生物系統(tǒng)建模、流程規(guī)劃、信號處理、機器人控制、決策支持以及仿真和系統(tǒng)辯識等方面，群智能理論和方法為解決這類應用問題提供了新的途徑。第29頁,共36頁，2024年2月25日，星期天7.蟻群算法的應用蟻群算法的模型改進及其應用 近年來,國內外學者在蟻群算法的模型改進和應用方面做了大量的工作,其共同目的是在合理時間復雜度的限制條件下,盡可能提高蟻群算法在一定空間復雜度下的尋優(yōu)能力,從而改善蟻群算法的全局收斂性,并拓寬蟻群算法的應用領域。(部分的蟻群算法改進模型及其應用情況--附Pr-1)第30頁,共36頁，2024年2月25日，星期天7.蟻群算法的應用蟻群優(yōu)化算法應用現狀 隨著群智能理論和應用算法研究的不斷發(fā)展，研究者已嘗試著將其用于各種工程優(yōu)化問題，并取得了意想不到的收獲。多種研究表明，群智能在離散求解空間和連續(xù)求解空間中均表現出良好的搜索效果，并在組合優(yōu)化問題中表現突出。蟻群優(yōu)化算法并不是旅行商問題的最佳解決方法，但是它卻為解決組合優(yōu)化問題提供了新思路，并很快被應用到其它組合優(yōu)化問題中。比較典型的應用研究包括：網絡路由優(yōu)化、數據挖掘以及一些經典的組合優(yōu)化問題。

第31頁,共36頁，2024年2月25日，星期天7.蟻群算法的應用

蟻群算法在電信路由優(yōu)化中已取得了一定的應用成果。HP公司和英國電信公司在90年代中后期都開展了這方面的研究，設計了蟻群路由算法（AntColonyRouting,ACR）。每只螞蟻就像蟻群優(yōu)化算法中一樣，根據它在網絡上的經驗與性能，動態(tài)更新路由表項。如果一只螞蟻因為經過了網絡中堵塞的路由而導致了比較大的延遲，那么就對該表項做較大的增強。同時根據信息素揮發(fā)機制實現系統(tǒng)的信息更新，從而拋棄過期的路由信息。這樣，在當前最優(yōu)路由出現擁堵現象時，ACR算法就能迅速的搜尋另一條可