蟻群算法的基本原理與改進.ppt

1、a,1,蟻群算法的基本原理與改進,a,2,蟻群算法,蟻群算法(ant colony alogrithm)是一種模擬進化算法。 蟻群算法（又稱為人工蟻群算法）是由意大利學者M.Dorigo，V.Mahiezzo，A.Colorni等人受到人們對自然界中真是蟻群集體行為的研究成果的啟發(fā)而首先提出來的。這個算法的主要目的是在圖中尋找優(yōu)化路徑的機率算法。 蟻群算法最早是為了解決TSP問題（即旅行商問題）。 TSP問題的要求：路徑的限制是每個城市只能拜訪一次；最后要回到原來出發(fā)的城市。求得的路徑路程為所有路徑之中的最小值。,a,3,概念原型 各個螞蟻在沒有事先告訴他們食物在什么地方的前提下開始尋找食物。

2、 當一只找到食物以后，它會向環(huán)境釋放一種揮發(fā)性分泌物pheromone (稱為信息素,該物質(zhì)隨著時間的推移會逐漸揮發(fā)消失，信息素濃度的大小表征路徑的遠近)來實現(xiàn)的，吸引其他的螞蟻過來，這樣越來越多的螞蟻會找到食物。 有些螞蟻并沒有象其它螞蟻一樣總重復同樣的路，他們會另辟蹊徑，如果另開辟的道路比原來的其他道路更短，那么，漸漸地，更多的螞蟻被吸引到這條較短的路上來。 最后，經(jīng)過一段時間運行，就可能會出現(xiàn)一條最短的路徑被大多數(shù)螞蟻重復著。,a,4,基本原理 蟻群算法是對自然界螞蟻的尋徑方式進行模似而得出的一種仿生算法。 螞蟻在運動過程中，能夠在它所經(jīng)過的路徑上留下一種稱之為外激素(pheromone

3、)的物質(zhì)進行信息傳遞，而且螞蟻在運動過程中能夠感知這種物質(zhì)，并以此指導自己的運動方向，因此由大量螞蟻組成的蟻群集體行為便表現(xiàn)出一種信息正反饋現(xiàn)象：某一路徑上走過的螞蟻越多，則后來者選擇該路徑的概率就越大。,a,5,假設以下條件： 每個時間單位有30只螞蟻（A-B） 每個時間單位有30只螞蟻（E-D） 螞蟻過后留下的外激素為1 初始時刻，路徑無信息存在且位于B和E可以隨機選擇路徑 HD = HB = 1 CD = CB = 0.5 圖中的數(shù)字表示距離,a,6,假設以下條件： 每個時間單位有30只螞蟻（A-B） 每個時間單位有30只螞蟻（E-D） 螞蟻過后留下的外激素為1 初始時刻，路徑無信息存在

4、且位于B和E可以隨機選擇路徑 HD = HB = 1 CD = CB = 0.5 備注： D-H D-C B-H B-C 圖中數(shù)字表示螞蟻的個數(shù),a,7,假設以下條件： 每個時間單位有30只螞蟻（A-B） 每個時間單位有30只螞蟻（E-D） 螞蟻過后留下的外激素為1 初始時刻，路徑無信息存在且位于B和E可以隨機選擇路徑 HD = HB = 1 CD = CB = 0.5 備注： D-H D-C B-H B-C 圖中數(shù)字表示螞蟻的個數(shù),a,8,下面以TSP為例說明基本蟻群算法模型。 首先將m只螞蟻隨機放置在n個城市，位于城市i的第k只螞蟻選擇下一個城市j的概率為:,a,9,螞蟻算法求解TSP,其

5、中： 表示邊（i，j）上的信息素濃度； 是啟發(fā)信息，d是城市i和j之間的距離； 和反映了信息素與啟發(fā)信息的相對重要性； 表示螞蟻k已經(jīng)訪問過的城市列表。 當所有螞蟻完成周游后，按以下公式進行信息素更新。,a,10,螞蟻算法求解TSP,其中：為小于1的常數(shù)，表示信息的持久性。,其中：Q為常數(shù)；lk表示第k只螞蟻在本次迭代中走過的路徑，Lk為路徑長度。,a,11,求解TSP算法步驟,初始化 隨機放置螞蟻，為每只螞蟻建立禁忌表tabuk，將初始節(jié)點置入禁忌表中; 迭代過程 k=1 while k=ItCount do (執(zhí)行迭代) for i = 1 to m do (對m只螞蟻循環(huán)) for j

