蟻群算法詳細講解第一頁，共八十一頁，2022年，8月28日第二頁，共八十一頁，2022年，8月28日2第三頁，共八十一頁，2022年，8月28日31.1蟻群優化算法概述1.1.1起源1.1.2應用領域1.1.3研究背景1.1.4研究現狀1.1.5應用現狀第四頁，共八十一頁，2022年，8月28日41.1.1蟻群優化算法起源

20世紀50年代中期創立了仿生學，人們從生物進化的機理中受到啟發。提出了許多用以解決復雜優化問題的新方法，如進化規劃、進化策略、遺傳算法等，這些算法成功地解決了一些實際問題。

20世紀90年代意大利學者M．Dorigo，V．Maniezzo，A．Colorni等從生物進化的機制中受到啟發，通過模擬自然界螞蟻搜索路徑的行為，提出來一種新型的模擬進化算法——

蟻群算法，是群智能理論研究領域的一種主要算法。用該方法求解TSP問題、分配問題、job-shop調度問題，取得了較好的試驗結果．雖然研究時間不長，但是現在的研究顯示出，蟻群算法在求解復雜優化問題（特別是離散優化問題）方面有一定優勢，表明它是一種有發展前景的算法．第五頁，共八十一頁，2022年，8月28日51.1.2蟻群優化算法應用領域

這種方法能夠被用于解決大多數優化問題或者能夠轉化為優化求解的問題?，F在其應用領域已擴展到多目標優化、數據分類、數據聚類、模式識別、電信QoS管理、生物系統建模、流程規劃、信號處理、機器人控制、決策支持以及仿真和系統辯識等方面，群智能理論和方法為解決這類應用問題提供了新的途徑。第六頁，共八十一頁，2022年，8月28日62.1.3蟻群優化算法研究背景1/3群智能理論研究領域有兩種主要的算法：蟻群算法(AntColonyOptimization,ACO)和微粒群算法（ParticleSwarmOptimization,PSO）。前者是對螞蟻群落食物采集過程的模擬，已成功應用于許多離散優化問題。微粒群算法也是起源于對簡單社會系統的模擬，最初是模擬鳥群覓食的過程，但后來發現它是一種很好的優化工具。

第七頁，共八十一頁，2022年，8月28日71.1.3蟻群優化算法研究背景2/3與大多數基于梯度的應用優化算法不同，群智能依靠的是概率搜索算法。雖然概率搜索算法通常要采用較多的評價函數，但是與梯度方法及傳統的演化算法相比，其優點還是顯著的，主要表現在以下幾個方面：1無集中控制約束，不會因個別個體的故障影響整個問題的求解，確保了系統具備更強的魯棒性

2以非直接的信息交流方式確保了系統的擴展性

3并行分布式算法模型，可充分利用多處理器

4對問題定義的連續性無特殊要求

5算法實現簡單

第八頁，共八十一頁，2022年，8月28日81.1.3蟻群優化算法研究背景3/3群智能方法易于實現，算法中僅涉及各種基本的數學操作，其數據處理過程對CPU和內存的要求也不高。而且，這種方法只需目標函數的輸出值，而無需其梯度信息。已完成的群智能理論和應用方法研究證明群智能方法是一種能夠有效解決大多數全局優化問題的新方法。更為重要是，群智能潛在的并行性和分布式特點為處理大量的以數據庫形式存在的數據提供了技術保證。無論是從理論研究還是應用研究的角度分析，群智能理論及其應用研究都是具有重要學術意義和現實價值的。

第九頁，共八十一頁，2022年，8月28日91.1.4蟻群優化算法研究現狀1/7

