蟻群算法詳細講解07944

1、1蟻群算法及其應用1.螞蟻覓食行為與覓食策略2.螞蟻系統(tǒng)蟻群系統(tǒng)的原型3.改進的蟻群優(yōu)化算法4.蟻群優(yōu)化算法的仿真研究5.蟻群算法的應用對QoS組播路由問題求解2341.1 蟻群優(yōu)化算法概述n1.1.1 起源n1.1.2 應用領域n1.1.3 研究背景n1.1.4 研究現(xiàn)狀n1.1.5 應用現(xiàn)狀51.1.1 蟻群優(yōu)化算法起源 20世紀50年代中期創(chuàng)立了仿生學，人們從生物進化的機理中受到啟發(fā)。提出了許多用以解決復雜優(yōu)化問題的新方法，如進化規(guī)劃、進化策略、遺傳算法等，這些算法成功地解決了一些實際問題。 20世紀90年代意大利學者MDorigo，VManiezzo，AColorni等從生物進化的機制

2、中受到啟發(fā)，通過模擬自然界螞蟻搜索路徑的行為，提出來一種新型的模擬進化算法 蟻群算法，是群智能理論研究領域的一種主要算法。用該方法求解TSP問題、分配問題、job-shop調度問題，取得了較好的試驗結果雖然研究時間不長，但是現(xiàn)在的研究顯示出，蟻群算法在求解復雜優(yōu)化問題（特別是離散優(yōu)化問題）方面有一定優(yōu)勢，表明它是一種有發(fā)展前景的算法61.1.2 蟻群優(yōu)化算法應用領域 這種方法能夠被用于解決大多數(shù)優(yōu)化問題或者能夠轉化為優(yōu)化求解的問題?，F(xiàn)在其應用領域已擴展到多目標優(yōu)化、數(shù)據(jù)分類、數(shù)據(jù)聚類、模式識別、電信QoS管理、生物系統(tǒng)建模、流程規(guī)劃、信號處理、機器人控制、決策支持以及仿真和系統(tǒng)辯識等方面，群智

3、能理論和方法為解決這類應用問題提供了新的途徑。72.1.3 蟻群優(yōu)化算法研究背景 1/3 群智能理論研究領域有兩種主要的算法：蟻群算法(Ant Colony Optimization, ACO)和微粒群算法（Particle Swarm Optimization, PSO）。前者是對螞蟻群落食物采集過程的模擬，已成功應用于許多離散優(yōu)化問題。微粒群算法也是起源于對簡單社會系統(tǒng)的模擬，最初是模擬鳥群覓食的過程，但后來發(fā)現(xiàn)它是一種很好的優(yōu)化工具。 81.1.3 蟻群優(yōu)化算法研究背景 2/3與大多數(shù)基于梯度的應用優(yōu)化算法不同，群智能依靠的是概率搜索算法。雖然概率搜索算法通常要采用較多的評價函數(shù)，但是與

4、梯度方法及傳統(tǒng)的演化算法相比，其優(yōu)點還是顯著的 ，主要表現(xiàn)在以下幾個方面：1 無集中控制約束，不會因個別個體的故障影響整個問題 的求解，確保了系統(tǒng)具備更強的魯棒性 2 以非直接的信息交流方式確保了系統(tǒng)的擴展性 3 并行分布式算法模型，可充分利用多處理器 4 對問題定義的連續(xù)性無特殊要求 5 算法實現(xiàn)簡單 91.1.3 蟻群優(yōu)化算法研究背景 3/3 群智能方法易于實現(xiàn)，算法中僅涉及各種基本的數(shù)學操作，其數(shù)據(jù)處理過程對CPU和內存的要求也不高。而且，這種方法只需目標函數(shù)的輸出值，而無需其梯度信息。已完成的群智能理論和應用方法研究證明群智能方法是一種能夠有效解決大多數(shù)全局優(yōu)化問題的新方法。更為重要是

5、，群智能潛在的并行性和分布式特點為處理大量的以數(shù)據(jù)庫形式存在的數(shù)據(jù)提供了技術保證。無論是從理論研究還是應用研究的角度分析，群智能理論及其應用研究都是具有重要學術意義和現(xiàn)實價值的。 101.1.4 蟻群優(yōu)化算法研究現(xiàn)狀 1/7 90年代Dorigo最早提出了蟻群優(yōu)化算法-螞蟻系統(tǒng)（Ant System, AS）并將其應用于解決計算機算法學中經(jīng)典的旅行商問題（TSP）。從螞蟻系統(tǒng)開始，基本的蟻群算法得到了不斷的發(fā)展和完善，并在TSP以及許多實際優(yōu)化問題求解中進一步得到了驗證。這些AS改進版本的一個共同點就是增強了螞蟻搜索過程中對最優(yōu)解的探索能力，它們之間的差異僅在于搜索控制策略方面。而且，取得了最

