蟻群算法介紹

蟻群算法介紹第1頁(yè)，共110頁(yè)，2023年，2月20日，星期日2內(nèi)容一、啟發(fā)式方法概述二、蟻群優(yōu)化算法第2頁(yè)，共110頁(yè)，2023年，2月20日，星期日3背景傳統(tǒng)實(shí)際問(wèn)題的特點(diǎn)連續(xù)性問(wèn)題——主要以微積分為基礎(chǔ)，且問(wèn)題規(guī)模較小傳統(tǒng)的優(yōu)化方法追求準(zhǔn)確——精確解理論的完美——結(jié)果漂亮主要方法：線性與非線性規(guī)劃、動(dòng)態(tài)規(guī)劃、多目標(biāo)規(guī)劃、整數(shù)規(guī)劃等；排隊(duì)論、庫(kù)存論、對(duì)策論、決策論等。傳統(tǒng)的評(píng)價(jià)方法算法收斂性（從極限角度考慮）收斂速度（線性、超線性、二次收斂等）第3頁(yè)，共110頁(yè)，2023年，2月20日，星期日4傳統(tǒng)運(yùn)籌學(xué)面臨新挑戰(zhàn)現(xiàn)代問(wèn)題的特點(diǎn)離散性問(wèn)題——主要以組合優(yōu)化（針對(duì)離散問(wèn)題，定義見(jiàn)后）理論為基礎(chǔ)不確定性問(wèn)題——隨機(jī)性數(shù)學(xué)模型半結(jié)構(gòu)或非結(jié)構(gòu)化的問(wèn)題——計(jì)算機(jī)模擬、決策支持系統(tǒng)大規(guī)模問(wèn)題——并行計(jì)算、大型分解理論、近似理論現(xiàn)代優(yōu)化方法追求滿意——近似解實(shí)用性強(qiáng)——解決實(shí)際問(wèn)題現(xiàn)代優(yōu)化算法的評(píng)價(jià)方法算法復(fù)雜性第4頁(yè)，共110頁(yè)，2023年，2月20日，星期日5現(xiàn)代優(yōu)化(啟發(fā)式)方法種類禁忌搜索（tabusearch）模擬退火（simulatedannealing）遺傳算法（geneticalgorithms）神經(jīng)網(wǎng)絡(luò)（neuralnetworks）蟻群算法（群體（群集）智能，SwarmIntelligence）拉格朗日松弛算法（lagrangeanrelaxation）第5頁(yè)，共110頁(yè)，2023年，2月20日，星期日61現(xiàn)代優(yōu)化計(jì)算方法概述1.1組合優(yōu)化問(wèn)題1.2計(jì)算復(fù)雜性的概念1.3啟發(fā)式算法第6頁(yè)，共110頁(yè)，2023年，2月20日，星期日71.1組合優(yōu)化問(wèn)題1/8組合優(yōu)化（combinatorialoptimization）:解決離散問(wèn)題的優(yōu)化問(wèn)題——運(yùn)籌學(xué)分支。通過(guò)數(shù)學(xué)方法的研究去尋找離散事件的最優(yōu)編排、分組、次序或篩選等，可以涉及信息技術(shù)、經(jīng)濟(jì)管理、工業(yè)工程、交通運(yùn)輸和通信網(wǎng)絡(luò)等許多方面。數(shù)學(xué)模型：第7頁(yè)，共110頁(yè)，2023年，2月20日，星期日81.1組合優(yōu)化問(wèn)題2/8組合優(yōu)化問(wèn)題的三參數(shù)表示：

第8頁(yè)，共110頁(yè)，2023年，2月20日，星期日91.1組合優(yōu)化問(wèn)題3/8例10-1背包問(wèn)題（0-1knapsackproblem）第9頁(yè)，共110頁(yè)，2023年，2月20日，星期日101.1組合優(yōu)化問(wèn)題4/8第10頁(yè)，共110頁(yè)，2023年，2月20日，星期日111.1組合優(yōu)化問(wèn)題5/8例2旅行商問(wèn)題（TSP,travelingsalesmanproblem）管梅谷教授1960年首先提出，國(guó)際上稱之為中國(guó)郵遞員問(wèn)題。問(wèn)題描述：一商人去n個(gè)城市銷貨，所有城市走一遍再回到起點(diǎn)，使所走路程最短。第11頁(yè)，共110頁(yè)，2023年，2月20日，星期日121.1組合優(yōu)化問(wèn)題6/8第12頁(yè)，共110頁(yè)，2023年，2月20日，星期日131.1組合優(yōu)化問(wèn)題7/8例3裝箱問(wèn)題（binpacking）尺寸為1的箱子有若干個(gè)，怎樣用最少的箱子裝下n個(gè)尺寸不超過(guò)1的物品，物品集合為：。

第13頁(yè)，共110頁(yè)，2023年，2月20日，星期日141.1組合優(yōu)化問(wèn)題8/8第14頁(yè)，共110頁(yè)，2023年，2月20日，星期日151.2計(jì)算復(fù)雜性的概念1/11評(píng)價(jià)算法的好壞——計(jì)算時(shí)間的多少、解的偏離程度例

非對(duì)稱距離TSP問(wèn)題的算法實(shí)現(xiàn)：所有路徑枚舉。計(jì)算時(shí)間：n個(gè)城市，固定1個(gè)為起終點(diǎn)需要(n-1)!個(gè)枚舉，設(shè)計(jì)算機(jī)1秒能完成24個(gè)城市的枚舉，則城市數(shù)與計(jì)算時(shí)間的關(guān)系如下表：第15頁(yè)，共110頁(yè)，2023年，2月20日，星期日161.2計(jì)算復(fù)雜性的概念2/11城市數(shù)2425262728293031計(jì)算時(shí)間1sec24sec10min4.3hour4.9day136.5day10.8year325year隨城市增多，計(jì)算時(shí)間增加很快。到31個(gè)城市時(shí)，要計(jì)算325年。描述算法的好壞——計(jì)算復(fù)雜性——討論計(jì)算時(shí)間與問(wèn)題規(guī)模之間的關(guān)系。以目前二進(jìn)制計(jì)算機(jī)中的存儲(chǔ)和計(jì)算為基礎(chǔ)，以理論的形式系統(tǒng)描述，是評(píng)估算法性能的基礎(chǔ)。第16頁(yè)，共110頁(yè)，2023年，2月20日，星期日171.2計(jì)算復(fù)雜性的概念3/11問(wèn)題（problem）：要回答的一般性提問(wèn)，通常含有若干個(gè)滿足一定條件的參數(shù)（或自由變量）?？梢詮膬煞矫婷枋觯海?）對(duì)所有參數(shù)的一般性描述；（2）答案（或解）必須滿足的性質(zhì)。實(shí)例（instance）:給問(wèn)題的所有參數(shù)指定具體值，得到問(wèn)題的一個(gè)實(shí)例。這些具體值稱為數(shù)據(jù)；這些數(shù)據(jù)輸入計(jì)算機(jī)所占的空間稱為實(shí)例的長(zhǎng)度（size）.第17頁(yè)，共110頁(yè)，2023年，2月20日，星期日181.2計(jì)算復(fù)雜性的概念4/11一類最優(yōu)化問(wèn)題是由一些類似的具體問(wèn)題（實(shí)例）組成的，每一個(gè)具體問(wèn)題可表達(dá)成二元組（F,C）.F為可行解集合;C是費(fèi)用函數(shù)，是由F到R（實(shí)數(shù)集）的映像。問(wèn)題是在F中找到一個(gè)點(diǎn)f*，使對(duì)F中任意的f，有C(f*)C(f),稱f*為這一具體問(wèn)題的最優(yōu)解（或全局最優(yōu)解）.第18頁(yè)，共110頁(yè)，2023年，2月20日，星期日191.2計(jì)算復(fù)雜性的概念5/11算法計(jì)算量的度量：加、減、乘、除、比較的總運(yùn)算次數(shù)與實(shí)例的計(jì)算機(jī)計(jì)算時(shí)的二進(jìn)制輸入數(shù)據(jù)的大小關(guān)系。正整數(shù)x的二進(jìn)制位數(shù)是:(整數(shù)到二進(jìn)制的轉(zhuǎn)換)

