第5章 蟻群算法

5蟻群算法

AntColonyOptimization23

目錄1、蟻群算法起源2、蟻群算法模型3、實例仿真4、蟻群算法特點5、總結雙橋實驗蟻群優(yōu)化（antcolonyoptimization,ACO）是20世紀90年代初由意大利學者M.Dorigo等通過模擬螞蟻的行為而提出的一種隨機優(yōu)化技術（尋找優(yōu)化路徑的機率型算法）。研究主要是以螞蟻尋找食物之后能選擇一條最短路徑來連接蟻穴和食物源。1991年，M.Dorigo在法國巴黎第一屆歐洲人工生命會議上最早提出了蟻群算法的基本模型，1992年又在其博士論文中進一步闡述了蟻群算法的核心思想。MacroDorigo1.蟻群算法起源螞蟻覓食過程在蟻群尋找食物時，能夠在它所經過的路徑上留下一種稱之為信息素(pheromone)的物質進行信息傳遞，而且螞蟻在運動過程中能夠感知這種物質，并以此指導自己的運動方向，因此由大量螞蟻組成的蟻群集體行為便表現出一種信息正反饋現象：某一路徑上走過的螞蟻越多，則后來者選擇該路徑的概率就越大。最優(yōu)路徑上的信息素濃度越來越大，而其它的路徑上激素濃度卻會隨著時間的流逝而消減。最終整個蟻群會找出最優(yōu)路徑。A點為蟻穴，食物在D點，可能隨機選擇路線ABD或ACD。假設初始時每條路線有一只螞蟻，每個時間單位行走一步，本圖為經過9個時間單位時的情形：走ABD的螞蟻到達食物，而走ACD的螞蟻剛好走到C點，為一半路程。簡化的螞蟻尋食過程本圖為從開始算起，經過18個時間單位時的情形：走ABD的螞蟻到達D點后得到食物又返回了起點A，而走ACD的螞蟻剛好走到D點。假設螞蟻每經過一處所留下的信息素為一個單位，則經過36個時間單位后，ABD的路線往返了2趟，每一處的信息素為4個單位，而ACD的路線往返了一趟，每一處的信息素為2個單位，其比值為2：1。按信息素的指導，ABD路線增加一只螞蟻（共2只），ACD路線仍為一只螞蟻。再經過36個時間單位后，兩條線路上的信息素為12和4，比值為3：1。于是，ABD路線增加一只螞蟻（共3只），ACD路線仍為一只螞蟻。再經過36個時間單位后，兩條線路上的信息素為24和6，比值為4：1。若繼續(xù)進行，則按信息素的指導，最終所有的螞蟻會放棄ACD路線，而都選擇ABD路線。蟻群算法通常用于求解復雜的組合優(yōu)化問題。所謂組合優(yōu)化,是指在離散的、有限的數學結構上,尋找一個滿足給定條件,并使其目標函數值達到最大或最小的解.理論假設1、蟻群之間通過信息素和環(huán)境進行通信。2、螞蟻對環(huán)境的反應由其內部模式決定。3、個體水平上，每個螞蟻相對獨立；群體水平上，每只螞蟻的行為是隨機的。2.蟻群算法模型算法規(guī)則121.范圍螞蟻觀察到的范圍是一個方格世界，螞蟻有一個參數為速度半徑（一般是3），那么它能觀察到的范圍就是3*3個方格世界，并且能移動的距離也在這個范圍之內。132.環(huán)境螞蟻所在的環(huán)境是一個虛擬的世界，其中有障礙物，有別的螞蟻，還有信息素，信息素有兩種，一種是找到食物的螞蟻灑下的食物信息素，一種是找到窩的螞蟻灑下的窩的信息素。每個螞蟻都僅僅能感知它范圍內環(huán)境信息。環(huán)境以一定的速率讓信息素消失。143.覓食規(guī)則在每只螞蟻能感知的范圍內尋找是否有食物，如果有就直接過去。否則看是否有信息素，并且比較在能感知的范圍內哪一點的信息素最多，這樣，它就朝信息素多的地方走，并且每只螞蟻都會以小概率犯錯誤，從而并不是往信息素最多的點移動。螞蟻找窩的規(guī)則和上面一樣，只不過它對窩的信息素做出反應，而對食物信息素沒反應。154.移動規(guī)則每只螞蟻都朝向信息素最多的方向移，并且，當周圍沒有信息素指引的時候，螞蟻會按照自己原來運動的方向慣性的運動下去，并且，在運動的方向有一個隨機的小的擾動。為了防止螞蟻原地轉圈，它會記住最近剛走過了哪些點，如果發(fā)現要走的下一點已經在最近走過了，它就會盡量避開。165.避障規(guī)則如果螞蟻要移動的方向有障礙物擋住，它會隨機的選擇另一個方向，并且有信息素指引的話，它會按照覓食的規(guī)則行為。176.播撒信息素規(guī)則每只螞蟻在剛找到食物或者窩的時候撒發(fā)的信息素最多，并隨著它走遠的距離，播撒的信息素越來越少。現以平面上n個城市的旅行商問題（TravelingSalesmanProblem，TSP）為例說明基本蟻群算法模型。旅行商問題：一商人去n個城市銷貨，所有城市走一遍再回到起點，使所走路程最短。TSP在許多工程領域具有廣泛的應用價值，例如電路板布線、VLSI芯片設計、機器人控制、網絡路由等。隨著城市數目的增多,問題空間將呈指數級增長。TSP問題的數學描述TSP問題表示為一個N個城市的有向圖G=（N，A），其中 城市之間距離目標函數為其中，，為城市1,2，…n的一個排列，。蟻群算法求解TSP下面以TSP為例說明基本蟻群算法模型。首先將m只螞蟻隨機放置在n個城市，通常