6、= 1 to n - 1 do (對n個城市循環(huán)) 根據(jù)式(1)，采用輪盤賭方法在窗口外選擇下一個城市j; 將j置入禁忌表,螞蟻轉移到j; end for end for 計算每只螞蟻的路徑長度; 根據(jù)式(2)更新所有螞蟻路徑上的信息量; k = k + 1; end while 輸出結果,結束算法.,a,12,基本蟻群算法流程,1. 在初始狀態(tài)下，一群螞蟻外出，此時沒有信息素，那么各自會隨機的選擇一條路徑。 2. 在下一個狀態(tài)，每只螞蟻到達了不同的點，從初始點到這些點之間留下了信息素，螞蟻繼續(xù)走，已經(jīng)到達目標的螞蟻開始返回，與此同時，下一批螞蟻出動，它們都會按照各條路徑上信息素的多少選擇路線

7、(selection)，更傾向于選擇信息素多的路徑走（當然也有隨機性）。 3. 又到了再下一個狀態(tài)，剛剛沒有螞蟻經(jīng)過的路線上的信息素不同程度的揮發(fā)掉了(evaporation)，而剛剛經(jīng)過了螞蟻的路線信息素增強(reinforcement)。然后又出動一批螞蟻，重復第2個步驟。 每個狀態(tài)到下一個狀態(tài)的變化稱為一次迭代，在迭代多次過后，就會有某一條路徑上的信息素明顯多于其它路徑，這通常就是一條最優(yōu)路徑。,a,13,蟻群算法采用了分布式正反饋并行計算機制, 易于與其他方法結合, 并具有較強的魯棒性。 （1）其原理是一種正反饋機制或稱增強型學習系統(tǒng)；它通過信息素的不斷更新達到最終收斂于最優(yōu)路徑上；

8、（2）它是一種通用型隨機優(yōu)化方法；但人工螞蟻決不是對實際螞蟻的一種簡單模擬，它融進了人類的智能； （3）它是一種分布式的優(yōu)化方法；不僅適合目前的串行計算機，而且適合未來的并行計算機； （4）它是一種全局優(yōu)化的方法；不僅可用于求解單目標優(yōu)化問題，而且可用于求解多目標優(yōu)化問題； （5）它是一種啟發(fā)式算法；計算復雜性為 O(NC*m*n2)，其中NC 是迭代次數(shù)，m 是螞蟻數(shù)目，n 是目的節(jié)點數(shù)目。,a,14,下面是對蟻群算法的進行過程中采用的規(guī)則進行的一些說明。 范圍 螞蟻觀察到的范圍是一個方格世界，螞蟻有一個參數(shù)為速度半徑（一般是3），那么它能觀察到的范圍就是3*3個方格世界，并且能移動的距離也

9、在這個范圍之內(nèi)。 環(huán)境 螞蟻所在的環(huán)境是一個虛擬的世界，其中有障礙物，有別的螞蟻，還有信息素，信息素有兩種，一種是找到食物的螞蟻灑下的食物信息素，一種是找到窩的螞蟻灑下的窩的信息素。每個螞蟻都僅僅能感知它范圍內(nèi)的環(huán)境信息。環(huán)境以一定的速率讓信息素消失。 覓食規(guī)則 在每只螞蟻能感知的范圍內(nèi)尋找是否有食物，如果有就直接過去。否則看是否有信息素，并且比較在能感知的范圍內(nèi)哪一點的信息素最多，這樣，它就朝信息素多的地方走，并且每只螞蟻都會以小概率犯錯誤，從而并不是往信息素最多的點移動。螞蟻找窩的規(guī)則和上面一樣，只不過它對窩的信息素做出反應，而對食物信息素沒反應。,a,15,移動規(guī)則 每只螞蟻都朝向信息素

