蟻群算法簡述

1、蟻群算法簡述蟻群算法簡述n1.蟻群算法的提出n2.蟻群算法的特征n3.蟻群算法的數(shù)學模型n4.蟻群算法的模型類型n5.蟻群算法的優(yōu)缺點n6.蟻群算法所解決的問題n7.蟻群算法的應用n8.蟻群算法的研究方向（發(fā)展方向）1.蟻群算法的提出n算法的提出蟻群算法（Ant Colony Optimization, ACO），又稱螞蟻算法一種用來在圖中尋找優(yōu)化路徑的機率型算法。 它由Marco Dorigo于1992年在他的博士論文“Ant system: optimization by a colony of cooperating agents”中提出，其靈感來源于螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為。

2、最早用于解決著名的旅行商問題(TSP , traveling salesman problem)。1.蟻群算法的提出n概念原型各個螞蟻在沒有事先告訴他們食物在什么地方的前提下開始尋找食物。當一只找到食物以后，它會向環(huán)境釋放一種揮發(fā)性分泌物pheromone (稱為信息素,該物質(zhì)隨著時間的推移會逐漸揮發(fā)消失，信息素濃度的大小表征路徑的遠近)來實現(xiàn)的，吸引其他的螞蟻過來，這樣越來越多的螞蟻會找到食物。有些螞蟻并沒有象其它螞蟻一樣總重復同樣的路，他們會另辟蹊徑，如果另開辟的道路比原來的其他道路更短，那么，漸漸地，更多的螞蟻被吸引到這條較短的路上來。最后，經(jīng)過一段時間運行，就可能會出現(xiàn)一條最短的路徑被

3、大多數(shù)螞蟻重復著。1.蟻群算法的提出n基本原理蟻群算法是對自然界螞蟻的尋徑方式進行模似而得出的一種仿生算法。 螞蟻在運動過程中，能夠在它所經(jīng)過的路徑上留下一種稱之為外激素(pheromone)的物質(zhì)進行信息傳遞，而且螞蟻在運動過程中能夠感知這種物質(zhì)，并以此指導自己的運動方向，因此由大量螞蟻組成的蟻群集體行為便表現(xiàn)出一種信息正反饋現(xiàn)象：某一路徑上走過的螞蟻越多，則后來者選擇該路徑的概率就越大。1.蟻群算法的提出n簡化的螞蟻尋食過程螞蟻從A點出發(fā)，速度相同，食物在D點，可能隨機選擇路線ABD或ACD。假設(shè)初始時每條分配路線一只螞蟻，每個時間單位行走一步，本圖為經(jīng)過9個時間單位時的情形：走ABD的螞

4、蟻到達終點，而走ACD的螞蟻剛好走到C點，為一半路程。1.蟻群算法的提出本圖為從開始算起，經(jīng)過18個時間單位時的情形：走ABD的螞蟻到達終點后得到食物又返回了起點A，而走ACD的螞蟻剛好走到D點。1.蟻群算法的提出假設(shè)螞蟻每經(jīng)過一處所留下的信息素為一個單位，則經(jīng)過36個時間單位后，所有開始一起出發(fā)的螞蟻都經(jīng)過不同路徑從D點取得了食物，此時ABD的路線往返了2趟，每一處的信息素為4個單位，而 ACD的路線往返了一趟，每一處的信息素為2個單位，其比值為2：1。 尋找食物的過程繼續(xù)進行，則按信息素的指導，蟻群在ABD路線上增派一只螞蟻（共2只），而ACD路線上仍然為一只螞蟻。再經(jīng)過36個時間單位后，

5、兩條線路上的信息素單位積累為12和4，比值為3：1。 若按以上規(guī)則繼續(xù)，蟻群在ABD路線上再增派一只螞蟻（共3只），而ACD路線上仍然為一只螞蟻。再經(jīng)過36個時間單位后，兩條線路上的信息素單位積累為24和6，比值為4：1。 若繼續(xù)進行，則按信息素的指導，最終所有的螞蟻會放棄ACD路線，而都選擇ABD路線。這也就是前面所提到的正反饋效應。1.蟻群算法的提出n人工蟻群算法基于以上蟻群尋找食物時的最優(yōu)路徑選擇問題，可以構(gòu)造人工蟻群，來解決最優(yōu)化問題，如TSP問題。人工蟻群中把具有簡單功能的工作單元看作螞蟻。二者的相似之處在于都是優(yōu)先選擇信息素濃度大的路徑。較短路徑的信息素濃度高，所以能夠最終被所有螞