第19頁(yè)，共110頁(yè)，2023年，2月20日，星期日201.2計(jì)算復(fù)雜性的概念6/11算法計(jì)算量的度量之例——TSP枚舉法計(jì)算量的統(tǒng)計(jì)：第20頁(yè)，共110頁(yè)，2023年，2月20日，星期日211.2計(jì)算復(fù)雜性的概念7/11實(shí)例的輸入長(zhǎng)度：實(shí)例的輸入長(zhǎng)度是n的多項(xiàng)式函數(shù)枚舉法的基本計(jì)算量是n的階乘函數(shù)，隨n的增加，比指數(shù)函數(shù)增加得還快.第21頁(yè)，共110頁(yè)，2023年，2月20日，星期日221.2計(jì)算復(fù)雜性的概念8/11第22頁(yè)，共110頁(yè)，2023年，2月20日，星期日231.2計(jì)算復(fù)雜性的概念9/11定義多項(xiàng)式算法給定問(wèn)題P，算法A，對(duì)一個(gè)實(shí)例I，存在多項(xiàng)式函數(shù)g(x)，使（XX）成立，稱算法A對(duì)實(shí)例I是多項(xiàng)式算法；若存在多項(xiàng)式函數(shù)g(x)，使（XX）對(duì)問(wèn)題P的任意實(shí)例I都成立，稱算法A為解決該問(wèn)題P的多項(xiàng)式算法.當(dāng)g(x)為指數(shù)函數(shù)時(shí)，稱A為P的指數(shù)時(shí)間算法。第23頁(yè)，共110頁(yè)，2023年，2月20日，星期日241.2計(jì)算復(fù)雜性的概念10/11利用復(fù)雜性分析對(duì)組合優(yōu)化問(wèn)題歸類。定義多項(xiàng)式問(wèn)題給定一個(gè)組合優(yōu)化問(wèn)題，若存在一個(gè)多項(xiàng)式算法，稱該問(wèn)題為多項(xiàng)式時(shí)間可解問(wèn)題，或簡(jiǎn)稱多項(xiàng)式問(wèn)題(或P問(wèn)題).所有多項(xiàng)式問(wèn)題的集合記為P.例：線性規(guī)劃是否為多項(xiàng)式問(wèn)題？第24頁(yè)，共110頁(yè)，2023年，2月20日，星期日251.2計(jì)算復(fù)雜性參考書(shū)11/11計(jì)算復(fù)雜性,

作者：Christos，Papadimitriou

清華大學(xué)出版社，2004年9月第1版計(jì)算復(fù)雜性導(dǎo)論，作者：堵丁柱等，高等教育出版社，2002年8月第1版

第25頁(yè)，共110頁(yè)，2023年，2月20日，星期日261.3啟發(fā)式算法_定義1/6啟發(fā)式算法（heuristicalgorithm）定義1.基于直觀或經(jīng)驗(yàn)構(gòu)造的算法，在可接受的花費(fèi)（時(shí)間、空間）下，給出待解組合優(yōu)化問(wèn)題的每個(gè)實(shí)例的一個(gè)可行解，該可行解與最優(yōu)解偏差事先不一定可以預(yù)計(jì).定義2.啟發(fā)式算法是一種技術(shù)，在可接受的計(jì)算費(fèi)用內(nèi)尋找最好解，但不保證該解的可行性與最優(yōu)性，無(wú)法描述該解與最優(yōu)解的近似程度。特點(diǎn)（與傳統(tǒng)優(yōu)化方法不同）：憑直觀和經(jīng)驗(yàn)給出算法；不考慮所得解與最優(yōu)解的偏離程度.第26頁(yè)，共110頁(yè)，2023年，2月20日，星期日271.3啟發(fā)式算法_優(yōu)點(diǎn)2/6

優(yōu)點(diǎn)：（1）有可能比簡(jiǎn)化數(shù)學(xué)模型解的誤差小；（2）對(duì)有些難題，計(jì)算時(shí)間可接受；（3）可用于某些最優(yōu)化算法（如分支定界算法）之中的估界；（4）直觀易行；（5）速度較快；（6）程序簡(jiǎn)單，易修改。第27頁(yè)，共110頁(yè)，2023年，2月20日，星期日281.3啟發(fā)式算法_不足3/6不足：（1）不能保證求得全局最優(yōu)解；（2）解的精度不穩(wěn)定，有時(shí)好有時(shí)壞；（3）算法設(shè)計(jì)與問(wèn)題、設(shè)計(jì)者經(jīng)驗(yàn)、技術(shù)有關(guān)，缺乏規(guī)律性；（4）不同算法之間難以比較。第28頁(yè)，共110頁(yè)，2023年，2月20日，星期日291.3啟發(fā)式算法_分類4/6（1）一步算法（2）改進(jìn)算法（迭代算法）(3)數(shù)學(xué)規(guī)劃算法(4)解空間松弛法

第29頁(yè)，共110頁(yè)，2023年，2月20日，星期日301.3啟發(fā)式算法_分類5/6（5）現(xiàn)代優(yōu)化算法：80年代初興起禁忌搜索（tabusearch）模擬退火（simulatedannealing）遺傳算法（geneticalgorithms）神經(jīng)網(wǎng)絡(luò)（neuralnetworks）螞蟻算法（AntAlgorithm，群體（群集）智能，SwarmIntelligence）（6）其他算法：多種啟發(fā)式算法的集成.第30頁(yè)，共110頁(yè)，2023年，2月20日，星期日311.3啟發(fā)式算法_性能分析6/6（1）最壞情形分析（worstcaseanalysis）

利用最壞實(shí)例分析計(jì)算復(fù)雜性、解的效果。

