【正文】 有最大裝包值的螞蟻為 t。把 GBAS算法中步驟 3中的 改為 ，若滿足此條件則替換當(dāng)前最好解為 ， 對 W上的弧進行信息素的加強，其他弧進行信息素的揮發(fā)。 算法中記錄了三個信息：信息素痕跡 ；行走路線 ；和問題的約束條件 ， 以確定是否將 加入。 ()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 算法中需要記憶的信息有三部分。 第一部分信息是存在每個節(jié)點的路由表數(shù)據(jù)結(jié)構(gòu) ，由此決定的的轉(zhuǎn)移概率為 其中 T可以看成節(jié)點 i的鄰域。 ? ?| ( , )i ijA a i j A??( 1 ) { ( 1 ) | ( , ) }i ijA k a k i j A? ? ? ?( 1 )( 1 ) ,0ijilijlTakjTakPjT???? ?? ?? ???? ??( 1 ) ( 1 )( 1 ) ( 1 )( 1 ) ,0ij ijil ilijlTkkkka k j TjT?????????? ??????? ? ??? ????智能優(yōu)化計算 2022/8/27 63 每一節(jié)點的記憶信息和系數(shù)的確定 需要記憶的信息 2/3 第二部分需要記憶的信息是每個螞蟻的記憶表中存儲著的自身的歷史信息，這一部分主要由算法的中的 記憶，表示螞蟻已經(jīng)行走過的節(jié)點。 第三部分為問題的約束條件。在 GBAS中， T集合表示滿足約束條件的候選集，在背包問題的蟻群算法中由判別條件 ， 來實現(xiàn)記 憶功能。 ()Ls11 jkijab???? 1 2 1( ) ( 0 , , , .. .. , , )kkL s i i i i ??智能優(yōu)化計算 2022/8/27 64 每一節(jié)點的記憶信息和系數(shù)的確定 系數(shù)的確定 3/3 殘留信息的相對重要程度 和預(yù)見值的相對重要程度 體現(xiàn)了相關(guān)信息痕跡和預(yù)見度對螞蟻決策的相對影響。 Dorigo在求解 TSP問題時，推薦參數(shù)的最佳設(shè)置為： 。 ??1 , 5 , ? ? ?? ? ?智能優(yōu)化計算 2022/8/27 65 蟻群的規(guī)模和停止規(guī)則 一、蟻群大小 一般情況下蟻群中螞蟻的個數(shù)不超過 TSP圖中節(jié)點的個數(shù)。 二、終止條件 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)值同下界之差小于給定的誤差值時，算法終止。 智能優(yōu)化計算 2022/8/27 66 信息素的更改 1/6 信息素的更新分為離線和在線兩種方式。離線方式（同步更新方式）的主要思想是在若干只螞蟻完成 n個城市的訪問后，統(tǒng)一對殘留信息進行更新處理。 信息素的在線更新（異步更新方式）即螞蟻每行走一步，立即回溯并且更新行走路徑上的信息素。 智能優(yōu)化計算 2022/8/27 67 信息素的更改 2/6 離線方式的信息素更新可以進一步分為單螞蟻離線更新和蟻群離線更新。 蟻群離線更新方式是在蟻群中的 m只螞蟻全部完成 n城市的訪問（第 k1次蟻群循環(huán)）后，統(tǒng)一對殘留信息進行更新處理。 其中， 為第 k1次循環(huán)后的的信息素的痕跡值。 單螞蟻離線更新是在第 s只螞蟻完成對所有 n個城市的訪問后，進行路徑回溯，更新行走路徑上的信息素，同時釋放分配給它的資源。更新公式為 第 s+1只螞蟻根據(jù) 重新計算路由表。 ( ) ( 1 ) ( 1 )ij ij ijk k k? ? ?? ? ? ? ?()ij k?( 1 ) ( ) ( )ij ij ijs s s? ? ?? ? ? ?( 1)ij s? ?智能優(yōu)化計算 2022/8/27 68 信息素的更改 3/6 TSP問題中，蟻群優(yōu)化算法根據(jù)信息素痕跡更新方式不同可以分為 不同的算法，采用離線方式，并且 時，其中 W為 t循環(huán)中 m只螞蟻所行走的最佳路線或第 t只螞蟻所行走 的一條路徑。 Q為一個常數(shù)，該算法名為蟻環(huán)算法（ antcycle algotithm） ,特點是行走的路徑越短對應(yīng)保存的信息素的值就越大。 ( 1 ) ( )i j i jks??? ? ?或為( ) , ( , )( , )0ijQWt i j Wi j W???? ? ??? ??智能優(yōu)化計算 2022/8/27 69 信息素的更改 4/6 GBAS算法是典型的離線信息素更新方式。該算法中，蟻群中螞蟻的先后出行順序沒有相關(guān)性，但是每次循環(huán)需要記憶 m只螞蟻的行走路徑，以進行比較選擇最優(yōu)路徑。相對而言，單螞蟻離線更新方式記憶信息少，只需要記憶第s只螞蟻的路徑，并通過信息素更新后，釋放該螞蟻的所有記錄信息。實際上這種方式等價于蟻群離線方式中只有一只螞蟻。 智能優(yōu)化計算 2022/8/27 70 信息素的更改 5/6 與單螞蟻離線更新方式相比，信息量記憶更小的是信息素在線更新方式，即螞蟻每走一步，馬上回溯并且更新剛剛走過的路徑上的信息素，其規(guī)則為 其中， k為螞蟻行走的第 k步。 ( 1 ) ( ) ( )ij ij ijk k k? ? ?? ? ? ?智能優(yōu)化計算 2022/8/27 71 信息素的更改 6/6 蟻量算法（ antquantity algorithm）的信息素更新 為 ,Q為常量， 表示 i到 j的距離，這樣信息 濃度會隨城市距離的減小而加大。 蟻密算法（ antdensity algorithm ）信息素更新為 。 以上三種算法中，蟻環(huán)算法效果最好，因為他用的是全局信息，而其余兩種算法用的是局部信息。蟻環(huán)離線更新方法很好地保證了殘留信息不至于無限積累，非最優(yōu)路徑會逐漸隨時間推移被忘記。 ()ijijQkd??? ijd()ij kQ???智能優(yōu)化計算 2022/8/27 72 應(yīng)用 1/5 光網(wǎng)絡(luò)的智能管理 分布式動態(tài)選路及波長分配 ( RWA , Routing and Wavelength Assignment ) 是指在實時業(yè)務(wù)情況下光通路的路由選擇和波長分配的優(yōu)化問題 ,是實現(xiàn)自動交換光網(wǎng)絡(luò) (ASON ,Automatically Switched Optical Network) 的關(guān)鍵技術(shù)之一。研究 RWA 問題的目的是盡可能減少所需要的波長數(shù)和降低光路連接請求的阻塞率。由于 RWA 問題是 NPC 問題 ,文獻中大多將 RWA 問題拆分成路由和波長分配兩個子問題分別加以解決。但是 ,由于 RWA 問題本身是一個不可分割的整體 ,把 RWA 分開考慮必然造成難以得到全局最優(yōu)解的后果。 智能優(yōu)化計算 2022/8/27 73 應(yīng)用 2/5 同時 ,分布式的計算方式則克服了傳統(tǒng)集中式算法可擴展性差的缺點 ,更適應(yīng)現(xiàn)代頻繁變化的大型光網(wǎng)絡(luò)。因此 ,近年來國內(nèi)外對RWA 并行的分布式算法表現(xiàn)出極大的興趣 ,此類算法建立的基礎(chǔ)是分層圖模型 。 用蟻群算法在分層圖模型的基礎(chǔ)上求解動態(tài) RWA 問題。基于螞蟻“信息素表”來完成局部信息的刷新計算。以分布的形式做少量的計算來刷新全局路由選擇信息。 參考文獻： 基于蟻群系統(tǒng)的分布式 RWA 算法研究 孫海金 , 朱 娜 , 周乃富 2022 年 第 2 期 光通信研究 智能優(yōu)化計算 2022/8/27 74 3/5 蟻群算法用于計算機網(wǎng)絡(luò)路由 參考文獻：計算機網(wǎng)絡(luò)中的組播路由算法 謝銀祥 智能優(yōu)化計算 2022/8/27 75 應(yīng)用 4/5 智能優(yōu)化計算 2022/8/27 76 5/5 蟻群算法用于聚類（蟻群蟻卵分類） 思想：把待聚類的數(shù)據(jù)隨機散布在一個平面上，放置若干只虛擬螞蟻使其在平面上隨機運動。當(dāng)一只螞蟻遇到一個數(shù)據(jù)時即拾起并繼續(xù)行走，在行走過程中，如果遇到附近的數(shù)據(jù)與背負的數(shù)據(jù)相似性高于設(shè)置的標(biāo)準(zhǔn)時則將數(shù)據(jù)放置在該位置，繼續(xù)移動。重復(fù)以上過程即可實現(xiàn)數(shù)據(jù)聚類。 智能優(yōu)化計算 2022/8/27 77 蟻群優(yōu)化算法 — 參考書 1 ? 智能蟻群算法及應(yīng)用 吳啟迪 上?？萍汲霭嫔? 從基本結(jié)構(gòu)、算法特點、改進方法、突破途徑、實現(xiàn)模式及應(yīng)用模式等方面進行了論述。主要內(nèi)容有蟻群算法的由來、研究成果、應(yīng)用綜述、算法的具體描述及改進、算法的典型優(yōu)化問題求解模式、算法的典型應(yīng)用及拓展應(yīng)用。 智能優(yōu)化計算 2022/8/27 78 蟻群優(yōu)化算法 — 參考書 2 ? 蟻群算法及其應(yīng)用 李士勇 哈工大出版社 國內(nèi)首部蟻群算法的專著，系統(tǒng)地闡述蟻群算法的基本原理、基本蟻群算法及改進算法，蟻群算法與遺傳、免疫算法的融合，自適應(yīng)蟻群算法，并行蟻群算法，蟻群算法的收斂性與理論模型及其在優(yōu)化問題中的應(yīng)用。 智能優(yōu)化計算 2022/8/27 79 蟻群優(yōu)化算法 — 參考文獻 ? 題目：群智能理論及應(yīng)用 ? 電子學(xué)報 , 2022年 S1期 【 作者 】 彭喜元 彭宇 戴毓豐 ? 【 關(guān)鍵詞 】 群智能 微粒群算法 蟻群算法 優(yōu)化算法