【正文】 外的增強(qiáng)，并將隨后與之對應(yīng)的行程記為 Tgb(全局最優(yōu)行程 )，當(dāng)進(jìn)行信息素更新時(shí)，對這些行程予以加權(quán)，同時(shí)將經(jīng)過這些行程的螞蟻記為 “ 精英 ” ，從而增大較好行程的選擇機(jī)會。但是若選擇的精英過多則算法會由于較早的收斂于局部次優(yōu)解而導(dǎo)致搜索的過早停滯。該系統(tǒng)的提出是以 AntQ算法為基礎(chǔ)的。 ACS與 AS之間存在三方面的主要差異：首先， ACS采用了更為大膽的行為選擇規(guī)則；其次，只增強(qiáng)屬于全局最優(yōu)解的路徑上的信息素。 42 4/7 再次，還引入了負(fù)反饋機(jī)制，每當(dāng)一只螞蟻由一個(gè)節(jié)點(diǎn)移動到另一個(gè)節(jié)點(diǎn)時(shí)，該路徑上的信息素都按照如下公式被相應(yīng)的消除一部分，從而實(shí)現(xiàn)一種信息素的局部調(diào)整，以減小已選擇過的路徑再次被選擇的概率。該算法修改了 AS的信息素更新方式，每次迭代之后只有一只螞蟻能夠進(jìn)行信息素的更新以獲取更好的解。 44 6/7 另一種對 AS改進(jìn)的算法是 Rankbased Version AS。 45 7/7 這種算法求解 TSP的能力與 AS、精英策略 AS、遺傳算法和模擬退火算法進(jìn)行了比較。而且在 Rankbased AS和精英策略 AS均優(yōu)于基本 AS的同時(shí)，前者還獲得了比精英策略 AS更好的解。多種研究表明，群智能在離散求解空間和連續(xù)求解空間中均表現(xiàn)出良好的搜索效果，并在組合優(yōu)化問題中表現(xiàn)突出。比較典型的應(yīng)用研究包括：網(wǎng)絡(luò)路由優(yōu)化、數(shù)據(jù)挖掘以及一些經(jīng)典的組合優(yōu)化問題。 HP公司和英國電信公司在 90年代中后期都開展了這方面的研究，設(shè)計(jì)了蟻群路由算法（ Ant Colony Routing, ACR）。如果一只螞蟻因?yàn)榻?jīng)過了網(wǎng)絡(luò)中堵塞的路由而導(dǎo)致了比較大的延遲，那么就對該表項(xiàng)做較大的增強(qiáng)。這樣，在當(dāng)前最優(yōu)路由出現(xiàn)擁堵現(xiàn)象時(shí)， ACR算法就能迅速的搜尋另一條可替代的最優(yōu)路徑，從而提高網(wǎng)絡(luò)的均衡性、負(fù)荷量和利用率。 48 蟻群優(yōu)化算法應(yīng)用現(xiàn)狀 3/5 基于群智能的聚類算法起源于對蟻群蟻卵的分類研究。其基本思想是將待聚類數(shù)據(jù)隨機(jī)地散布到一個(gè)二維平面內(nèi)，然后將虛擬螞蟻分布到這個(gè)空間內(nèi)，并以隨機(jī)方式移動，當(dāng)一只螞蟻遇到一個(gè)待聚類數(shù)據(jù)時(shí)即將之拾起并繼續(xù)隨機(jī)運(yùn)動，若運(yùn)動路徑附近的數(shù)據(jù)與背負(fù)的數(shù)據(jù)相似性高于設(shè)置的標(biāo)準(zhǔn)則將其放置在該位置，然后繼續(xù)移動，重復(fù)上述數(shù)據(jù)搬運(yùn)過程。 49 蟻群優(yōu)化算法應(yīng)用現(xiàn)狀 4/5 ACO還在許多經(jīng)典組合優(yōu)化問題中獲得了成功的應(yīng)用，如二次規(guī)劃問題（ QAP）、機(jī)器人路徑規(guī)劃、作業(yè)流程規(guī)劃、圖著色（ Graph Coloring）等問題。 AS在作業(yè)流程計(jì)劃（ Jobshop Scheduling）問題中的應(yīng)用實(shí)例已經(jīng)出現(xiàn)，這說明了 AS在此領(lǐng)域的應(yīng)用潛力。利用 ACO實(shí)現(xiàn)對生產(chǎn)流程和特料管理的綜合優(yōu)化，并通過與遺傳、模擬退火和禁忌搜索算法的比較證明了 ACO的工程應(yīng)用價(jià)值。 Costa和 Herz還提出了一種 AS在規(guī)劃問題方面的擴(kuò)展應(yīng)用 —— 圖著色問題，并取得了可與其他啟發(fā)式算法相比的效果。螞蟻在運(yùn)動過程中，能夠在它所經(jīng)過的路徑上留下一種稱之為外激素 (pheromone)的物質(zhì)進(jìn)行信息傳遞，而且螞蟻在運(yùn)動過程中能夠感知這種物質(zhì)，并以此指導(dǎo)自己的運(yùn)動方向，因此由大量螞蟻組成的蟻群集體行為便表現(xiàn)出一種信息正反饋現(xiàn)象：某一路徑上走過的螞蟻越多，則后來者選擇該路徑的概率就越大。在蟻群尋找食物時(shí)，它們總能找到一條從食物到巢穴之間的最優(yōu)路徑。當(dāng)它們碰到一個(gè)還沒有走過的路口時(shí)．就隨機(jī)地挑選一條路徑前行。路徑越長，釋放的激索濃度越低 .當(dāng)后來的螞蟻再次碰到這個(gè)路口的時(shí)候．選擇激素濃度較高路徑概率就會相對較大。最優(yōu)路徑上的激索濃度越來越大．而其它的路徑上激素濃度卻會隨著時(shí)間的流逝而消減。 53 簡化的螞蟻尋食過程 1/3 螞蟻從 A點(diǎn)出發(fā)，速度相同，食物在 D點(diǎn)，可能隨機(jī)選擇路線 ABD或 ACD。 54 簡化的螞蟻尋食過程 2/3 本圖為從開始算起，經(jīng)過 18個(gè)時(shí)間單位時(shí)的情形：走 ABD的螞蟻到達(dá)終點(diǎn)后得到食物又返回了起點(diǎn) A，而走 ACD的螞蟻剛好走到 D點(diǎn)。 尋找食物的過程繼續(xù)進(jìn)行，則按信息素的指導(dǎo)，蟻群在 ABD路線上增派一只螞蟻（共 2只），而 ACD路線上仍然為一只螞蟻。 若按以上規(guī)則繼續(xù)，蟻群在 ABD路線上再增派一只螞蟻（共 3只），而ACD路線上仍然為一只螞蟻。 若繼續(xù)進(jìn)行，則按信息素的指導(dǎo)，最終所有的螞蟻會放棄 ACD路線，而都選擇 ABD路線。 56 自然蟻群與人工蟻群算法 基于以上蟻群尋找食物時(shí)的最優(yōu)路徑選擇問題，可以構(gòu)造 人工蟻群，來解決最優(yōu)化問題，如 TSP問題。二者的 相似之處在于都是優(yōu)先選擇信息素濃度大的路徑。 兩者的區(qū)別在于人工蟻群有一定的記憶能力，能夠記憶已 經(jīng)訪問過的節(jié)點(diǎn)。例如 在 TSP問題中，可以預(yù)先知道當(dāng)前城市到下一個(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é)作異步地得到問題的解。 2 可見度，即先驗(yà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)解。 60 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS） 1/12 初始的蟻群算法是基于圖的蟻群算法， graphbased ant system,簡稱為 GBAS，是由 Gutjahr W J在 2022年的Future Generation Computing Systems提出的，課本的參考文獻(xiàn) 2。當(dāng)前最好解是 。否則使螞蟻 s從起點(diǎn) 出發(fā)，用 表示螞蟻 s行走的城市集合，初始 為空集， 。當(dāng)螞蟻在城市 i，若 完成第 s只螞蟻的計(jì)算。 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, ( ) ( ) { }, : 。比較 m只螞蟻中的路徑長度，記走最短路徑的螞蟻為 t。用如下公式對 W路徑 上的信息素痕跡加強(qiáng)，對其他路徑上的信息素進(jìn)行揮發(fā)。 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)路徑的信息素逐漸減少至消失。 算法中包括信息素更新的過程 1 信息素?fù)]發(fā)（ evaporation） 信息素痕跡的揮發(fā)過程是每個(gè)連接上的信 息素痕跡的濃度自動逐漸減弱的過程，由 表示，這個(gè) 揮發(fā)過程主要用于避免算法過快地向局部最優(yōu)區(qū)域集中，有助于搜索區(qū) 域的擴(kuò)展。這種方式可以實(shí)現(xiàn)由單個(gè)螞 蟻無法實(shí)現(xiàn)的集中行動。這種增強(qiáng)過程中進(jìn)行的 信息素更新稱為離線的信息素更新。 (1 ) ( )k ij k???65 圖的蟻群系統(tǒng)（ GBAS） 6/12 可以驗(yàn)證，下式滿足： 即 是一個(gè)隨機(jī)矩陣。此時(shí)，觀察 GBAS的計(jì)算過程。2 : , ( 2) 。4 : , ( 4) 。 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ā)。 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????????????70 初始的蟻群優(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ā)。假設(shè)第 K次外循環(huán)后得 到信息素矩陣 ，得到當(dāng)前最優(yōu)解 。由于螞蟻的一步轉(zhuǎn)移 概率是隨機(jī)的，從 到 也是隨機(jī)的，是一個(gè)馬爾可夫過程。 73 蟻群優(yōu)化算法 — 算法模型和收斂性分析 馬氏過程的收斂定義 GBAS算法的收斂性分析 74 馬氏過程的收斂定義 蟻群優(yōu)化算法的每步迭代對應(yīng)隨機(jī)變量 其中 為信息素痕跡； 為 n城市的一個(gè)排列，最多有 個(gè)狀態(tài)。 的變化僅由 決定，而與先前的狀態(tài)無關(guān)，這是一個(gè)典型的馬爾可夫過程。 ( ( ) , ( ) ) , 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 ??? ? ? ?75 GBAS算法的收斂性分析 1/8 定理 滿足 指定條件 的馬爾可夫過程 依概率 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)76 GBAS算法的收斂性分析 2/8 證明以概率 1到達(dá)一個(gè)最優(yōu)路徑 對于最優(yōu)路徑 ,令 為蟻群中的一個(gè)螞蟻在第 k次外循環(huán)后第一次走到最優(yōu)路徑 的事件 . 表示僅第 k次外循環(huán)沒有走到 的事件 ,但前 k1次可能走到過這條最優(yōu)路徑 . 永遠(yuǎn)不會被走到的事件為 ,其概率為 : *WkF*W kF *W*W12FF 12*1*1()|{} ){(2}kkP F FP k WP k W????