(2）概率分析（probabilityanalysis）

用最壞情況分析，會(huì)因一個(gè)最壞實(shí)例影響總體評(píng)價(jià).在實(shí)例數(shù)據(jù)服從一定概率分布情形下，研究算法復(fù)雜性和解的效果.

(3)大規(guī)模計(jì)算分析通過(guò)大量實(shí)例計(jì)算，評(píng)價(jià)算法效果.注意數(shù)據(jù)的隨機(jī)性和代表性.第31頁(yè)，共110頁(yè)，2023年，2月20日，星期日322蟻群優(yōu)化算法蟻群優(yōu)化算法概述蟻群優(yōu)化算法概念算法模型和收斂性分析算法實(shí)現(xiàn)的技術(shù)問(wèn)題應(yīng)用參考資料第32頁(yè)，共110頁(yè)，2023年，2月20日，星期日332.1蟻群優(yōu)化算法概述2.1.1起源2.1.2應(yīng)用領(lǐng)域2.1.3研究背景2.1.4研究現(xiàn)狀2.1.5應(yīng)用現(xiàn)狀第33頁(yè)，共110頁(yè)，2023年，2月20日，星期日342.1.1蟻群優(yōu)化算法起源

20世紀(jì)50年代中期創(chuàng)立了仿生學(xué)，人們從生物進(jìn)化的機(jī)理中受到啟發(fā)。提出了許多用以解決復(fù)雜優(yōu)化問(wèn)題的新方法，如進(jìn)化規(guī)劃、進(jìn)化策略、遺傳算法等，這些算法成功地解決了一些實(shí)際問(wèn)題。

20世紀(jì)90年代意大利學(xué)者M(jìn)．Dorigo，V．Maniezzo，A．Colorni等從生物進(jìn)化的機(jī)制中受到啟發(fā)，通過(guò)模擬自然界螞蟻搜索路徑的行為，提出來(lái)一種新型的模擬進(jìn)化算法——

蟻群算法，是群智能理論研究領(lǐng)域的一種主要算法。用該方法求解TSP問(wèn)題、分配問(wèn)題、job-shop調(diào)度問(wèn)題，取得了較好的試驗(yàn)結(jié)果．雖然研究時(shí)間不長(zhǎng)，但是現(xiàn)在的研究顯示出，蟻群算法在求解復(fù)雜優(yōu)化問(wèn)題（特別是離散優(yōu)化問(wèn)題）方面有一定優(yōu)勢(shì)，表明它是一種有發(fā)展前景的算法．第34頁(yè)，共110頁(yè)，2023年，2月20日，星期日352.1.2蟻群優(yōu)化算法應(yīng)用領(lǐng)域

這種方法能夠被用于解決大多數(shù)優(yōu)化問(wèn)題或者能夠轉(zhuǎn)化為優(yōu)化求解的問(wèn)題?，F(xiàn)在其應(yīng)用領(lǐng)域已擴(kuò)展到多目標(biāo)優(yōu)化、數(shù)據(jù)分類、數(shù)據(jù)聚類、模式識(shí)別、電信QoS管理、生物系統(tǒng)建模、流程規(guī)劃、信號(hào)處理、機(jī)器人控制、決策支持以及仿真和系統(tǒng)辯識(shí)等方面，群智能理論和方法為解決這類應(yīng)用問(wèn)題提供了新的途徑。第35頁(yè)，共110頁(yè)，2023年，2月20日，星期日362.1.3蟻群優(yōu)化算法研究背景1/3群智能理論研究領(lǐng)域有兩種主要的算法：蟻群算法(AntColonyOptimization,ACO)和微粒群算法（ParticleSwarmOptimization,PSO）。前者是對(duì)螞蟻群落食物采集過(guò)程的模擬，已成功應(yīng)用于許多離散優(yōu)化問(wèn)題。微粒群算法也是起源于對(duì)簡(jiǎn)單社會(huì)系統(tǒng)的模擬，最初是模擬鳥(niǎo)群覓食的過(guò)程，但后來(lái)發(fā)現(xiàn)它是一種很好的優(yōu)化工具。

第36頁(yè)，共110頁(yè)，2023年，2月20日，星期日372.1.3蟻群優(yōu)化算法研究背景2/3與大多數(shù)基于梯度的應(yīng)用優(yōu)化算法不同，群智能依靠的是概率搜索算法。雖然概率搜索算法通常要采用較多的評(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)單

第37頁(yè)，共110頁(yè)，2023年，2月20日，星期日382.1.3蟻群優(yōu)化算法研究背景3/3群智能方法易于實(shí)現(xiàn)，算法中僅涉及各種基本的數(shù)學(xué)操作，其數(shù)據(jù)處理過(guò)程對(duì)CPU和內(nèi)存的要求也不高。而且，這種方法只需目標(biāo)函數(shù)的輸出值，而無(wú)需其梯度信息。已完成的群智能理論和應(yīng)用方法研究證明群智能方法是一種能夠有效解決大多數(shù)全局優(yōu)化問(wèn)題的新方法。更為重要是，群智能潛在的并行性和分布式特點(diǎn)為處理大量的以數(shù)據(jù)庫(kù)形式存在的數(shù)據(jù)提供了技術(shù)保證。無(wú)論是從理論研究還是應(yīng)用研究的角度分析，群智能理論及其應(yīng)用研究都是具有重要學(xué)術(shù)意義和現(xiàn)實(shí)價(jià)值的。

第38頁(yè)，共110頁(yè)，2023年，2月20日，星期日392.1.4蟻群優(yōu)化算法研究現(xiàn)狀1/7

90年代Dorigo最早提出了蟻群優(yōu)化算法---螞蟻系統(tǒng)（AntSystem,AS）并將其應(yīng)用于解決計(jì)算機(jī)算法學(xué)中經(jīng)典的旅行商問(wèn)題（TSP）。從螞蟻系統(tǒng)開(kāi)始，基本的蟻群算法得到了不斷的發(fā)展和完善，并在TSP以及許多實(shí)際優(yōu)化問(wèn)題求解中進(jìn)一步得到了驗(yàn)證。這些AS改進(jìn)版本的一個(gè)共同點(diǎn)就是增強(qiáng)了螞蟻搜索過(guò)程中對(duì)最優(yōu)解的探索能力，它們之間的差異僅在于搜索控制策略方面。而且，取得了最佳結(jié)果的ACO是通過(guò)引入局部搜索算法實(shí)現(xiàn)的，這實(shí)際上是一些結(jié)合了標(biāo)準(zhǔn)局域搜索算法的混合型概率搜索算法，有利于提高蟻群各級(jí)系統(tǒng)在優(yōu)化問(wèn)題中的求解質(zhì)量。第39頁(yè)，共110頁(yè)，2023年，2月20日，星期日402.1.4蟻群優(yōu)化算法研究現(xiàn)狀2/7最初提出的AS有三種版本：Ant-density、Ant-quantity和Ant-cycle。在Ant-density和Ant-quantity中螞蟻在兩個(gè)位置節(jié)點(diǎn)間每移動(dòng)一次后即更新信息素，而在Ant-cycle中當(dāng)所有的螞蟻都完成了自己的行程后才對(duì)信息素進(jìn)行更新，而且每個(gè)螞蟻所釋放的信息素被表達(dá)為反映相應(yīng)行程質(zhì)量的函數(shù)。通過(guò)與其它各種通用的啟發(fā)式算法相比，在不大于75城市的TSP中，這三種基本算法的求解能力還是比較理想的，但是當(dāng)問(wèn)題規(guī)模擴(kuò)展時(shí)，AS的解題能力大幅度下降。因此，其后的ACO研究工作主要都集中于AS性能的改進(jìn)方面。較早的一種改進(jìn)方法是精英策略(ElitistStrategy)，其思想是在算法開(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ì)。這種改進(jìn)型算法能夠以更快的速度獲得更好的解。但是若選擇的精英過(guò)多則算法會(huì)由于較早的收斂于局部次優(yōu)解而導(dǎo)致搜索的過(guò)早停滯。

第40頁(yè)，共110頁(yè)，2023年，2月20日，星期日412.1.4蟻群優(yōu)化算法研究現(xiàn)狀3/7

為了進(jìn)一步克服AS中暴露出的問(wèn)題，提出了蟻群系統(tǒng)(AntColonySystem,ACS)。該系統(tǒng)的提出是以Ant-Q算法為基礎(chǔ)的。Ant-Q將螞蟻算法和一種增強(qiáng)型學(xué)習(xí)算法Q-learning有機(jī)的結(jié)合了起來(lái)。ACS與AS之間存在三方面的主要差異：首先，ACS采用了更為大膽的行為選擇規(guī)則；其次，只增強(qiáng)屬于全局最優(yōu)解的路徑上的信息素。其中，0<ρ<1是信息素?fù)]發(fā)參數(shù)，是從尋路開(kāi)始到當(dāng)前為止全局最優(yōu)的路徑長(zhǎng)度。第41頁(yè)，共110頁(yè)，2023年，2月20日，星期日422.1.4蟻群優(yōu)化算法研究現(xiàn)狀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ò)的路徑再次被選擇的概率。

