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