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