【正文】 70 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS） 11/12重復(fù)外循環(huán)，由于 W2全局最優(yōu)解， GBAS只記錄第一個最優(yōu)解，因此一但得到了全局最優(yōu)解，信息素的更新將不再依賴于以群的行走路線，而只是不斷增強最優(yōu)路線的信息素，同時進行揮發(fā)。69 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS） 10/12重復(fù)外循環(huán)，由于上一次得到的 W2已經(jīng)是全局最優(yōu)解，因此按算法步驟 3的信息素更新規(guī)則，無論螞蟻如何行走，都只是對 W2路線上的城市信息素進行增強，其他的城市信息素進行揮發(fā)。此時，觀察 GBAS的計算過程。65圖的蟻群系統(tǒng)（ GBAS） 6/12可以驗證，下式滿足：即 是一個隨機矩陣。這種增強過程中進行的信息素更新稱為離線的信息素更新。這種方式可以實現(xiàn)由單個螞蟻無法實現(xiàn)的集中行動。 算法中包括信息素更新的過程 1 信息素揮發(fā)（ evaporation） 信息素痕跡的揮發(fā)過程是每個連接上的信息素痕跡的濃度自動逐漸減弱的過程，由 表示，這個揮發(fā)過程主要用于避免算法過快地向局部最優(yōu)區(qū)域集中，有助于搜索區(qū)域的擴展。63 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS） 4/12在 STEP 3 中，揮發(fā)因子 對于一個固定的 ，滿足并且 經(jīng)過 k次揮發(fā)，非最優(yōu)路徑的信息素逐漸減少至消失。用如下公式對 W路徑上的信息素痕跡加強，對其他路徑上的信息素進行揮發(fā)。比較 m只螞蟻中的路徑長度，記走最短路徑的螞蟻為 t。否則，若，則以概率 ， 到達 j， ；若則到達 重復(fù) STEP 2。STEP 2 (內(nèi)循環(huán) ) 按螞蟻 的順序分別計算。61 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS） 2/12STEP 1 （外循環(huán)）如果滿足算法的停止規(guī)則，則停止計算并輸出計算得到的最好解。算法步驟如下：STEP 0 對 n個城市的 TSP問題，城市間的距離矩陣為 ，給 TSP圖中的每一條弧 賦信息素初值 ，假設(shè) m只螞蟻在工作，所有螞蟻都從同一城市 出發(fā)。 螞蟻在尋找過程中，或者找到一個解后，會評估該解或解的一部分的優(yōu)化程度，并把評價信息保存在相關(guān)連接的信息素中。 信息素的更新方式有 2種，一是揮發(fā)，也就是所有路徑上的信息素以一定的比率進行減少，模擬自然蟻群的信息素隨時間揮發(fā)的過程；二是增強，給評價值 “好 ”(有螞蟻走過 )的邊增加信息素。每只螞蟻的一步轉(zhuǎn)移概率由圖中的每條邊上的兩類參數(shù)決定： 1 信息素值 也稱信息素痕跡。57 蟻群算法與 TSP問題 1/3TSP問題表示為一個 N個城市的有向圖 G=（ N， A），其中 城市之間距離目標函數(shù)為 ，其中 為城市 1,2， …n 的一個排列， 。同時，人工蟻群再選擇下一條路徑的時候是按一定算法規(guī)律有意識地尋找最短路徑，而不是盲目的。較短路徑的信息素濃度高，所以能夠最終被所有螞蟻選擇，也就是最終的優(yōu)化結(jié)果。 人工蟻群中把具有簡單功能的工作單元看作螞蟻。這也就是前面所提到的正反饋效應(yīng)。再經(jīng)過 36個時間單位后，兩條線路上的信息素單位積累為 24和 6，比值為 4： 1。再經(jīng)過 36個時間單位后，兩條線路上的信息素單位積累為 12和 4，比值為 3： 1。55 簡化的螞蟻尋食過程 3/3 假設(shè)螞蟻每經(jīng)過一處所留下的信息素為一個單位，則經(jīng)過 36個時間單位后，所有開始一起出發(fā)的螞蟻都經(jīng)過不同路徑從 D點取得了食物，此時 ABD的路線往返了 2趟，每一處的信息素為 4個單位，而 ACD的路線往返了一趟，每一處的信息素為 2個單位，其比值為 2： 1。假設(shè)初始時每條分配路線一只螞蟻，每個時間單位行走一步，本圖為經(jīng)過 9個時間單位時的情形：走 ABD的螞蟻到達終點，而走 ACD的螞蟻剛好走到 C點，為一半路程。最終整個蟻群會找出最優(yōu)路徑。這樣形成一個正反饋。與此同時釋放出與路徑長度有關(guān)的信息素。這是因為螞蟻在尋找路徑時會在路徑上釋放出一種特殊的信息素。 為了說明蟻群算法的原理，先簡要介紹一下螞蟻搜尋食物的具體過程。51 蟻群優(yōu)化算法概念 蟻群算法原理 簡化的螞蟻尋食過程 自然蟻群與人工蟻群算法 蟻群算法與 TSP問題 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS） 一般蟻群算法的框架52 蟻群算法原理 蟻群算法是對自然界螞蟻的尋徑方式進行模似而得出的一種仿生算法。50 蟻群優(yōu)化算法應(yīng)用現(xiàn)狀 5/5 許多研究者將 ACO用于了武器攻擊目標分配和優(yōu)化問題、車輛運行路徑規(guī)劃、區(qū)域性無線電頻率自動分配、 Bayesian works的訓(xùn)練和集合覆蓋等應(yīng)用優(yōu)化問題。利用 MAXMIN AS解決 PAQ也取得了比較理想的效果，并通過實驗中的計算數(shù)據(jù)證明采用該方法處理 PAQ比較早的 SA算法更好，且與禁忌搜索算法性能相當。 經(jīng)過多年的發(fā)展， ACO已成為能夠有效解決實際二次規(guī)劃問題的幾種重要算法之一。按照這樣的方法可實現(xiàn)對相似數(shù)據(jù)的聚類。 Lumer和 Faieta將 Deneubourg提出將蟻巢分類模型應(yīng)用于數(shù)據(jù)聚類分析。目前這方面的應(yīng)用研究仍在升溫，因為通信網(wǎng)絡(luò)的分布式信息結(jié)構(gòu)、非穩(wěn)定隨機動態(tài)特性以及網(wǎng)絡(luò)狀態(tài)的異步演化與 ACO的算法本質(zhì)和特性非常相似。同時根據(jù)信息素揮發(fā)機制實現(xiàn)系統(tǒng)的信息更新，從而拋棄過期的路由信息。 每只螞蟻就像蟻群優(yōu)化算法中一樣，根據(jù)它在網(wǎng)絡(luò)上的經(jīng)驗與性能，動態(tài)更新路由表項。 47 蟻群優(yōu)化算法應(yīng)用現(xiàn)狀 2/5 蟻群算法在電信路由優(yōu)化中已取得了一定的應(yīng)用成果。 蟻群優(yōu)化算法并不是旅行商問題的最佳解決方法，但是它卻為解決組合優(yōu)化問題提供了新思路，并很快被應(yīng)用到其它組合優(yōu)化問題中。 46 蟻群優(yōu)化算法應(yīng)用現(xiàn)狀 1/5 隨著群智能理論和應(yīng)用算法研究的不斷發(fā)展，研究者已嘗試著將其用于各種工程優(yōu)化問題，并取得了意想不到的收獲。在大型TSP問題中（最多包含 132座城市），基于 AS的算法都顯示出了優(yōu)于 GA和 SA的特性。與 “精英策略 ”相似，在此算法中總是更新更好進程上的信息素，選擇的標準是其行程長度 決定的排序，且每個螞蟻放置信息素的強度通過下式中的排序加權(quán)處理確定，其中，ｗ為每次迭代后放置信息素的螞蟻總數(shù)。為了避免搜索停滯，路徑上的信息素濃度被限制在 [MAX， MIN ]范圍內(nèi)，另外，信息素的初始值被設(shè)為其取值上限，這樣有助于增加算法初始階段的搜索能力。 43 5/7 在對 AS進行直接完善的方法中， MAXMIN Ant System是一個典型代表。其中， 0ρ1是信息素揮發(fā)參數(shù)， 是從尋路開始到當前為止全局最優(yōu)的路徑長度。 AntQ將螞蟻算法和一種增強型學(xué)習算法 Qlearning有機的結(jié)合了起來。 41 3/7 為了進一步克服 AS中暴露出的問題，提出了蟻群系統(tǒng) (Ant Colony System, ACS)。這種改進型算法能夠以更快的速度獲得更好的解。 因此，其后的 ACO研究工作主要都集中于 AS性能的改進方面。在 Antdensity和 Antquantity中螞蟻在兩個位置節(jié)點間每移動一次后即更新信息素，而在 Antcycle中當所有的螞蟻都完成了自己的行程后才對信息素進行更新，而且每個螞蟻所釋放的信息素被表達為反映相應(yīng)行程質(zhì)量的函數(shù)。而且，取得了最佳結(jié)果的 ACO是通過引入局部搜索算法實現(xiàn)的，這實際上是一些結(jié)合了標準局域搜索算法的混合型概率搜索算法，有利于提高蟻群各級系統(tǒng)在優(yōu)化問題中的求解質(zhì)量。從螞蟻系統(tǒng)開始，基本的蟻群算法得到了不斷的發(fā)展和完善，并在 TSP以及許多實際優(yōu)化問題求解中進一步得到了驗證。無論是從理論研究還是應(yīng)用研究的角度分析，群智能理論及其應(yīng)用研究都是具有重要學(xué)術(shù)意義和現(xiàn)實價值的。已完成的群智能理論和應(yīng)用方法研究證明群智能方法是一種能夠有效解決大多數(shù)全局優(yōu)化問題的新方法。雖然概率搜索算法通常要采用較多的評價函數(shù)，但是與梯度方法及傳統(tǒng)的演化算法相比，其優(yōu)點還是顯著的 ，主要表現(xiàn)在以下幾個方面：1 無集中控制 約 束，不會因個 別 個體的故障影響整個 問題 的求解，確保了系 統(tǒng) 具 備 更 強 的 魯 棒性 2 以非直接的信息交流方式確保了系 統(tǒng) 的 擴 展性 3 并行分布