：，m只螞蟻同時由一個城市運動到下一個城市，逐步完成它們的搜索過程。整個算法的迭代過程以N為刻度，，為預設的最大迭代次數。每次迭代過程中以t為刻度，，螞蟻k根據概率轉換規(guī)則選擇下一個城市，由此生成一個由n個城市組成的行動路線，并伴隨信息素的更新。（2）能見度

定義為距離的倒數，即

代表由城市i到城市j的啟發(fā)性愿望，距離越短，能見度越大，被選擇的愿望越大，由此引導螞蟻搜索。其信息是固定的。

（3）虛擬信息素

當由城市i選擇城市j后，將在ij路徑上留下虛擬信息素，代表由城市i到j的獲知性愿望，是動態(tài)的全局信息，在線實時更新。

螞蟻k由城市i轉到城市j的決定因素：（1）禁忌列表

該表用于存儲第k只螞蟻在當前時刻已訪問過的所有城市，每只螞蟻在選擇下一個城市前，先檢索該表來確定下一步可能選擇的城市是否已經走過，如果走過就不在選擇范圍內，這樣可以避免重復訪問同一個城市。信息素更新方式體現在信息素的增加和信息素的揮發(fā)兩個方面。揮發(fā)系數信息素更新公式如下：表示當m個螞蟻都選擇了下一個城市后，所有選擇由i到j的螞蟻在該路徑上遺留的信息素之和表示第k只螞蟻在路徑ij上留下的信息素為預設參數，表示信息素的強度表示第k只螞蟻在t時刻選擇城市j后經過的所有城市構成的路徑長度其中： 表示ij路徑上的信息素濃度； 是啟發(fā)信息，能見度；

α和β反映了信息素與啟發(fā)信息的相對重要性； 表示螞蟻k已經訪問過的城市列表，禁忌列表。（4）概率轉換規(guī)則位于城市i的第k只螞蟻選擇下一個城市j的概率為:注意：處在同一城市i的兩只螞蟻，即使都按照上述概率選擇下一個城市，結果也可能是不同的。系統(tǒng)在上述四個因素（禁忌列表、能見度、虛擬信息素、概率轉換規(guī)則）的控制下，實現路徑選擇策略和信息素更新策略。上述信息素更新方式與真實螞蟻覓食過程最為接近，但是在解決TSP問題上，效果并不是特別理想。Dorigo針對信息素更新策略又給出了三種模型。蟻量系統(tǒng)（Ant-Quantity）蟻密系統(tǒng)（Ant-Density）蟻周系統(tǒng)（Ant-Cycle）三種模型它們的差別在于表達式

的不同(即更新信息素的方式和更新量不同)。Ant-Quantity和Ant-Density模型都是利用局部信息，即m個螞蟻都各自選完下一城市后，就對所走路徑并行進行信息素更新，兩者的區(qū)別僅僅在于更新的信息素量有所不同。Ant-Cycle模型是所有螞蟻選擇完所有城市完成一次迭代后，更新所有路徑上的信息素，并且每只螞蟻經過的路徑所更新的信息素是相同的。