6、蟻選擇，也就是最終的優(yōu)化結(jié)果。兩者的區(qū)別在于人工蟻群有一定的記憶能力，能夠記憶已經(jīng)訪問過的節(jié)點。同時，人工蟻群再選擇下一條路徑的時候是按一定算法規(guī)律有意識地尋找最短路徑，而不是盲目的。例如在TSP問題中，可以預先知道當前城市到下一個目的地的距離。1.蟻群算法的提出n1) 標有距離的路徑圖標有距離的路徑圖n2) 在在0時刻，路徑上沒有信息素累積，螞蟻選擇路徑為任意時刻，路徑上沒有信息素累積，螞蟻選擇路徑為任意n3) 在在1時刻，路徑上信息素堆積，短邊信息素多與長邊，所以螞蟻更傾向于選擇時刻，路徑上信息素堆積，短邊信息素多與長邊，所以螞蟻更傾向于選擇ABCDE2.蟻群算法的特征n蟻群算法采用了分布

7、式正反饋并行計算機制, 易于與其他方法結(jié)合, 并具有較強的魯棒性。n（1）其原理是一種正反饋機制或稱增強型學習系統(tǒng)；）其原理是一種正反饋機制或稱增強型學習系統(tǒng)；它通過信息素的不斷更新達到最終收斂于最優(yōu)路徑上；n（2）它是一種通用型隨機優(yōu)化方法；）它是一種通用型隨機優(yōu)化方法；但人工螞蟻決不是對實際螞蟻的一種簡單模擬，它融進了人類的智能；n（3）它是一種分布式的優(yōu)化方法；）它是一種分布式的優(yōu)化方法；不僅適合目前的串行計算機，而且適合未來的并行計算機；n（4）它是一種全局優(yōu)化的方法；）它是一種全局優(yōu)化的方法；不僅可用于求解單目標優(yōu)化問題，而且可用于求解多目標優(yōu)化問題；n（5）它是一種啟發(fā)式算法；）它

8、是一種啟發(fā)式算法；計算復雜性為 O(NC*m*n2)，其中NC 是迭代次數(shù)，m 是螞蟻數(shù)目，n 是目的節(jié)點數(shù)目。2.蟻群算法的特征下面是對蟻群算法的進行過程中采用的規(guī)則進行的一些說明。n范圍范圍螞蟻觀察到的范圍是一個方格世界，螞蟻有一個參數(shù)為速度半徑（一般是3），那么它能觀察到的范圍就是3*3個方格世界，并且能移動的距離也在這個范圍之內(nèi)。n環(huán)境環(huán)境螞蟻所在的環(huán)境是一個虛擬的世界，其中有障礙物，有別的螞蟻，還有信息素，信息素有兩種，一種是找到食物的螞蟻灑下的食物信息素，一種是找到窩的螞蟻灑下的窩的信息素。每個螞蟻都僅僅能感知它范圍內(nèi)的環(huán)境信息。環(huán)境以一定的速率讓信息素消失。n覓食規(guī)則覓食規(guī)則在每

9、只螞蟻能感知的范圍內(nèi)尋找是否有食物，如果有就直接過去。否則看是否有信息素，并且比較在能感知的范圍內(nèi)哪一點的信息素最多，這樣，它就朝信息素多的地方走，并且每只螞蟻都會以小概率犯錯誤，從而并不是往信息素最多的點移動。螞蟻找窩的規(guī)則和上面一樣，只不過它對窩的信息素做出反應，而對食物信息素沒反應。2.蟻群算法的特征n移動規(guī)則移動規(guī)則每只螞蟻都朝向信息素最多的方向移，并且，當周圍沒有信息素指引的時候，螞蟻會按照自己原來運動的方向慣性的運動下去，并且，在運動的方向有一個隨機的小的擾動。為了防止螞蟻原地轉(zhuǎn)圈，它會記住剛才走過了哪些點，如果發(fā)現(xiàn)要走的下一點已經(jīng)在之前走過了，它就會盡量避開。n避障規(guī)則避障規(guī)則如

