【正文】 擬退火和禁忌搜索算法的比較證明了 ACO的工程應(yīng)用價(jià)值。 智能優(yōu)化計(jì)算 2022/8/27 20 蟻群優(yōu)化算法應(yīng)用現(xiàn)狀 5/5 許多研究者將 ACO用于了武器攻擊目標(biāo)分配和優(yōu)化問(wèn)題、車輛運(yùn)行路徑規(guī)劃、區(qū)域性無(wú)線電頻率自動(dòng)分配、 Bayesian works的訓(xùn)練和集合覆蓋等應(yīng)用優(yōu)化問(wèn)題。 Costa和 Herz還提出了一種 AS在規(guī)劃問(wèn)題方面的擴(kuò)展應(yīng)用 ——圖著色問(wèn)題，并取得了可與其他啟發(fā)式算法相比的效果。 智能優(yōu)化計(jì)算 2022/8/27 21 蟻群優(yōu)化算法概念 蟻群算法原理 簡(jiǎn)化的螞蟻尋食過(guò)程 自然蟻群與人工蟻群算法 蟻群算法與 TSP問(wèn)題 初始的蟻群優(yōu)化算法 —基于圖的蟻群系統(tǒng)（ GBAS） 一般蟻群算法的框架 智能優(yōu)化計(jì)算 2022/8/27 22 蟻群算法原理 蟻群算法是對(duì)自然界螞蟻的尋徑方式進(jìn)行模似而得出的一種仿生算法。螞蟻在運(yùn)動(dòng)過(guò)程中，能夠在它所經(jīng)過(guò)的路徑上留下一種稱之為外激素(pheromone)的物質(zhì)進(jìn)行信息傳遞，而且螞蟻在運(yùn)動(dòng)過(guò)程中能夠感知這種物質(zhì)，并以此指導(dǎo)自己的運(yùn)動(dòng)方向，因此由大量螞蟻組成的蟻群集體行為便表現(xiàn)出一種信息正反饋現(xiàn)象：某一路徑上走過(guò)的螞蟻越多，則后來(lái)者選擇該路徑的概率就越大。 為了說(shuō)明蟻群算法的原理，先簡(jiǎn)要介紹一下螞蟻搜尋食物的具體過(guò)程。在蟻群尋找食物時(shí)，它們總能找到一條從食物到巢穴之間的最優(yōu)路徑。這是因?yàn)槲浵佋趯ふ衣窂綍r(shí)會(huì)在路徑上釋放出一種特殊的信息素。當(dāng)它們碰到一個(gè)還沒(méi)有走過(guò)的路口時(shí)．就隨機(jī)地挑選一條路徑前行。與此同時(shí)釋放出與路徑長(zhǎng)度有關(guān)的信息素。路徑越長(zhǎng)，釋放的激索濃度越低 .當(dāng)后來(lái)的螞蟻再次碰到這個(gè)路口的時(shí)候．選擇激素濃度較高路徑概率就會(huì)相對(duì)較大。這樣形成一個(gè)正反饋。最優(yōu)路徑上的激索濃度越來(lái)越大．而其它的路徑上激素濃度卻會(huì)隨著時(shí)間的流逝而消減。最終整個(gè)蟻群會(huì)找出最優(yōu)路徑。 智能優(yōu)化計(jì)算 2022/8/27 23 簡(jiǎn)化的螞蟻尋食過(guò)程 1/3 螞蟻從 A點(diǎn)出發(fā)，速度相同，食物在 D點(diǎn)，可能隨機(jī)選擇路線 ABD或 ACD。假設(shè)初始時(shí)每條分配路線一只螞蟻，每個(gè)時(shí)間單位行走一步，本圖為經(jīng)過(guò) 9個(gè)時(shí)間單位時(shí)的情形：走 ABD的螞蟻到達(dá)終點(diǎn)，而走 ACD的螞蟻剛好走到 C點(diǎn)，為一半路程。 智能優(yōu)化計(jì)算 2022/8/27 24 簡(jiǎn)化的螞蟻尋食過(guò)程 2/3 本圖為從開(kāi)始算起，經(jīng)過(guò) 18個(gè)時(shí)間單位時(shí)的情形：走 ABD的螞蟻到達(dá)終點(diǎn)后得到食物又返回了起點(diǎn) A，而走 ACD的螞蟻剛好走到 D點(diǎn)。 智能優(yōu)化計(jì)算 2022/8/27 25 簡(jiǎn)化的螞蟻尋食過(guò)程 3/3 假設(shè)螞蟻每經(jīng)過(guò)一處所留下的信息素為一個(gè)單位，則經(jīng)過(guò) 36個(gè)時(shí)間單位后，所有開(kāi)始一起出發(fā)的螞蟻都經(jīng)過(guò)不同路徑從 D點(diǎn)取得了食物，此時(shí) ABD的路線往返了 2趟，每一處的信息素為 4個(gè)單位，而 ACD的路線往返了一趟，每一處的信息素為 2個(gè)單位，其比值為 2： 1。 尋找食物的過(guò)程繼續(xù)進(jìn)行，則按信息素的指導(dǎo)，蟻群在 ABD路線上增派一只螞蟻（共 2只），而 ACD路線上仍然為一只螞蟻。再經(jīng)過(guò) 36個(gè)時(shí)間單位后，兩條線路上的信息素單位積累為 12和 4，比值為 3： 1。 若按以上規(guī)則繼續(xù)，蟻群在 ABD路線上再增派一只螞蟻（共 3只），而ACD路線上仍然為一只螞蟻。再經(jīng)過(guò) 36個(gè)時(shí)間單位后，兩條線路上的信息素單位積累為 24和 6，比值為 4： 1。 若繼續(xù)進(jìn)行，則按信息素的指導(dǎo)，最終所有的螞蟻會(huì)放棄 ACD路線，而都選擇 ABD路線。這也就是前面所提到的正反饋效應(yīng)。 智能優(yōu)化計(jì)算 2022/8/27 26 自然蟻群與人工蟻群算法 基于以上蟻群尋找食物時(shí)的最優(yōu)路徑選擇問(wèn)題，可以構(gòu)造 人工蟻群，來(lái)解決最優(yōu)化問(wèn)題，如 TSP問(wèn)題。 人工蟻群中把具有簡(jiǎn)單功能的工作單元看作螞蟻。二者的 相似之處在于都是優(yōu)先選擇信息素濃度大的路徑。較短路徑的 信息素濃度高，所以能夠最終被所有螞蟻選擇，也就是最終的 優(yōu)化結(jié)果。 兩者的區(qū)別在于人工蟻群有一定的記憶能力，能夠記憶已 經(jīng)訪問(wèn)過(guò)的節(jié)點(diǎn)。同時(shí)，人工蟻群再選擇下一條路徑的時(shí)候是 按一定算法規(guī)律有意識(shí)地尋找最短路徑，而不是盲目的。例如 在 TSP問(wèn)題中，可以預(yù)先知道當(dāng)前城市到下一個(gè)目的地的距離。 智能優(yōu)化計(jì)算 2022/8/27 27 蟻群算法與 TSP問(wèn)題 1/3 TSP問(wèn)題表示為一個(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 ??智能優(yōu)化計(jì)算 2022/8/27 28 蟻群算法與 TSP問(wèn)題 2/3 TSP問(wèn)題的人工蟻群算法中，假設(shè) m只螞蟻在圖的相鄰節(jié)點(diǎn)間移動(dòng)，從而協(xié)作異步地得到問(wèn)題的解。每只螞蟻的一步轉(zhuǎn)移概率由圖中的每條邊上的兩類參數(shù)決定： 1 信息素值 也稱信息素痕跡。 2 可見(jiàn)度，即先驗(yàn)值。 信息素的更新方式有 2種，一是揮發(fā)，也就是所有路徑上的信息素以一定的比率進(jìn)行減少，模擬自然蟻群的信息素隨時(shí)間揮發(fā)的過(guò)程；二是增強(qiáng)，給評(píng)價(jià)值“好” (有螞蟻?zhàn)哌^(guò) )的邊增加信息素。 智能優(yōu)化計(jì)算 2022/8/27 29 蟻群算法與 TSP問(wèn)題 3/3 螞蟻向下一個(gè)目標(biāo)的運(yùn)動(dòng)是通過(guò)一個(gè)隨機(jī)原則來(lái)實(shí)現(xiàn)的，也就是運(yùn)用當(dāng)前所在節(jié)點(diǎn)存儲(chǔ)的信息，計(jì)算出下一步可達(dá)節(jié)點(diǎn)的概率，并按此概率實(shí)現(xiàn)一步移動(dòng)，逐此往復(fù)，越來(lái)越接近最優(yōu)解。 螞蟻在尋找過(guò)程中，或者找到一個(gè)解后，會(huì)評(píng)估該解或解的一部分的優(yōu)化程度，并把評(píng)價(jià)信息保存在相關(guān)連接的信息素中。 智能優(yōu)化計(jì)算 2022/8/27 30 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS） 1/12 初始的蟻群算法是基于圖的蟻群算法， graphbased ant system,簡(jiǎn)稱為 GBAS，是由 Gutjahr W J在 2022年的Future Generation Computing Systems提出的，算法步驟如下： STEP 0 對(duì) n個(gè)城市的 TSP問(wèn)題， 城市間的距離矩陣為 ，給 TSP圖中的每一條弧 賦信息素初值 ，假設(shè) m只螞蟻在工作，所有螞蟻都從同一城市 出發(fā)。當(dāng)前最好解是 。 }, |j), { ( iA n}{ 1 , 2 , . . . ,N Nji ???nnijd ?)(),( ji ||1)0( Aij ??0i),2,1( nw ?? 初始的蟻群優(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??智能優(yōu)化計(jì)算 2022/8/27 32 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS） 3/12 STRP 3 對(duì) ，若 ，按 中城市的順序計(jì)算 路徑長(zhǎng)度；若 ，路徑長(zhǎng)度置為一個(gè)無(wú)窮大值（即不可 達(dá)）。比較 m只螞蟻中的路徑長(zhǎng)度，記走最短路徑的螞蟻為 t。 若 ，則 。用如下公式對(duì) W路徑 上的信息素痕跡加強(qiáng)，對(duì)其他路徑上的信息素進(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?? ? ?? ? ??????? ? ? ???? ? ???為 上的一條弧不是 上的一條弧智能優(yōu)化計(jì)算 2022/8/27 33 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS） 4/12 在 STEP 3 中，揮發(fā)因子 對(duì)于一個(gè)固定的 ，滿足 并且 經(jīng)過(guò) k次揮發(fā)，非最優(yōu)路徑的信息素逐漸減少至消失。 k?ln1,l n ( 1 )kk kKk? ? ? ??1K?1kk??????智能優(yōu)化計(jì)算 2022/8/27 34