蟻群算法簡(jiǎn)述

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

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

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

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

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

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

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

8、是一種啟發(fā)式算法；計(jì)算復(fù)雜性為 O(NC*m*n2)，其中NC 是迭代次數(shù)，m 是螞蟻數(shù)目，n 是目的節(jié)點(diǎn)數(shù)目。2.蟻群算法的特征2.蟻群算法的特征n移動(dòng)規(guī)則移動(dòng)規(guī)則每只螞蟻都朝向信息素最多的方向移，并且，當(dāng)周圍沒有信息素指引的時(shí)候，螞蟻會(huì)按照自己原來(lái)運(yùn)動(dòng)的方向慣性的運(yùn)動(dòng)下去，并且，在運(yùn)動(dòng)的方向有一個(gè)隨機(jī)的小的擾動(dòng)。為了防止螞蟻原地轉(zhuǎn)圈，它會(huì)記住剛才走過了哪些點(diǎn)，如果發(fā)現(xiàn)要走的下一點(diǎn)已經(jīng)在之前走過了，它就會(huì)盡量避開。n避障規(guī)則避障規(guī)則如果螞蟻要移動(dòng)的方向有障礙物擋住，它會(huì)隨機(jī)的選擇另一個(gè)方向，并且有信息素指引的話，它會(huì)按照覓食的規(guī)則行為。n信息素規(guī)則信息素規(guī)則每只螞蟻在剛找到食物或者窩的時(shí)候撒

9、發(fā)的信息素最多，并隨著它走遠(yuǎn)的距離，播撒的信息素越來(lái)越少。根據(jù)這幾條規(guī)則，螞蟻之間并沒有直接的關(guān)系，但是每只螞蟻都和環(huán)境發(fā)生交互，而通過信息素這個(gè)紐帶，實(shí)際上把各個(gè)螞蟻之間關(guān)聯(lián)起來(lái)了。比如，當(dāng)一只螞蟻找到了食物，它并沒有直接告訴其它螞蟻這兒有食物，而是向環(huán)境播撒信息素，當(dāng)其它的螞蟻經(jīng)過它附近的時(shí)候，就會(huì)感覺到信息素的存在，進(jìn)而根據(jù)信息素的指引找到了食物。2.蟻群算法的特征n基本蟻群算法流程圖（詳細(xì)）1. 在初始狀態(tài)下，一群螞蟻外出，此時(shí)沒有信息素，那么各自會(huì)隨機(jī)的選擇一條路徑。2. 在下一個(gè)狀態(tài)，每只螞蟻到達(dá)了不同的點(diǎn)，從初始點(diǎn)到這些點(diǎn)之間留下了信息素，螞蟻繼續(xù)走，已經(jīng)到達(dá)目標(biāo)的螞蟻開始返回，

10、與此同時(shí)，下一批螞蟻出動(dòng)，它們都會(huì)按照各條路徑上信息素的多少選擇路線(selection)，更傾向于選擇信息素多的路徑走（當(dāng)然也有隨機(jī)性）。3. 又到了再下一個(gè)狀態(tài)，剛剛沒有螞蟻經(jīng)過的路線上的信息素不同程度的揮發(fā)掉了(evaporation)，而剛剛經(jīng)過了螞蟻的路線信息素增強(qiáng)(reinforcement)。然后又出動(dòng)一批螞蟻，重復(fù)第2個(gè)步驟。每個(gè)狀態(tài)到下一個(gè)狀態(tài)的變化稱為一次迭代，在迭代多次過后，就會(huì)有某一條路徑上的信息素明顯多于其它路徑，這通常就是一條最優(yōu)路徑。 3.蟻群算法的數(shù)學(xué)模型n一般蟻群算法的框架主要有三個(gè)組成部分：1.蟻群的活動(dòng)；2.信息素的揮發(fā)；3.信息素的增強(qiáng)；n主要體現(xiàn)在轉(zhuǎn)移

11、概率公式和信息素更新公式。3.蟻群算法的數(shù)學(xué)模型n蟻群算法數(shù)學(xué)模型在路徑搜索過程中，螞蟻會(huì)根據(jù)路徑上信息素的多少及距離啟發(fā)信息進(jìn)行節(jié)點(diǎn)間的轉(zhuǎn)移。螞蟻在時(shí)刻由節(jié)點(diǎn)轉(zhuǎn)移到節(jié)點(diǎn)的狀態(tài)轉(zhuǎn)移概率如式所示：3.蟻群算法的數(shù)學(xué)模型另外，為了避免殘留信息素過多引起殘留信息淹沒啟發(fā)信息, 在每只螞蟻?zhàn)咄暌徊交蛘咄瓿蓪?duì)所有n個(gè)元素的遍歷后, 要對(duì)殘留信息進(jìn)行更新處理。由此, t+n時(shí)刻在路徑(i,j) 上的信息量可按如下規(guī)則進(jìn)行調(diào)整其更新規(guī)則如下式所示：由于信息素更新策略的不同, 以及城市規(guī)模取值在適當(dāng)范圍時(shí)，全局搜索能使之得到更優(yōu)的解，因此采用全局信息素更新規(guī)則，形式如下：式中，Q表示螞蟻循環(huán)一周，且在一定程度