10、果螞蟻要移動的方向有障礙物擋住，它會隨機的選擇另一個方向，并且有信息素指引的話，它會按照覓食的規(guī)則行為。n信息素規(guī)則信息素規(guī)則每只螞蟻在剛找到食物或者窩的時候撒發(fā)的信息素最多，并隨著它走遠的距離，播撒的信息素越來越少。根據(jù)這幾條規(guī)則，螞蟻之間并沒有直接的關(guān)系，但是每只螞蟻都和環(huán)境發(fā)生交互，而通過信息素這個紐帶，實際上把各個螞蟻之間關(guān)聯(lián)起來了。比如，當一只螞蟻找到了食物，它并沒有直接告訴其它螞蟻這兒有食物，而是向環(huán)境播撒信息素，當其它的螞蟻經(jīng)過它附近的時候，就會感覺到信息素的存在，進而根據(jù)信息素的指引找到了食物。2.蟻群算法的特征n基本蟻群算法流程圖（詳細）1. 在初始狀態(tài)下，一群螞蟻外出，此時

11、沒有信息素，那么各自會隨機的選擇一條路徑。2. 在下一個狀態(tài)，每只螞蟻到達了不同的點，從初始點到這些點之間留下了信息素，螞蟻繼續(xù)走，已經(jīng)到達目標的螞蟻開始返回，與此同時，下一批螞蟻出動，它們都會按照各條路徑上信息素的多少選擇路線(selection)，更傾向于選擇信息素多的路徑走（當然也有隨機性）。3. 又到了再下一個狀態(tài)，剛剛沒有螞蟻經(jīng)過的路線上的信息素不同程度的揮發(fā)掉了(evaporation)，而剛剛經(jīng)過了螞蟻的路線信息素增強(reinforcement)。然后又出動一批螞蟻，重復第2個步驟。每個狀態(tài)到下一個狀態(tài)的變化稱為一次迭代，在迭代多次過后，就會有某一條路徑上的信息素明顯多于其它路

12、徑，這通常就是一條最優(yōu)路徑。 3.蟻群算法的數(shù)學模型n一般蟻群算法的框架主要有三個組成部分：n蟻群的活動；n信息素的揮發(fā)；n信息素的增強；n主要體現(xiàn)在轉(zhuǎn)移概率公式和信息素更新公式。3.蟻群算法的數(shù)學模型n蟻群算法數(shù)學模型在路徑搜索過程中，螞蟻會根據(jù)路徑上信息素的多少及距離啟發(fā)信息進行節(jié)點間的轉(zhuǎn)移。螞蟻在時刻由節(jié)點轉(zhuǎn)移到節(jié)點的狀態(tài)轉(zhuǎn)移概率如式所示：3.蟻群算法的數(shù)學模型另外，為了避免殘留信息素過多引起殘留信息淹沒啟發(fā)信息, 在每只螞蟻走完一步或者完成對所有n個元素的遍歷后, 要對殘留信息進行更新處理。由此, t+n時刻在路徑(i,j) 上的信息量可按如下規(guī)則進行調(diào)整其更新規(guī)則如下式所示：由于信息

13、素更新策略的不同, 以及城市規(guī)模取值在適當范圍時，全局搜索能使之得到更優(yōu)的解，因此采用全局信息素更新規(guī)則，形式如下：式中，Q表示螞蟻循環(huán)一周，且在一定程度上影響算法收斂速度的信息素總量；Lk表示本次循環(huán)中，螞蟻k所走路段的長度。3.蟻群算法的數(shù)學模型n蟻群的規(guī)模和停止規(guī)則n蟻群大小:一般情況下蟻群中螞蟻的個數(shù)不超過TSP圖中節(jié)點的個數(shù)。n終止條件: 1 給定一個外循環(huán)的最大數(shù)目，表明已經(jīng)有足夠的螞蟻工作； 2 當前最優(yōu)解連續(xù)K次相同而停止，其中K是一個給定的整數(shù)，表示算法已經(jīng)收斂，不再需要繼續(xù)； 3 目標值控制規(guī)則，給定優(yōu)化問題（目標最小化）的一個下界和一個誤差值，當算法得到的目標值同下界之差

