【正文】 包括：網(wǎng)絡(luò)路由優(yōu)化、數(shù)據(jù)挖掘以及一些經(jīng)典的組合優(yōu)化問(wèn)題。而且在 Rankbased AS和精英策略 AS均優(yōu)于基本AS的同時(shí)，前者還獲得了比精英策略 AS更好的解。 智能優(yōu)化計(jì)算 2022/8/27 14 6/7 另一種對(duì) AS改進(jìn)的算法是 Rankbased Version AS。 智能優(yōu)化計(jì)算 2022/8/27 12 4/7 再次，還引入了負(fù)反饋機(jī)制，每當(dāng)一只螞蟻由一個(gè)節(jié)點(diǎn)移動(dòng)到另一個(gè)節(jié)點(diǎn)時(shí)，該路徑上的信息素都按照如下公式被相應(yīng)的消除一部分，從而實(shí)現(xiàn)一種信息素的局部調(diào)整，以減小已選擇過(guò)的路徑再次被選擇的概率。該系統(tǒng)的提出是以 AntQ算法為基礎(chǔ)的。較早的一種改進(jìn)方法是精英策略 (Elitist Strategy)，其思想是在算法開(kāi)始后即對(duì)所有已發(fā)現(xiàn)的最好路徑給予額外的增強(qiáng)，并將隨后與之對(duì)應(yīng)的行程記為 Tgb(全局最優(yōu)行程 )，當(dāng)進(jìn)行信息素更新時(shí)，對(duì)這些行程予以加權(quán)，同時(shí)將經(jīng)過(guò)這些行程的螞蟻記為“精英”，從而增大較好行程的選擇機(jī)會(huì)。 智能優(yōu)化計(jì)算 2022/8/27 10 2/7 最初提出的 AS有三種版本： Antdensity、 Antquantity和 Antcycle。 智能優(yōu)化計(jì)算 2022/8/27 9 蟻群優(yōu)化算法研究現(xiàn)狀 1/7 90年代 Dorigo最早提出了蟻群優(yōu)化算法 螞蟻系統(tǒng)（ Ant System, AS）并將其應(yīng)用于解決計(jì)算機(jī)算法學(xué)中經(jīng)典的旅行商問(wèn)題（ TSP）。而且，這種方法只需目標(biāo)函數(shù)的輸出值，而無(wú)需其梯度信息。前者是對(duì)螞蟻群落食物采集過(guò)程的模擬，已成功應(yīng)用于許多離散優(yōu)化問(wèn)題。 20世紀(jì) 90年代意大利學(xué)者 M． Dorigo， V． Maniezzo，A． Colorni等從生物進(jìn)化的機(jī)制中受到啟發(fā)，通過(guò)模擬自然界螞蟻搜索路徑的行為，提出來(lái)一種新型的模擬進(jìn)化算法 —— 蟻群算法，是群智能理論研究領(lǐng)域的一種主要算法。提出了許多用以解決復(fù)雜優(yōu)化問(wèn)題的新方法，如進(jìn)化規(guī)劃、進(jìn)化策略、遺傳算法等，這些算法成功地解決了一些實(shí)際問(wèn)題。 智能優(yōu)化計(jì)算 2022/8/27 6 蟻群優(yōu)化算法研究背景 1/3 群智能理論研究領(lǐng)域有兩種主要的算法：蟻群算法 (Ant Colony Optimization, ACO)和微粒群算法（ Particle Swarm Optimization, PSO）。雖然概率搜索算法通常要采用較多的評(píng)價(jià) 函數(shù)，但是與梯度方法及傳統(tǒng)的演化算法相比，其優(yōu)點(diǎn)還 是顯著的 ，主要表現(xiàn)在以下幾個(gè)方面： 1 無(wú)集中控制約束，不會(huì)因個(gè)別個(gè)體的故障影響整個(gè)問(wèn)題 的求解，確保了系統(tǒng)具備更強(qiáng)的魯棒性 2 以非直接的信息交流方式確保了系統(tǒng)的擴(kuò)展性 3 并行分布式算法模型，可充分利用多處理器 4 對(duì)問(wèn)題定義的連續(xù)性無(wú)特殊要求 5 算法實(shí)現(xiàn)簡(jiǎn)單 智能優(yōu)化計(jì)算 2022/8/27 8 蟻群優(yōu)化算法研究背景 3/3 群智能方法易于實(shí)現(xiàn)，算法中僅涉及各種基本的數(shù)學(xué)操作，其數(shù)據(jù)處理過(guò)程對(duì) CPU和內(nèi)存的要求也不高。無(wú)論是從理論研究還是應(yīng)用研究的角度分析，群智能理論及其應(yīng)用研究都是具有重要學(xué)術(shù)意義和現(xiàn)實(shí)價(jià)值的。而且，取得了最佳結(jié)果的 ACO是通過(guò)引入局部搜索算法實(shí)現(xiàn)的，這實(shí)際上是一些結(jié)合了標(biāo)準(zhǔn)局域搜索算法的混合型概率搜索算法，有利于提高蟻群各級(jí)系統(tǒng)在優(yōu)化問(wèn)題中的求解質(zhì)量。 因此，其后的 ACO研究工作主要都集中于 AS性能的改進(jìn)方面。 智能優(yōu)化計(jì)算 2022/8/27 11 3/7 為了進(jìn)一步克服 AS中暴露出的問(wèn)題，提出了蟻群系統(tǒng) (Ant Colony System, ACS)。其中， 0ρ1是信息素?fù)]發(fā)參數(shù)， 是從尋路開(kāi)始到當(dāng)前為止全局最優(yōu)的路徑長(zhǎng)度。為了避免搜索停滯，路徑上的信息素濃度被限制在 [MAX， MIN ]范圍內(nèi)，另外，信息素的初始值被設(shè)為其取值上限，這樣有助于增加算法初始階段的搜索能力。在大型TSP問(wèn)題中（最多包含 132座城市），基于 AS的算法都顯示出了優(yōu)于 GA和 SA的特性。 蟻群優(yōu)化算法并不是旅行商問(wèn)題的最佳解決方法，但是它卻為解決組合優(yōu)化問(wèn)題提供了新思路，并很快被應(yīng)用到其它組合優(yōu)化問(wèn)題中。 每只螞蟻就像蟻群優(yōu)化算法中一樣，根據(jù)它在網(wǎng)絡(luò)上的經(jīng)驗(yàn)與性能，動(dòng)態(tài)更新路由表項(xiàng)。目前這方面的應(yīng)用研究仍在升溫，因?yàn)橥ㄐ啪W(wǎng)絡(luò)的分布式信息結(jié)構(gòu)、非穩(wěn)定隨機(jī)動(dòng)態(tài)特性以及網(wǎng)絡(luò)狀態(tài)的異步演化與 ACO的算法本質(zhì)和特性非常相似。按照這樣的方法可實(shí)現(xiàn)對(duì)相似數(shù)據(jù)的聚類。利用 MAXMIN AS解決 PAQ也取得了比較理想的效果，并通過(guò)實(shí)驗(yàn)中的計(jì)算數(shù)據(jù)證明采用該方法處理 PAQ比較早的 SA算法更好，且與禁忌搜索算法性能相當(dāng)。 智能優(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)槲浵佋趯ふ衣窂綍r(shí)會(huì)在路徑上釋放出一種特殊的信息素。這樣形成一個(gè)正反饋。假設(shè)初始時(shí)每條分配路線一只螞蟻，每個(gè)時(shí)間單位行走一步，本圖為經(jīng)過(guò) 9個(gè)時(shí)間單位時(shí)的情形：走 ABD的螞蟻到達(dá)終點(diǎn)，而走 ACD的螞蟻剛好走到 C點(diǎn)，為一半路程。再經(jīng)過(guò) 36個(gè)時(shí)間單位后，兩條線路上的信息素單位積累為 12和 4，比值為 3： 1。這也就是前面所提到的正反饋效應(yīng)。較短路徑的 信息素濃度高，所以能夠最終被所有螞蟻選擇，也就是最終的 優(yōu)化結(jié)果。 智能優(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è)排列， 。 信息素的更新方式有 2種，一是揮發(fā)，也就是所有路徑上的信息素以一定的比率進(jìn)行減少，模擬自然蟻群的信息素隨時(shí)間揮發(fā)的過(guò)程；二是增強(qiáng)，給評(píng)價(jià)值“好” (有螞蟻?zhàn)哌^(guò) )的邊增加信息素。當(dāng)前最好解是 。當(dāng)螞蟻在城市 i，若 完成第 s只螞蟻的計(jì)算。比較 m只螞蟻中的路徑長(zhǎng)度，記走最短路徑的螞蟻為 t。 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)路徑的信息素逐漸減少至消失。這種方式可以實(shí)現(xiàn)由單個(gè)螞 蟻無(wú)法實(shí)現(xiàn)的集中行動(dòng)。 (1 ) ( )k ij k???智能優(yōu)化計(jì)算 2022/8/27 35 圖的蟻群系統(tǒng)（ GBAS） 6/12 可以驗(yàn)證，下式滿足： 即 是一個(gè)隨機(jī)矩陣。2 : , ( 2) 。 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ā)。假設(shè)第 K次外循環(huán)后得 到信息素矩陣 ，得到當(dāng)前最優(yōu)解 。 智能優(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)。 ( ( ) , ( ) ) , 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 GBA