第42頁(yè)，共110頁(yè)，2023年，2月20日，星期日432.1.4蟻群優(yōu)化算法研究現(xiàn)狀5/7在對(duì)AS進(jìn)行直接完善的方法中，MAX-MINAntSystem是一個(gè)典型代表。該算法修改了AS的信息素更新方式，每次迭代之后只有一只螞蟻能夠進(jìn)行信息素的更新以獲取更好的解。為了避免搜索停滯，路徑上的信息素濃度被限制在[MAX，MIN]范圍內(nèi)，另外，信息素的初始值被設(shè)為其取值上限，這樣有助于增加算法初始階段的搜索能力。第43頁(yè)，共110頁(yè)，2023年，2月20日，星期日442.1.4蟻群優(yōu)化算法研究現(xiàn)狀6/7

另一種對(duì)AS改進(jìn)的算法是Rank-basedVersionAS。與“精英策略”相似，在此算法中總是更新更好進(jìn)程上的信息素，選擇的標(biāo)準(zhǔn)是其行程長(zhǎng)度決定的排序，且每個(gè)螞蟻放置信息素的強(qiáng)度通過(guò)下式中的排序加權(quán)處理確定，其中，ｗ為每次迭代后放置信息素的螞蟻總數(shù)。

第44頁(yè)，共110頁(yè)，2023年，2月20日，星期日452.1.4蟻群優(yōu)化算法研究現(xiàn)狀7/7這種算法求解TSP的能力與AS、精英策略AS、遺傳算法和模擬退火算法進(jìn)行了比較。在大型TSP問(wèn)題中（最多包含132座城市），基于AS的算法都顯示出了優(yōu)于GA和SA的特性。而且在Rank-basedAS和精英策略AS均優(yōu)于基本AS的同時(shí)，前者還獲得了比精英策略AS更好的解。

第45頁(yè)，共110頁(yè)，2023年，2月20日，星期日462.1.5蟻群優(yōu)化算法應(yīng)用現(xiàn)狀1/5

隨著群智能理論和應(yīng)用算法研究的不斷發(fā)展，研究者已嘗試著將其用于各種工程優(yōu)化問(wèn)題，并取得了意想不到的收獲。多種研究表明，群智能在離散求解空間和連續(xù)求解空間中均表現(xiàn)出良好的搜索效果，并在組合優(yōu)化問(wèn)題中表現(xiàn)突出。蟻群優(yōu)化算法并不是旅行商問(wèn)題的最佳解決方法，但是它卻為解決組合優(yōu)化問(wèn)題提供了新思路，并很快被應(yīng)用到其它組合優(yōu)化問(wèn)題中。比較典型的應(yīng)用研究包括：網(wǎng)絡(luò)路由優(yōu)化、數(shù)據(jù)挖掘以及一些經(jīng)典的組合優(yōu)化問(wèn)題。

第46頁(yè)，共110頁(yè)，2023年，2月20日，星期日472.1.5蟻群優(yōu)化算法應(yīng)用現(xiàn)狀2/5蟻群算法在電信路由優(yōu)化中已取得了一定的應(yīng)用成果。HP公司和英國(guó)電信公司在90年代中后期都開(kāi)展了這方面的研究，設(shè)計(jì)了蟻群路由算法（AntColonyRouting,ACR）。每只螞蟻就像蟻群優(yōu)化算法中一樣，根據(jù)它在網(wǎng)絡(luò)上的經(jīng)驗(yàn)與性能，動(dòng)態(tài)更新路由表項(xiàng)。如果一只螞蟻因?yàn)榻?jīng)過(guò)了網(wǎng)絡(luò)中堵塞的路由而導(dǎo)致了比較大的延遲，那么就對(duì)該表項(xiàng)做較大的增強(qiáng)。同時(shí)根據(jù)信息素?fù)]發(fā)機(jī)制實(shí)現(xiàn)系統(tǒng)的信息更新，從而拋棄過(guò)期的路由信息。這樣，在當(dāng)前最優(yōu)路由出現(xiàn)擁堵現(xiàn)象時(shí)，ACR算法就能迅速的搜尋另一條可替代的最優(yōu)路徑，從而提高網(wǎng)絡(luò)的均衡性、負(fù)荷量和利用率。目前這方面的應(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ì)和特性非常相似。第47頁(yè)，共110頁(yè)，2023年，2月20日，星期日482.1.5蟻群優(yōu)化算法應(yīng)用現(xiàn)狀3/5

基于群智能的聚類算法起源于對(duì)蟻群蟻卵的分類研究。Lumer和Faieta將Deneubourg提出將蟻巢分類模型應(yīng)用于數(shù)據(jù)聚類分析。其基本思想是將待聚類數(shù)據(jù)隨機(jī)地散布到一個(gè)二維平面內(nèi)，然后將虛擬螞蟻分布到這個(gè)空間內(nèi)，并以隨機(jī)方式移動(dòng)，當(dāng)一只螞蟻遇到一個(gè)待聚類數(shù)據(jù)時(shí)即將之拾起并繼續(xù)隨機(jī)運(yùn)動(dòng)，若運(yùn)動(dòng)路徑附近的數(shù)據(jù)與背負(fù)的數(shù)據(jù)相似性高于設(shè)置的標(biāo)準(zhǔn)則將其放置在該位置，然后繼續(xù)移動(dòng)，重復(fù)上述數(shù)據(jù)搬運(yùn)過(guò)程。按照這樣的方法可實(shí)現(xiàn)對(duì)相似數(shù)據(jù)的聚類。第48頁(yè)，共110頁(yè)，2023年，2月20日，星期日492.1.5蟻群優(yōu)化算法應(yīng)用現(xiàn)狀4/5

