蟻群算法及其應用講座ppt課件

1、蟻群算法及其運用啟發(fā)式算法_分類現代優(yōu)化算法：現代優(yōu)化算法： 80年代初興起年代初興起忌諱搜索忌諱搜索tabu search模擬退火模擬退火simulated annealing神經網絡神經網絡neural networks遺傳算法遺傳算法genetic algorithms螞蟻算法螞蟻算法Ant Algorithm，群體智能，群體智能，Swarm Intelligence遺傳算法 n遺傳算法(Genetic Algorithm, GA)是1962年親密根大學Holland教授初次提出的一種全局優(yōu)化算法，它借用了生物遺傳學的觀念，經過自然選擇、遺傳、變異等作用機制，實現各個體的順應性的提高，并

2、迅速推行到優(yōu)化、搜索、機器學習等方面。 遺傳算法的過程 編碼和初始群體生成編碼和初始群體生成個體順應度的評測個體順應度的評測(適值函數適值函數 )選擇選擇交叉交叉變異變異蟻群算法1 1 原理原理2 2 在在TSPTSP中的運用及改良中的運用及改良3 3 在在QoSQoS多播路由中的運用多播路由中的運用1 蟻群算法原理n20 20 世紀世紀90 90 年代初，意大利學者年代初，意大利學者Dorigo Dorigo 等等受螞蟻尋食行為的啟發(fā)，提出了蟻群算法，是受螞蟻尋食行為的啟發(fā)，提出了蟻群算法，是一種仿生算法。一種仿生算法。n螞蟻在尋食過程中可以找出巢穴到食物源的最螞蟻在尋食過程中可以找出巢穴到

3、食物源的最短途徑，為什么？短途徑，為什么？n1 1信息素信息素(pheromone)(pheromone)n2 2正反響景象：某一途徑上走過的正反響景象：某一途徑上走過的螞蟻越多，那么后來者選擇該途徑的概率就越螞蟻越多，那么后來者選擇該途徑的概率就越大。大。簡化的螞蟻尋食過程螞蟻從螞蟻從A A點出發(fā)，速度一樣，食物在點出發(fā)，速度一樣，食物在D D點，能夠隨機點，能夠隨機選擇道路選擇道路ABDABD或或ACDACD。假設初始時每條分配道路一只。假設初始時每條分配道路一只螞蟻，每個時間單位行走一步，本圖為經過螞蟻，每個時間單位行走一步，本圖為經過9 9個時個時間單位時的情形：走間單位時的情形：走A

4、BDABD的螞蟻到達終點，而走的螞蟻到達終點，而走ACDACD的螞蟻剛好走到的螞蟻剛好走到C C點，為一半路程。點，為一半路程。簡化的螞蟻尋食過程經過經過1818個時間單位時的情形：走個時間單位時的情形：走ABDABD的螞蟻到達的螞蟻到達終點后得到食物又前往了起點終點后得到食物又前往了起點A A，而走，而走ACDACD的螞蟻的螞蟻剛好走到剛好走到D D點。點。自然蟻群與人工蟻群類似之處在于：都是優(yōu)先選擇信息素濃度大的途徑。類似之處在于：都是優(yōu)先選擇信息素濃度大的途徑。兩者的區(qū)別：兩者的區(qū)別：1在于人工蟻群有一定的記憶才干，可以記憶在于人工蟻群有一定的記憶才干，可以記憶曾經訪問過的節(jié)點。曾經訪問

5、過的節(jié)點。2人工蟻群選擇途徑時不是盲目的。而是按一人工蟻群選擇途徑時不是盲目的。而是按一定規(guī)律有認識地尋覓最短途徑。例如，在定規(guī)律有認識地尋覓最短途徑。例如，在TSP問題中，可問題中，可以預先知道當前城市到下一個目的地的間隔。以預先知道當前城市到下一個目的地的間隔。運用一：TSP問題n游覽商問題游覽商問題TSP,traveling salesman TSP,traveling salesman problemproblem19601960年首先提出。年首先提出。n問題描畫：問題描畫：n一商人去一商人去n n個城市銷貨，一切城市走一個城市銷貨，一切城市走一遍再回到起點，使所走路程最短。遍再回到起