6、佳結果的ACO是通過引入局部搜索算法實現(xiàn)的，這實際上是一些結合了標準局域搜索算法的混合型概率搜索算法，有利于提高蟻群各級系統(tǒng)在優(yōu)化問題中的求解質量。111.1.4蟻群優(yōu)化算法研究現(xiàn)狀 2/7 最初提出的AS有三種版本：Ant-density、Ant-quantity和Ant-cycle。在Ant-density和Ant-quantity中螞蟻在兩個位置節(jié)點間每移動一次后即更新信息素，而在Ant-cycle中當所有的螞蟻都完成了自己的行程后才對信息素進行更新，而且每個螞蟻所釋放的信息素被表達為反映相應行程質量的函數(shù)。通過與其它各種通用的啟發(fā)式算法相比，在不大于75城市的TSP中，這三種基本算法的

7、求解能力還是比較理想的，但是當問題規(guī)模擴展時，AS的解題能力大幅度下降。 因此，其后的ACO研究工作主要都集中于AS性能的改進方面。較早的一種改進方法是精英策略(Elitist Strategy)，其思想是在算法開始后即對所有已發(fā)現(xiàn)的最好路徑給予額外的增強，并將隨后與之對應的行程記為Tgb(全局最優(yōu)行程)，當進行信息素更新時，對這些行程予以加權，同時將經(jīng)過這些行程的螞蟻記為“精英”，從而增大較好行程的選擇機會。這種改進型算法能夠以更快的速度獲得更好的解。但是若選擇的精英過多則算法會由于較早的收斂于局部次優(yōu)解而導致搜索的過早停滯。 121.1.4蟻群優(yōu)化算法研究現(xiàn)狀 3/7 為了進一步克服AS中

8、暴露出的問題，提出了蟻群系統(tǒng)(Ant Colony System, ACS)。該系統(tǒng)的提出是以Ant-Q算法為基礎的。Ant-Q將螞蟻算法和一種增強型學習算法Q-learning有機的結合了起來。ACS與AS之間存在三方面的主要差異：首先，ACS采用了更為大膽的行為選擇規(guī)則；其次，只增強屬于全局最優(yōu)解的路徑上的信息素。其中，01是信息素揮發(fā)參數(shù)， 是從尋路開始到當前為止全局最優(yōu)的路徑長度。131.1.4蟻群優(yōu)化算法研究現(xiàn)狀 4/7 再次，還引入了負反饋機制，每當一只螞蟻由一個節(jié)點移動到另一個節(jié)點時，該路徑上的信息素都按照如下公式被相應的消除一部分，從而實現(xiàn)一種信息素的局部調整，以減小已選擇過的

9、路徑再次被選擇的概率。 141.1.4蟻群優(yōu)化算法研究現(xiàn)狀 5/7 在對AS進行直接完善的方法中，MAX-MIN Ant System是一個典型代表。該算法修改了AS的信息素更新方式，每次迭代之后只有一只螞蟻能夠進行信息素的更新以獲取更好的解。為了避免搜索停滯，路徑上的信息素濃度被限制在MAX，MIN 范圍內，另外，信息素的初始值被設為其取值上限，這樣有助于增加算法初始階段的搜索能力。151.1.4蟻群優(yōu)化算法研究現(xiàn)狀 6/7 另一種對AS改進的算法是Rank-based Version AS。與“精英策略”相似，在此算法中總是更新更好進程上的信息素，選擇的標準是其行程長度 決定的排序，且每個

10、螞蟻放置信息素的強度通過下式中的排序加權處理確定，其中，為每次迭代后放置信息素的螞蟻總數(shù)。 161.1.4蟻群優(yōu)化算法研究現(xiàn)狀 7/7 這種算法求解TSP的能力與AS、精英策略AS、遺傳算法和模擬退火算法進行了比較。在大型TSP問題中（最多包含132座城市），基于AS的算法都顯示出了優(yōu)于GA和SA的特性。而且在Rank-based AS和精英策略AS均優(yōu)于基本AS的同時，前者還獲得了比精英策略AS更好的解。 171.1.5 蟻群優(yōu)化算法應用現(xiàn)狀 1/5 隨著群智能理論和應用算法研究的不斷發(fā)展，研究者已嘗試著將其用于各種工程優(yōu)化問題，并取得了意想不到的收獲。多種研究表明，群智能在離散求解空間和連

11、續(xù)求解空間中均表現(xiàn)出良好的搜索效果，并在組合優(yōu)化問題中表現(xiàn)突出。 蟻群優(yōu)化算法并不是旅行商問題的最佳解決方法，但是它卻為解決組合優(yōu)化問題提供了新思路，并很快被應用到其它組合優(yōu)化問題中。比較典型的應用研究包括：網(wǎng)絡路由優(yōu)化、數(shù)據(jù)挖掘以及一些經(jīng)典的組合優(yōu)化問題。 181.1.5 蟻群優(yōu)化算法應用現(xiàn)狀 2/5 蟻群算法在電信路由優(yōu)化中已取得了一定的應用成果。HP公司和英國電信公司在90年代中后期都開展了這方面的研究，設計了蟻群路由算法（Ant Colony Routing, ACR）。 每只螞蟻就像蟻群優(yōu)化算法中一樣，根據(jù)它在網(wǎng)絡上的經(jīng)驗與性能，動態(tài)更新路由表項。如果一只螞蟻因為經(jīng)過了網(wǎng)絡中堵塞的路