ACO還在許多經(jīng)典組合優(yōu)化問(wèn)題中獲得了成功的應(yīng)用，如二次規(guī)劃問(wèn)題（QAP）、機(jī)器人路徑規(guī)劃、作業(yè)流程規(guī)劃、圖著色（GraphColoring）等問(wèn)題。經(jīng)過(guò)多年的發(fā)展，ACO已成為能夠有效解決實(shí)際二次規(guī)劃問(wèn)題的幾種重要算法之一。AS在作業(yè)流程計(jì)劃（Job-shopScheduling）問(wèn)題中的應(yīng)用實(shí)例已經(jīng)出現(xiàn)，這說(shuō)明了AS在此領(lǐng)域的應(yīng)用潛力。利用MAX-MINAS解決PAQ也取得了比較理想的效果，并通過(guò)實(shí)驗(yàn)中的計(jì)算數(shù)據(jù)證明采用該方法處理PAQ比較早的SA算法更好，且與禁忌搜索算法性能相當(dāng)。利用ACO實(shí)現(xiàn)對(duì)生產(chǎn)流程和特料管理的綜合優(yōu)化，并通過(guò)與遺傳、模擬退火和禁忌搜索算法的比較證明了ACO的工程應(yīng)用價(jià)值。第49頁(yè)，共110頁(yè)，2023年，2月20日，星期日502.1.5蟻群優(yōu)化算法應(yīng)用現(xiàn)狀5/5許多研究者將ACO用于了武器攻擊目標(biāo)分配和優(yōu)化問(wèn)題、車輛運(yùn)行路徑規(guī)劃、區(qū)域性無(wú)線電頻率自動(dòng)分配、Bayesiannetworks的訓(xùn)練和集合覆蓋等應(yīng)用優(yōu)化問(wèn)題。Costa和Herz還提出了一種AS在規(guī)劃問(wèn)題方面的擴(kuò)展應(yīng)用——圖著色問(wèn)題，并取得了可與其他啟發(fā)式算法相比的效果。第50頁(yè)，共110頁(yè)，2023年，2月20日，星期日512.2蟻群優(yōu)化算法概念 2.2.1蟻群算法原理2.2.2簡(jiǎn)化的螞蟻尋食過(guò)程2.2.3自然蟻群與人工蟻群算法2.2.4蟻群算法與TSP問(wèn)題2.2.5初始的蟻群優(yōu)化算法—基于圖的蟻群系統(tǒng)（GBAS）2.2.6一般蟻群算法的框架第51頁(yè)，共110頁(yè)，2023年，2月20日，星期日522.2.1蟻群算法原理

蟻群算法是對(duì)自然界螞蟻的尋徑方式進(jìn)行模似而得出的一種仿生算法。螞蟻在運(yùn)動(dòng)過(guò)程中，能夠在它所經(jīng)過(guò)的路徑上留下一種稱之為外激素(pheromone)的物質(zhì)進(jìn)行信息傳遞，而且螞蟻在運(yùn)動(dòng)過(guò)程中能夠感知這種物質(zhì)，并以此指導(dǎo)自己的運(yùn)動(dòng)方向，因此由大量螞蟻組成的蟻群集體行為便表現(xiàn)出一種信息正反饋現(xiàn)象：某一路徑上走過(guò)的螞蟻越多，則后來(lái)者選擇該路徑的概率就越大。為了說(shuō)明蟻群算法的原理，先簡(jiǎn)要介紹一下螞蟻搜尋食物的具體過(guò)程。在蟻群尋找食物時(shí)，它們總能找到一條從食物到巢穴之間的最優(yōu)路徑。這是因?yàn)槲浵佋趯ふ衣窂綍r(shí)會(huì)在路徑上釋放出一種特殊的信息素。當(dāng)它們碰到一個(gè)還沒(méi)有走過(guò)的路口時(shí)．就隨機(jī)地挑選一條路徑前行。與此同時(shí)釋放出與路徑長(zhǎng)度有關(guān)的信息素。路徑越長(zhǎng)，釋放的激索濃度越低.當(dāng)后來(lái)的螞蟻再次碰到這個(gè)路口的時(shí)候．選擇激素濃度較高路徑概率就會(huì)相對(duì)較大。這樣形成一個(gè)正反饋。最優(yōu)路徑上的激索濃度越來(lái)越大．而其它的路徑上激素濃度卻會(huì)隨著時(shí)間的流逝而消減。最終整個(gè)蟻群會(huì)找出最優(yōu)路徑。第52頁(yè)，共110頁(yè)，2023年，2月20日，星期日532.2.2簡(jiǎn)化的螞蟻尋食過(guò)程1/3螞蟻從A點(diǎn)出發(fā)，速度相同，食物在D點(diǎn)，可能隨機(jī)選擇路線ABD或ACD。假設(shè)初始時(shí)每條分配路線一只螞蟻，每個(gè)時(shí)間單位行走一步，本圖為經(jīng)過(guò)9個(gè)時(shí)間單位時(shí)的情形：走ABD的螞蟻到達(dá)終點(diǎn)，而走ACD的螞蟻剛好走到C點(diǎn)，為一半路程。第53頁(yè)，共110頁(yè)，2023年，2月20日，星期日542.2.2

簡(jiǎn)化的螞蟻尋食過(guò)程2/3本圖為從開(kāi)始算起，經(jīng)過(guò)18個(gè)時(shí)間單位時(shí)的情形：走ABD的螞蟻到達(dá)終點(diǎn)后得到食物又返回了起點(diǎn)A，而走ACD的螞蟻剛好走到D點(diǎn)。第54頁(yè)，共110頁(yè)，2023年，2月20日，星期日552.2.2簡(jiǎn)化的螞蟻尋食過(guò)程3/3

假設(shè)螞蟻每經(jīng)過(guò)一處所留下的信息素為一個(gè)單位，則經(jīng)過(guò)36個(gè)時(shí)間單位后，所有開(kāi)始一起出發(fā)的螞蟻都經(jīng)過(guò)不同路徑從D點(diǎn)取得了食物，此時(shí)ABD的路線往返了2趟，每一處的信息素為4個(gè)單位，而ACD的路線往返了一趟，每一處的信息素為2個(gè)單位，其比值為2：1。尋找食物的過(guò)程繼續(xù)進(jìn)行，則按信息素的指導(dǎo)，蟻群在ABD路線上增派一只螞蟻（共2只），而ACD路線上仍然為一只螞蟻。再經(jīng)過(guò)36個(gè)時(shí)間單位后，兩條線路上的信息素單位積累為12和4，比值為3：1。若按以上規(guī)則繼續(xù)，蟻群在ABD路線上再增派一只螞蟻（共3只），而ACD路線上仍然為一只螞蟻。再經(jīng)過(guò)36個(gè)時(shí)間單位后，兩條線路上的信息素單位積累為24和6，比值為4：1。若繼續(xù)進(jìn)行，則按信息素的指導(dǎo)，最終所有的螞蟻會(huì)放棄ACD路線，而都選擇ABD路線。這也就是前面所提到的正反饋效應(yīng)。第55頁(yè)，共110頁(yè)，2023年，2月20日，星期日562.2.3自然蟻群與人工蟻群算法基于以上蟻群尋找食物時(shí)的最優(yōu)路徑選擇問(wèn)題，可以構(gòu)造人工蟻群，來(lái)解決最優(yōu)化問(wèn)題，如TSP問(wèn)題。人工蟻群中把具有簡(jiǎn)單功能的工作單元看作螞蟻。二者的相似之處在于都是優(yōu)先選擇信息素濃度大的路徑。較短路徑的信息素濃度高，所以能夠最終被所有螞蟻選擇，也就是最終的優(yōu)化結(jié)果。兩者的區(qū)別在于人工蟻群有一定的記憶能力，能夠記憶已經(jīng)訪問(wèn)過(guò)的節(jié)點(diǎn)。同時(shí)，人工蟻群再選擇下一條路徑的時(shí)候是按一定算法規(guī)律有意識(shí)地尋找最短路徑，而不是盲目的。例如在TSP問(wèn)題中，可以預(yù)先知道當(dāng)前城市到下一個(gè)目的地的距離。第56頁(yè)，共110頁(yè)，2023年，2月20日，星期日572.2.4蟻群算法與TSP問(wèn)題1/3TSP問(wèn)題表示為一個(gè)N個(gè)城市的有向圖G=（N，A），其中 城市之間距離目標(biāo)函數(shù)為，其中為城市1,2，…n的一個(gè)排列，。第57頁(yè)，共110頁(yè)，2023年，2月20日，星期日582.2.4蟻群算法與TSP問(wèn)題2/3