14、小于給定的誤差值時，算法終止。4.蟻群算法的模型類型根據(jù)信息素更新策略的不同, M. Dorigo 曾提出3 種不同的基本蟻群算法模型,其差別在于kij (t)求法的不同,即:nAnt - Cycle 模型nAnt - Quantity 模型nAnt - Density 模型其中Ant - antity 模型和Ant - Density 模型利用的是局部信息; 而Ant- Cycle 模型利用的是整體信息, 在求解TSP 時性能較好, 因此通常采用Ant - Cycle 模型模型作為蟻群算法的基本模型。4.蟻群算法的模型類型nAnt-Cycle模型n式中，Q表示信息素強度，它在一定程度上影響算

15、法的收斂速度；Lk表示第k只螞蟻在本次循環(huán)中所走路徑的總長度。4.蟻群算法的模型類型nAnt-Quantity模型n Ant-Density模型 4.蟻群算法的模型類型n區(qū)別后兩個式子中利用的是局部信息，即螞蟻完成一步后更新路徑上的信息素；而第一個式中利用的是全局信息，即螞蟻完成一個循環(huán)后更新所有路徑上的信息素，在求解TSP時性能較好，因此通常采用第一個模型作為蟻群算法的基本模型。4.蟻群算法的模型類型n下面是一些最常用的變異蟻群算法變異蟻群算法n1.精英螞蟻系統(tǒng)全局最優(yōu)解決方案在每個迭代以及其他所有的螞蟻的沉積信息素。n2.最大最小螞蟻系統(tǒng)（ MMAS）添加的最大和最小的信息素量 max ，

16、 min ，只有全局最佳或迭代最好的巡邏沉積的信息素。所有的邊緣都被初始化為max并且當接近停滯時重新初始化為max。n3.蟻群系統(tǒng)蟻群系統(tǒng)已被提出。n4.基于排序的螞蟻系統(tǒng)（ ASrank ）所有解決方案都根據(jù)其長度排名。然后為每個解決方案衡量信息素的沉積量，最短路徑相比較長路徑的解沉積了更多的信息素。n5.連續(xù)正交蟻群（COAC）COAC的信息素沉積機制能使螞蟻協(xié)作而有效地尋解。 利用正交設(shè)計方法，在可行域的螞蟻可以使用增大的全局搜索能力和精度，快速、高效地探索他們選擇的區(qū)域。 正交設(shè)計方法和自適應半徑調(diào)整方法也可推廣到其他優(yōu)化算法中，在解決實際問題施展更大的威力。5.蟻群算法的優(yōu)缺點蟻群

17、算法的優(yōu)點： n蟻群算法與其他啟發(fā)式算法相比，在求解性能上，具有很強的魯棒性（對基本蟻群算法模型稍加修改，便可以應用于其他問題）和搜索較好解的能力。 n蟻群算法是一種基于種群的進化算法，具有本質(zhì)并行性，易于并行實現(xiàn)。 n蟻群算法很容易與多種啟發(fā)式算法結(jié)合，以改善算法性能。 5.蟻群算法的優(yōu)缺點蟻群算法存在的問題：nTSP問題是一類經(jīng)典的組合優(yōu)化問題，即在給定城市個數(shù)和各城市之間距離的條件下，找到一條遍歷所有城市且每個城市只能訪問一次的總路程最短的路線。蟻群算法在TSP問題應用中取得了良好的效果，但是也存在一些不足： （1）如果參數(shù)設(shè)置不當，導致求解速度很慢且所得解的質(zhì)量特別差。 （2）基本蟻群

18、算法計算量大，求解所需時間較長。 （3）基本蟻群算法中理論上要求所有的螞蟻選擇同一路線，該線路即為所求的最優(yōu)線路；但在實際計算中，在給定一定循環(huán)數(shù)的條件下很難達到這種情況。 另一方面，在其它的實際應用中，如圖像處理中尋求最優(yōu)模板問題，我們并不要求所有的螞蟻都找到最優(yōu)模板，而只需要一只找到最優(yōu)模板即可。如果要求所有的螞蟻都找到最優(yōu)模板，反而影響了計算效率。 蟻群算法收斂速度慢、易陷入局部最優(yōu)。蟻群算法中初始信息素匱乏。蟻群算法收斂速度慢、易陷入局部最優(yōu)。蟻群算法中初始信息素匱乏。 蟻群算法一般需要較長的搜索時間，其復雜度可以反映這一點；而且該方法容易出現(xiàn)停滯現(xiàn)象，即搜索進行到一定程度后，所有個體

