【正文】 用該方法處理 PAQ比較早的 SA算法更好，且與禁忌搜索算法性能相當。這是因為螞蟻在尋找路徑時會在路徑上釋放出一種特殊的信息素。假設初始時每條分配路線一只螞蟻，每個時間單位行走一步，本圖為經過 9個時間單位時的情形：走 ABD的螞蟻到達終點，而走 ACD的螞蟻剛好走到 C點，為一半路程。這也就是前面所提到的正反饋效應。 智能優(yōu)化計算 2022/8/27 27 蟻群算法與 TSP問題 1/3 TSP問題表示為一個 N個城市的有向圖 G=（ N， A）， 其中 城市之間距離 目標函數(shù)為 ， 其中 為城市 1,2， ?n 的 一個排列， 。當前最好解是 。比較 m只螞蟻中的路徑長度，記走最短路徑的螞蟻為 t。這種方式可以實現(xiàn)由單個螞 蟻無法實現(xiàn)的集中行動。2 : , ( 2) 。假設第 K次外循環(huán)后得 到信息素矩陣 ，得到當前最優(yōu)解 。 ( ( ) , ( ) ) , 0 , 1 , ...,kX k W k k???()k? ()Wk !n( 1)k? ? ( 1)Wk?()Wk ()k? 1kX?kX? ?, 0 , 1 , ...kXk ? 0??*X? ?, 0 ,1, 2 , .. .kXk ?? ?*l im 1kk p X X ??? ? ? ?智能優(yōu)化計算 2022/8/27 45 GBAS算法的收斂性分析 1/8 定理 滿足 指定條件 的馬爾可夫過程 依概率 1收斂到 ,其中 為一條最優(yōu)路徑 , 定義為 : 證明分析 : 蟻群算法中 ,一但達到全局最優(yōu) ,由 只記錄第一個最優(yōu)解 .證明分三部分 : – 證明以概率 1達到一個最優(yōu)路徑 – 證明 (1)上式成立 – 證明以概率 1收斂到一個最優(yōu)路徑 ( ( ) , ( ) ) , 0 , 1 , ...,kX k W k k???* **( , )XW??*W *?**1, ( , )0( 1 )ij W i j W???????為 的一條弧其他f(L(t))f(w)智能優(yōu)化計算 2022/8/27 46 GBAS算法的收斂性分析 2/8 證明以概率 1到達一個最優(yōu)路徑 對于最優(yōu)路徑 ,令 為蟻群中的一個螞蟻在第 k次外循環(huán)后第一次走到最優(yōu)路徑 的事件 . 表示僅第 k次外循環(huán)沒有走到 的事件 ,但前 k1次可能走到過這條最優(yōu)路徑 . 永遠不會被走到的事件為 ,其概率為 : *W kF*W kF*W*W12FF12*1*1()|{} ){(2}kkP F FP k WP k W????????*第 次循環(huán)蟻群沒有走到 第i k 次循環(huán)蟻群沒有走到W前 次循環(huán)蟻群沒有走到智能優(yōu)化計算 2022/8/27 47 GBAS算法的收斂性分析 3/8 任意給定的固定弧 (i,j),在第 k次循環(huán)后 ,其信息素值的下界可以計算出 . 111111111( ) ( 1 ) ( 1 )ln( 1 ) ( 1 )l n( 1 )ln( 1 ) ( 1 )ln1( 1 ) l n ( 1 ) ( 3 )lnijkij llKkl ijl l KKl ijlKl ijlkllKkKk? ? ???????????????????????????????智能優(yōu)化計算 2022/8/27 48 GBAS算法的收斂性分析 4/8 令 ,任何一個固定節(jié)點最多有 (n1)后續(xù)節(jié)點 ,并且其弧上的信息素值都小于 1或者等于 : 蟻群中的一只螞蟻在第 次循環(huán)走到路徑 W* 的概率為 一個蟻群中至少有一只螞蟻，因此這是一個蟻群到達最優(yōu)路徑 的一個下界 . 上式右側與 k無關 , 11(1 ) l n (1 )K l ijlK????? ? ??,( 1 ) l nijp k Knk????k(k K)?*( , ) *( ) ( )( ( 4 )1 ) l n Wiji j Wpk nk?????智能優(yōu)化計算 2022/8/27 49 GBAS算法的收斂性分析 5/8 則 取對數(shù)有 從而得到 **( , * ){ } 1 ( ) 1 ( )( 1 ) l n wiji j WP k W p k nk??? ? ? ???前 次循環(huán)蟻群沒有走到*1*{}( 1 ( ) )( 1 ) l n( 2)( 5 )kwkKP k Wnk??????????前 次循環(huán)蟻群沒有走到**l n ( 1 ( ) ) ( )( 1 ) l n ( 1 ) l nwwk K k Kn k n k??????? ? ? ? ? ?????12( ) 1P F F ?智能優(yōu)化計算 2022/8/27 50 GBAS算法的收斂性分析 6/8 證明右式成立 隨機過程 以概率 1達到一條最優(yōu)路徑 .當某條最優(yōu)路徑 Z在第 k次循環(huán)被首次走到后 ,在第 k+1輪循環(huán)按信息素的更新原則 ,可以用歸納法證明 ,對于任意 **1, ( , )0ij W i j W???????為 的一條弧其他( i ,j ) W * ,r =1,2,... .?11 10 11( ) ( 1 ) ( ) ( 1 )*( 6 )K r rri j l i j K lll K q lK r K K qW? ? ? ? ?? ? ????? ? ?? ? ? ? ? ????智能優(yōu)化計算 2022/8/27 51 GBAS算法的收斂性分析 7/8 由于級數(shù) 是發(fā)散的 ,可知 .因此 ,當 時 ,在第 K輪迭代之后 ,該弧永遠不再被加強 ,從而有 也既 弧上的信息素之和將趨于 0. 對于信息素的更新公式 (2),可以歸納證明 (6)式的第二項與 (i,j)弧無關 ,結合 (7)式可得 的極限存在 ,且所有的極限之和為 l?? 1 (1 ) 0ll ??????1( ) ( 1 ) ( 0 7)) (Kri j l i jlKK r K? ? ????? ? ? ??( , ) *i j W?( , ) *i j W?( , )( ) 1 ,iji j Akk????? 成立( , ) *i j W?1l i m ( ) l i m ( * (8, * )* )i j lrlK r X WW??? ? ? ?? ? ?, 即可得智能優(yōu)化計算 2022/8/27 52 GBAS算法的收斂性分析 8/8 結合前兩部分討論 ,當 Xn首次到達最優(yōu)路徑后 ,對于任何最優(yōu)路徑上的弧 ,(1)式的轉移概率 ,即 依概率 1收斂到 . ( ) 1ijpl ? { ( ( ) , ( ) ) , 0 , 1 , .. ., }kX k W k k???* **( , )XW??智能優(yōu)化計算 2022/8/27 53 其他算法及收斂性分析 1/4 MAXMIN蟻群優(yōu)化算法指定揮發(fā)系數(shù)不隨時間變化 ,這是和 GBAS算法不同的一點 ,改變了信息素揮發(fā)和增強的規(guī)則 (9式 )，同時給出一個下界 控制信息素的揮發(fā) . 定理 在 MAXMIN算法中 , m in ( 1)k? ?m inm a x{( 1 ) ( 1 ) , ( 1 ) } ( , )()m a x{( 1 ) ( 1 ) , ( 1 ) }, 0 1 , ( 1 )ij ijijij ijk W k i j Wkkkk? ? ? ??? ? ???? ? ? ? ? ??? ?? ? ???? ? ?其他其中 為實數(shù)。 諸如車間作業(yè)及下料等問題，他們的共同特點是解以一個順序表示。若 則 ，否則，此螞蟻不再繼續(xù)行走，退回起點。在 GBAS中， T集合表示滿足約束條件的候選集，在背包問題的蟻群算法中由判別條件 ， 來實現(xiàn)記 憶功能。 智能優(yōu)化計算 2022/8/27 67 信息素的更改 2/6 離線方式的信息素更新可以進一步分為單螞蟻離線更新和蟻群離線更新。該算法中，蟻群中螞蟻的先后出行順序沒有相關性，但是每次循環(huán)需要記憶 m只螞蟻的行走路徑，以進行比較選擇最優(yōu)路徑。 ()ijijQkd??? ijd()ij kQ???智能優(yōu)化計算 2022/8/27 72 應用 1/5 光網絡的智能管理 分布式動態(tài)選路及波長分配 ( RWA , Routing and Wavelength Assignment ) 是指在實時業(yè)務情況下光通路的路由選擇和波長分配的優(yōu)化問題 ,是實現(xiàn)自動交換光網絡 (ASON ,Automatically Switched Optical Network) 的關鍵技術之一。以分布的形式做少量的計算來刷新全局路由選