【文章內(nèi)容簡介】 一條從食物到巢穴之間的最優(yōu)路徑。這是因?yàn)槲浵佋趯ふ衣窂綍r(shí)會在路徑上釋放出一種特殊的信息素。當(dāng)它們碰到一個(gè)還沒有走過的路口時(shí)．就隨機(jī)地挑選一條路徑前行。與此同時(shí)釋放出與路徑長度有關(guān)的信息素。路徑越長，釋放的激索濃度越低 .當(dāng)后來的螞蟻再次碰到這個(gè)路口的時(shí)候．選擇激素濃度較高路徑概率就會相對較大。這樣形成一個(gè)正反饋。最優(yōu)路徑上的激索濃度越來越大．而其它的路徑上激素濃度卻會隨著時(shí)間的流逝而消減。最終整個(gè)蟻群會找出最優(yōu)路徑。 53 簡化的螞蟻尋食過程 1/3 螞蟻從 A點(diǎn)出發(fā)，速度相同，食物在 D點(diǎn)，可能隨機(jī)選擇路線 ABD或 ACD。假設(shè)初始時(shí)每條分配路線一只螞蟻，每個(gè)時(shí)間單位行走一步，本圖為經(jīng)過 9個(gè)時(shí)間單位時(shí)的情形：走 ABD的螞蟻到達(dá)終點(diǎn)，而走 ACD的螞蟻剛好走到 C點(diǎn)，為一半路程。 54 簡化的螞蟻尋食過程 2/3 本圖為從開始算起，經(jīng)過 18個(gè)時(shí)間單位時(shí)的情形：走 ABD的螞蟻到達(dá)終點(diǎn)后得到食物又返回了起點(diǎn) A，而走 ACD的螞蟻剛好走到 D點(diǎn)。 55 簡化的螞蟻尋食過程 3/3 假設(shè)螞蟻每經(jīng)過一處所留下的信息素為一個(gè)單位，則經(jīng)過 36個(gè)時(shí)間單位后，所有開始一起出發(fā)的螞蟻都經(jīng)過不同路徑從 D點(diǎn)取得了食物，此時(shí) ABD的路線往返了 2趟，每一處的信息素為 4個(gè)單位，而 ACD的路線往返了一趟，每一處的信息素為 2個(gè)單位，其比值為 2： 1。 尋找食物的過程繼續(xù)進(jìn)行，則按信息素的指導(dǎo)，蟻群在 ABD路線上增派一只螞蟻（共 2只），而 ACD路線上仍然為一只螞蟻。再經(jīng)過 36個(gè)時(shí)間單位后，兩條線路上的信息素單位積累為 12和 4，比值為 3： 1。 若按以上規(guī)則繼續(xù)，蟻群在 ABD路線上再增派一只螞蟻（共 3只），而ACD路線上仍然為一只螞蟻。再經(jīng)過 36個(gè)時(shí)間單位后，兩條線路上的信息素單位積累為 24和 6，比值為 4： 1。 若繼續(xù)進(jìn)行，則按信息素的指導(dǎo)，最終所有的螞蟻會放棄 ACD路線，而都選擇 ABD路線。這也就是前面所提到的正反饋效應(yīng)。 56 自然蟻群與人工蟻群算法 基于以上蟻群尋找食物時(shí)的最優(yōu)路徑選擇問題，可以構(gòu)造 人工蟻群，來解決最優(yōu)化問題，如 TSP問題。 人工蟻群中把具有簡單功能的工作單元看作螞蟻。二者的 相似之處在于都是優(yōu)先選擇信息素濃度大的路徑。較短路徑的 信息素濃度高，所以能夠最終被所有螞蟻選擇，也就是最終的 優(yōu)化結(jié)果。 兩者的區(qū)別在于人工蟻群有一定的記憶能力，能夠記憶已 經(jīng)訪問過的節(jié)點(diǎn)。同時(shí)，人工蟻群再選擇下一條路徑的時(shí)候是 按一定算法規(guī)律有意識地尋找最短路徑，而不是盲目的。例如 在 TSP問題中，可以預(yù)先知道當(dāng)前城市到下一個(gè)目的地的距離。 57 蟻群算法與 TSP問題 1/3 TSP問題表示為一個(gè) N個(gè)城市的有向圖 G=（ N， A）， 其中 城市之間距離 目標(biāo)函數(shù)為 ， 其中 為城市 1,2， ?n 的 一個(gè)排列， 。 }, |j), { ( iA n}{ 1 , 2 , . . . ,N Nji ???nnijd ?)(?? ??nlii lldwf1 1)(),( 21 niiiw ??11 iin ??58 蟻群算法與 TSP問題 2/3 TSP問題的人工蟻群算法中，假設(shè) m只螞蟻在圖的相鄰節(jié)點(diǎn)間移動，從而協(xié)作異步地得到問題的解。每只螞蟻的一步轉(zhuǎn)移概率由圖中的每條邊上的兩類參數(shù)決定： 1 信息素值 也稱信息素痕跡。 2 可見度，即先驗(yàn)值。 信息素的更新方式有 2種，一是揮發(fā)，也就是所有路徑上的信息素以一定的比率進(jìn)行減少，模擬自然蟻群的信息素隨時(shí)間揮發(fā)的過程；二是增強(qiáng)，給評價(jià)值 “ 好 ” (有螞蟻?zhàn)哌^ )的邊增加信息素。 59 蟻群算法與 TSP問題 3/3 螞蟻向下一個(gè)目標(biāo)的運(yùn)動是通過一個(gè)隨機(jī)原則來實(shí)現(xiàn)的，也就是運(yùn)用當(dāng)前所在節(jié)點(diǎn)存儲的信息，計(jì)算出下一步可達(dá)節(jié)點(diǎn)的概率，并按此概率實(shí)現(xiàn)一步移動，逐此往復(fù)，越來越接近最優(yōu)解。 螞蟻在尋找過程中，或者找到一個(gè)解后，會評估該解或解的一部分的優(yōu)化程度，并把評價(jià)信息保存在相關(guān)連接的信息素中。 60 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS） 1/12 初始的蟻群算法是基于圖的蟻群算法， graphbased ant system,簡稱為 GBAS，是由 Gutjahr W J在 2022年的Future Generation Computing Systems提出的，課本的參考文獻(xiàn) 2。算法步驟如下： STEP 0 對 n個(gè)城市的 TSP問題， 城市間的距離矩陣為 ，給 TSP圖中的每一條弧 賦信息素初值 ，假設(shè) m只螞蟻在工作，所有螞蟻都從同一城市 出發(fā)。當(dāng)前最好解是 。 }, |j), { ( iA n}{ 1 , 2 , . . . ,N Nji ???nnijd ?)(),( ji ||1)0( Aij ??0i),2,1( nw ??61 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS） 2/12 STEP 1 （外循環(huán)）如果滿足算法的停止規(guī)則，則停止計(jì)算并輸出計(jì)算得到的最好解。否則使螞蟻 s從起點(diǎn) 出發(fā)，用 表示螞蟻 s行走的城市集合，初始 為空集， 。 STEP 2 (內(nèi)循環(huán) ) 按螞蟻 的順序分別計(jì)算。當(dāng)螞蟻在城市 i，若 完成第 s只螞蟻的計(jì)算。否則，若 ，則以概率 ， 到達(dá) j， ；若 則到達(dá) 重復(fù) STEP 2。 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, ( ) ( ) { }, : 。i L s L s i i i??62 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS） 3/12 STRP 3 對 ，若 ，按 中城市的順序計(jì)算 路徑程度；若 ，路徑長度置為一個(gè)無窮大值（即不可 達(dá)）。比較 m只螞蟻中的路徑長度，記走最短路徑的螞蟻為 t。 若 ，則 。用如下公式對 W路徑 上的信息素痕跡加強(qiáng)，對其他路徑上的信息素進(jìn)行揮發(fā)。 得到新的 ，重復(fù)步驟 STEP 1。 1 sm?? ()L s N? ()Ls()L s N?( ( ) ) ( ( ) )f L t f L W? ()W L t?( ) , : 1ij k k k? ??111( ) ( 1 ) ( 1 ) ( , )( ) ( 1 ) ( 1 ) ( , )kij k ijij k ijk k i j WWk k i j W?? ? ?? ? ??????? ? ? ???? ? ???為 上的一條弧不是 上的一條弧63 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS） 4/12 在 STEP 3 中，揮發(fā)因子 對于一個(gè)固定的 ，滿足 并且 經(jīng)過 k次揮發(fā)，非最優(yōu)路徑的信息素逐漸減少至消失。 k?ln1,l n ( 1 )kk kKk? ? ? ??1K ?1kk??????64 — 基于圖的蟻群系統(tǒng)（ GBAS） 5/12 以上算法中，在螞蟻的搜尋過程中，以信息素的概率分布來決定從城市 i到城市 j的轉(zhuǎn)移。 算法中包括信息素更新的過程 1 信息素?fù)]發(fā)（ evaporation） 信息素痕跡的揮發(fā)過程是每個(gè)連接上的信 息素痕跡的濃度自動逐漸減弱的過程，由 表示，這個(gè) 揮發(fā)過程主要用于避免算法過快地向局部最優(yōu)區(qū)域集中，有助于搜索區(qū) 域的擴(kuò)展。 2 信息素增強(qiáng)（ reinforcement）增強(qiáng)過程是蟻群優(yōu)化算法中可選的部分， 稱為離線更新方式（還有在線更新方式）。這種方式可以實(shí)現(xiàn)由單個(gè)螞 蟻無法實(shí)現(xiàn)的集中行動。也就是說，增強(qiáng)過程體現(xiàn)在觀察蟻群（ m只螞蟻） 中每只螞蟻所找到的路徑，并選擇其中最優(yōu)路徑上的弧進(jìn)行信息素的增強(qiáng)， 揮發(fā)過程是所有弧都進(jìn)行的，不于螞蟻數(shù)量相關(guān)。這種增強(qiáng)過程中進(jìn)行的 信息素更新稱為離線的信息素更新。 在 STEP 3中，蟻群永遠(yuǎn)記憶到目前為止的最優(yōu)解。 (1 ) ( )k ij k???65 圖的蟻群系統(tǒng)（ GBAS） 6/12 可以驗(yàn)證，下式滿足： 即 是一個(gè)隨機(jī)矩陣。 ()k?( , )( ) 1 , 0iji j Akk??? ? ??四個(gè)城市的非對稱 TSP問題，距離矩陣和城市圖示如下： 0 1 0 .5 11 0 1 1()1 .5 5 0 11 1 1 0ijDd??????????66 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS） 7/12 假設(shè)共 4只螞蟻，所有螞蟻都從城市 A出發(fā)，揮發(fā)因子 。此時(shí)，觀察 GBAS的計(jì)算過程。 矩陣 共有 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????????????67 初始的蟻群優(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? ? ? ? ?? ? ? ? ?? ? ? ? ?? ? ? ? ?第一只第二只第三只第四只68 初始的蟻群優(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????????????69 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS） 10/12 重復(fù)外循環(huán)，由于上一次得到的 W2已經(jīng)是全局最優(yōu)解，因此按算法步驟 3的信息素更新規(guī)則，無論螞蟻如何行走，都只是對 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 24