19、發(fā)現(xiàn)的解完全一致，不能對解空間進一步進行搜索，不利于發(fā)現(xiàn)更好的解。 6.蟻群算法所解決的問題n調(diào)度問題調(diào)度問題n車間作業(yè)調(diào)度問題（ JSP ）n開放式車間調(diào)度問題（ OSP ）n排列流水車間問題（ PFSP ）n單機總延遲時間問題（ SMTTP ）n單機總加權(quán)延遲問題（ SMTWTP ）n資源受限項目調(diào)度問題（ RCPSP ）n車間組調(diào)度問題（ GSP ）n附帶依賴安裝時間順序的單機總延遲問題（ SMTTPDST ）n附帶順序相依設(shè)置/轉(zhuǎn)換時間的多階段流水車間調(diào)度問題（ MFSP ）n車輛路徑問題車輛路徑問題n限量車輛路徑問題（ CVRP ）n多站車輛路徑問題（ MDVRP ）n周期車輛路徑問

20、題（ PVRP ）n分批配送車輛路徑問題（ SDVRP ）n隨機車輛路徑問題（ SVRP ）n裝貨配送的車輛路徑問題（ VRPPD ）n帶有時間窗的車輛路徑問題（ VRPTW）n依賴時間的時間窗車輛路徑問題（ TDVRPTW ）1.帶時間窗和復合服務員工的車輛路徑問題（ VRPTWMS ）6.蟻群算法所解決的問題n分配問題分配問題n二次分配問題（ QAP）n廣義分配問題（GAP）n頻率分配問題（ FAP ）n冗余分配問題（ RAP ）n設(shè)置問題設(shè)置問題n覆蓋設(shè)置問題（ SCP ）n分區(qū)設(shè)置問題（ SPP ）n約束重量的樹圖劃分問題（ WCGTPP ）n加權(quán)弧L-基數(shù)樹問題（ AWlCTP ）n

21、多背包問題（MKP）n最大獨立集問題（ MIS ）n其他其他n面向關(guān)系的網(wǎng)絡路由n無連接網(wǎng)絡路由n數(shù)據(jù)挖掘n項目調(diào)度中的貼現(xiàn)現(xiàn)金流n分布式信息檢索n網(wǎng)格工作流調(diào)度問題n圖像處理n系統(tǒng)識別n蛋白質(zhì)折疊1.電子電路設(shè)計6.蟻群算法所解決的問題蟻群優(yōu)化算法已應用于許多組合優(yōu)化問題，包括蛋白質(zhì)折疊或路由車輛的二次分配問題，很多派生的方法已經(jīng)應用于實變量動力學問題，隨機問題，多目標并行的實現(xiàn)。它也被用于產(chǎn)生貨郎擔問題的擬最優(yōu)解。在圖表動態(tài)變化的情況下解決相似問題時，他們相比模擬退火和遺傳算法方法有優(yōu)勢；蟻群算法可以連續(xù)運行并適應實時變化。這在網(wǎng)絡路由和城市交通系統(tǒng)中是有利的。 第一蟻群優(yōu)化算法被稱為“螞

22、蟻系統(tǒng)”，它旨在解決貨郎擔問題，其目標是要找到一系列城市的最短遍歷路線?？傮w算法相對簡單，它基于一組螞蟻，每只完成一次城市間的遍歷。在每個階段，螞蟻根據(jù)一些規(guī)則選擇從一個城市移動到另一個：它必須訪問每個城市一次;一個越遠的城市被選中的機會越少（能見度更低）;在兩個城市邊際的一邊形成的信息素越濃烈，這邊被選擇的概率越大;如果路程短的話，已經(jīng)完成旅程的螞蟻會在所有走過的路徑上沉積更多信息素，每次迭代后，信息素軌跡揮發(fā)。6.蟻群算法所解決的問題n在實驗和應用中，蟻群算法有他的優(yōu)勢也有自己的劣勢，但若與其他方法相結(jié)合，也能對解決問題的可行性和有效性有一定的幫助。下面列出與蟻群算法相關(guān)的方法n遺傳算法（