12、由而導致了比較大的延遲，那么就對該表項做較大的增強。同時根據(jù)信息素揮發(fā)機制實現(xiàn)系統(tǒng)的信息更新，從而拋棄過期的路由信息。這樣，在當前最優(yōu)路由出現(xiàn)擁堵現(xiàn)象時，ACR算法就能迅速的搜尋另一條可替代的最優(yōu)路徑，從而提高網(wǎng)絡的均衡性、負荷量和利用率。目前這方面的應用研究仍在升溫，因為通信網(wǎng)絡的分布式信息結構、非穩(wěn)定隨機動態(tài)特性以及網(wǎng)絡狀態(tài)的異步演化與ACO的算法本質和特性非常相似。191.1.5 蟻群優(yōu)化算法應用現(xiàn)狀 3/5 基于群智能的聚類算法起源于對蟻群蟻卵的分類研究。Lumer和Faieta將Deneubourg提出將蟻巢分類模型應用于數(shù)據(jù)聚類分析。其基本思想是將待聚類數(shù)據(jù)隨機地散布到一個二維平面

13、內，然后將虛擬螞蟻分布到這個空間內，并以隨機方式移動，當一只螞蟻遇到一個待聚類數(shù)據(jù)時即將之拾起并繼續(xù)隨機運動，若運動路徑附近的數(shù)據(jù)與背負的數(shù)據(jù)相似性高于設置的標準則將其放置在該位置，然后繼續(xù)移動，重復上述數(shù)據(jù)搬運過程。按照這樣的方法可實現(xiàn)對相似數(shù)據(jù)的聚類。201.1.5 蟻群優(yōu)化算法應用現(xiàn)狀 4/5 ACO還在許多經(jīng)典組合優(yōu)化問題中獲得了成功的應用，如二次規(guī)劃問題（QAP）、機器人路徑規(guī)劃、作業(yè)流程規(guī)劃、圖著色（Graph Coloring）等問題。 經(jīng)過多年的發(fā)展，ACO已成為能夠有效解決實際二次規(guī)劃問題的幾種重要算法之一。AS在作業(yè)流程計劃（Job-shop Scheduling）問題中的

14、應用實例已經(jīng)出現(xiàn)，這說明了AS在此領域的應用潛力。利用MAX-MIN AS解決PAQ也取得了比較理想的效果，并通過實驗中的計算數(shù)據(jù)證明采用該方法處理PAQ比較早的SA算法更好，且與禁忌搜索算法性能相當。利用ACO實現(xiàn)對生產(chǎn)流程和特料管理的綜合優(yōu)化，并通過與遺傳、模擬退火和禁忌搜索算法的比較證明了ACO的工程應用價值。211.1.5 蟻群優(yōu)化算法應用現(xiàn)狀 5/5 許多研究者將ACO用于了武器攻擊目標分配和優(yōu)化問題、車輛運行路徑規(guī)劃、區(qū)域性無線電頻率自動分配、Bayesian networks的訓練和集合覆蓋等應用優(yōu)化問題。Costa和Herz還提出了一種AS在規(guī)劃問題方面的擴展應用圖著色問題，并

15、取得了可與其他啟發(fā)式算法相比的效果。221.2 蟻群優(yōu)化算法概念1.2.1 蟻群算法原理1.2.2 簡化的螞蟻尋食過程1.2.3 自然蟻群與人工蟻群算法1.2.4 蟻群算法與TSP問題1.2.5 初始的蟻群優(yōu)化算法基于圖的蟻群系統(tǒng)（GBAS）1.2.6 一般蟻群算法的框架231.2.1 蟻群算法原理 蟻群算法是對自然界螞蟻的尋徑方式進行模似而得出的一種仿生算法。螞蟻在運動過程中，能夠在它所經(jīng)過的路徑上留下一種稱之為外激素(pheromone)的物質進行信息傳遞，而且螞蟻在運動過程中能夠感知這種物質，并以此指導自己的運動方向，因此由大量螞蟻組成的蟻群集體行為便表現(xiàn)出一種信息正反饋現(xiàn)象：某一路徑上

16、走過的螞蟻越多，則后來者選擇該路徑的概率就越大。 為了說明蟻群算法的原理，先簡要介紹一下螞蟻搜尋食物的具體過程。在蟻群尋找食物時，它們總能找到一條從食物到巢穴之間的最優(yōu)路徑。這是因為螞蟻在尋找路徑時會在路徑上釋放出一種特殊的信息素。當它們碰到一個還沒有走過的路口時就隨機地挑選一條路徑前行。與此同時釋放出與路徑長度有關的信息素。路徑越長，釋放的激索濃度越低.當后來的螞蟻再次碰到這個路口的時候選擇激素濃度較高路徑概率就會相對較大。這樣形成一個正反饋。最優(yōu)路徑上的激索濃度越來越大而其它的路徑上激素濃度卻會隨著時間的流逝而消減。最終整個蟻群會找出最優(yōu)路徑。241.2.2 簡化的螞蟻尋食過程 1/3螞蟻

17、從A點出發(fā)，速度相同，食物在D點，可能隨機選擇路線ABD或ACD。假設初始時每條分配路線一只螞蟻，每個時間單位行走一步，本圖為經(jīng)過9個時間單位時的情形：走ABD的螞蟻到達終點，而走ACD的螞蟻剛好走到C點，為一半路程。251.2.2 簡化的螞蟻尋食過程 2/3本圖為從開始算起，經(jīng)過18個時間單位時的情形：走ABD的螞蟻到達終點后得到食物又返回了起點A，而走ACD的螞蟻剛好走到D點。261.2.2 簡化的螞蟻尋食過程 3/3 假設螞蟻每經(jīng)過一處所留下的信息素為一個單位，則經(jīng)過36個時間單位后，所有開始一起出發(fā)的螞蟻都經(jīng)過不同路徑從D點取得了食物，此時ABD的路線往返了2趟，每一處的信息素為4個單

