【文章內(nèi)容簡(jiǎn)介】 — 基于圖的蟻群系統(tǒng)（ GBAS） 5/12 以上算法中，在螞蟻的搜尋過(guò)程中，以信息素的概率分布來(lái)決定從城市 i到城市 j的轉(zhuǎn)移。 算法中包括信息素更新的過(guò)程 1 信息素?fù)]發(fā)（ evaporation） 信息素痕跡的揮發(fā)過(guò)程是每個(gè)連接上的信 息素痕跡的濃度自動(dòng)逐漸減弱的過(guò)程，由 表示，這個(gè) 揮發(fā)過(guò)程主要用于避免算法過(guò)快地向局部最優(yōu)區(qū)域集中，有助于搜索區(qū) 域的擴(kuò)展。 2 信息素增強(qiáng)（ reinforcement）增強(qiáng)過(guò)程是蟻群優(yōu)化算法中可選的部分， 稱為離線更新方式（還有在線更新方式）。這種方式可以實(shí)現(xiàn)由單個(gè)螞 蟻無(wú)法實(shí)現(xiàn)的集中行動(dòng)。也就是說(shuō)，增強(qiáng)過(guò)程體現(xiàn)在觀察蟻群（ m只螞蟻） 中每只螞蟻所找到的路徑，并選擇其中最優(yōu)路徑上的弧進(jìn)行信息素的增強(qiáng)， 揮發(fā)過(guò)程是所有弧都進(jìn)行的，不于螞蟻數(shù)量相關(guān)。這種增強(qiáng)過(guò)程中進(jìn)行的 信息素更新稱為離線的信息素更新。 在 STEP 3中，蟻群永遠(yuǎn)記憶到目前為止的最優(yōu)解。 (1 ) ( )k ij k???智能優(yōu)化計(jì)算 2022/8/27 35 圖的蟻群系統(tǒng)（ GBAS） 6/12 可以驗(yàn)證，下式滿足： 即 是一個(gè)隨機(jī)矩陣。 ()k?( , )( ) 1 , 0iji j Akk??? ? ??四個(gè)城市的非對(duì)稱 TSP問(wèn)題，距離矩陣和城市圖示如下： 0 1 0 .5 11 0 1 1()1 .5 5 0 11 1 1 0ijDd??????????智能優(yōu)化計(jì)算 2022/8/27 36 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS） 7/12 假設(shè)共 4只螞蟻，所有螞蟻都從城市 A出發(fā)，揮發(fā)因子 。此時(shí)，觀察 GBAS的計(jì)算過(guò)程。 矩陣 共有 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 。2 : , ( 2) 。3 : , ( 3 ) 8 。4 : , ( 4) 。W A B C D A f WW A C D B A f WW A D C B A f WW A B D C A f W? ? ? ? ?? ? ? ? ?? ? ? ? ?? ? ? ? ?第一只第二只第三只第四只智能優(yōu)化計(jì)算 2022/8/27 38 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS） 9/12 按算法步驟 3的信息素更新規(guī)則，得到更新矩陣 這是第一次外循環(huán)結(jié)束的狀態(tài)。 0 1 24 1 6 1 241 6 0 1 24 1 24( 1 ) ( ( 1 ) )1 24 1 12 0 1 61 24 1 6 1 24 0ij????????????智能優(yōu)化計(jì)算 2022/8/27 39 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS） 10/12 重復(fù)外循環(huán)，由于上一次得到的 W2已經(jīng)是全局最優(yōu)解，因此按算法步驟 3的信息素更新規(guī)則，無(wú)論螞蟻如何行走，都只是對(duì) W2路線上的城市信息素進(jìn)行增強(qiáng)，其他的城市信息素進(jìn)行揮發(fā)。得到更新矩陣 這是第一次外循環(huán)結(jié)束的狀態(tài)。 0 1 48 5 24 1 485 24 0 1 48 1 48( 2) ( ( 2) )1 48 1 48 0 5 241 48 5 24 1 48 0ij????????????智能優(yōu)化計(jì)算 2022/8/27 40 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS） 11/12 重復(fù)外循環(huán)，由于 W2全局最優(yōu)解， GBAS只記錄第一個(gè)最優(yōu)解，因此一但得到了全局最優(yōu)解，信息素的更新將不再依賴于以群的行走路線，而只是不斷增強(qiáng)最優(yōu)路線的信息素，同時(shí)進(jìn)行揮發(fā)。第三次外循環(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)化計(jì)算 2022/8/27 41 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS） 12/12 螞蟻以一定的概率從城市 i到城市 j進(jìn)行轉(zhuǎn)移，信息素的 更新在 STEP 3 完成，并隨 K而變化。假設(shè)第 K次外循環(huán)后得 到信息素矩陣 ，得到當(dāng)前最優(yōu)解 。 第 K次循環(huán)前的信息素和最優(yōu)解為 ，經(jīng)過(guò) 第 K次外循環(huán)后，得到 。由于螞蟻的一步轉(zhuǎn)移 概率是隨機(jī)的，從 到 也是隨機(jī)的，是一個(gè)馬爾可夫過(guò)程。 ( ) ( ( ) | ( , ) )ijk k i j A???? ()Wk? ?( 1 ) , ( 1 )k W k? ??? ?( ) , ( )k W k?? ?( 1 ) , ( 1 )k W k? ?? ? ?( ) , ( )k W k?智能優(yōu)化計(jì)算 2022/8/27 42 一般蟻群算法的框架 一般蟻群算法的框架和 GBAS基本相同，有三個(gè)組成部分： 蟻群的活動(dòng)； 信息素的揮發(fā)； 信息素的增強(qiáng)； 主要體現(xiàn)在前面的算法中步驟 2和步驟 3中的轉(zhuǎn)移概率公式和信息素更新公式。 智能優(yōu)化計(jì)算 2022/8/27 43 蟻群優(yōu)化算法 — 算法模型和收斂性分析 馬氏過(guò)程的收斂定義 GBAS算法的收斂性分析 智能優(yōu)化計(jì)算 2022/8/27 44 馬氏過(guò)程的收斂定義 蟻群優(yōu)化算法的每步迭代對(duì)應(yīng)隨機(jī)變量 其中 為信息素痕跡； 為 n城市的一個(gè)排列，最多有 個(gè)狀態(tài)。第 s只螞蟻在第 k輪轉(zhuǎn)移只由 決定，這個(gè)螞蟻行走的路徑和 一起，共同決定了 ，再通過(guò)信息素的更新原則可以進(jìn)一步得到 。 的變化僅由 決定，而與先前的狀態(tài)無(wú)關(guān)，這是一個(gè)典型的馬爾可夫過(guò)程。 定義 ：若一個(gè)馬爾可夫過(guò)程 ，對(duì)任意給定的 滿足 則稱馬爾可夫過(guò)程 依概率 1收斂到 。 ( ( ) , ( ) ) , 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)化計(jì)算 2022/8/27 45 GBAS算法的收斂性分析 1/8 定理 滿足 指定條件 的馬爾可夫過(guò)程 依概率 1收斂到 ,其中 為一條最優(yōu)路徑 , 定義為 : 證明分析 : 蟻群算法中 ,一但達(dá)到全局最優(yōu) ,由 只記錄第一個(gè)最優(yōu)解 .證明分三部分 : – 證明以概率 1達(dá)到一個(gè)最優(yōu)路徑 – 證明 (1)上式成立 – 證明以概率 1收斂到一個(gè)最優(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)化計(jì)算 2022/8/27 46 GBAS算法的收斂性分析 2/8 證明以概率 1到達(dá)一個(gè)最優(yōu)路徑 對(duì)于最優(yōu)路徑 ,令 為蟻群中的一個(gè)螞蟻在第 k次外循環(huán)后第一次走到最優(yōu)路徑 的事件 . 表示僅第 k次外循環(huán)沒有走到 的事件 ,但前 k1次可能走到過(guò)這條最優(yōu)路徑 . 永遠(yuǎn)不會(huì)被走到的事件為 ,其概率為 : *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)化計(jì)算 2022/8/27 47 GBAS算法的收斂性分析 3/8 任意給定的固定弧 (i,j),在第 k次循環(huán)后 ,其信息素值的下界可以計(jì)算出 . 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)化計(jì)算 2022/8/27 48 GBAS算法的收斂性分析 4/8 令 ,任何一個(gè)固定節(jié)點(diǎn)最多有 (n1)后續(xù)節(jié)點(diǎn) ,并且其弧上的信息素值都小于 1或者等于 : 蟻群中的一只螞蟻在第 次循環(huán)走到路徑 W* 的概率為