TSP問(wèn)題的人工蟻群算法中，假設(shè)m只螞蟻在圖的相鄰節(jié)點(diǎn)間移動(dòng)，從而協(xié)作異步地得到問(wèn)題的解。每只螞蟻的一步轉(zhuǎn)移概率由圖中的每條邊上的兩類參數(shù)決定：1信息素值也稱信息素痕跡。2可見(jiàn)度，即先驗(yàn)值。信息素的更新方式有2種，一是揮發(fā)，也就是所有路徑上的信息素以一定的比率進(jìn)行減少，模擬自然蟻群的信息素隨時(shí)間揮發(fā)的過(guò)程；二是增強(qiáng)，給評(píng)價(jià)值“好”(有螞蟻?zhàn)哌^(guò))的邊增加信息素。第58頁(yè)，共110頁(yè)，2023年，2月20日，星期日592.2.4蟻群算法與TSP問(wèn)題3/3

螞蟻向下一個(gè)目標(biāo)的運(yùn)動(dòng)是通過(guò)一個(gè)隨機(jī)原則來(lái)實(shí)現(xiàn)的，也就是運(yùn)用當(dāng)前所在節(jié)點(diǎn)存儲(chǔ)的信息，計(jì)算出下一步可達(dá)節(jié)點(diǎn)的概率，并按此概率實(shí)現(xiàn)一步移動(dòng)，逐此往復(fù)，越來(lái)越接近最優(yōu)解。螞蟻在尋找過(guò)程中，或者找到一個(gè)解后，會(huì)評(píng)估該解或解的一部分的優(yōu)化程度，并把評(píng)價(jià)信息保存在相關(guān)連接的信息素中。第59頁(yè)，共110頁(yè)，2023年，2月20日，星期日602.2.5初始的蟻群優(yōu)化算法—基于圖的蟻群系統(tǒng)（GBAS）1/12初始的蟻群算法是基于圖的蟻群算法，graph-basedantsystem,簡(jiǎn)稱為GBAS，是由GutjahrWJ在2000年的FutureGenerationComputingSystems提出的，課本的參考文獻(xiàn)2。算法步驟如下：STEP0

對(duì)n個(gè)城市的TSP問(wèn)題，城市間的距離矩陣為，給TSP圖中的每一條弧賦信息素初值，假設(shè)m只螞蟻在工作，所有螞蟻都從同一城市出發(fā)。當(dāng)前最好解是 。第60頁(yè)，共110頁(yè)，2023年，2月20日，星期日612.2.5初始的蟻群優(yōu)化算法—基于圖的蟻群系統(tǒng)（GBAS）2/12STEP1

（外循環(huán)）如果滿足算法的停止規(guī)則，則停止計(jì)算并輸出計(jì)算得到的最好解。否則使螞蟻s從起點(diǎn)出發(fā)，用表示螞蟻s行走的城市集合，初始為空集，。STEP2(內(nèi)循環(huán))按螞蟻的順序分別計(jì)算。當(dāng)螞蟻在城市i，若 完成第s只螞蟻的計(jì)算。否則，若，則以概率 ， 到達(dá)j， ；若則到達(dá) 重復(fù)STEP2。第61頁(yè)，共110頁(yè)，2023年，2月20日，星期日622.2.5初始的蟻群優(yōu)化算法—基于圖的蟻群系統(tǒng)（GBAS）3/12STRP3

對(duì) ，若，按中城市的順序計(jì)算路徑程度；若，路徑長(zhǎng)度置為一個(gè)無(wú)窮大值（即不可達(dá)）。比較m只螞蟻中的路徑長(zhǎng)度，記走最短路徑的螞蟻為t。若，則。用如下公式對(duì)W路徑上的信息素痕跡加強(qiáng)，對(duì)其他路徑上的信息素進(jìn)行揮發(fā)。得到新的，重復(fù)步驟STEP1。第62頁(yè)，共110頁(yè)，2023年，2月20日，星期日632.2.5初始的蟻群優(yōu)化算法—基于圖的蟻群系統(tǒng)（GBAS）4/12在STEP3

中，揮發(fā)因子對(duì)于一個(gè)固定的，滿足并且

經(jīng)過(guò)k次揮發(fā)，非最優(yōu)路徑的信息素逐漸減少至消失。第63頁(yè)，共110頁(yè)，2023年，2月20日，星期日642.2.5初始的蟻群優(yōu)化算法—基于圖的蟻群系統(tǒng)（GBAS）5/12以上算法中，在螞蟻的搜尋過(guò)程中，以信息素的概率分布來(lái)決定從城市i到城市j的轉(zhuǎn)移。算法中包括信息素更新的過(guò)程

1信息素?fù)]發(fā)（evaporation）信息素痕跡的揮發(fā)過(guò)程是每個(gè)連接上的信息素痕跡的濃度自動(dòng)逐漸減弱的過(guò)程，由表示，這個(gè)揮發(fā)過(guò)程主要用于避免算法過(guò)快地向局部最優(yōu)區(qū)域集中，有助于搜索區(qū)域的擴(kuò)展。