18、位，而 ACD的路線往返了一趟，每一處的信息素為2個單位，其比值為2：1。 尋找食物的過程繼續(xù)進行，則按信息素的指導，蟻群在ABD路線上增派一只螞蟻（共2只），而ACD路線上仍然為一只螞蟻。再經(jīng)過36個時間單位后，兩條線路上的信息素單位積累為12和4，比值為3：1。 若按以上規(guī)則繼續(xù)，蟻群在ABD路線上再增派一只螞蟻（共3只），而ACD路線上仍然為一只螞蟻。再經(jīng)過36個時間單位后，兩條線路上的信息素單位積累為24和6，比值為4：1。 若繼續(xù)進行，則按信息素的指導，最終所有的螞蟻會放棄ACD路線，而都選擇ABD路線。這也就是前面所提到的正反饋效應。271.2.3 自然蟻群與人工蟻群算法 基于以上

19、蟻群尋找食物時的最優(yōu)路徑選擇問題，可以構造人工蟻群，來解決最優(yōu)化問題，如TSP問題。 人工蟻群中把具有簡單功能的工作單元看作螞蟻。二者的相似之處在于都是優(yōu)先選擇信息素濃度大的路徑。較短路徑的信息素濃度高，所以能夠最終被所有螞蟻選擇，也就是最終的優(yōu)化結果。 兩者的區(qū)別在于人工蟻群有一定的記憶能力，能夠記憶已經(jīng)訪問過的節(jié)點。同時，人工蟻群再選擇下一條路徑的時候是按一定算法規(guī)律有意識地尋找最短路徑，而不是盲目的。例如在TSP問題中，可以預先知道當前城市到下一個目的地的距離。281.2.4 蟻群算法與TSP問題 1/3TSP問題表示為一個N個城市的有向圖G=（N，A），其中城市之間距離目標函數(shù)為 ，其

