【正文】 智能優(yōu)化計算 2022/8/27 77 蟻群優(yōu)化算法 — 參考書 1 ? 智能蟻群算法及應用 吳啟迪 上?？萍汲霭嫔? 從基本結(jié)構(gòu)、算法特點、改進方法、突破途徑、實現(xiàn)模式及應用模式等方面進行了論述。 智能優(yōu)化計算 2022/8/27 73 應用 2/5 同時 ,分布式的計算方式則克服了傳統(tǒng)集中式算法可擴展性差的缺點 ,更適應現(xiàn)代頻繁變化的大型光網(wǎng)絡。 ( 1 ) ( ) ( )ij ij ijk k k? ? ?? ? ? ?智能優(yōu)化計算 2022/8/27 71 信息素的更改 6/6 蟻量算法（ antquantity algorithm）的信息素更新 為 ,Q為常量， 表示 i到 j的距離，這樣信息 濃度會隨城市距離的減小而加大。更新公式為 第 s+1只螞蟻根據(jù) 重新計算路由表。 二、終止條件 1 給定一個外循環(huán)的最大數(shù)目，表明已經(jīng)有足夠的螞蟻工作； 2 當前最優(yōu)解連續(xù) K次相同而停止，其中 K是一個給定的整數(shù)，表示算法已經(jīng)收斂，不再需要繼續(xù)； 3 目標值控制規(guī)則，給定優(yōu)化問題（目標最小化）的一個下界和一個誤差值，當算法得到的目標值同下界之差小于給定的誤差值時，算法終止。 ()0, 1 , 2 , .. .,ii L sic s m????( ( )) ( )f L t f w?( ( )) ( )f L t f w? : ( )W L t?ij?1 2 1( ) ( 0 , , , .. .. , , )kkL s i i i i ?? 11 jkijab????1ki ?智能優(yōu)化計算 2022/8/27 62 每一節(jié)點的記憶信息和系數(shù)的確定 需要記憶的信息 1/3 算法中需要記憶的信息有三部分。 ( 1, 2 , ..., )ia i n? ( 1, 2 , ..., )ic i n?? ?11m a x..0 , 1 , 1 , ....,niiiniiiicxs t a x bx j n???????? ?120 , , , ..., ni i i ? ?12, , .. ., ni i i? ?1, 2 , 3, ..., n智能優(yōu)化計算 2022/8/27 60 解的表達形式與算法的實現(xiàn) 3/4 算法的實現(xiàn) 建立有向圖 ，其中 A中共有 條弧。和 體現(xiàn)了相關(guān)信息痕跡和預見度對螞蟻決策的相對影響。 智能優(yōu)化計算 2022/8/27 43 蟻群優(yōu)化算法 — 算法模型和收斂性分析 馬氏過程的收斂定義 GBAS算法的收斂性分析 智能優(yōu)化計算 2022/8/27 44 馬氏過程的收斂定義 蟻群優(yōu)化算法的每步迭代對應隨機變量 其中 為信息素痕跡； 為 n城市的一個排列，最多有 個狀態(tài)。 0 1 24 1 6 1 241 6 0 1 24 1 24( 1 ) ( ( 1 ) )1 24 1 12 0 1 61 24 1 6 1 24 0ij????????????智能優(yōu)化計算 2022/8/27 39 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS） 10/12 重復外循環(huán)，由于上一次得到的 W2已經(jīng)是全局最優(yōu)解，因此按算法步驟 3的信息素更新規(guī)則，無論螞蟻如何行走，都只是對 W2路線上的城市信息素進行增強，其他的城市信息素進行揮發(fā)。 (1 ) ( )k ij k???智能優(yōu)化計算 2022/8/27 35 圖的蟻群系統(tǒng)（ GBAS） 6/12 可以驗證，下式滿足： 即 是一個隨機矩陣。 1 sm?? ()L s N? ()Ls()L s N?( ( ) ) ( ( ) )f L t f L W? ()W L t?( ) , : 1ij k k k? ??111( ) ( 1 ) ( 1 ) ( , )( ) ( 1 ) ( 1 ) ( , )kij k ijij k ijk k i j WWk k i j W?? ? ?? ? ??????? ? ? ???? ? ???為 上的一條弧不是 上的一條弧智能優(yōu)化計算 2022/8/27 33 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS） 4/12 在 STEP 3 中，揮發(fā)因子 對于一個固定的 ，滿足 并且 經(jīng)過 k次揮發(fā)，非最優(yōu)路徑的信息素逐漸減少至消失。當螞蟻在城市 i，若 完成第 s只螞蟻的計算。 信息素的更新方式有 2種，一是揮發(fā)，也就是所有路徑上的信息素以一定的比率進行減少，模擬自然蟻群的信息素隨時間揮發(fā)的過程；二是增強，給評價值“好” (有螞蟻走過 )的邊增加信息素。較短路徑的 信息素濃度高，所以能夠最終被所有螞蟻選擇，也就是最終的 優(yōu)化結(jié)果。再經(jīng)過 36個時間單位后，兩條線路上的信息素單位積累為 12和 4，比值為 3： 1。這樣形成一個正反饋。 智能優(yōu)化計算 2022/8/27 21 蟻群優(yōu)化算法概念 蟻群算法原理 簡化的螞蟻尋食過程 自然蟻群與人工蟻群算法 蟻群算法與 TSP問題 初始的蟻群優(yōu)化算法 —基于圖的蟻群系統(tǒng)（ GBAS） 一般蟻群算法的框架 智能優(yōu)化計算 2022/8/27 22 蟻群算法原理 蟻群算法是對自然界螞蟻的尋徑方式進行模似而得出的一種仿生算法。按照這樣的方法可實現(xiàn)對相似數(shù)據(jù)的聚類。 每只螞蟻就像蟻群優(yōu)化算法中一樣，根據(jù)它在網(wǎng)絡上的經(jīng)驗與性能，動態(tài)更新路由表項。在大型TSP問題中（最多包含 132座城市），基于 AS的算法都顯示出了優(yōu)于 GA和 SA的特性。其中， 0ρ1是信息素揮發(fā)參數(shù)， 是從尋路開始到當前為止全局最優(yōu)的路徑長度。 因此，其后的 ACO研究工作主要都集中于 AS性能的改進方面。無論是從理論研究還是應用研究的角度分析，群智能理論及其應用研究都是具有重要學術(shù)意義和現(xiàn)實價值的。 智能優(yōu)化計算 2022/8/27 6 蟻群優(yōu)化算法研究背景 1/3 群智能理論研究領(lǐng)域有兩種主要的算法：蟻群算法 (Ant Colony Optimization, ACO)和微粒群算法（ Particle Swarm Optimization, PSO）。 20世紀 90年代意大利學者 M． Dorigo， V． Maniezzo，A． Colorni等從生物進化的機制中受到啟發(fā)，通過模擬自然界螞蟻搜索路徑的行為，提出來一種新型的模擬進化算法 —— 蟻群算法，是群智能理論研究領(lǐng)域的一種主要算法。而且，這種方法只需目標函數(shù)的輸出值，而無需其梯度信息。 智能優(yōu)化計算 2022/8/27 10 2/7 最初提出的 AS有三種版本： Antdensity、 Antquantity和 Antcycle。該系統(tǒng)的提出是以 AntQ算法為基礎(chǔ)的。 智能優(yōu)化計算 2022/8/27 14 6/7 另一種對 AS改進的算法是 Rankbased Version AS。比較典型的應用研究包括：網(wǎng)絡路由優(yōu)化、數(shù)據(jù)挖掘以及一些經(jīng)典的組合優(yōu)化問題。 智能優(yōu)化計算 2022/8/27 18 蟻群優(yōu)化算法應用現(xiàn)狀 3/5 基于群智能的聚類算法起源于對蟻群蟻卵的分類研究。利用 ACO實現(xiàn)對生產(chǎn)流程和特料管理的綜合優(yōu)化，并通過與遺傳、模擬退火和禁忌搜索算法的比較證明了 ACO的工程應用價值。當它們碰到一個還沒有走過的路口時．就隨機地挑選一條路徑前行。 智能優(yōu)化計算 2022/8/27 24 簡化的螞蟻尋食過程 2/3 本圖為從開始算起，經(jīng)過 18個時間單位時的情形：走 ABD的螞蟻到達終點后得到食物又返回了起點 A，而走 ACD的螞蟻剛好走到 D點。 智能優(yōu)化計算 2022/8/27 26 自然蟻群與人工蟻群算法 基于以上蟻群尋找食物時的最優(yōu)路徑選擇問題，可以構(gòu)造 人工蟻群，來解決最優(yōu)化問題，如 TSP問題。 }, |j), { ( iA n}{ 1 , 2 , . . . ,N Nji ???nnijd ?)(?? ??nlii lldwf1 1)(),( 21 niiiw ??11 iin ??智能優(yōu)化計算 2022/8/27 28 蟻群算法與 TSP問題 2/3 TSP問題的人工蟻群算法中，假設(shè) m只螞蟻在圖的相鄰節(jié)點間移動，從而協(xié)作異步地得到問題的解。 }, |j), { ( iA n}{ 1 , 2 , . . . ,N Nji ???nnijd ?)(),( ji ||1)0( Aij ??0i),2,1( nw ?? 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS） 2/12 STEP 1 （外循環(huán)）如果滿足算法的停止規(guī)則，則停止計算并輸出計算得到的最好解。 若 ，則 。也就是說，增強過程體現(xiàn)在觀察蟻群（ m只螞蟻） 中每只螞蟻所找到的路徑，并選擇其中最優(yōu)路徑上的弧進行信息素的增強， 揮發(fā)過程是所有弧都進行的，不于螞蟻數(shù)量相關(guān)。3 : , ( 3 ) 8 。 第 K次循環(huán)前的信息素和最優(yōu)解為 ，經(jīng)過 第 K次外循環(huán)后，得到 。 （9）m in( ) , 1l n( 1 )l im 0kkkckkkc???????令：其中 ，則定理5. 2. 1的 結(jié)論也成立。 TSP問題尋找的是最短回路，而一般優(yōu)化問題中， STEP 3 中的判斷條件 需要根據(jù)實際問題進行修改。 ( , )G V A? ? ?0 , 1 , 2 , .. .. , , {( , ) | , }V n A i j i j V? ? ? ?( 1)nn? 1 ( 1 )ij nn? ??12( ) ( 0 , , , ...., )kL s i i i