【正文】 1次循環(huán)后的的信息素的痕跡值。由于 RWA 問題是 NPC 問題 ,文獻中大多將 RWA 問題拆分成路由和波長分配兩個子問題分別加以解決。 智能優(yōu)化計算 2022/8/27 78 蟻群優(yōu)化算法 — 參考書 2 ? 蟻群算法及其應(yīng)用 李士勇 哈工大出版社 國內(nèi)首部蟻群算法的專著，系統(tǒng)地闡述蟻群算法的基本原理、基本蟻群算法及改進算法，蟻群算法與遺傳、免疫算法的融合，自適應(yīng)蟻群算法，并行蟻群算法，蟻群算法的收斂性與理論模型及其在優(yōu)化問題中的應(yīng)用。 以上三種算法中，蟻環(huán)算法效果最好，因為他用的是全局信息，而其余兩種算法用的是局部信息。離線方式（同步更新方式）的主要思想是在若干只螞蟻完成 n個城市的訪問后，統(tǒng)一對殘留信息進行更新處理。 設(shè)第 s只螞蟻第 k步所走的路線為 ， 表示螞蟻從 0點出發(fā)，順序到達 。 的變化僅由 決定，而與先前的狀態(tài)無關(guān)，這是一個典型的馬爾可夫過程。此時，觀察 GBAS的計算過程。 0i)(sL)(sL ms ??11 sm??( ) { | ( , ) , ( ) }L s N l i l A l L s? ? ? ? ?或0( ) { | ( , ) , ( ) } { }L s N T l i l A l L s i? ? ? ? ? ? ?且( 1 ) ,( 1 )ijijijlTkp j Tk????????0,ijp j T??( ) ( ) { } , :L s L s j i j?? 0( ) { | ( , ) , ( ) } { }L s N T l i l A l L s i? ? ? ? ? ? ?且0 0 0, ( ) ( ) { } , : 。同時，人工蟻群再選擇下一條路徑的時候是 按一定算法規(guī)律有意識地尋找最短路徑，而不是盲目的。最終整個蟻群會找出最優(yōu)路徑。 經(jīng)過多年的發(fā)展， ACO已成為能夠有效解決實際二次規(guī)劃問題的幾種重要算法之一。 智能優(yōu)化計算 2022/8/27 16 蟻群優(yōu)化算法應(yīng)用現(xiàn)狀 1/5 隨著群智能理論和應(yīng)用算法研究的不斷發(fā)展，研究者已嘗試著將其用于各種工程優(yōu)化問題，并取得了意想不到的收獲。這種改進型算法能夠以更快的速度獲得更好的解。微粒群算法也是起源于對簡單社會系統(tǒng)的模擬，最初是模擬鳥群覓食的過程，但后來發(fā)現(xiàn)它是一種很好的優(yōu)化工具。 智能優(yōu)化計算 2022/8/27 7 蟻群優(yōu)化算法研究背景 2/3 與大多數(shù)基于梯度的應(yīng)用優(yōu)化算法不同，群智能依靠的是 概率搜索算法。但是若選擇的精英過多則算法會由于較早的收斂于局部次優(yōu)解而導(dǎo)致搜索的過早停滯。多種研究表明，群智能在離散求解空間和連續(xù)求解空間中均表現(xiàn)出良好的搜索效果，并在組合優(yōu)化問題中表現(xiàn)突出。 AS在作業(yè)流程計劃（ Jobshop Scheduling）問題中的應(yīng)用實例已經(jīng)出現(xiàn)，這說明了 AS在此領(lǐng)域的應(yīng)用潛力。 智能優(yōu)化計算 2022/8/27 23 簡化的螞蟻尋食過程 1/3 螞蟻從 A點出發(fā)，速度相同，食物在 D點，可能隨機選擇路線 ABD或 ACD。例如 在 TSP問題中，可以預(yù)先知道當(dāng)前城市到下一個目的地的距離。i L s L s i i i??智能優(yōu)化計算 2022/8/27 32 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS） 3/12 STRP 3 對 ，若 ，按 中城市的順序計算 路徑長度；若 ，路徑長度置為一個無窮大值（即不可 達）。 矩陣 共有 12條弧，初始信息素記憶矩陣為： 1 , 1 , 2 , 32k k? ??0 1 12 1 12 1 121 12 0 1 12 1 12( 0) ( ( 0))1 12 1 12 0 1 121 12 1 12 1 12 0ij????????????智能優(yōu)化計算 2022/8/27 37 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS） 8/12 執(zhí)行 GBAS算法的步驟 2，假設(shè)螞蟻的行走路線分別為： 當(dāng)前最優(yōu)解為，這個解是截止到當(dāng)前的最優(yōu)解，碰巧是實際 最優(yōu)解 1 : , ( 1 ) 4 。 定義 ：若一個馬爾可夫過程 ，對任意給定的 滿足 則稱馬爾可夫過程 依概率 1收斂到 。第 步按 TSP算法 的轉(zhuǎn)移概率公式行走選擇 。 信息素的在線更新（異步更新方式）即螞蟻每行走一步，立即回溯并且更新行走路徑上的信息素。蟻環(huán)離線更新方法很好地保證了殘留信息不至于無限積累，非最優(yōu)路徑會逐漸隨時間推移被忘記。 智能優(yōu)化計算 2022/8/27 79 蟻群優(yōu)化算法 — 參考文獻 ? 題目：群智能理論及應(yīng)用 ? 電子學(xué)報 , 2022年 S1期 【 作者 】 彭喜元 彭宇 戴毓豐 ? 【 關(guān)鍵詞 】 群智能 微粒群算法 蟻群算法 優(yōu)化算法 。研究 RWA 問題的目的是盡可能減少所需要的波長數(shù)和降低光路連接請求的阻塞率。 蟻群離線更新方式是在蟻群中的 m只螞蟻全部完成 n城市的訪問（第 k1次蟻群循環(huán)）后，統(tǒng)一對殘留信息進行更新處理。 ( , )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?12, , ...., ki i i 1k?1ki?11 jkijab????1 2 1( ) ( 0 , , , .. .. , , )kkL s i i i i ??智能優(yōu)化計算 2022/8/27 61 解的表達形式與算法的實現(xiàn) 4/4 算法的實現(xiàn) 對蟻群重復(fù)以上過程，比較 m只螞蟻的裝包值 并記憶具有最大裝包值的螞蟻為 t。 （9）m in( ) , 1l n( 1 )l im 0kkkckkkc???????令：其中 ，則定理5. 2. 1的 結(jié)論也成立。3 : , ( 3 ) 8 。 若 ，則 。 }, |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é)作異步地得到問題的解。 智能優(yōu)化計算 2022/8/27 24 簡化的螞蟻尋食過程 2/3 本圖為從開始算起，經(jīng)過 18個時間單位時的情形：走 ABD的螞蟻到達終點后得到食物又返回了起點 A，而走 ACD的螞蟻剛好走到 D點。利用 ACO實現(xiàn)對生產(chǎn)流程和特料管理的綜合優(yōu)化，并通過與遺傳、模擬退火和禁忌搜索算法的比較證明了 ACO的工程應(yīng)用價值。比較典型的應(yīng)用研究包括：網(wǎng)絡(luò)路由優(yōu)化、數(shù)據(jù)挖掘以及一些經(jīng)典的組合優(yōu)化問題。該系統(tǒng)的提出是以 AntQ算法為基礎(chǔ)的。而且，這種方法只需目標(biāo)函數(shù)的輸出值，而無需其梯度信息。 智能優(yōu)化計算 2022/8/27 6 蟻群優(yōu)化算法研究背景 1/3 群智能理論研究領(lǐng)域有兩種主要的算法：蟻群算法 (Ant Colony Optimization, ACO)和微粒群算法（ Particle Swarm Optimization, PSO）。 因此，其后的 ACO研究工作主要都集中于 AS性能的改進方面。在大型TSP問題中（最多包含 132座城市），基于 AS的算法都顯示出了優(yōu)于 GA和 SA的特性。按照這樣的方法可實現(xiàn)對相似數(shù)據(jù)的聚類。這樣形成一個正反饋。較短路徑的 信息素濃度高，所以能夠最終被所有螞蟻選擇，也就是最終的 優(yōu)化結(jié)果。當(dāng)螞蟻在城市 i，若 完成第 s只螞蟻的計算。 (1 ) ( )k ij k???智能優(yōu)化計算 2022/8/27 35 圖的蟻群系統(tǒng)（ GBAS） 6/12 可以驗證，下式滿足： 即 是一個隨機矩陣。 智能優(yōu)化計算 2022/8/27 43 蟻群優(yōu)化算法 — 算法模型和收斂性分析 馬氏過程的收斂定義 GBAS算法的收斂性分析 智能優(yōu)化計算 2022/8/27 44 馬氏過程的收斂定義 蟻群優(yōu)化算法的每步迭代對應(yīng)隨機變量 其中 為信息素痕跡； 為 n城市的一個排列，最多有 個狀態(tài)。 ( 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中共有 條弧。 二、終止條件 1 給定一個外循環(huán)的最大數(shù)目，表明已經(jīng)有足夠的螞蟻工作； 2 當(dāng)前最優(yōu)解連續(xù) K次相同而停止，其中 K是一個給定的整數(shù)，表示算法已經(jīng)收斂，不再需要繼續(xù)； 3 目標(biāo)值控制規(guī)則，給定優(yōu)化問題（目標(biāo)最小化）的一個下界和一個誤差值，當(dāng)算法得到的目標(biāo)值同下界之差小于給定的誤差值時，算法終止。 ( 1 ) ( ) ( )ij ij ijk k k? ? ?? ? ? ?智能優(yōu)化計算 2022/8/27 71 信息素的更改