90年代Dorigo最早提出了蟻群優化算法---螞蟻系統（AntSystem,AS）并將其應用于解決計算機算法學中經典的旅行商問題（TSP）。從螞蟻系統開始，基本的蟻群算法得到了不斷的發展和完善，并在TSP以及許多實際優化問題求解中進一步得到了驗證。這些AS改進版本的一個共同點就是增強了螞蟻搜索過程中對最優解的探索能力，它們之間的差異僅在于搜索控制策略方面。而且，取得了最佳結果的ACO是通過引入局部搜索算法實現的，這實際上是一些結合了標準局域搜索算法的混合型概率搜索算法，有利于提高蟻群各級系統在優化問題中的求解質量。第十頁，共八十一頁，2022年，8月28日10蟻群優化算法研究現狀2/7最初提出的AS有三種版本：Ant-density、Ant-quantity和Ant-cycle。在Ant-density和Ant-quantity中螞蟻在兩個位置節點間每移動一次后即更新信息素，而在Ant-cycle中當所有的螞蟻都完成了自己的行程后才對信息素進行更新，而且每個螞蟻所釋放的信息素被表達為反映相應行程質量的函數。通過與其它各種通用的啟發式算法相比，在不大于75城市的TSP中，這三種基本算法的求解能力還是比較理想的，但是當問題規模擴展時，AS的解題能力大幅度下降。因此，其后的ACO研究工作主要都集中于AS性能的改進方面。較早的一種改進方法是精英策略(ElitistStrategy)，其思想是在算法開始后即對所有已發現的最好路徑給予額外的增強，并將隨后與之對應的行程記為Tgb(全局最優行程)，當進行信息素更新時，對這些行程予以加權，同時將經過這些行程的螞蟻記為“精英”，從而增大較好行程的選擇機會。這種改進型算法能夠以更快的速度獲得更好的解。但是若選擇的精英過多則算法會由于較早的收斂于局部次優解而導致搜索的過早停滯。

第十一頁，共八十一頁，2022年，8月28日11蟻群優化算法研究現狀3/7

為了進一步克服AS中暴露出的問題，提出了蟻群系統(AntColonySystem,ACS)。該系統的提出是以Ant-Q算法為基礎的。Ant-Q將螞蟻算法和一種增強型學習算法Q-learning有機的結合了起來。ACS與AS之間存在三方面的主要差異：首先，ACS采用了更為大膽的行為選擇規則；其次，只增強屬于全局最優解的路徑上的信息素。其中，0<ρ<1是信息素揮發參數，是從尋路開始到當前為止全局最優的路徑長度。第十二頁，共八十一頁，2022年，8月28日12蟻群優化算法研究現狀4/7

再次，還引入了負反饋機制，每當一只螞蟻由一個節點移動到另一個節點時，該路徑上的信息素都按照如下公式被相應的消除一部分，從而實現一種信息素的局部調整，以減小已選擇過的路徑再次被選擇的概率。

第十三頁，共八十一頁，2022年，8月28日13蟻群優化算法研究現狀5/7在對AS進行直接完善的方法中，MAX-MINAntSystem是一個典型代表。該算法修改了AS的信息素更新方式，每次迭代之后只有一只螞蟻能夠進行信息素的更新以獲取更好的解。為了避免搜索停滯，路徑上的信息素濃度被限制在[MAX，MIN]范圍內，另外，信息素的初始值被設為其取值上限，這樣有助于增加算法初始階段的搜索能力。第十四頁，共八十一頁，2022年，8月28日14蟻群優化算法研究現狀6/7

另一種對AS改進的算法是Rank-basedVersionAS。與“精英策略”相似，在此算法中總是更新更好進程上的信息素，選擇的標準是其行程長度決定的排序，且每個螞蟻放置信息素的強度通過下式中的排序加權處理確定，其中，ｗ為每次迭代后放置信息素的螞蟻總數。

第十五頁，共八十一頁，2022年，8月28日15蟻群優化算法研究現狀7/7這種算法求解TSP的能力與AS、精英策略AS、遺傳算法和模擬退火算法進行了比較。在大型TSP問題中（最多包含132座城市），基于AS的算法都顯示出了優于GA和SA的特性。而且在Rank-basedAS和精英策略AS均優于基本AS的同時，前者還獲得了比精英策略AS更好的解。

第十六頁，共八十一頁，2022年，8月28日161.1.5蟻群優化算法應用現狀1/5隨著群智能理論和應用算法研究的不斷發展，研究者已嘗試著將其用于各種工程優化問題，并取得了意想不到的收獲。多種研究表明，群智能在離散求解空間和連續求解空間中均表現出良好的搜索效果，并在組合優化問題中表現突出。蟻群優化算法并不是旅行商問題的最佳解決方法，但是它卻為解決組合優化問題提供了新思路，并很快被應用到其它組合優化問題中。比較典型的應用研究包括：網絡路由優化、數據挖掘以及一些經典的組合優化問題。