6、點，使所走路程最短。nTSPTSP在許多工程領域具有廣泛的運用價值在許多工程領域具有廣泛的運用價值n例如電路板布線、例如電路板布線、VLSIVLSI芯片設計、機芯片設計、機器人控制、交通路由等。器人控制、交通路由等。nTSPTSP的求解是的求解是NP-hardNP-hard問題。隨著城市數目的增問題。隨著城市數目的增多多, ,問題空間將呈指數級增長。問題空間將呈指數級增長。 TSP問題的數學描畫TSP問題表示為一個問題表示為一個N個城市的有向圖個城市的有向圖G=N，A，其中，其中城市之間間隔城市之間間隔目的函數為目的函數為其中，其中， ，為城市，為城市1,2，n的的一個陳列，一個陳列， 。,

7、|j), (iA n1,2,.,NNjinnijd)(nliilldwf11)(),(21niiiw11iin螞蟻算法求解TSPn下面以下面以TSPTSP為例闡明根本蟻群算法模型。為例闡明根本蟻群算法模型。n首先將首先將m m只螞蟻隨機放置在只螞蟻隨機放置在n n個城市，位個城市，位于城市于城市i i的第的第k k只螞蟻選擇下一個城市只螞蟻選擇下一個城市j j的的概率為概率為: : 螞蟻算法求解TSP其中：其中：表示邊表示邊i i，j j上的信息素濃度；上的信息素濃度； 是啟發(fā)信息，是啟發(fā)信息，d d是城市是城市i i和和j j之間的間隔；之間的間隔； 和和反映了信息素與啟發(fā)信息的相對重要性；

8、反映了信息素與啟發(fā)信息的相對重要性；表示螞蟻表示螞蟻k k曾經訪問過的城市列表。曾經訪問過的城市列表。 當一切螞蟻完成周游后，按以下公式進展信息素更新。當一切螞蟻完成周游后，按以下公式進展信息素更新。 ) 1 (,0,),(),(),(),(),(otherwisetabujifsisijijijiPktabuskk),(/1),(jidji),(jiktabu螞蟻算法求解TSPn其中：其中：為小于為小于1 1的常數，表示信息的耐久性。的常數，表示信息的耐久性。)2()()(1mkkijijijijijtnt) 3(0otherwiselijLQkkkijn其中：其中：Q Q為常數；為常數；l

9、klk表示第表示第k k只螞蟻在本次迭代只螞蟻在本次迭代中走過的途徑，中走過的途徑，LkLk為途徑長度。為途徑長度。 求解求解TSPTSP算法步驟算法步驟 初始化隨機放置螞蟻，為每只螞蟻建立忌諱表初始化隨機放置螞蟻，為每只螞蟻建立忌諱表tabuktabuk，將初始節(jié)，將初始節(jié)點置入忌諱表中點置入忌諱表中; ;迭代過程迭代過程k=1k=1while k=ItCount do (while k=ItCount do (執(zhí)行迭代執(zhí)行迭代) )for i = 1 to m do (for i = 1 to m do (對對m m只螞蟻循環(huán)只螞蟻循環(huán)) ) for j = 1 to n - 1 do (

10、 for j = 1 to n - 1 do (對對n n個城市循環(huán)個城市循環(huán)) ) 根據式根據式(1)(1)，采用輪盤賭方法在窗口外選擇下一個城市，采用輪盤賭方法在窗口外選擇下一個城市j;j; 將將j j置入忌諱表置入忌諱表, ,螞蟻轉移到螞蟻轉移到j;j; end for end for end for end for 計算每只螞蟻的途徑長度計算每只螞蟻的途徑長度; ; 根據式根據式(2)(2)更新一切螞蟻途徑上的信息量更新一切螞蟻途徑上的信息量; ; k = k + 1; k = k + 1;end whileend while輸出結果輸出結果, ,終了算法終了算法. .蟻群的規(guī)模和停頓

11、規(guī)那么一、蟻群大小一、蟻群大小 普通情況下蟻群中螞蟻的個數不超越普通情況下蟻群中螞蟻的個數不超越TSPTSP圖中節(jié)點的個圖中節(jié)點的個數。數。二、終止條件二、終止條件 1 1 給定一個外循環(huán)的最大數目；給定一個外循環(huán)的最大數目； 2 2 當前最優(yōu)解延續(xù)當前最優(yōu)解延續(xù)K K次一樣而停頓，其中次一樣而停頓，其中K K是一個給定是一個給定的整數，表示算法曾經收斂，不再需求繼續(xù)。的整數，表示算法曾經收斂，不再需求繼續(xù)。螞蟻算法的缺陷螞蟻算法的缺陷螞蟻算法的缺陷：螞蟻算法的缺陷：1 1收斂速度慢收斂速度慢2 2易于墮入部分最優(yōu)易于墮入部分最優(yōu)改良：改良：1 1采用部分優(yōu)化，設計了三種優(yōu)化算子。采用部分優(yōu)化

12、，設計了三種優(yōu)化算子。2 2采用蟻群優(yōu)化算法。采用蟻群優(yōu)化算法。3 3其它優(yōu)化算法其它優(yōu)化算法改良一：部分優(yōu)化算子改良一：部分優(yōu)化算子1 1 n對Kroa100，算子1優(yōu)化前后的途徑如下圖。優(yōu)化前28596，算子1優(yōu)化后26439 改良一：部分優(yōu)化算子改良一：部分優(yōu)化算子2 n對Kroa100，算子2優(yōu)化前后的途徑如下圖。算子126439，算子2優(yōu)化后23012 nTSPTSP具有鄰域特征，設置候選窗口，窗口大小應具有鄰域特征，設置候選窗口，窗口大小應取一個合理值。取一個合理值。n螞蟻總是優(yōu)先選擇候選窗口中的城市。搜索終螞蟻總是優(yōu)先選擇候選窗口中的城市。搜索終了后，根據候選窗口對途徑進展優(yōu)化，

13、假設將候了后，根據候選窗口對途徑進展優(yōu)化，假設將候選窗口內的節(jié)點交換到當前節(jié)點附近后間隔更短，選窗口內的節(jié)點交換到當前節(jié)點附近后間隔更短，那么進展變異。那么進展變異。 改良一：部分優(yōu)化算子改良一：部分優(yōu)化算子3 n對Kroa100，算子3優(yōu)化前后的途徑如下圖。23012，算子3優(yōu)化后21282 收斂特性對比 改良二：蟻群優(yōu)化算法n1)ACS采用了更為大膽的行為選擇規(guī)那么，在城市r的螞蟻k轉移到城市s的規(guī)那么為:2.1.4蟻群優(yōu)化算法第三，僅對全局最優(yōu)解邊上的信息素進展加強，更新如下第三，僅對全局最優(yōu)解邊上的信息素進展加強，更新如下: :其它改良1精英戰(zhàn)略2基于排序的螞蟻系統(tǒng)3 MAX-MIN螞