23、GA）支持一系列的解決方案。解的合并或突變增加了解集，其中質(zhì)量低劣的解被丟棄，尋找高級解決方案的過程模仿了這一演變。n模擬退火（SA）是一個全局優(yōu)化相關(guān)的通過產(chǎn)生當前解的相鄰解來遍歷搜索空間的技術(shù)。高級的相鄰解總是可接受的。低級的相鄰解可能會根據(jù)基于質(zhì)量和溫度參數(shù)德差異的概率被接受。溫度參數(shù)隨著算法的進程被修改以改變搜索的性質(zhì)。n反作用搜索優(yōu)化的重點在于將機器學習與優(yōu)化的結(jié)合，加入內(nèi)部反饋回路以根據(jù)問題、根據(jù)實例、根據(jù)當前解的附近情況的特點自動調(diào)整算法的自由參數(shù)。n禁忌搜索（ TS ）類似于模擬退火，他們都是通過測試獨立解的突變來遍歷解空間的。而模擬退火算法對于一個獨立解只生成一個突變，禁忌搜

24、索會產(chǎn)生許多變異解并且移動到產(chǎn)生的解中的符合度最低的一個。為了防止循環(huán)并且促進在解空間中的更大進展，由部分或完整的解組建維系了一個禁忌列表。移動到元素包含于禁忌列表的解是禁止，禁忌列表隨著解遍歷解空間的過程而不斷更新。n人工免疫系統(tǒng)（AIS）算法仿照了脊椎動物的免疫系統(tǒng)。n粒子群優(yōu)化（PSO ），群智能方法n引力搜索算法（ GSA ），群智能方法n蟻群聚類方法（ ACCM中） ，這個方法利用了聚類方法擴展了蟻群優(yōu)化。n隨機傳播搜索（ SDS ），基于代理的概率全局搜索和優(yōu)化技術(shù)，最適合于將目標函數(shù)分解成多個獨立的分布函數(shù)的優(yōu)化問題。7.蟻群算法的應用n應用領(lǐng)域蟻群算法能夠被用于解決大多數(shù)優(yōu)化問

25、題或者能夠轉(zhuǎn)化為優(yōu)化求解的問題?，F(xiàn)在其應用領(lǐng)域已擴展到多目標優(yōu)化、數(shù)據(jù)分類、數(shù)據(jù)聚類、模式識別、電信QoS管理、生物系統(tǒng)建模、流程規(guī)劃、信號處理、機器人控制、決策支持以及仿真和系統(tǒng)辯識等方面，群智能理論和方法為解決這類應用問題提供了新的途徑。7.蟻群算法的應用n蟻群算法的模型改進及其應用近年來, 國內(nèi)外學者在蟻群算法的模型改進和應用方面做了大量的工作, 其共同目的是在合理時間復雜度的限制條件下, 盡可能提高蟻群算法在一定空間復雜度下的尋優(yōu)能力, 從而改善蟻群算法的全局收斂性, 并拓寬蟻群算法的應用領(lǐng)域。(部分的蟻群算法改進模型及其應用情況-附Pr-1)7.蟻群算法的應用n蟻群優(yōu)化算法應用現(xiàn)狀隨

26、著群智能理論和應用算法研究的不斷發(fā)展，研究者已嘗試著將其用于各種工程優(yōu)化問題，并取得了意想不到的收獲。多種研究表明，群智能在離散求解空間和連續(xù)求解空間中均表現(xiàn)出良好的搜索效果，并在組合優(yōu)化問題中表現(xiàn)突出。 蟻群優(yōu)化算法并不是旅行商問題的最佳解決方法，但是它卻為解決組合優(yōu)化問題提供了新思路，并很快被應用到其它組合優(yōu)化問題中。比較典型的應用研究包括：網(wǎng)絡路由優(yōu)化、數(shù)據(jù)挖掘以及一些經(jīng)典的組合優(yōu)化問題。 7.蟻群算法的應用蟻群算法在電信路由優(yōu)化中已取得了一定的應用成果。HP公司和英國電信公司在90年代中后期都開展了這方面的研究，設(shè)計了蟻群路由算法（Ant Colony Routing, ACR）。 每

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