蟻量算法（Ant-Quantity）：蟻密算法（Ant-Density）：蟻周算法（Ant-Cycle）：27通過實驗表明，在這三種算法中：Ant-Cycle算法的效果最好，這是因為它用的是全局信息；而其余兩種算法用的是局部信息。這種更新方法很好地保證了殘留信息不至于無限累積，非最優(yōu)路徑會逐漸隨時間推移被忘記。TSP算法流程圖（Ant-Cycle）k是否等于mt是否等于nN是否等于Nmax根據公式更新信息素記錄當前最優(yōu)路徑T+和最優(yōu)路徑長度L+禁忌表清零輸出最優(yōu)路徑T+和最優(yōu)路徑長度L+結束設置參數各個參數，并計算各個城市之間的距離，生成距離矩陣D，生成禁忌列表及存儲最優(yōu)路徑和最優(yōu)路徑長度的矩陣T+和L+開始將m個螞蟻隨機分布到n個城市，并將螞蟻所在的位置存儲到禁忌表中，并令N=0令t=0,N=N+1令k=0,t=t+1令k=k+1第k個螞蟻根據公式選擇下一個城市，并更新禁忌表NNNYYY蟻群算法的誤區(qū)與對策29誤區(qū)一：利用最大概率確定被選城市。

s40.31s20.49s10.14S30.06輪盤賭法（賭輪選擇法）①在［0,1］區(qū)間內產生一個均勻分布的隨機數r。②若r≤q1,則城市x1被選中。③若qk-1<r≤qk(2≤k≤N),則城市xk被選中。其中的qi稱為城市xi(i=1,2,…,n)的積累概率,其計算公式為對策一31誤區(qū)二：

Q值的影響不大32對策二33誤區(qū)三：參數組合選擇34對策三3.實例仿真采用靳潘教授所提出的31個城市的CTSP（求一條從北京出發(fā)經過中國31個省會城市及直轄市最后又回到北京的最短回路。36下圖對應31個城市的巡回路線為：北京-福州-南昌-合肥-杭州-南京-西安-臺北-太原-呼和浩特-沈陽-上海-石家莊-長春-哈爾濱-濟南-天津-武漢-鄭州-長沙-銀川-蘭州-廣州-?？?南寧-西寧-成都-烏魯木齊-昆明-拉薩-貴陽-北京。從仿真結果看最優(yōu)解為:15708km。目前，公認的TSP問題最優(yōu)結果為15398km，雖然，不完全相等，但是結果比較相近，這說明螞蟻算法雖然不是TSP問題的最好算法，但是依據螞蟻覓食過程提出的蟻群算法具有一定的可行性。一、蟻群大小一般情況下蟻群中螞蟻的個數不超過TSP圖中節(jié)點的個數。二、終止條件

1給定一個外循環(huán)的最大數目；

2當前最優(yōu)解連續(xù)K次相同而停止，其中K是一個給定的整數，表示算法已經收斂，不再需要繼續(xù)。蟻群的規(guī)模及停止規(guī)則優(yōu)化問題螞蟻覓食問題各個狀態(tài)要遍歷的各個路徑解螞蟻經過的一條完整路徑最優(yōu)解最短路徑各狀態(tài)的吸引度信息素的濃度狀態(tài)更新信息素更新目標函數路徑長度螞蟻覓食行為與優(yōu)化問題的對照關系

①其原理是一種正反饋機制或稱增強型學習系統(tǒng);它通過【最優(yōu)路徑上螞蟻數量的增加→信息素強度增加→后來螞蟻選擇概率增大→最優(yōu)路徑上螞蟻數量更大增加】達到最終收斂于最優(yōu)路徑上。

②它是一種通用型隨機優(yōu)化方法,它吸收了螞蟻的行為特點,它是使用人工螞蟻仿真來求解問題。但人工螞蟻決不是對實際螞蟻的一種簡單模擬,它融進了人類的智能。具有一定的記憶能力，能夠記憶已經訪問過的節(jié)點。選擇路徑時不是盲目的。而是按一定規(guī)律有意識地尋找最短路徑。例如，在TSP問題中，可以預先知道當前城市到下一個目的地的距離。

4.蟻群算法的特點⑤它是一種啟發(fā)式算法,計算復雜性為,其中Nc是迭代次數,m是螞蟻數目,n是目的節(jié)點數目。③它是一種本質上的并行算法。

④它是一種全局優(yōu)化的方法,不僅可用于求解單目標優(yōu)化問題,而且可用于求解多目標優(yōu)化問題。

蟻群算法還不像其它的啟發(fā)式算法那樣已形成系統(tǒng)的分析方法和具有堅實的數