14、蟻系統(tǒng)運用二：QoS多播路由問題什么是多播路由？什么是多播路由？構造一棵費用最小的多播樹，且滿足構造一棵費用最小的多播樹，且滿足以下限制條件：以下限制條件：(1) d(T(s, D)D (1) d(T(s, D)D 延時延時(2) dj(T(s, D)DJ (2) dj(T(s, D)DJ 抖動抖動(3) pl(T(s, D)PL (3) pl(T(s, D)PL 丟包率丟包率(4) b(T(s, D)B. (4) b(T(s, D)B. 帶寬帶寬途徑的QoS參數計算(1)d(n)d(e)dd(p(s,)dp(s,n)dp(s,eiii(2)dj(n)dj(e)ddj(p(s,)dp(s,n)

15、d p(s,eiii(3)(1 (1)dpl(p(s,)p(s,dniinpl多播樹的QoS參數計算(4)|),(maxD)d(T(s,Dddspdii)5(|),(maxD)dj(T(s,Dddspdjii)6(|),(maxD)pl(T(s,Dddspplii)7(),(| )(minD)b(T(s,DsTeeb)8(c(n)c(e)D)c(T(s,D)(s,nD)(s,eTT算法n方法方法1 1：用蟻群算法找到去每一個目的節(jié)：用蟻群算法找到去每一個目的節(jié)點的點的QoSQoS最優(yōu)途徑，再交融。最優(yōu)途徑，再交融。n方法方法2 2：找到一條：找到一條QoSQoS最優(yōu)途徑，其它目最優(yōu)途徑，其它目的節(jié)點再依次參與多播樹中。的節(jié)點再依次參與多播樹中。12356478(18,3,100,9)(8,1,110,21)(4,1,130,10)(12,2,80,