12、上影響算法收斂速度的信息素總量；Lk表示本次循環(huán)中，螞蟻k所走路段的長(zhǎng)度。3.蟻群算法的數(shù)學(xué)模型n蟻群的規(guī)模和停止規(guī)則n蟻群大小:一般情況下蟻群中螞蟻的個(gè)數(shù)不超過TSP圖中節(jié)點(diǎn)的個(gè)數(shù)。n終止條件: 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)化問題（目標(biāo)最小化）的一個(gè)下界和一個(gè)誤差值，當(dāng)算法得到的目標(biāo)值同下界之差小于給定的誤差值時(shí)，算法終止。4.蟻群算法的模型類型根據(jù)信息素更新策略的不同, M. Dorigo 曾提出3 種不同的基本蟻群算法模型,其差別在于kij

13、(t)求法的不同,即:nAnt - Cycle 模型nAnt - Quantity 模型nAnt - Density 模型其中Ant - antity 模型和Ant - Density 模型利用的是局部信息; 而Ant- Cycle 模型利用的是整體信息, 在求解TSP 時(shí)性能較好, 因此通常采用Ant - Cycle 模型模型作為蟻群算法的基本模型。4.蟻群算法的模型類型nAnt-Cycle模型n式中，Q表示信息素強(qiáng)度，它在一定程度上影響算法的收斂速度；Lk表示第k只螞蟻在本次循環(huán)中所走路徑的總長(zhǎng)度。4.蟻群算法的模型類型nAnt-Quantity模型n Ant-Density模型 4.蟻群

14、算法的模型類型n區(qū)別后兩個(gè)式子中利用的是局部信息，即螞蟻完成一步后更新路徑上的信息素；而第一個(gè)式中利用的是全局信息，即螞蟻完成一個(gè)循環(huán)后更新所有路徑上的信息素，在求解TSP時(shí)性能較好，因此通常采用第一個(gè)模型作為蟻群算法的基本模型。4.蟻群算法的模型類型n下面是一些最常用的變異蟻群算法變異蟻群算法n1.精英螞蟻系統(tǒng)全局最優(yōu)解決方案在每個(gè)迭代以及其他所有的螞蟻的沉積信息素。n2.最大最小螞蟻系統(tǒng)（ MMAS）添加的最大和最小的信息素量 max ， min ，只有全局最佳或迭代最好的巡邏沉積的信息素。所有的邊緣都被初始化為max并且當(dāng)接近停滯時(shí)重新初始化為max。n3.蟻群系統(tǒng)蟻群系統(tǒng)已被提出。n4

15、.基于排序的螞蟻系統(tǒng)（ ASrank ）所有解決方案都根據(jù)其長(zhǎng)度排名。然后為每個(gè)解決方案衡量信息素的沉積量，最短路徑相比較長(zhǎng)路徑的解沉積了更多的信息素。n5.連續(xù)正交蟻群（COAC）COAC的信息素沉積機(jī)制能使螞蟻協(xié)作而有效地尋解。 利用正交設(shè)計(jì)方法，在可行域的螞蟻可以使用增大的全局搜索能力和精度，快速、高效地探索他們選擇的區(qū)域。 正交設(shè)計(jì)方法和自適應(yīng)半徑調(diào)整方法也可推廣到其他優(yōu)化算法中，在解決實(shí)際問題施展更大的威力。5.蟻群算法的優(yōu)缺點(diǎn)蟻群算法的優(yōu)點(diǎn)： n蟻群算法與其他啟發(fā)式算法相比，在求解性能上，具有很強(qiáng)的魯棒性（對(duì)基本蟻群算法模型稍加修改，便可以應(yīng)用于其他問題）和搜索較好解的能力。 n蟻

16、群算法是一種基于種群的進(jìn)化算法，具有本質(zhì)并行性，易于并行實(shí)現(xiàn)。 n蟻群算法很容易與多種啟發(fā)式算法結(jié)合，以改善算法性能。 5.蟻群算法的優(yōu)缺點(diǎn)蟻群算法存在的問題：nTSP問題是一類經(jīng)典的組合優(yōu)化問題，即在給定城市個(gè)數(shù)和各城市之間距離的條件下，找到一條遍歷所有城市且每個(gè)城市只能訪問一次的總路程最短的路線。蟻群算法在TSP問題應(yīng)用中取得了良好的效果，但是也存在一些不足： （1）如果參數(shù)設(shè)置不當(dāng)，導(dǎo)致求解速度很慢且所得解的質(zhì)量特別差。 （2）基本蟻群算法計(jì)算量大，求解所需時(shí)間較長(zhǎng)。 （3）基本蟻群算法中理論上要求所有的螞蟻選擇同一路線，該線路即為所求的最優(yōu)線路；但在實(shí)際計(jì)算中，在給定一定循環(huán)數(shù)的條件下

