【正文】 ?12, , ...., ki i i 1k?1ki?11 jkijab????1 2 1( ) ( 0 , , , .. .. , , )kkL s i i i i ??智能優(yōu)化計算 2022/8/27 61 解的表達(dá)形式與算法的實現(xiàn) 4/4 算法的實現(xiàn) 對蟻群重復(fù)以上過程，比較 m只螞蟻的裝包值 并記憶具有最大裝包值的螞蟻為 t。 ()Ls11 jkijab???? 1 2 1( ) ( 0 , , , .. .. , , )kkL s i i i i ??智能優(yōu)化計算 2022/8/27 64 每一節(jié)點(diǎn)的記憶信息和系數(shù)的確定 系數(shù)的確定 3/3 殘留信息的相對重要程度 和預(yù)見值的相對重要程度 體現(xiàn)了相關(guān)信息痕跡和預(yù)見度對螞蟻決策的相對影響。 蟻群離線更新方式是在蟻群中的 m只螞蟻全部完成 n城市的訪問（第 k1次蟻群循環(huán)）后，統(tǒng)一對殘留信息進(jìn)行更新處理。相對而言，單螞蟻離線更新方式記憶信息少，只需要記憶第s只螞蟻的路徑，并通過信息素更新后，釋放該螞蟻的所有記錄信息。研究 RWA 問題的目的是盡可能減少所需要的波長數(shù)和降低光路連接請求的阻塞率。 參考文獻(xiàn)： 基于蟻群系統(tǒng)的分布式 RWA 算法研究 孫海金 , 朱 娜 , 周乃富 2022 年 第 2 期 光通信研究 智能優(yōu)化計算 2022/8/27 74 3/5 蟻群算法用于計算機(jī)網(wǎng)絡(luò)路由 參考文獻(xiàn)：計算機(jī)網(wǎng)絡(luò)中的組播路由算法 謝銀祥 智能優(yōu)化計算 2022/8/27 75 應(yīng)用 4/5 智能優(yōu)化計算 2022/8/27 76 5/5 蟻群算法用于聚類（蟻群蟻卵分類） 思想：把待聚類的數(shù)據(jù)隨機(jī)散布在一個平面上，放置若干只虛擬螞蟻使其在平面上隨機(jī)運(yùn)動。 智能優(yōu)化計算 2022/8/27 79 蟻群優(yōu)化算法 — 參考文獻(xiàn) ? 題目：群智能理論及應(yīng)用 ? 電子學(xué)報 , 2022年 S1期 【 作者 】 彭喜元 彭宇 戴毓豐 ? 【 關(guān)鍵詞 】 群智能 微粒群算法 蟻群算法 優(yōu)化算法 ?；谖浵仭靶畔⑺乇怼眮硗瓿删植啃畔⒌乃⑿掠嬎?。蟻環(huán)離線更新方法很好地保證了殘留信息不至于無限積累，非最優(yōu)路徑會逐漸隨時間推移被忘記。 ( 1 ) ( )i j i jks??? ? ?或為( ) , ( , )( , )0ijQWt i j Wi j W???? ? ??? ??智能優(yōu)化計算 2022/8/27 69 信息素的更改 4/6 GBAS算法是典型的離線信息素更新方式。 信息素的在線更新（異步更新方式）即螞蟻每行走一步，立即回溯并且更新行走路徑上的信息素。 第三部分為問題的約束條件。第 步按 TSP算法 的轉(zhuǎn)移概率公式行走選擇 。蟻群算法在解決這類問題時，只需要建立一個虛擬的始終點(diǎn)，就可以把 TSP問題的解法推廣，用于諸多的優(yōu)化問題。 定義 ：若一個馬爾可夫過程 ，對任意給定的 滿足 則稱馬爾可夫過程 依概率 1收斂到 。第三次外循環(huán)后得到的信息素矩陣為： 0 1 96 11 48 1 9611 48 0 1 96 1 96( 3 ) ( ( 3 ) )1 96 1 96 0 11 481 96 11 48 1 96 0ij????????????智能優(yōu)化計算 2022/8/27 41 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS） 12/12 螞蟻以一定的概率從城市 i到城市 j進(jìn)行轉(zhuǎn)移，信息素的 更新在 STEP 3 完成，并隨 K而變化。 矩陣 共有 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 。 2 信息素增強(qiáng)（ reinforcement）增強(qiáng)過程是蟻群優(yōu)化算法中可選的部分， 稱為離線更新方式（還有在線更新方式）。i L s L s i i i??智能優(yōu)化計算 2022/8/27 32 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS） 3/12 STRP 3 對 ，若 ，按 中城市的順序計算 路徑長度；若 ，路徑長度置為一個無窮大值（即不可 達(dá)）。 智能優(yōu)化計算 2022/8/27 30 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS） 1/12 初始的蟻群算法是基于圖的蟻群算法， graphbased ant system,簡稱為 GBAS，是由 Gutjahr W J在 2022年的Future Generation Computing Systems提出的，算法步驟如下： STEP 0 對 n個城市的 TSP問題， 城市間的距離矩陣為 ，給 TSP圖中的每一條弧 賦信息素初值 ，假設(shè) m只螞蟻在工作，所有螞蟻都從同一城市 出發(fā)。例如 在 TSP問題中，可以預(yù)先知道當(dāng)前城市到下一個目的地的距離。 若繼續(xù)進(jìn)行，則按信息素的指導(dǎo)，最終所有的螞蟻會放棄 ACD路線，而都選擇 ABD路線。 智能優(yōu)化計算 2022/8/27 23 簡化的螞蟻尋食過程 1/3 螞蟻從 A點(diǎn)出發(fā)，速度相同，食物在 D點(diǎn)，可能隨機(jī)選擇路線 ABD或 ACD。在蟻群尋找食物時，它們總能找到一條從食物到巢穴之間的最優(yōu)路徑。 AS在作業(yè)流程計劃（ Jobshop Scheduling）問題中的應(yīng)用實例已經(jīng)出現(xiàn)，這說明了 AS在此領(lǐng)域的應(yīng)用潛力。這樣，在當(dāng)前最優(yōu)路由出現(xiàn)擁堵現(xiàn)象時， ACR算法就能迅速的搜尋另一條可替代的最優(yōu)路徑，從而提高網(wǎng)絡(luò)的均衡性、負(fù)荷量和利用率。多種研究表明，群智能在離散求解空間和連續(xù)求解空間中均表現(xiàn)出良好的搜索效果，并在組合優(yōu)化問題中表現(xiàn)突出。該算法修改了 AS的信息素更新方式，每次迭代之后只有一只螞蟻能夠進(jìn)行信息素的更新以獲取更好的解。但是若選擇的精英過多則算法會由于較早的收斂于局部次優(yōu)解而導(dǎo)致搜索的過早停滯。這些AS改進(jìn)版本的一個共同點(diǎn)就是增強(qiáng)了螞蟻搜索過程中對最優(yōu)解的探索能力，它們之間的差異僅在于搜索控制策略方面。 智能優(yōu)化計算 2022/8/27 7 蟻群優(yōu)化算法研究背景 2/3 與大多數(shù)基于梯度的應(yīng)用優(yōu)化算法不同，群智能依靠的是 概率搜索算法。智能優(yōu)化計算 2022/8/27 1 第六章 蟻群算法介紹 智能優(yōu)化計算 2022/8/27 2 蟻群優(yōu)化算法 1. 蟻群優(yōu)化算法概述 2. 蟻群優(yōu)化算法概念 3. 算法模型和收斂性分析 4. 算法實現(xiàn)的技術(shù)問題 5. 應(yīng)用 6. 參考資料 智能優(yōu)化計算 2022/8/27 3 蟻群優(yōu)化算法概述 ? 起源 ? 應(yīng)用領(lǐng)域 ? 研究背景 ? 研究現(xiàn)狀 ? 應(yīng)用現(xiàn)狀 智能優(yōu)化計算 2022/8/27 4 蟻群優(yōu)化算法起源 20世紀(jì) 50年代中期創(chuàng)立了仿生學(xué)，人們從生物進(jìn)化的機(jī)理中受到啟發(fā)。微粒群算法也是起源于對簡單社會系統(tǒng)的模擬，最初是模擬鳥群覓食的過程，但后來發(fā)現(xiàn)它是一種很好的優(yōu)化工具。從螞蟻系統(tǒng)開始，基本的蟻群算法得到了不斷的發(fā)展和完善，并在 TSP以及許多實際優(yōu)化問題求解中進(jìn)一步得到了驗證。這種改進(jìn)型算法能夠以更快的速度獲得更好的解。 智能優(yōu)化計算 2022/8/27 13 5/7 在對 AS進(jìn)行直接完善的方法中， MAXMIN Ant System是一個典型代表。 智能優(yōu)化計算 2022/8/27 16 蟻群優(yōu)化算法應(yīng)用現(xiàn)狀 1/5 隨著群智能理論和應(yīng)用算法研究的不斷發(fā)展，研究者已嘗試著將其用于各種工程優(yōu)化問題，并取得了意想不到的收獲。同時根據(jù)信息素?fù)]發(fā)機(jī)制實現(xiàn)系統(tǒng)的信息更新，從而拋棄過期的路由信息。 經(jīng)過多年的發(fā)展， ACO已成為能夠有效解決實際二次規(guī)劃問題的幾種重要算法之一。 為了說明蟻群算法的原理，先簡要介紹一下螞蟻搜尋食物的具體過程。最終整個蟻群會找出最優(yōu)路徑。再經(jīng)過 36個時間單位后，兩條線路上的信息素單位積累為 24和 6，比值為 4： 1。同時，人工蟻群再選擇下一條路徑的時候是 按一定算法規(guī)律有意識地尋找最短路徑，而不是盲目的。 螞蟻在尋找過程中，或者找到一個解后，會評估該解或解的一部分的優(yōu)化程度，并把評價信息保存在相關(guān)連接的信息素中。 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, ( ) ( ) { } , : 。 算法中包括信息素更新的過程 1 信息素?fù)]發(fā)（ evaporation） 信息素痕跡的揮發(fā)過程是每個連接上的信 息素痕跡的濃度自動逐漸減弱的過程，由 表示，這個 揮發(fā)過程主要用于避免算法過快地向局部最優(yōu)區(qū)域集中，有助于搜索區(qū) 域的