2信息素增強(qiáng)（reinforcement）增強(qiáng)過(guò)程是蟻群優(yōu)化算法中可選的部分，稱為離線更新方式（還有在線更新方式）。這種方式可以實(shí)現(xiàn)由單個(gè)螞蟻無(wú)法實(shí)現(xiàn)的集中行動(dòng)。也就是說(shuō)，增強(qiáng)過(guò)程體現(xiàn)在觀察蟻群（m只螞蟻）中每只螞蟻所找到的路徑，并選擇其中最優(yōu)路徑上的弧進(jìn)行信息素的增強(qiáng)，揮發(fā)過(guò)程是所有弧都進(jìn)行的，不于螞蟻數(shù)量相關(guān)。這種增強(qiáng)過(guò)程中進(jìn)行的信息素更新稱為離線的信息素更新。在STEP3中，蟻群永遠(yuǎn)記憶到目前為止的最優(yōu)解。第64頁(yè)，共110頁(yè)，2023年，2月20日，星期日65圖的蟻群系統(tǒng)（GBAS）6/12可以驗(yàn)證，下式滿足：即是一個(gè)隨機(jī)矩陣。四個(gè)城市的非對(duì)稱TSP問(wèn)題，距離矩陣和城市圖示如下：第65頁(yè)，共110頁(yè)，2023年，2月20日，星期日662.2.5初始的蟻群優(yōu)化算法—基于圖的蟻群系統(tǒng)（GBAS）7/12假設(shè)共4只螞蟻，所有螞蟻都從城市A出發(fā)，揮發(fā)因子。此時(shí)，觀察GBAS的計(jì)算過(guò)程。矩陣共有12條弧，初始信息素記憶矩陣為：第66頁(yè)，共110頁(yè)，2023年，2月20日，星期日672.2.5初始的蟻群優(yōu)化算法—基于圖的蟻群系統(tǒng)（GBAS）8/12執(zhí)行GBAS算法的步驟2，假設(shè)螞蟻的行走路線分別為：當(dāng)前最優(yōu)解為，這個(gè)解是截止到當(dāng)前的最優(yōu)解，碰巧是實(shí)際最優(yōu)解第67頁(yè)，共110頁(yè)，2023年，2月20日，星期日682.2.5初始的蟻群優(yōu)化算法—基于圖的蟻群系統(tǒng)（GBAS）9/12按算法步驟3的信息素更新規(guī)則，得到更新矩陣這是第一次外循環(huán)結(jié)束的狀態(tài)。第68頁(yè)，共110頁(yè)，2023年，2月20日，星期日692.2.5初始的蟻群優(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ā)。得到更新矩陣這是第一次外循環(huán)結(jié)束的狀態(tài)。第69頁(yè)，共110頁(yè)，2023年，2月20日，星期日702.2.5初始的蟻群優(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ā)。第三次外循環(huán)后得到的信息素矩陣為：第70頁(yè)，共110頁(yè)，2023年，2月20日，星期日712.2.5初始的蟻群優(yōu)化算法—基于圖的蟻群系統(tǒng)（GBAS）12/12螞蟻以一定的概率從城市i到城市j進(jìn)行轉(zhuǎn)移，信息素的更新在STEP3完成，并隨K而變化。假設(shè)第K次外循環(huán)后得到信息素矩陣，得到當(dāng)前最優(yōu)解。第K次循環(huán)前的信息素和最優(yōu)解為，經(jīng)過(guò)第K次外循環(huán)后，得到。由于螞蟻的一步轉(zhuǎn)移概率是隨機(jī)的，從到也是隨機(jī)的，是一個(gè)馬爾可夫過(guò)程。第71頁(yè)，共110頁(yè)，2023年，2月20日，星期日722.2.6一般蟻群算法的框架一般蟻群算法的框架和GBAS基本相同，有三個(gè)組成部分：蟻群的活動(dòng)；信息素的揮發(fā)；信息素的增強(qiáng)；主要體現(xiàn)在前面的算法中步驟2和步驟3中的轉(zhuǎn)移概率公式和信息素更新公式。第72頁(yè)，共110頁(yè)，2023年，2月20日，星期日732.3蟻群優(yōu)化算法—算法模型和收斂性分析2.3.0馬氏過(guò)程的收斂定義2.3.1GBAS算法的收斂性分析2.3.2其他算法及收斂性分析第73頁(yè)，共110頁(yè)，2023年，2月20日，星期日742.3.0馬氏過(guò)程的收斂定義蟻群優(yōu)化算法的每步迭代對(duì)應(yīng)隨機(jī)變量其中為信息素痕跡；為n城市的一個(gè)排列，最多有個(gè)狀態(tài)。第s只螞蟻在第k輪轉(zhuǎn)移只由決定，這個(gè)螞蟻行走的路徑和一起，共同決定了，再通過(guò)信息素的更新原則可以進(jìn)一步得到。的變化僅由決定，而與先前的狀態(tài)無(wú)關(guān)，這是一個(gè)典型的馬爾可夫過(guò)程。

定義：若一個(gè)馬爾可夫過(guò)程，對(duì)任意給定的滿足

則稱馬爾可夫過(guò)程依概率1收斂到。第74頁(yè)，共110頁(yè)，2023年，2月20日，星期日752.3.1GBAS算法的收斂性分析1/8

定理

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

證明分析:蟻群算法中,一但達(dá)到全局最優(yōu),由只記錄第一個(gè)最優(yōu)解.證明分三部分:

證明以概率1達(dá)到一個(gè)最優(yōu)路徑證明(1)上式成立證明以概率1收斂到一個(gè)最優(yōu)路徑第75頁(yè)，共110頁(yè)，2023年，2月20日，星期日762.3.1GBAS算法的收斂性分析2/8證明以概率1到達(dá)一個(gè)最優(yōu)路徑對(duì)于最優(yōu)路徑,令為蟻群中的一個(gè)螞蟻在第k次外循環(huán)后第一次走到最優(yōu)路徑的事件.表示僅第k次外循環(huán)沒(méi)有走到的事件,但前k-1次可能走到過(guò)這條最優(yōu)路徑.永遠(yuǎn)不會(huì)被走到的事件為,其概率為:第76頁(yè)，共110頁(yè)，2023年，2月20日，星期日772.3.1GBAS算法的收斂性分析3/8任意給定的固定弧(i,j),在第k次循環(huán)后,其信息素值的下界可以計(jì)算出.第77頁(yè)，共110頁(yè)，2023年，2月20日，星期日782.3.1GBAS算法的收斂性分析4/8令 ,任何一個(gè)固定節(jié)點(diǎn)最多有(n-1)后續(xù)節(jié)點(diǎn),并且其弧上的信息素值都小于1或者等于1.得:蟻群中的一只螞蟻在第次循環(huán)走到路徑W*的概率為一個(gè)蟻群中至少有一只螞蟻，因此這是一個(gè)蟻群到達(dá)最優(yōu)路徑的一個(gè)下界.上式右側(cè)與k無(wú)關(guān),第78頁(yè)，共110頁(yè)，2023年，2月20日，星期日792.3.1GBAS算法的收斂性分析5/8

則取對(duì)數(shù)有從而得到第79頁(yè)，共110頁(yè)，2023年，2月20日，星期日802.3.1GBAS算法的收斂性分析6/8證明右式成立隨機(jī)過(guò)程以概率1達(dá)到一條最優(yōu)路徑.當(dāng)某條最優(yōu)路徑Z在第k次循環(huán)被首次走到后,在第k+1輪循環(huán)按信息素的更新原則,可以用歸納法證明,對(duì)于任意第80頁(yè)，共110頁(yè)，2023年，2月20日，星期日812.3.1GBAS算法的收斂性分析7/8由于級(jí)數(shù)是發(fā)散的,可知.因此,當(dāng)時(shí),在第K輪迭代之后,該弧永遠(yuǎn)不再被加強(qiáng),從而有也既弧上的信息素之和將趨于0.對(duì)于信息素的更新公式(2),可以歸納證明(6)式的第二項(xiàng)與(i,j)弧無(wú)關(guān),結(jié)合(7)式可得的極限存在,且所有的極限之和為1.對(duì)于所有的第81頁(yè)，共110頁(yè)，2023年，2月20日，星期日822.3.1GBAS算法的收斂性分析8/8結(jié)合前兩部分討論,當(dāng)Xn首次到達(dá)最優(yōu)路徑后,對(duì)于任何最優(yōu)路徑上的弧,(1)式的轉(zhuǎn)移概率

,即依概率1收斂到

.第82頁(yè)，共110頁(yè)，2023年，2月20日，星期日832.3.2

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

MAX-MIN蟻群優(yōu)化算法指定揮發(fā)系數(shù)不隨時(shí)間變化,這是和GBAS算法不同的一點(diǎn),改變了信息素?fù)]發(fā)和增強(qiáng)的規(guī)則(9式)，同時(shí)給出一個(gè)下界控制信息素的揮發(fā).

定理