第十七頁，共八十一頁，2022年，8月28日171.1.5蟻群優化算法應用現狀2/5蟻群算法在電信路由優化中已取得了一定的應用成果。HP公司和英國電信公司在90年代中后期都開展了這方面的研究，設計了蟻群路由算法（AntColonyRouting,ACR）。每只螞蟻就像蟻群優化算法中一樣，根據它在網絡上的經驗與性能，動態更新路由表項。如果一只螞蟻因為經過了網絡中堵塞的路由而導致了比較大的延遲，那么就對該表項做較大的增強。同時根據信息素揮發機制實現系統的信息更新，從而拋棄過期的路由信息。這樣，在當前最優路由出現擁堵現象時，ACR算法就能迅速的搜尋另一條可替代的最優路徑，從而提高網絡的均衡性、負荷量和利用率。目前這方面的應用研究仍在升溫，因為通信網絡的分布式信息結構、非穩定隨機動態特性以及網絡狀態的異步演化與ACO的算法本質和特性非常相似。第十八頁，共八十一頁，2022年，8月28日181.1.5蟻群優化算法應用現狀3/5

基于群智能的聚類算法起源于對蟻群蟻卵的分類研究。Lumer和Faieta將Deneubourg提出將蟻巢分類模型應用于數據聚類分析。其基本思想是將待聚類數據隨機地散布到一個二維平面內，然后將虛擬螞蟻分布到這個空間內，并以隨機方式移動，當一只螞蟻遇到一個待聚類數據時即將之拾起并繼續隨機運動，若運動路徑附近的數據與背負的數據相似性高于設置的標準則將其放置在該位置，然后繼續移動，重復上述數據搬運過程。按照這樣的方法可實現對相似數據的聚類。第十九頁，共八十一頁，2022年，8月28日191.1.5蟻群優化算法應用現狀4/5

ACO還在許多經典組合優化問題中獲得了成功的應用，如二次規劃問題（QAP）、機器人路徑規劃、作業流程規劃、圖著色（GraphColoring）等問題。經過多年的發展，ACO已成為能夠有效解決實際二次規劃問題的幾種重要算法之一。AS在作業流程計劃（Job-shopScheduling）問題中的應用實例已經出現，這說明了AS在此領域的應用潛力。利用MAX-MINAS解決PAQ也取得了比較理想的效果，并通過實驗中的計算數據證明采用該方法處理PAQ比較早的SA算法更好，且與禁忌搜索算法性能相當。利用ACO實現對生產流程和特料管理的綜合優化，并通過與遺傳、模擬退火和禁忌搜索算法的比較證明了ACO的工程應用價值。第二十頁，共八十一頁，2022年，8月28日201.1.5蟻群優化算法應用現狀5/5許多研究者將ACO用于了武器攻擊目標分配和優化問題、車輛運行路徑規劃、區域性無線電頻率自動分配、Bayesiannetworks的訓練和集合覆蓋等應用優化問題。Costa和Herz還提出了一種AS在規劃問題方面的擴展應用——圖著色問題，并取得了可與其他啟發式算法相比的效果。第二十一頁，共八十一頁，2022年，8月28日211.2蟻群優化算法概念 1.2.1蟻群算法原理1.2.2簡化的螞蟻尋食過程1.2.3自然蟻群與人工蟻群算法1.2.4蟻群算法與TSP問題1.2.5初始的蟻群優化算法—基于圖的蟻群系統（GBAS）1.2.6一般蟻群算法的框架第二十二頁，共八十一頁，2022年，8月28日221.2.1蟻群算法原理蟻群算法是對自然界螞蟻的尋徑方式進行模似而得出的一種仿生算法。螞蟻在運動過程中，能夠在它所經過的路徑上留下一種稱之為外激素(pheromone)的物質進行信息傳遞，而且螞蟻在運動過程中能夠感知這種物質，并以此指導自己的運動方向，因此由大量螞蟻組成的蟻群集體行為便表現出一種信息正反饋現象：某一路徑上走過的螞蟻越多，則后來者選擇該路徑的概率就越大。為了說明蟻群算法的原理，先簡要介紹一下螞蟻搜尋食物的具體過程。在蟻群尋找食物時，它們總能找到一條從食物到巢穴之間的最優路徑。這是因為螞蟻在尋找路徑時會在路徑上釋放出一種特殊的信息素。當它們碰到一個還沒有走過的路口時．就隨機地挑選一條路徑前行。與此同時釋放出與路徑長度有關的信息素。路徑越長，釋放的激索濃度越低.當后來的螞蟻再次碰到這個路口的時候．選擇激素濃度較高路徑概率就會相對較大。這樣形成一個正反饋。最優路徑上的激索濃度越來越大．而其它的路徑上激素濃度卻會隨著時間的流逝而消減。最終整個蟻群會找出最優路徑。第二十三頁，共八十一頁，2022年，8月28日231.2.2簡化的螞蟻尋食過程1/3螞蟻從A點出發，速度相同，食物在D點，可能隨機選擇路線ABD或ACD。假設初始時每條分配路線一只螞蟻，每個時間單位行走一步，本圖為經過9個時間單位時的情形：走ABD的螞蟻到達終點，而走ACD的螞蟻剛好走到C點，為一半路程。第二十四頁，共八十一頁，2022年，8月28日24

