《遼寧大學(xué)智能控制課件《蟻群優(yōu)化算法》》由會員分享，可在線閱讀，更多相關(guān)《遼寧大學(xué)智能控制課件《蟻群優(yōu)化算法》（60頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、第 五 部 分蟻群優(yōu)化算法Ant Colony Optimization 參考文獻(xiàn)n M. Dorigo and T. Stutzle, Ant Colony OptimizationM: MIT Press, 2004n段海濱，蟻群算法原理極其應(yīng)用M，2007.科學(xué)出版社 0 蟻群優(yōu)化算法的歷史沿革n意大利學(xué)者M(jìn)arco Dorigo（Alberto Colorni）于1991年在其博士論文中提出。n和Vittorio Maniezzo一同設(shè)計(jì)了第一個ACO算法螞蟻系統(tǒng)（Ant System）。n在真實(shí)螞蟻覓食行為的啟發(fā)下提出的一種高度創(chuàng)新性的啟發(fā)式算法。 Marco DorigoMacro

2、 Dorigo 重要文獻(xiàn)n Colorni等，1994，“Ant System for Job-shop Scheduling”n Colorni等，1996，“Heuristics From Natrure for Hard Combinatorial Optimization Problems”n Dorigo M等，1996，“Ant system: optimization by a colony of cooperating agents” Ant system: optimization by a colony of cooperating agentsn更加系統(tǒng)地闡述了蟻群算法的

3、基本原理和數(shù)學(xué)模型；n與遺傳算法、禁忌搜索算法、模擬退火算法、爬山法等進(jìn)行了仿真實(shí)驗(yàn)比較；n把單純地解決對稱TSP拓展到解決非對稱TSP、QAP和JSP； n對蟻群算法中的初始化參數(shù)對性能的影響做了初步探討；n蟻群算法發(fā)展史上的一篇奠基性文章。 近期發(fā)展n 2000年，Dorigo M和Bonabeau E等在Nature上發(fā)表蟻群算法的研究綜述，把這一領(lǐng)域的研究推向了國際學(xué)術(shù)的最前沿；n進(jìn)入21世紀(jì)的最近幾年里，Nature曾多次對蟻群算法的研究成果進(jìn)行報告。 相關(guān)書籍n 2004年9月，Marco Dorigo and Thomas SttzleAnt Colony Optimizatio

4、n；n系統(tǒng)介紹蟻群算法，為蟻群算法的傳播和科普做出了很重要一步；n 2007年翻譯成中文出版。 理論建設(shè)n在理論建設(shè)方面，ACO取得的成果比較少，也是最薄弱的一方面。n 1999年Gutjahr W J的技術(shù)報告和2000年的論文中首次對蟻群算法的收斂性進(jìn)行了證明。n將蟻群算法的行為簡化為在一幅代表所求問題的有向圖上的隨機(jī)行走過程，進(jìn)而從有向圖論的角度對一種改進(jìn)蟻群算法圖搜索螞蟻系統(tǒng)（Graph-Based Ant System，GBAS）的收斂性進(jìn)行了理論分析。 n采用的數(shù)學(xué)工具是Markov鏈，證明了在一些合理的假設(shè)條件下他所提出的GBAS能以一定概率收斂到所求問題的最優(yōu)解。 蟻群優(yōu)化算法

5、的發(fā)展n精華螞蟻系統(tǒng)（Elitist Strategy for Ant System，EAS）n對解構(gòu)造過程中表現(xiàn)優(yōu)異的人工螞蟻給予特殊的信息素釋放獎勵；n Ant-Q算法n將蟻群算法與Q學(xué)習(xí)算法結(jié)合，利用多個人工螞蟻的協(xié)同效應(yīng)；n后期 n蟻群系統(tǒng)（Ant Colony System，ACS），n基于排序的螞蟻系統(tǒng)（Rank Based version AS，ASrank），n最大最小螞蟻系統(tǒng)（Max-Min Ant System，MMAS） 蟻群優(yōu)化算法的應(yīng)用n路由類問題n旅行商、車輛路由、順序排列等n分配類問題n二次分配、圖著色、廣義分配、頻率分配、大學(xué)生課程時間表等n調(diào)度類問題 n工序車

6、間、開放車間、工作流車間、總延遲、總權(quán)重延遲、項(xiàng) 目調(diào)度、組車間等 蟻群優(yōu)化算法的應(yīng)用n子集類問題n多重背包、最大獨(dú)立集、冗余分配、集合覆蓋、帶權(quán)約束圖樹分割、邊帶權(quán)l(xiāng)-基樹、最大圖等n機(jī)器學(xué)習(xí)類問題n分配規(guī)則、貝葉斯網(wǎng)絡(luò)、模糊系統(tǒng)等n網(wǎng)絡(luò)路由類問題 n面向連接的網(wǎng)絡(luò)路由、無連接的網(wǎng)絡(luò)路由、光學(xué)網(wǎng)絡(luò)路由等 1 蟻群優(yōu)化算法的生物學(xué)基礎(chǔ)n阿根廷螞蟻n雙橋?qū)嶒?yàn) 實(shí)驗(yàn)結(jié)果（1） 摘自Ant Colony Optimization 實(shí)驗(yàn)結(jié)果（2） 摘自Ant Colony Optimization 實(shí)驗(yàn)結(jié)果（3） 摘自Ant Colony Optimization 障礙實(shí)驗(yàn) 摘自Ant System:

7、 Optimization by A Colony of Cooperating Agents 生物螞蟻的特點(diǎn)n沒有視覺n計(jì)算與記憶能力有限n依賴信息素(pheromone)通信、協(xié)作n釋放n揮發(fā)n正反饋 2 人工蟻群系統(tǒng)n人工螞蟻與生物螞蟻的區(qū)別n人工螞蟻具有一定的記憶能力n人工螞蟻具有一定的視力（啟發(fā)）n人工螞蟻生活在離散的時間環(huán)境中 人工蟻群模型 摘自Ant System: Optimization by A Colony of Cooperating Agents 人工蟻群n a) 初始狀態(tài)；n b) t=0，無信息素，人工螞蟻以等概率選擇左 轉(zhuǎn)或右轉(zhuǎn)；n c) t=1 ，較短的路徑上

8、信息素濃度較高，人工 螞蟻以較高的概率選擇信息素濃度高的路徑 實(shí)例：TSPn Graph (N,E)n Euclidean距離n螞蟻數(shù)量)(tbm Ni i 1 22 )()( jijiij yyxxd 實(shí)例：TSPn人工螞蟻的行為n路徑選擇的概率是城市距離和路徑上信息素濃度的函數(shù)；n符合TSP規(guī)則；n完成一次旅行后，在經(jīng)過的路徑上釋放信息素； n無需按原路返回。 實(shí)例：TSP（參數(shù)與機(jī)制）n路徑上的信息素濃度n信息素更新n信息素釋放(ant-cycle) ijijij tnt )()( )(tij otherwise n) t and t ime(between t tour itsin j

9、) (i, edge usesant th -k if0kkij LQ mk kijij 1 實(shí)例：TSP（參數(shù)與機(jī)制）n路徑選擇概率ijij d1 otherwisej if)()()( k0 allowedtttp kallowedl ilil ijijkij TSP蟻群算法(ant-cycle)n Step 1 Initialize:Set t:=0 t is the time counterSet NC:=0 NC is the cycles counterFor every edge (i,j) set an initial value for trailintensity andP

10、lace the m ants on the n nodes ctij )(0 ij TSP蟻群算法（ant-cycle）n Step 2 Set s:=1 s is the tabu list index For k:=1 to m do Place the starting town of the k-th ant in tabuk(s) TSP蟻群算法（ant-cycle）n Step 3 Repeat until tabu list is full this step will be repeated (n-1) timesSet s:=s+1For k:=1 to m do Choo

11、se the town j to move to, with probability at time t the k-th ant is on town i=tabu k(s-1) Move the k-th ant to the town j Insert town j in tabuk (s) )(tpkij TSP蟻群算法（ant-cycle）n Step 4.1 For k:=1 to m doMove the k-th ant from tabuk(n) to tabuk(1)Compute the length Lk of the tour described by the k-t

12、h antUpdate the shortest tour found TSP蟻群算法（ant-cycle）n Step 4.2For every edge (i,j) For k:=1 to m do mk kijij 1 otherwise by tabu describedtour j) (i, if k0kkij LQ TSP蟻群算法（ant-cycle）n Step 5 For every edge (i,j) compute according to equation Set t:=t+nSet NC:=NC+1For every edge (i,j) set )( ntij ij

13、ijij tnt )()( 0 :ij TSP蟻群算法（ant-cycle）n Step 6 If (NC NCMAX) and (not stagnation behavior)thenEmpty all tabu listsGoto step 2elsePrint shortest tourStop 3 蟻群算法調(diào)整與參數(shù)設(shè)置n ：信息素的相對重要性；n ：啟發(fā)性因素的相對重要性；n ：信息素殘留因子；n Q ：常數(shù)，控制信息素的釋放；n m ：蟻群規(guī)模；n其他： n蟻群的初始分布 信息素釋放算法ant-cyclen ant-cycle otherwise n) t and t ime(b

14、etween t tour itsin j) (i, edge usesant th -k if0kkij LQ 信息素釋放算法ant-densityn ant-density otherwise 1 t and t mebetween ti j toi from goesant th -k theifQ0kij 信息素釋放算法ant-quantityn ant-quantity otherwise 1 t and t mebetween ti j toi from goesant th -k theif0ijkij dQ 信息素釋放算法對比n測試集： Oliver30 problemn循環(huán)次

15、數(shù)：NCMAX=5000n測試次數(shù)：10 摘自Ant Colony Optimization GA：424.635 實(shí)驗(yàn)數(shù)據(jù)1 ant-cycle 摘自Ant Colony Optimization 實(shí)驗(yàn)數(shù)據(jù)2 ant-cycle 摘自Ant Colony Optimization 實(shí)驗(yàn)數(shù)據(jù)3 ant-cycle 摘自Ant Colony Optimization 參數(shù)：n ant-cyclen NCMAX=5000n ,50. 摘自Ant Colony Optimization 蟻群規(guī)模：mn ant-cyclen 4x4 grid 摘自Ant Colony Optimization 蟻群初

16、始分布n均勻分布優(yōu)于集中（單一城市）分布n隨機(jī)分布略好于均勻分布 算法復(fù)雜度n O(NC n2 m) n step 1 : O(n2+m), n step 2 : O(m), n step 3 : O(n2 m), n step 4 : O(n2 m), n step 5 : O(n2), n step 6 : O(n m). 實(shí)驗(yàn)數(shù)據(jù)（算法復(fù)雜度） 摘自Ant Colony Optimization 4 實(shí)例：JSPn Job-shop Scheduling Problemn M:機(jī)器數(shù)量n J :任務(wù)數(shù)n ojm:工序n djm:工時 n :工序集合 , jmoO JSP(Muth & T

17、hompson 6x6)m.t m.t m.t m.t m.t m.tJob1 3.1 1.3 2.6 4.7 6.3 5.6Job2 2.8 3.5 5.10 6.10 1.10 4.4Job3 3.5 4.4 6.8 1.9 2.1 5.7Job4 2.5 1.5 3.5 4.3 5.8 6.9Job5 3.9 2.3 5.5 6.4 1.3 4.1Job6 2.3 4.3 6.9 1.10 5.4 3.1 JSPn 3x2 problem JSPn路徑選擇 otherwisej if)()()( k0 allowedtttp kallowedl ilil ijijkij ijij T1

18、JSPn待訪問節(jié)點(diǎn)集合：n下一步允許訪問節(jié)點(diǎn)集合：n算法結(jié)束： 654321 ,kG 321 ,kS kG 5 實(shí)例：PID參數(shù)整定n整定參數(shù)n目標(biāo)函數(shù)idp TTK , dttetJ 0 )( PID參數(shù)整定n Kp=12.345n Td=6.7890n Ti =9.8765n (123456789098765)x(1234567890) PID參數(shù)整定n信息素釋放 otherwise ),(node passesant th -k theif),( 0 iikiik yxJQyx PID參數(shù)整定n路徑選擇概率 1010 jjji yytyx , otherwisej if),(),( ),