10、最多的方向移，并且，當周圍沒有信息素指引的時候，螞蟻會按照自己原來運動的方向慣性的運動下去，并且，在運動的方向有一個隨機的小的擾動。為了防止螞蟻原地轉圈，它會記住剛才走過了哪些點，如果發(fā)現(xiàn)要走的下一點已經(jīng)在之前走過了，它就會盡量避開。 避障規(guī)則 如果螞蟻要移動的方向有障礙物擋住，它會隨機的選擇另一個方向，并且有信息素指引的話，它會按照覓食的規(guī)則行為。 信息素規(guī)則 每只螞蟻在剛找到食物或者窩的時候撒發(fā)的信息素最多，并隨著它走遠的距離，播撒的信息素越來越少。 根據(jù)這幾條規(guī)則，螞蟻之間并沒有直接的關系，但是每只螞蟻都和環(huán)境發(fā)生交互，而通過信息素這個紐帶，實際上把各個螞蟻之間關聯(lián)起來了。比如，當一只螞

11、蟻找到了食物，它并沒有直接告訴其它螞蟻這兒有食物，而是向環(huán)境播撒信息素，當其它的螞蟻經(jīng)過它附近的時候，就會感覺到信息素的存在，進而根據(jù)信息素的指引找到了食物。,a,16,一般蟻群算法的框架主要有三個組成部分： 蟻群的活動； 信息素的揮發(fā)； 信息素的增強； 主要體現(xiàn)在轉移概率公式和信息素更新公式。,a,17,蟻群的規(guī)模和停止規(guī)則 蟻群大小: 一般情況下蟻群中螞蟻的個數(shù)不超過TSP圖中節(jié)點的個數(shù)。 終止條件: 1 給定一個外循環(huán)的最大數(shù)目，表明已經(jīng)有足夠的螞蟻工作； 2 當前最優(yōu)解連續(xù)K次相同而停止，其中K是一個給定的整數(shù)，表示算法已經(jīng)收斂，不再需要繼續(xù)； 3 目標值控制規(guī)則，給定優(yōu)化問題（目標最

12、小化）的一個下界和一個誤差值，當算法得到的目標值同下界之差小于給定的誤差值時，算法終止。,a,18,蟻群算法的優(yōu)點,蟻群算法與其他啟發(fā)式算法相比，在求解性能上，具有很強的魯棒性（對基本蟻群算法模型稍加修改，便可以應用于其他問題）和搜索較好解的能力。 蟻群算法是一種基于種群的進化算法，具有本質(zhì)并行性，易于并行實現(xiàn)。 蟻群算法很容易與多種啟發(fā)式算法結合，以改善算法性能。,a,19,蟻群算法存在的問題,TSP問題是一類經(jīng)典的組合優(yōu)化問題，即在給定城市個數(shù)和各城市之間距離的條件下，找到一條遍歷所有城市且每個城市只能訪問一次的總路程最短的路線。蟻群算法在TSP問題應用中取得了良好的效果，但是也存在一些不

13、足： （1）如果參數(shù)設置不當，導致求解速度很慢且所得解的質(zhì)量特別差。 （2）基本蟻群算法計算量大，求解所需時間較長。 （3）基本蟻群算法中理論上要求所有的螞蟻選擇同一路線，該線路即為所求的最優(yōu)線路；但在實際計算中，在給定一定循環(huán)數(shù)的條件下很難達到這種情況。 另一方面，在其它的實際應用中，如圖像處理中尋求最優(yōu)模板問題，我們并不要求所有的螞蟻都找到最優(yōu)模板，而只需要一只找到最優(yōu)模板即可。如果要求所有的螞蟻都找到最優(yōu)模板，反而影響了計算效率。 蟻群算法收斂速度慢、易陷入局部最優(yōu)。蟻群算法中初始信息素匱乏。 蟻群算法一般需要較長的搜索時間，其復雜度可以反映這一點；而且該方法容易出現(xiàn)停滯現(xiàn)象，即搜索進行到一定程度后，所有個體發(fā)現(xiàn)的解完全一致，不能對解空間進一步進行搜索，不利于發(fā)現(xiàn)更好的解。,a,20,算法改進,下面是一些最常用的變異蟻群算法 1.精英螞蟻系統(tǒng) 全局最優(yōu)解決方案在每個迭代以及其他所有的螞蟻的沉積信息素。 2.最大最小螞蟻系統(tǒng)（ MMAS） 添加的最大和最小的信息素量 max ， min ，只有全局最佳或迭代最好的巡邏沉積的信息素。所有的邊緣都被初始化為max并且當接近停滯時重新初始化為max。 3.蟻群系統(tǒng) 蟻群系統(tǒng)已被提出。,a,21,4.基于排序的螞蟻系統(tǒng)（ A