20、中 為城市1,2，n的一個排列， 。, |j), (iA n1,2,.,NNjinnijd)(nliilldwf11)(),(21niiiw11iin291.2.4 蟻群算法與TSP問題 2/3 TSP問題的人工蟻群算法中，假設m只螞蟻在圖的相鄰節(jié)點間移動，從而協(xié)作異步地得到問題的解。每只螞蟻的一步轉移概率由圖中的每條邊上的兩類參數(shù)決定：1 信息素值 也稱信息素痕跡。2 可見度，即先驗值。 信息素的更新方式有2種，一是揮發(fā)，也就是所有路徑上的信息素以一定的比率進行減少，模擬自然蟻群的信息素隨時間揮發(fā)的過程；二是增強，給評價值“好”(有螞蟻走過)的邊增加信息素。301.2.4 蟻群算法與TSP問

21、題 3/3 螞蟻向下一個目標的運動是通過一個隨機原則來實現(xiàn)的，也就是運用當前所在節(jié)點存儲的信息，計算出下一步可達節(jié)點的概率，并按此概率實現(xiàn)一步移動，逐此往復，越來越接近最優(yōu)解。 螞蟻在尋找過程中，或者找到一個解后，會評估該解或解的一部分的優(yōu)化程度，并把評價信息保存在相關連接的信息素中。311.2.5 初始的蟻群優(yōu)化算法基于圖的蟻群系統(tǒng)（GBAS） 1/12初始的蟻群算法是基于圖的蟻群算法，graph-based ant system,簡稱為GBAS，是由Gutjahr W J在2000年的Future Generation Computing Systems提出的，課本的參考文獻2。算法步驟如

22、下：STEP 0 對n個城市的TSP問題，城市間的距離矩陣為 ，給TSP圖中的每一條弧 賦信息素初值 ，假設m只螞蟻在工作，所有螞蟻都從同一城市 出發(fā)。當前最好解是。, |j), (iA n1,2,.,NNjinnijd)(),(ji|1)0(Aij0i),2,1(nw321.2.5 初始的蟻群優(yōu)化算法基于圖的蟻群系統(tǒng)（GBAS） 2/12STEP 1 （外循環(huán)）如果滿足算法的停止規(guī)則，則停止計算并輸出計算得到的最好解。否則使螞蟻s從起點 出發(fā)，用 表示螞蟻s行走的城市集合，初始 為空集， 。STEP 2 (內循環(huán)) 按螞蟻 的順序分別計算。當螞蟻在城市i，若 完成第s只螞蟻的計算。否則，若，

23、則以概率，到達j， ；若則到達重復STEP 2。0i)(sL)(sLms 11sm( ) |( , ),( )L sNli lA lL s 或0( ) |( , ),( ) L sNTli lA lL si 且(1),(1)ijijijl TkpjTk0,ijpjT( )( ) , :L sL sjij0( ) |( , ),( ) L sNTli lA lL si 且000, ( )( ) , :;i L sL siii331.2.5 初始的蟻群優(yōu)化算法基于圖的蟻群系統(tǒng)（GBAS） 3/12STRP 3 對 ，若 ，按 中城市的順序計算路徑程度；若 ，路徑長度置為一個無窮大值（即不可達）。比

24、較m只螞蟻中的路徑長度，記走最短路徑的螞蟻為t。若 ，則 。用如下公式對W路徑上的信息素痕跡加強，對其他路徑上的信息素進行揮發(fā)。 得到新的 ，重復步驟STEP 1。1sm( )L sN( )L s( )L sN( ( )( ()f L tf L W( )WL t( ), :1ijk kk111( )(1)(1)( , )( )(1)(1)( , )kijkijijkijkki jWWkki jW為上的一條弧不是上的一條弧341.2.5 初始的蟻群優(yōu)化算法基于圖的蟻群系統(tǒng)（GBAS） 4/12在STEP 3 中，揮發(fā)因子 對于一個固定的 ，滿足并且 經(jīng)過k次揮發(fā)，非最優(yōu)路徑的信息素逐漸減少至消失

25、。kln1,ln(1)kkkKk 1K 1kk 351.2.5初始的蟻群優(yōu)化算法基于圖的蟻群系統(tǒng)（GBAS） 5/12 以上算法中，在螞蟻的搜尋過程中，以信息素的概率分布來決定從城市i到城市j的轉移。 算法中包括信息素更新的過程 1 信息素揮發(fā)（evaporation） 信息素痕跡的揮發(fā)過程是每個連接上的信息素痕跡的濃度自動逐漸減弱的過程，由 表示，這個揮發(fā)過程主要用于避免算法過快地向局部最優(yōu)區(qū)域集中，有助于搜索區(qū)域的擴展。 2 信息素增強（reinforcement）增強過程是蟻群優(yōu)化算法中可選的部分，稱為離線更新方式（還有在線更新方式）。這種方式可以實現(xiàn)由單個螞蟻無法實現(xiàn)的集中行動。也就是

26、說，增強過程體現(xiàn)在觀察蟻群（m只螞蟻）中每只螞蟻所找到的路徑，并選擇其中最優(yōu)路徑上的弧進行信息素的增強，揮發(fā)過程是所有弧都進行的，不于螞蟻數(shù)量相關。這種增強過程中進行的信息素更新稱為離線的信息素更新。 在STEP 3中，蟻群永遠記憶到目前為止的最優(yōu)解。(1)( )kijk 36圖的蟻群系統(tǒng)（GBAS） 6/12可以驗證，下式滿足：即 是一個隨機矩陣。( )k( , )( )1,0iji jAkk 四個城市的非對稱TSP問題，距離矩陣和城市圖示如下：010.511011()1.55011110ijDd371.2.5 初始的蟻群優(yōu)化算法基于圖的蟻群系統(tǒng)（GBAS） 7/12假設共4只螞蟻，所有螞蟻

27、都從城市A出發(fā)，揮發(fā)因子 。此時，觀察GBAS的計算過程。 矩陣共有12條弧，初始信息素記憶矩陣為：1,1,2,32kk01 121 121 121 1201 121 12(0)(0)1 121 1201 121 121 121 120ij381.2.5 初始的蟻群優(yōu)化算法基于圖的蟻群系統(tǒng)（GBAS） 8/12執(zhí)行GBAS算法的步驟2，假設螞蟻的行走路線分別為：當前最優(yōu)解為，這個解是截止到當前的最優(yōu)解，碰巧是實際最優(yōu)解1:,(1)4;2:,(2)3.5;3:,(3)8;4:,(4)4.5;WABCDA f WWACDBA f WWADCBA f WWABDCA f W第一只第二只第三只第四只3

28、91.2.5 初始的蟻群優(yōu)化算法基于圖的蟻群系統(tǒng)（GBAS） 9/12按算法步驟3的信息素更新規(guī)則，得到更新矩陣這是第一次外循環(huán)結束的狀態(tài)。01 241 61 241 601 241 24(1)(1)1 241 1201 61 241 61 240ij401.2.5 初始的蟻群優(yōu)化算法基于圖的蟻群系統(tǒng)（GBAS） 10/12重復外循環(huán)，由于上一次得到的W2已經(jīng)是全局最優(yōu)解，因此按算法步驟3的信息素更新規(guī)則，無論螞蟻如何行走，都只是對W2路線上的城市信息素進行增強，其他的城市信息素進行揮發(fā)。得到更新矩陣這是第一次外循環(huán)結束的狀態(tài)。01 485 241 485 2401 481 48(2)(2)1

29、 481 4805 241 485 241 480ij411.2.5 初始的蟻群優(yōu)化算法基于圖的蟻群系統(tǒng)（GBAS） 11/12重復外循環(huán)，由于W2全局最優(yōu)解，GBAS只記錄第一個最優(yōu)解，因此一但得到了全局最優(yōu)解，信息素的更新將不再依賴于以群的行走路線，而只是不斷增強最優(yōu)路線的信息素，同時進行揮發(fā)。第三次外循環(huán)后得到的信息素矩陣為：01 9611 481 9611 4801 961 96(3)(3)1 961 96011 481 9611 481 960ij421.2.5 初始的蟻群優(yōu)化算法基于圖的蟻群系統(tǒng)（GBAS） 12/12 螞蟻以一定的概率從城市i到城市j進行轉移，信息素的更新在STE

30、P 3 完成，并隨K而變化。假設第K次外循環(huán)后得到信息素矩陣 ，得到當前最優(yōu)解 。第K次循環(huán)前的信息素和最優(yōu)解為 ，經(jīng)過第K次外循環(huán)后，得到 。由于螞蟻的一步轉移概率是隨機的，從 到 也是隨機的，是一個馬爾可夫過程。( )( )|( , )ijkki jA( )W k(1),(1)kW k( ),( )k W k(1),(1)kW k( ),( )k W k431.2.6 一般蟻群算法的框架一般蟻群算法的框架和GBAS基本相同，有三個組成部分： 蟻群的活動； 信息素的揮發(fā)； 信息素的增強；主要體現(xiàn)在前面的算法中步驟2和步驟3中的轉移概率公式和信息素更新公式。441.3 蟻群優(yōu)化算法算法模型和收

31、斂性分析1.3.0 馬氏過程的收斂定義1.3.1 GBAS算法的收斂性分析1.3.2其他算法及收斂性分析451.3.0 馬氏過程的收斂定義 蟻群優(yōu)化算法的每步迭代對應隨機變量 其中 為信息素痕跡； 為n城市的一個排列，最多有 個狀態(tài)。第s只螞蟻在第k輪轉移只由 決定，這個螞蟻行走的路徑和 一起，共同決定了 ，再通過信息素的更新原則可以進一步得到 。 的變化僅由 決定，而與先前的狀態(tài)無關，這是一個典型的馬爾可夫過程。 定義定義：若一個馬爾可夫過程 ，對任意給定的 滿足 則稱馬爾可夫過程 依概率1收斂到 。( ( ),( ),0,1,.,kXk W kk( )k( )W k!n(1)k(1)W k

32、 ( )W k( )k1kXkX,0,1,.kXk 0*X,0,1,2,.kXk *lim1kkp XX461.3.1 GBAS算法的收斂性分析 1/8 定理 滿足指定條件的馬爾可夫過程 依概率1收斂到 ,其中 為一條最優(yōu)路徑, 定義為: 證明分析: 蟻群算法中,一但達到全局最優(yōu),由 只記錄第一個最優(yōu)解.證明分三部分:n 證明以概率1達到一個最優(yōu)路徑n 證明(1)上式成立n 證明以概率1收斂到一個最優(yōu)路徑( ( ),( ),0,1,.,kXk W kk*(,)XW*W*1,( ,)0(1)ijWi jW為的一條弧其他f(L(t)f(w)471.3.1 GBAS算法的收斂性分析 2/8證明以概率

33、1到達一個最優(yōu)路徑 對于最優(yōu)路徑 ,令 為蟻群中的一個螞蟻在第k次外循環(huán)后第一次走到最優(yōu)路徑 的事件. 表示僅第k次外循環(huán)沒有走到 的事件,但前k-1次可能走到過這條最優(yōu)路徑. 永遠不會被走到的事件為 ,其概率為:*WkF*WkF*W*W12FF12*1*1()|)(2kkP FFPkWPkW*第 次循環(huán)蟻群沒有走到第ik次循環(huán)蟻群沒有走到W前 次循環(huán)蟻群沒有走到481.3.1 GBAS算法的收斂性分析 3/8 任意給定的固定弧(i,j),在第k次循環(huán)后,其信息素值的下界可以計算出.111111111()(1)(1)ln(1)(1)ln (1)ln(1)(1)ln1(1) ln(1)(3 )l

34、ni jkijllKklijllKKlijlKlijlkllKkKk 491.3.1 GBAS算法的收斂性分析 4/8令,任何一個固定節(jié)點最多有(n-1)后續(xù)節(jié)點,并且其弧上的信息素值都小于1或者等于1.得:蟻群中的一只螞蟻在第 次循環(huán)走到路徑 W* 的概率為一個蟻群中至少有一只螞蟻，因此這是一個蟻群到達最優(yōu)路徑的一個下界. 上式右側與k無關,11(1)ln(1)KlijlK ,(1)lnijpkKnkk(kK)*( , )*( ) ()(4)1)lnWiji jWpknk501.3.1 GBAS算法的收斂性分析 5/8 則取對數(shù)有從而得到*( ,*)1( )1 ()(1)lnwiji j W

35、PkWpknk 前 次循環(huán)蟻群沒有走到*1*(1 ()(1)ln(2)(5)kwk KPkWnk前 次循環(huán)蟻群沒有走到*ln(1 () )()(1)ln(1)lnwwk Kk Knknk12()1P FF511.3.1 GBAS算法的收斂性分析 6/8 證明右式成立 隨機過程 以概率1達到一條最優(yōu)路徑.當某條最優(yōu)路徑Z在第k次循環(huán)被首次走到后,在第k+1輪循環(huán)按信息素的更新原則,可以用歸納法證明,對于任意*1,( , )0ijWi jW為的一條弧其他(i,j)W*,r=1,2,.111011()(1) ( )(1)*(6)K rrrijlijK lll Kq lK rKK qW 521.3.1

36、 GBAS算法的收斂性分析 7/8由于級數(shù) 是發(fā)散的,可知 .因此,當 時,在第K輪迭代之后,該弧永遠不再被加強,從而有 也既 弧上的信息素之和將趨于0.對于信息素的更新公式(2),可以歸納證明(6)式的第二項與(i,j)弧無關,結合(7)式可得 的極限存在,且所有的極限之和為1.對于所有的l1(1)0ll1()(1)(07)(KrijlijlKKrK ( , )*i jW( , )*i jW( , )( )1,iji jAkk成立( , )*i jW1lim()lim( *(8,*)*)ijlrlKrXWW ,即 可 得531.3.1 GBAS算法的收斂性分析 8/8 結合前兩部分討論,當X

37、n首次到達最優(yōu)路徑后,對于任何最優(yōu)路徑上的弧,(1)式的轉移概率 ,即 依概率1收斂到 .( )1ijp l ( ( ),( ),0,1,.,kXk W kk*(,)XW541.3.2 其他算法及收斂性分析 1/4 MAX-MIN蟻群優(yōu)化算法指定揮發(fā)系數(shù)不隨時間變化,這是和GBAS算法不同的一點,改變了信息素揮發(fā)和增強的規(guī)則(9式)，同時給出一個下界 控制信息素的揮發(fā). 定理 在MAX-MIN算法中,min(1)kminmax(1)(1),(1)( , )( )max(1)(1),(1),01,(1)ijijijijijkWki jWkkkk 其他其中為實數(shù)。 （9）min( ),1ln(1)

38、lim0kkkckkkc令：其中，則定理5.2.1的結論也成立。551.3.2 其他算法及收斂性分析 2/4ij(1)(1)p0(1)(1) | ( , )(1)(1)1.ijill TiijijijakjTakjTAkaki jAkkiij式螞蟻轉移概率更一般的規(guī)則由存儲在每個節(jié)點的路由表數(shù)據(jù)結構A =a |(i,j)A決定，即轉移概率為其中，取決于三部分因素，T是從i可以直接到達的節(jié)點結合。第一部分為每個節(jié)點的信息素痕跡和預見度第二部分為每（ ）個螞蟻自身的記憶表中存儲的歷史信息.第三部分為問題的約束條件.561.3.2 其他算法及收斂性分析 3/4(1)(1)(1)(1)(1)01(1)

39、,.ijijilill Tijijkkj Tkkkj TTSPkd ij常見的路由表信息由下式求得：a其中， 為殘留信息的相對重要程度， 為預見值的相對重要程度。和 體現(xiàn)了相關信息痕跡和預見度對螞蟻決策的相對影響。問題中為先驗知識 571.3.2 其他算法及收斂性分析 4/4(1)1.,( )(1)( ):(1) ( ),(0,1)ijijijijijkki jkkkk ij信息素痕跡為時刻連接城市和的路徑上的信息殘留濃度為避免過多的殘留信息會淹沒全局最優(yōu)解需要在每只螞蟻完成一次循環(huán)后對殘留信息進行更新,削弱舊信息,增強新信息.記(i,j)弧上的信息素在第k-1個循環(huán)的變化為(k-1),則保留

40、的信息素為然后進行信息素的揮發(fā)其中為信息素的衰退系數(shù).581.4 蟻群優(yōu)化算法技術問題1.4.1 解的表達形式與算法的實現(xiàn)1.4.2 每一節(jié)點的記憶信息和系數(shù)的確定1.4.3 蟻群的規(guī)模和停止規(guī)則1.4.4 信息素的更改591.4.1 解的表達形式與算法的實現(xiàn) 1/4 -解的表達形式 解的表達形式 基于TSP問題的蟻群優(yōu)化算法，其解的形式是所有城市的一個排列（閉圈，這種情況下誰在第一并不重要），信息素痕跡按每個弧記錄。而對于一般以順序作為解的優(yōu)化問題，誰在第一是很重要的。蟻群算法在解決這類問題時，只需要建立一個虛擬的始終點，就可以把TSP問題的解法推廣，用于諸多的優(yōu)化問題。 諸如車間作業(yè)及下料

41、等問題，他們的共同特點是解以一個順序表示。TSP問題尋找的是最短回路，而一般優(yōu)化問題中，STEP 3 中的判斷條件 需要根據(jù)實際問題進行修改。( )L sN601.4.1 解的表達形式與算法的實現(xiàn) 2/4 -算法的實現(xiàn)例：0-1背包問題的解順序表達形式與算法實現(xiàn)。設有一個容積為b的背包，n個尺寸分別為 ，價值分別為 的物品，0-1背包問題的數(shù)學模型為：假設其解的順序表達形式為，其中為的一個排列。(1,2,., )ia in(1,2,., )ic in11m a x. .0 ,1,1, .,niiiniiiic xs ta xbxjn120,.,niii12, ,.,ni ii1,2,3,.,n

42、611.4.1 解的表達形式與算法的實現(xiàn) 3/4 -算法的實現(xiàn)建立有向圖 ，其中 A中共有 條弧。初始信息素痕跡定義為 。設第s只螞蟻第k步所走的路線為 ，表示螞蟻從0點出發(fā)，順序到達 。第 步按TSP算法的轉移概率公式行走選擇 。若 則 ，否則，此螞蟻不再繼續(xù)行走，退回起點。( ,)GV A0,1,2,.,( ,) |,VnAi ji jV(1)n n1(1)ijn n12( )(0,.,)kL siii12,.,kiii1k 1ki11jkijab121( )(0, ,.,)kkL si iii621.4.1 解的表達形式與算法的實現(xiàn)4/4 -算法的實現(xiàn) 對蟻群重復以上過程，比較m只螞蟻的

43、裝包值 并記憶具有最大裝包值的螞蟻為t。把GBAS算法中步驟3中的改為 ，若滿足此條件則替換當前最好解為 ，對W上的弧進行信息素的加強，其他弧進行信息素的揮發(fā)。 算法中記錄了三個信息：信息素痕跡 ；行走路線 ；和問題的約束條件，以確定是否將 加入。 ( )0,1,2,.,ii L sic sm( ( )( )f L tf w( ( )( )f L tf w:( )WL tij121( )(0, ,.,)kkL si iii11jkijab1ki631.4.2 每一節(jié)點的記憶信息和系數(shù)的確定-需要記憶的信息 1/3算法中需要記憶的信息有三部分。第一部分信息是存在每個節(jié)點的路由表數(shù)據(jù)結構 ，由此決

44、定的的轉移概率為其中T可以看成節(jié)點i的鄰域。|( , )iijAai jA(1)(1)|( , )iijA kaki jA(1)(1),0ijili jlTakjTakPjT(1)(1)(1)(1)(1),0ijijililijl TkkkkakjTjT641.4.2 每一節(jié)點的記憶信息和系數(shù)的確定-需要記憶的信息 2/3 第二部分需要記憶的信息是每個螞蟻的記憶表中存儲著的自身的歷史信息，這一部分主要由算法的中的 記憶，表示螞蟻已經(jīng)行走過的節(jié)點。 第三部分為問題的約束條件。在GBAS中，T集合表示滿足約束條件的候選集，在背包問題的蟻群算法中由判別條件 ，來實現(xiàn)記 憶功能。( )L s11jki

45、jab121( )(0, ,.,)kkL si iii651.4.2 每一節(jié)點的記憶信息和系數(shù)的確定-系數(shù)的確定 3/3 殘留信息的相對重要程度 和預見值的相對重要程度 體現(xiàn)了相關信息痕跡和預見度對螞蟻決策的相對影響。Dorigo在求解TSP問題時，推薦參數(shù)的最佳設置為： 。1,5,0.5661.4.3 蟻群的規(guī)模和停止規(guī)則一、蟻群大小 一般情況下蟻群中螞蟻的個數(shù)不超過TSP圖中節(jié)點的個數(shù)。二、終止條件 1 給定一個外循環(huán)的最大數(shù)目，表明已經(jīng)有足夠的螞蟻工作； 2 當前最優(yōu)解連續(xù)K次相同而停止，其中K是一個給定的整數(shù)，表示算法已經(jīng)收斂，不再需要繼續(xù)； 3 目標值控制規(guī)則，給定優(yōu)化問題（目標最小

46、化）的一個下界和一個誤差值，當算法得到的目標值同下界之差小于給定的誤差值時，算法終止。671.4.4 信息素的更改 1/6 信息素的更新分為離線和在線兩種方式。離線方式（同步更新方式）的主要思想是在若干只螞蟻完成n個城市的訪問后，統(tǒng)一對殘留信息進行更新處理。 信息素的在線更新（異步更新方式）即螞蟻每行走一步，立即回溯并且更新行走路徑上的信息素。681.4.4 信息素的更改 2/6 離線方式的信息素更新可以進一步分為單螞蟻離線更新和蟻群離線更新。 蟻群離線更新方式是在蟻群中的m只螞蟻全部完成n城市的訪問（第k-1次蟻群循環(huán)）后，統(tǒng)一對殘留信息進行更新處理。 其中， 為第k-1次循環(huán)后的的信息素的

47、痕跡值。 單螞蟻離線更新是在第s只螞蟻完成對所有n個城市的訪問后，進行路徑回溯，更新行走路徑上的信息素，同時釋放分配給它的資源。更新公式為 第s+1只螞蟻根據(jù) 重新計算路由表。 ( )(1)(1)ijijijkkk( )ijk(1)( )( )ijijijsss(1)ijs691.4.4 信息素的更改 3/6TSP問題中，蟻群優(yōu)化算法根據(jù)信息素痕跡更新方式不同可以分為不同的算法，采用離線方式，并且時，其中W為t循環(huán)中m只螞蟻所行走的最佳路線或第t只螞蟻所行走的一條路徑。Q為一個常數(shù)，該算法名為蟻環(huán)算法（ant-cycle algotithm）,特點是行走的路徑越短對應保存的信息素的值就越大。(1)( )i ji jks或為( ),( , )( , )0i jQWti jWi jW701.4.4 信息素的更改 4/6 GBAS算法是典型的離線信息素更新方式。該算法中，蟻群中螞蟻的先后出行順序沒有相關性，但是每次循環(huán)需要記憶m只螞蟻的行走路徑，以進行比較選擇最優(yōu)路徑。相對而言，單螞蟻離線更新方式記憶信息少，只需要記憶第s只螞蟻的路徑，并通過信息素更新后，釋放該螞蟻的所有記錄信息。實際上這種方式等價于蟻群離線方