簡化的螞蟻尋食過程2/3本圖為從開始算起，經過18個時間單位時的情形：走ABD的螞蟻到達終點后得到食物又返回了起點A，而走ACD的螞蟻剛好走到D點。第二十五頁，共八十一頁，2022年，8月28日251.2.2簡化的螞蟻尋食過程3/3

假設螞蟻每經過一處所留下的信息素為一個單位，則經過36個時間單位后，所有開始一起出發的螞蟻都經過不同路徑從D點取得了食物，此時ABD的路線往返了2趟，每一處的信息素為4個單位，而ACD的路線往返了一趟，每一處的信息素為2個單位，其比值為2：1。尋找食物的過程繼續進行，則按信息素的指導，蟻群在ABD路線上增派一只螞蟻（共2只），而ACD路線上仍然為一只螞蟻。再經過36個時間單位后，兩條線路上的信息素單位積累為12和4，比值為3：1。若按以上規則繼續，蟻群在ABD路線上再增派一只螞蟻（共3只），而ACD路線上仍然為一只螞蟻。再經過36個時間單位后，兩條線路上的信息素單位積累為24和6，比值為4：1。若繼續進行，則按信息素的指導，最終所有的螞蟻會放棄ACD路線，而都選擇ABD路線。這也就是前面所提到的正反饋效應。第二十六頁，共八十一頁，2022年，8月28日261.2.3自然蟻群與人工蟻群算法基于以上蟻群尋找食物時的最優路徑選擇問題，可以構造人工蟻群，來解決最優化問題，如TSP問題。人工蟻群中把具有簡單功能的工作單元看作螞蟻。二者的相似之處在于都是優先選擇信息素濃度大的路徑。較短路徑的信息素濃度高，所以能夠最終被所有螞蟻選擇，也就是最終的優化結果。兩者的區別在于人工蟻群有一定的記憶能力，能夠記憶已經訪問過的節點。同時，人工蟻群再選擇下一條路徑的時候是按一定算法規律有意識地尋找最短路徑，而不是盲目的。例如在TSP問題中，可以預先知道當前城市到下一個目的地的距離。第二十七頁，共八十一頁，2022年，8月28日271.2.4蟻群算法與TSP問題1/3TSP問題表示為一個N個城市的有向圖G=（N，A），其中 城市之間距離目標函數為，其中為城市1,2，…n的一個排列，。第二十八頁，共八十一頁，2022年，8月28日281.2.4蟻群算法與TSP問題2/3