19、(),(),( k090 allowedtyxtyx tyxtyxtyxp lil li jijijik 6 蟻群優(yōu)化算法研究現(xiàn)狀n蟻群系統(tǒng)（Ant Colony System，ACS）n基于排序的螞蟻系統(tǒng)（Rank Based version AS，ASrank）n最大最小螞蟻系統(tǒng)（Max-Min Ant System，MMAS） 蟻群系統(tǒng)ACSn結(jié)合Q-learning；n ACS采用了更為大膽的行為選擇規(guī)則；n只增強(qiáng)屬于全局最優(yōu)解的路徑上的信息素；gbgbij gbijijij Lt ttnt 11 )( )()()()( 到當(dāng)前為止全局最優(yōu)的路徑長度 蟻群系統(tǒng)ACSn引入負(fù)反饋機(jī)制。每

20、當(dāng)螞蟻由一個節(jié)點(diǎn)移動到另一個節(jié)點(diǎn)時，該路徑上的信息素按照如下公式被相應(yīng)的消除一部分，從而實(shí)現(xiàn)一種信息素的局部調(diào)整，以減小已選擇過的路徑再次被選擇的概率。01 ijij )( 最大最小螞蟻系統(tǒng)MMASn修改了AS的信息素更新方式；n每次迭代之后只有一只螞蟻能夠進(jìn)行信息素的更新，以獲取更好的解；n為了避免搜索停滯，路徑上的信息素濃度被限制在MAX，MIN 范圍內(nèi)；n信息素的初始值被設(shè)為其取值上限，有助于增加算法初始階段的搜索能力。 基于排序的螞蟻系統(tǒng)ASrankn與“精英策略”相似；n算法中總是更新更好進(jìn)程上的信息素；n選擇的標(biāo)準(zhǔn)是其行程長度決定的排序；)()()()( tLtLtLtL m321 基于排序的螞蟻系統(tǒng)ASrankn每個螞蟻釋放信息素的強(qiáng)度通過排序加權(quán)處理確定。其中，為每次迭代后釋放信息素的螞蟻總數(shù)。gbgbij rrij gbijwr rijijij Lt Lt twtrwtt 1111 1 )()( )()()()()()(