17、很難達(dá)到這種情況。 另一方面，在其它的實(shí)際應(yīng)用中，如圖像處理中尋求最優(yōu)模板問題，我們并不要求所有的螞蟻都找到最優(yōu)模板，而只需要一只找到最優(yōu)模板即可。如果要求所有的螞蟻都找到最優(yōu)模板，反而影響了計(jì)算效率。 蟻群算法收斂速度慢、易陷入局部最優(yōu)。蟻群算法中初始信息素匱乏。蟻群算法收斂速度慢、易陷入局部最優(yōu)。蟻群算法中初始信息素匱乏。 蟻群算法一般需要較長(zhǎng)的搜索時(shí)間，其復(fù)雜度可以反映這一點(diǎn)；而且該方法容易出現(xiàn)停滯現(xiàn)象，即搜索進(jìn)行到一定程度后，所有個(gè)體發(fā)現(xiàn)的解完全一致，不能對(duì)解空間進(jìn)一步進(jìn)行搜索，不利于發(fā)現(xiàn)更好的解。 6.蟻群算法所解決的問題n調(diào)度問題調(diào)度問題1.車間作業(yè)調(diào)度問題（ JSP ）2.開放式

18、車間調(diào)度問題（ OSP ）3.排列流水車間問題（ PFSP ）4.單機(jī)總延遲時(shí)間問題（ SMTTP ）5.單機(jī)總加權(quán)延遲問題（ SMTWTP ）6.資源受限項(xiàng)目調(diào)度問題（ RCPSP ）7.車間組調(diào)度問題（ GSP ）8.附帶依賴安裝時(shí)間順序的單機(jī)總延遲問題（ SMTTPDST ）9.附帶順序相依設(shè)置/轉(zhuǎn)換時(shí)間的多階段流水車間調(diào)度問題（ MFSP ）n車輛路徑問題車輛路徑問題1.限量車輛路徑問題（ CVRP ）2.多站車輛路徑問題（ MDVRP ）3.周期車輛路徑問題（ PVRP ）4.分批配送車輛路徑問題（ SDVRP ）5.隨機(jī)車輛路徑問題（ SVRP ）6.裝貨配送的車輛路徑問題（ VR

19、PPD ）7.帶有時(shí)間窗的車輛路徑問題（ VRPTW）8.依賴時(shí)間的時(shí)間窗車輛路徑問題（ TDVRPTW ）9.帶時(shí)間窗和復(fù)合服務(wù)員工的車輛路徑問題（ VRPTWMS ）6.蟻群算法所解決的問題n分配問題分配問題1.二次分配問題（ QAP）2.廣義分配問題（GAP）3.頻率分配問題（ FAP ）4.冗余分配問題（ RAP ）n設(shè)置問題設(shè)置問題1.覆蓋設(shè)置問題（ SCP ）2.分區(qū)設(shè)置問題（ SPP ）3.約束重量的樹圖劃分問題（ WCGTPP ）4.加權(quán)弧L-基數(shù)樹問題（ AWlCTP ）5.多背包問題（MKP）6.最大獨(dú)立集問題（ MIS ）n其他其他1.面向關(guān)系的網(wǎng)絡(luò)路由2.無(wú)連接網(wǎng)絡(luò)路由

20、3.數(shù)據(jù)挖掘4.項(xiàng)目調(diào)度中的貼現(xiàn)現(xiàn)金流5.分布式信息檢索6.網(wǎng)格工作流調(diào)度問題7.圖像處理8.系統(tǒng)識(shí)別9.蛋白質(zhì)折疊10.電子電路設(shè)計(jì)6.蟻群算法所解決的問題蟻群優(yōu)化算法已應(yīng)用于許多組合優(yōu)化問題，包括蛋白質(zhì)折疊或路由車輛的二次分配問題，很多派生的方法已經(jīng)應(yīng)用于實(shí)變量動(dòng)力學(xué)問題，隨機(jī)問題，多目標(biāo)并行的實(shí)現(xiàn)。它也被用于產(chǎn)生貨郎擔(dān)問題的擬最優(yōu)解。在圖表動(dòng)態(tài)變化的情況下解決相似問題時(shí)，他們相比模擬退火和遺傳算法方法有優(yōu)勢(shì)；蟻群算法可以連續(xù)運(yùn)行并適應(yīng)實(shí)時(shí)變化。這在網(wǎng)絡(luò)路由和城市交通系統(tǒng)中是有利的。 第一蟻群優(yōu)化算法被稱為“螞蟻系統(tǒng)”，它旨在解決貨郎擔(dān)問題，其目標(biāo)是要找到一系列城市的最短遍歷路線?？傮w算法