TSP問題的人工蟻群算法中，假設m只螞蟻在圖的相鄰節點間移動，從而協作異步地得到問題的解。每只螞蟻的一步轉移概率由圖中的每條邊上的兩類參數決定：1信息素值也稱信息素痕跡。2可見度，即先驗值。信息素的更新方式有2種，一是揮發，也就是所有路徑上的信息素以一定的比率進行減少，模擬自然蟻群的信息素隨時間揮發的過程；二是增強，給評價值“好”(有螞蟻走過)的邊增加信息素。第二十九頁，共八十一頁，2022年，8月28日291.2.4蟻群算法與TSP問題3/3螞蟻向下一個目標的運動是通過一個隨機原則來實現的，也就是運用當前所在節點存儲的信息，計算出下一步可達節點的概率，并按此概率實現一步移動，逐此往復，越來越接近最優解。螞蟻在尋找過程中，或者找到一個解后，會評估該解或解的一部分的優化程度，并把評價信息保存在相關連接的信息素中。第三十頁，共八十一頁，2022年，8月28日301.2.5初始的蟻群優化算法—基于圖的蟻群系統（GBAS）1/12初始的蟻群算法是基于圖的蟻群算法，graph-basedantsystem,簡稱為GBAS，是由GutjahrWJ在2000年的FutureGenerationComputingSystems提出的，課本的參考文獻2。算法步驟如下：STEP0

對n個城市的TSP問題，城市間的距離矩陣為，給TSP圖中的每一條弧賦信息素初值，假設m只螞蟻在工作，所有螞蟻都從同一城市出發。當前最好解是 。第三十一頁，共八十一頁，2022年，8月28日311.2.5初始的蟻群優化算法—基于圖的蟻群系統（GBAS）2/12STEP1

（外循環）如果滿足算法的停止規則，則停止計算并輸出計算得到的最好解。否則使螞蟻s從起點出發，用表示螞蟻s行走的城市集合，初始為空集，。STEP2(內循環)按螞蟻的順序分別計算。當螞蟻在城市i，若 完成第s只螞蟻的計算。否則，若，則以概率 ， 到達j， ；若則到達 重復STEP2。第三十二頁，共八十一頁，2022年，8月28日321.2.5初始的蟻群優化算法—基于圖的蟻群系統（GBAS）3/12STRP3

對 ，若，按中城市的順序計算路徑程度；若，路徑長度置為一個無窮大值（即不可達）。比較m只螞蟻中的路徑長度，記走最短路徑的螞蟻為t。若，則。用如下公式對W路徑上的信息素痕跡加強，對其他路徑上的信息素進行揮發。得到新的，重復步驟STEP1。第三十三頁，共八十一頁，2022年，8月28日331.2.5初始的蟻群優化算法—基于圖的蟻群系統（GBAS）4/12在STEP3

中，揮發因子對于一個固定的，滿足并且

經過k次揮發，非最優路徑的信息素逐漸減少至消失。第三十四頁，共八十一頁，2022年，8月28日341.2.5初始的蟻群優化算法—基于圖的蟻群系統（GBAS）5/12以上算法中，在螞蟻的搜尋過程中，以信息素的概率分布來決定從城市i到城市j的轉移。算法中包括信息素更新的過程

1信息素揮發（evaporation）信息素痕跡的揮發過程是每個連接上的信息素痕跡的濃度自動逐漸減弱的過程，由表示，這個揮發過程主要用于避免算法過快地向局部最優區域集中，有助于搜索區域的擴展。