在MAX-MIN算法中,第83頁(yè)，共110頁(yè)，2023年，2月20日，星期日842.3.2其他算法及收斂性分析2/4第84頁(yè)，共110頁(yè)，2023年，2月20日，星期日852.3.2其他算法及收斂性分析3/4第85頁(yè)，共110頁(yè)，2023年，2月20日，星期日862.3.2其他算法及收斂性分析4/4第86頁(yè)，共110頁(yè)，2023年，2月20日，星期日872.4蟻群優(yōu)化算法—技術(shù)問(wèn)題4.1解的表達(dá)形式與算法的實(shí)現(xiàn)4.2每一節(jié)點(diǎn)的記憶信息和系數(shù)的確定4.3蟻群的規(guī)模和停止規(guī)則4.4信息素的更改第87頁(yè)，共110頁(yè)，2023年，2月20日，星期日882.4.1解的表達(dá)形式與算法的實(shí)現(xiàn)1/4

----解的表達(dá)形式解的表達(dá)形式基于TSP問(wèn)題的蟻群優(yōu)化算法，其解的形式是所有城市的一個(gè)排列（閉圈，這種情況下誰(shuí)在第一并不重要），信息素痕跡按每個(gè)弧記錄。而對(duì)于一般以順序作為解的優(yōu)化問(wèn)題，誰(shuí)在第一是很重要的。蟻群算法在解決這類問(wèn)題時(shí)，只需要建立一個(gè)虛擬的始終點(diǎn)，就可以把TSP問(wèn)題的解法推廣，用于諸多的優(yōu)化問(wèn)題。諸如車間作業(yè)及下料等問(wèn)題，他們的共同特點(diǎn)是解以一個(gè)順序表示。TSP問(wèn)題尋找的是最短回路，而一般優(yōu)化問(wèn)題中，STEP3中的判斷條件需要根據(jù)實(shí)際問(wèn)題進(jìn)行修改。第88頁(yè)，共110頁(yè)，2023年，2月20日，星期日892.4.1

解的表達(dá)形式與算法的實(shí)現(xiàn)2/4

----算法的實(shí)現(xiàn)例：0-1背包問(wèn)題的解順序表達(dá)形式與算法實(shí)現(xiàn)。設(shè)有一個(gè)容積為b的背包，n個(gè)尺寸分別為，價(jià)值分別為的物品，0-1背包問(wèn)題的數(shù)學(xué)模型為：假設(shè)其解的順序表達(dá)形式為，其中為的一個(gè)排列。第89頁(yè)，共110頁(yè)，2023年，2月20日，星期日902.4.1

解的表達(dá)形式與算法的實(shí)現(xiàn)3/4

----算法的實(shí)現(xiàn)建立有向圖，其中A中共有條弧。初始信息素痕跡定義為。設(shè)第s只螞蟻第k步所走的路線為，表示螞蟻從0點(diǎn)出發(fā)，順序到達(dá)。第步按TSP算法的轉(zhuǎn)移概率公式行走選擇。若則，否則，此螞蟻不再繼續(xù)行走，退回起點(diǎn)。第90頁(yè)，共110頁(yè)，2023年，2月20日，星期日912.4.1

解的表達(dá)形式與算法的實(shí)現(xiàn)4/4----算法的實(shí)現(xiàn)對(duì)蟻群重復(fù)以上過(guò)程，比較m只螞蟻的裝包值 并記憶具有最大裝包值的螞蟻為t。把GBAS算法中步驟3中的改為，若滿足此條件則替換當(dāng)前最好解為，對(duì)W上的弧進(jìn)行信息素的加強(qiáng)，其他弧進(jìn)行信息素的揮發(fā)。算法中記錄了三個(gè)信息：信息素痕跡；行走路線；和問(wèn)題的約束條件 ，以確定是否將加入。第91頁(yè)，共110頁(yè)，2023年，2月20日，星期日922.4.2

每一節(jié)點(diǎn)的記憶信息和系數(shù)的確定----需要記憶的信息1/3算法中需要記憶的信息有三部分。第一部分信息是存在每個(gè)節(jié)點(diǎn)的路由表數(shù)據(jù)結(jié)構(gòu)，由此決定的的轉(zhuǎn)移概率為其中T可以看成節(jié)點(diǎn)i的鄰域。第92頁(yè)，共110頁(yè)，2023年，2月20日，星期日932.4.2每一節(jié)點(diǎn)的記憶信息和系數(shù)的確定----需要記憶的信息2/3第二部分需要記憶的信息是每個(gè)螞蟻的記憶表中存儲(chǔ)著的自身的歷史信息，這一部分主要由算法的中的記憶，表示螞蟻已經(jīng)行走過(guò)的節(jié)點(diǎn)。第三部分為問(wèn)題的約束條件。在GBAS中，T集合表示滿足約束條件的候選集，在背包問(wèn)題的蟻群算法中由判別條件， 來(lái)實(shí)現(xiàn)記

憶功能。第93頁(yè)，共110頁(yè)，2023年，2月20日，星期日942.4.2每一節(jié)點(diǎn)的記憶信息和系數(shù)的確定----系數(shù)的確定3/3

殘留信息的相對(duì)重要程度和預(yù)見(jiàn)值的相對(duì)重要程度體現(xiàn)了相關(guān)信息痕跡和預(yù)見(jiàn)度對(duì)螞蟻決策的相對(duì)影響。Dorigo在求解TSP問(wèn)題時(shí)，推薦參數(shù)的最佳設(shè)置為：。第94頁(yè)，共110頁(yè)，2023年，2月20日，星期日952.4.3蟻群的規(guī)模和停止規(guī)則一、蟻群大小一般情況下蟻群中螞蟻的個(gè)數(shù)不超過(guò)TSP圖中節(jié)點(diǎn)的個(gè)數(shù)。二、終止條件

1給定一個(gè)外循環(huán)的最大數(shù)目，表明已經(jīng)有足夠的螞蟻工作；

2當(dāng)前最優(yōu)解連續(xù)K次相同而停止，其中K是一個(gè)給定的整數(shù)，表示算法已經(jīng)收斂，不再需要繼續(xù)；

3目標(biāo)值控制規(guī)則，給定優(yōu)化問(wèn)題（目標(biāo)最小化）的一個(gè)下界和一個(gè)誤差值，當(dāng)算法得到的目標(biāo)值同下界之差小于給定的誤差值時(shí)，算法終止。第95頁(yè)，共110頁(yè)，2023年，2月20日，星期日962.4.4信息素的更改1/6信息素的更新分為離線和在線兩種方式。離線方式（同步更新方式）的主要思想是在若干只螞蟻完成n個(gè)城市的訪問(wèn)后，統(tǒng)一對(duì)殘留信息進(jìn)行更新處理。信息素的在線更新（異步更新方式）即螞蟻每行走一步，立即回溯并且更新行走路徑上的信息素。第96頁(yè)，共110頁(yè)，2023年，2月20日，星期日972.4.4

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

第97頁(yè)，共110頁(yè)，2023年，2月20日，星期日982.4.4

信息素的更改3/6TSP問(wèn)題中，蟻群優(yōu)化算法根據(jù)信息素痕跡更新方式不同可以分為不同的算法，采用離線方式，并且時(shí)，其中W為t循環(huán)中m只螞蟻所行走的最佳路線或第t只螞蟻所行走的一條路徑。Q為一個(gè)常數(shù)，該算法名為蟻環(huán)算法（ant-cyclealgotithm）,特點(diǎn)是行走的路徑越短對(duì)應(yīng)保存的信息素的值就越大。第98頁(yè)，共11