21、相對(duì)簡(jiǎn)單，它基于一組螞蟻，每只完成一次城市間的遍歷。在每個(gè)階段，螞蟻根據(jù)一些規(guī)則選擇從一個(gè)城市移動(dòng)到另一個(gè)：它必須訪問每個(gè)城市一次;一個(gè)越遠(yuǎn)的城市被選中的機(jī)會(huì)越少（能見度更低）;在兩個(gè)城市邊際的一邊形成的信息素越濃烈，這邊被選擇的概率越大;如果路程短的話，已經(jīng)完成旅程的螞蟻會(huì)在所有走過的路徑上沉積更多信息素，每次迭代后，信息素軌跡揮發(fā)。6.蟻群算法所解決的問題n在實(shí)驗(yàn)和應(yīng)用中，蟻群算法有他的優(yōu)勢(shì)也有自己的劣勢(shì)，但若與其他方法相結(jié)合，也能對(duì)解決問題的可行性和有效性有一定的幫助。下面列出與蟻群算法相關(guān)的方法n遺傳算法（GA）支持一系列的解決方案。解的合并或突變?cè)黾恿私饧?，其中質(zhì)量低劣的解被丟棄，尋

22、找高級(jí)解決方案的過程模仿了這一演變。n模擬退火（SA）是一個(gè)全局優(yōu)化相關(guān)的通過產(chǎn)生當(dāng)前解的相鄰解來(lái)遍歷搜索空間的技術(shù)。高級(jí)的相鄰解總是可接受的。低級(jí)的相鄰解可能會(huì)根據(jù)基于質(zhì)量和溫度參數(shù)德差異的概率被接受。溫度參數(shù)隨著算法的進(jìn)程被修改以改變搜索的性質(zhì)。n反作用搜索優(yōu)化的重點(diǎn)在于將機(jī)器學(xué)習(xí)與優(yōu)化的結(jié)合，加入內(nèi)部反饋回路以根據(jù)問題、根據(jù)實(shí)例、根據(jù)當(dāng)前解的附近情況的特點(diǎn)自動(dòng)調(diào)整算法的自由參數(shù)。n禁忌搜索（ TS ）類似于模擬退火，他們都是通過測(cè)試獨(dú)立解的突變來(lái)遍歷解空間的。而模擬退火算法對(duì)于一個(gè)獨(dú)立解只生成一個(gè)突變，禁忌搜索會(huì)產(chǎn)生許多變異解并且移動(dòng)到產(chǎn)生的解中的符合度最低的一個(gè)。為了防止循環(huán)并且促進(jìn)在

23、解空間中的更大進(jìn)展，由部分或完整的解組建維系了一個(gè)禁忌列表。移動(dòng)到元素包含于禁忌列表的解是禁止，禁忌列表隨著解遍歷解空間的過程而不斷更新。n人工免疫系統(tǒng)（AIS）算法仿照了脊椎動(dòng)物的免疫系統(tǒng)。n粒子群優(yōu)化（PSO ），群智能方法n引力搜索算法（ GSA ），群智能方法n蟻群聚類方法（ ACCM中） ，這個(gè)方法利用了聚類方法擴(kuò)展了蟻群優(yōu)化。n隨機(jī)傳播搜索（ SDS ），基于代理的概率全局搜索和優(yōu)化技術(shù)，最適合于將目標(biāo)函數(shù)分解成多個(gè)獨(dú)立的分布函數(shù)的優(yōu)化問題。7.蟻群算法的應(yīng)用n應(yīng)用領(lǐng)域蟻群算法能夠被用于解決大多數(shù)優(yōu)化問題或者能夠轉(zhuǎn)化為優(yōu)化求解的問題?，F(xiàn)在其應(yīng)用領(lǐng)域已擴(kuò)展到多目標(biāo)優(yōu)化、數(shù)據(jù)分類、數(shù)據(jù)

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

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

26、一只螞蟻因?yàn)榻?jīng)過了網(wǎng)絡(luò)中堵塞的路由而導(dǎo)致了比較大的延遲，那么就對(duì)該表項(xiàng)做較大的增強(qiáng)。同時(shí)根據(jù)信息素?fù)]發(fā)機(jī)制實(shí)現(xiàn)系統(tǒng)的信息更新，從而拋棄過期的路由信息。這樣，在當(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ì)和特性非常相似。7.蟻群算法的應(yīng)用基于群智能的聚類算法起源于對(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)