2信息素增強（reinforcement）增強過程是蟻群優化算法中可選的部分，稱為離線更新方式（還有在線更新方式）。這種方式可以實現由單個螞蟻無法實現的集中行動。也就是說，增強過程體現在觀察蟻群（m只螞蟻）中每只螞蟻所找到的路徑，并選擇其中最優路徑上的弧進行信息素的增強，揮發過程是所有弧都進行的，不于螞蟻數量相關。這種增強過程中進行的信息素更新稱為離線的信息素更新。在STEP3中，蟻群永遠記憶到目前為止的最優解。第三十五頁，共八十一頁，2022年，8月28日35圖的蟻群系統（GBAS）6/12可以驗證，下式滿足：即是一個隨機矩陣。四個城市的非對稱TSP問題，距離矩陣和城市圖示如下：第三十六頁，共八十一頁，2022年，8月28日361.2.5初始的蟻群優化算法—基于圖的蟻群系統（GBAS）7/12假設共4只螞蟻，所有螞蟻都從城市A出發，揮發因子。此時，觀察GBAS的計算過程。矩陣共有12條弧，初始信息素記憶矩陣為：第三十七頁，共八十一頁，2022年，8月28日371.2.5初始的蟻群優化算法—基于圖的蟻群系統（GBAS）8/12執行GBAS算法的步驟2，假設螞蟻的行走路線分別為：當前最優解為，這個解是截止到當前的最優解，碰巧是實際最優解第三十八頁，共八十一頁，2022年，8月28日381.2.5初始的蟻群優化算法—基于圖的蟻群系統（GBAS）9/12按算法步驟3的信息素更新規則，得到更新矩陣這是第一次外循環結束的狀態。第三十九頁，共八十一頁，2022年，8月28日391.2.5初始的蟻群優化算法—基于圖的蟻群系統（GBAS）10/12重復外循環，由于上一次得到的W2已經是全局最優解，因此按算法步驟3的信息素更新規則，無論螞蟻如何行走，都只是對W2路線上的城市信息素進行增強，其他的城市信息素進行揮發。得到更新矩陣這是第一次外循環結束的狀態。第四十頁，共八十一頁，2022年，8月28日401.2.5初始的蟻群優化算法—基于圖的蟻群系統（GBAS）11/12重復外循環，由于W2全局最優解，GBAS只記錄第一個最優解，因此一但得到了全局最優解，信息素的更新將不再依賴于以群的行走路線，而只是不斷增強最優路線的信息素，同時進行揮發。第三次外循環后得到的信息素矩陣為：第四十一頁，共八十一頁，2022年，8月28日411.2.5初始的蟻群優化算法—基于圖的蟻群系統（GBAS）12/12螞蟻以一定的概率從城市i到城市j進行轉移，信息素的更新在STEP3完成，并隨K而變化。假設第K次外循環后得到信息素矩陣，得到當前最優解。第K次循環前的信息素和最優解為，經過第K次外循環后，得到。由于螞蟻的一步轉移概率是隨機的，從到也是隨機的，是一個馬爾可夫過程。第四十二頁，共八十一頁，2022年，8月28日421.2.6一般蟻群算法的框架一般蟻群算法的框架和GBAS基本相同，有三個組成部分：蟻群的活動；信息素的揮發；信息素的增強；主要體現在前面的算法中步驟2和步驟3中的轉移概率公式和信息素更新公式。第四十三頁，共八十一頁，2022年，8月28日431.3蟻群優化算法—算法模型和收斂性分析1.3.0馬氏過程的收斂定義1.3.1GBAS算法的收斂性分析其他算法及收斂性分析第四十四頁，共八十一頁，2022年，8月28日441.3.0馬氏過程的收斂定義蟻群優化算法的每步迭代對應隨機變量其中為信息素痕跡；為n城市的一個排列，最多有個狀態。第s只螞蟻在第k輪轉移只由決定，這個螞蟻行走的路徑和一起，共同決定了，再通過信息素的更新原則可以進一步得到。的變化僅由決定，而與先前的狀態無關，這是一個典型的馬爾可夫過程。

定義：若一個馬爾可夫過程，對任意給定的滿足

則稱馬爾可夫過程依概率1收斂到。第四十五頁，共八十一頁，2022年，8月28日451.3.1GBAS算法的收斂性分析1/8

定理

滿足指定條件的馬爾可夫過程依概率1收斂到,其中為一條最優路徑,定義為:

證明分析:蟻群算法中,一但達到全局最優,由只記錄第一個最優解.證明分三部分:

證明以概率1達到一個最優路徑證明(1)上式成立證明以概率1收斂到一個最優路徑第四十六頁，共八十一頁，2022年，8月28日46GBAS算法的收斂性分析2/8證明以概率1到達一個最優路徑對于最優路徑,令為蟻群中的一個螞蟻在第k次外循環后第一次走到最優路徑的事件.表示僅第k次外循環沒有走到的事件,但前k-1次可能走到過這條最優路徑.永遠不會被走到的事件為,其概率為:第四十七頁，共八十一頁，2022年，8月28日47GBAS算法的收斂性分析3/8任意給定的固定弧(i,j),在第k次循環后,其信息素值的下界可以計算出.第四十八頁，共八十一頁，2022年，8月28日48GBAS算法的收斂性分析4/8令 ,任何一個固定節點最多有(n-1)后續節點,并且其弧上的信息素值都小于1或者等于1.得:蟻群中的一只螞蟻在第次循環走到路徑W*的概率為一個蟻群中至少有一只螞蟻，因此這是一個蟻群到達最優路徑的一個下界.上式右側與k無關,第四十九頁，共八十一頁，2022年，8月28日49GBAS算法的收斂性分析5/8

則取對數有從而得到第五十頁，共八十一頁，2022年，8月28日50GBAS算法的收斂性分析6/8證明右式成立隨機過程以概率1達到一條最優路徑.當某條最優路徑Z在第k次循環被首次走到后,在第k+1輪循環按信息素的更新原則,可以用歸納法證明,對于任意第五十一頁，共八十一頁，2022年，8月28日51GBAS算法的收斂性分析7/8由于級數是發散的,可知.因此,當時,在第K輪迭代之后,該弧永遠不再被加強,從而有也既弧上的信息素之和將趨于0.對于信息素的更新公式(2),可以歸納證明(6)式的第二項與(i,j)弧無關,結合(7)式可得的極限存在,且所有的極限之和為1.對于所有的第五十二頁，共八十一頁，2022年，8月28日52GBAS算法的收斂性分析8/8結合前兩部分討論,當Xn首次到達最優路徑后,對于任何最優路徑上的弧,(1)式的轉移概率

,即依概率1收斂到

.第五十三頁，共八十一頁，2022年，8月28日53

其他算法及收斂性分析1/4

MAX-MIN蟻群優化算法指定揮發系數不隨時間變化,這是和GBAS算法不同的一點,改變了信息素揮發和增強的規則(9式)，同時給出一個下界控制信息素的揮發.

定理

在MAX-MIN算法中,第五十四頁，共八十一頁，2022年，8月28日541.3.2其他算法及收斂性分析2/4第五十五頁，共八十一頁，2022年，8月28日551.3.2其他算法及收斂性分析3/4第五十六頁，共八十一頁，2022年，8月28日561.3.2其他算法及收斂性分析4/4第五十七頁，共八十一頁，2022年，8月28日571.4蟻群優化算法—技術問題1.4.1解的表達形式與算法的實現1.4.2每一節點的記憶信息和系數的確定1.4.3蟻群的規模和停止規則1.4.4信息素的更改第五十八頁，共八十一頁，2022年，8月28日581.4.1解的表達形式與算法的實現1/4

----解的表達形式解的表達形式基于TSP問題的蟻群優化算法，其解的形式是所有城市的一個排列（閉圈，這種情況下誰在第一并不重要），信息素痕跡按每個弧記錄。而對于一般以順序作為解的優化問題，誰在第一是很重要的。蟻群算法在解決這類問題時，只需要建立一個虛擬的始終點，就可以把TSP問題的解法推廣，用于諸多的優化問題。諸如車間作業及下料等問題，他們的共同特點是解以一個順序表示。TSP問題尋找的是最短回路，而一般優化問題中，STEP3中的判斷條件需要根據實際問題進行修改。第五十九頁，共八十一頁，2022年，8月28日59

解的表達形式與算法的實現2/4

----算法的實現例：0-1背包問題的解順序表達形式與算法實現。設有一個容積為b的背包，n個尺寸分別為，價值分別為的物品，0-1背包問題的數學模型為：假設其解的順序表達形式為，其中為的一個排列。第六十頁，共八十一頁，2022年，8月28日60

解的表達形式與算法的實現3/4

----算法的實現建立有向圖，其中A中共有條弧。初始信息素痕跡定義為。設第s只螞蟻第k步所走的路線為，表示螞蟻從0點出發，順序到達。第步按TSP算法的轉移概率公式行走選擇。若則，否則，此螞蟻不再繼續行走，退回起點。第六十一頁，共八十一頁，2022年，8月28日61

解的表達形式與算法的實現4/4----算法的實現對蟻群重復以上過程，比較m只螞蟻的裝包值 并記憶具有最大裝包值的螞蟻為t。把GBAS算法中步驟3中的改為，若滿足此條件則替換當前最好解為，對W上的弧進行信息素的加強，其他弧進行信息素的揮發。算法中記錄了三個信息：信息素痕跡；行走路線；和問題的約束條件 ，以確定是否將加入。第六十二頁，共八十一頁，2022年，8月28日62

每一節點的記憶信息和系數的確定----需要記憶的信息1/3算法中需要記憶的信息有三部分。第一部分信息是存在每個節點的路由表數據結構，由此決定的的轉移概率為其中T可以看成節點i的鄰域。第六十三頁，共八十一頁，2022年，8月28日631.4.2每一節點的記憶信息和系數的確定----需要記憶的信息2/3第二部分需要記憶的信息是每個螞蟻的記憶表中存儲著的自身的歷史信息，這一部分主要由算法的中的記憶，表示螞蟻已經行走過的節點。第三部分為問題的約束條件。在GBAS中，T集合表示滿足約束條件的候選集，在背包問題的蟻群算法中由判別條件， 來實現記

憶功能。第六十四頁，共八十一頁，2022年，8月28日641.4.2每一節點的記憶信息和系數的確定----系數的確定3/3

殘留信息的相對重要程度和預見值的相對重要程度體現了相關信息痕跡和預見度對螞蟻決策的相對影響。Dorigo在求解TSP問題時，推薦參數的最佳設置為：。第六十五頁，共八十一頁，2022年，8月28日651.4.3蟻群的規模和停止規則一、蟻群大小一般情況下蟻群中螞蟻的個數不超過TSP圖中節點的個數。二、終止條件

1給定一個外循環的最大數目，表明已經有足夠的螞蟻工作；

2當前最優解連續K次相同而停止，其中K是一個給定的整數，表示算法已經收斂，不再需要繼續；

3目標值控制規則，給定優化問題（目標最小化）的一個下界和一個誤差值，當算法得到的目標值同下界之差小于給定的誤差值時，算法終止。第六十六頁，共八十一頁，2022年，8月28日661.4.4信息素的更改1/6信息素的更新分為離線和在線兩種方式。離線方式（同步更新方式）的主要思想是在若干只螞蟻完成n個城市的訪問后，統一對殘留信息進行更新處理。信息素的在線更新（異步更新方式）即螞蟻每行走一步，立即回溯并且更新行走路徑上的信息素。第六十七頁，共八十一頁，2022年，8月28日67

信息素的更改2/6離線方式的信息素更新可以進一步分為單螞蟻離線更新和蟻群離線更新。蟻群離線更新方式是在蟻群中的m只螞蟻全部完成n城市的訪問（第k-1次蟻群循環）后，統一對殘留信息進行更新處理。其中，為第k-1次循環后的的信息素的痕跡值。單螞蟻離線更新是在第s只螞蟻完成對所有n個城市的訪問后，進行路徑回溯，更新行走路徑上的信息素，同時釋放分配給它的資源。更新公式為第s+1只螞蟻根據重新計算路由表。

第六十八頁，共八十一頁，2022年，8月28日68

信息素的更改3/6TSP問題中，蟻群優化算法根據信息素痕跡更新方式不同可以分為不同的算法，采用離線方式，并且時，其中W為t循環中m只螞蟻所行走的最佳路線或第t只螞蟻所行走的一條路徑。Q為一個常數，該算法名為蟻環算法（ant-cyclealgotithm）,特點是行走的路徑越短對應保存的信息素的值就越大。第六十九頁，共八十一頁，2022年，8月28日69

信息素的更改4/6

GBAS算法是典型的離線信息素更新方式。該算法中，蟻群中螞蟻的先后出行順序沒有相關性，但是每次循環需要記憶m只螞蟻的行走路徑，以進行比較選擇最優路徑。相對而言，單螞蟻離線更新方式記憶信息少，只需要記憶第s只螞蟻的路徑，并通過信息素更新后，釋放該螞蟻的所有記錄信息。實際上這種方式等價于蟻群離線方式中只有一只螞蟻。第七十頁，共八十一頁，2022年，8月28日70

信息素的更改5/6與單螞蟻離線更新方式相比，信息量記憶更小的是信息素在線更新方式，即螞蟻每走一步，馬上回溯并且更新剛剛走過的路徑上的信息素，其規則為其中，k為螞蟻行走的第k步。第七十一頁，共八十一頁，2022年，8月28日71

信息素的更改6/6

蟻量算法（ant-quantityalgorithm）的信息素更新為