蟻群算法簡(jiǎn)述

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

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

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

4、蟻到達(dá)終點(diǎn)，而走ACD的螞蟻剛好走到C點(diǎn)，為一半路程。1.蟻群算法的提出本圖為從開(kāi)始算起，經(jīng)過(guò)18個(gè)時(shí)間單位時(shí)的情形：走ABD的螞蟻到達(dá)終點(diǎn)后得到食物又返回了起點(diǎn)A，而走ACD的螞蟻剛好走到D點(diǎn)。1.蟻群算法的提出假設(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í)間單位后，

5、兩條線路上的信息素單位積累為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)。1.蟻群算法的提出n人工蟻群算法基于以上蟻群尋找食物時(shí)的最優(yōu)路徑選擇問(wèn)題，可以構(gòu)造人工蟻群，來(lái)解決最優(yōu)化問(wèn)題，如TSP問(wèn)題。人工蟻群中把具有簡(jiǎn)單功能的工作單元看作螞蟻。二者的相似之處在于都是優(yōu)先選擇信息素濃度大的路徑。較短路徑的信息素濃度高，所以能夠最終被所有螞

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

7、式正反饋并行計(jì)算機(jī)制, 易于與其他方法結(jié)合, 并具有較強(qiáng)的魯棒性。n（1）其原理是一種正反饋機(jī)制或稱(chēng)增強(qiáng)型學(xué)習(xí)系統(tǒng)；）其原理是一種正反饋機(jī)制或稱(chēng)增強(qiáng)型學(xué)習(xí)系統(tǒng)；它通過(guò)信息素的不斷更新達(dá)到最終收斂于最優(yōu)路徑上；n（2）它是一種通用型隨機(jī)優(yōu)化方法；）它是一種通用型隨機(jī)優(yōu)化方法；但人工螞蟻決不是對(duì)實(shí)際螞蟻的一種簡(jiǎn)單模擬，它融進(jìn)了人類(lèi)的智能；n（3）它是一種分布式的優(yōu)化方法；）它是一種分布式的優(yōu)化方法；不僅適合目前的串行計(jì)算機(jī)，而且適合未來(lái)的并行計(jì)算機(jī)；n（4）它是一種全局優(yōu)化的方法；）它是一種全局優(yōu)化的方法；不僅可用于求解單目標(biāo)優(yōu)化問(wèn)題，而且可用于求解多目標(biāo)優(yōu)化問(wèn)題；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)周?chē)鷽](méi)有信息素指引的時(shí)候，螞蟻會(huì)按照自己原來(lái)運(yùn)動(dòng)的方向慣性的運(yùn)動(dòng)下去，并且，在運(yùn)動(dòng)的方向有一個(gè)隨機(jī)的小的擾動(dòng)。為了防止螞蟻原地轉(zhuǎn)圈，它會(huì)記住剛才走過(guò)了哪些點(diǎn)，如果發(fā)現(xiàn)要走的下一點(diǎn)已經(jīng)在之前走過(guò)了，它就會(huì)盡量避開(kāi)。n避障規(guī)則避障規(guī)則如果螞蟻要移動(dòng)的方向有障礙物擋住，它會(huì)隨機(jī)的選擇另一個(gè)方向，并且有信息素指引的話，它會(huì)按照覓食的規(guī)則行為。n信息素規(guī)則信息素規(guī)則每只螞蟻在剛找到食物或者窩的時(shí)候撒

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

10、與此同時(shí)，下一批螞蟻出動(dòng)，它們都會(huì)按照各條路徑上信息素的多少選擇路線(selection)，更傾向于選擇信息素多的路徑走（當(dāng)然也有隨機(jī)性）。3. 又到了再下一個(gè)狀態(tài)，剛剛沒(méi)有螞蟻經(jīng)過(guò)的路線上的信息素不同程度的揮發(fā)掉了(evaporation)，而剛剛經(jīng)過(guò)了螞蟻的路線信息素增強(qiáng)(reinforcement)。然后又出動(dòng)一批螞蟻，重復(fù)第2個(gè)步驟。每個(gè)狀態(tài)到下一個(gè)狀態(tài)的變化稱(chēng)為一次迭代，在迭代多次過(guò)后，就會(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é)模型在路徑搜索過(guò)程中，螞蟻會(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é)模型另外，為了避免殘留信息素過(guò)多引起殘留信息淹沒(méi)啟發(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ù)不超過(guò)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)化問(wèn)題（目標(biāo)最小化）的一個(gè)下界和一個(gè)誤差值，當(dāng)算法得到的目標(biāo)值同下界之差小于給定的誤差值時(shí)，算法終止。4.蟻群算法的模型類(lèi)型根據(jù)信息素更新策略的不同, M. Dorigo 曾提出3 種不同的基本蟻群算法模型,其差別在于kij

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

14、算法的模型類(lèi)型n區(qū)別后兩個(gè)式子中利用的是局部信息，即螞蟻完成一步后更新路徑上的信息素；而第一個(gè)式中利用的是全局信息，即螞蟻完成一個(gè)循環(huán)后更新所有路徑上的信息素，在求解TSP時(shí)性能較好，因此通常采用第一個(gè)模型作為蟻群算法的基本模型。4.蟻群算法的模型類(lèi)型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í)際問(wèn)題施展更大的威力。5.蟻群算法的優(yōu)缺點(diǎn)蟻群算法的優(yōu)點(diǎn)： n蟻群算法與其他啟發(fā)式算法相比，在求解性能上，具有很強(qiáng)的魯棒性（對(duì)基本蟻群算法模型稍加修改，便可以應(yīng)用于其他問(wèn)題）和搜索較好解的能力。 n蟻

16、群算法是一種基于種群的進(jìn)化算法，具有本質(zhì)并行性，易于并行實(shí)現(xiàn)。 n蟻群算法很容易與多種啟發(fā)式算法結(jié)合，以改善算法性能。 5.蟻群算法的優(yōu)缺點(diǎn)蟻群算法存在的問(wèn)題：nTSP問(wèn)題是一類(lèi)經(jīng)典的組合優(yōu)化問(wèn)題，即在給定城市個(gè)數(shù)和各城市之間距離的條件下，找到一條遍歷所有城市且每個(gè)城市只能訪問(wèn)一次的總路程最短的路線。蟻群算法在TSP問(wèn)題應(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)模板問(wèn)題，我們并不要求所有的螞蟻都找到最優(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.蟻群算法所解決的問(wèn)題n調(diào)度問(wèn)題調(diào)度問(wèn)題1.車(chē)間作業(yè)調(diào)度問(wèn)題（ JSP ）2.開(kāi)放式

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

19、PPD ）7.帶有時(shí)間窗的車(chē)輛路徑問(wèn)題（ VRPTW）8.依賴(lài)時(shí)間的時(shí)間窗車(chē)輛路徑問(wèn)題（ TDVRPTW ）9.帶時(shí)間窗和復(fù)合服務(wù)員工的車(chē)輛路徑問(wèn)題（ VRPTWMS ）6.蟻群算法所解決的問(wèn)題n分配問(wèn)題分配問(wèn)題1.二次分配問(wèn)題（ QAP）2.廣義分配問(wèn)題（GAP）3.頻率分配問(wèn)題（ FAP ）4.冗余分配問(wèn)題（ RAP ）n設(shè)置問(wèn)題設(shè)置問(wèn)題1.覆蓋設(shè)置問(wèn)題（ SCP ）2.分區(qū)設(shè)置問(wèn)題（ SPP ）3.約束重量的樹(shù)圖劃分問(wèn)題（ WCGTPP ）4.加權(quán)弧L-基數(shù)樹(shù)問(wèn)題（ AWlCTP ）5.多背包問(wèn)題（MKP）6.最大獨(dú)立集問(wèn)題（ 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)度問(wèn)題7.圖像處理8.系統(tǒng)識(shí)別9.蛋白質(zhì)折疊10.電子電路設(shè)計(jì)6.蟻群算法所解決的問(wèn)題蟻群優(yōu)化算法已應(yīng)用于許多組合優(yōu)化問(wèn)題，包括蛋白質(zhì)折疊或路由車(chē)輛的二次分配問(wèn)題，很多派生的方法已經(jīng)應(yīng)用于實(shí)變量動(dòng)力學(xué)問(wèn)題，隨機(jī)問(wèn)題，多目標(biāo)并行的實(shí)現(xiàn)。它也被用于產(chǎn)生貨郎擔(dān)問(wèn)題的擬最優(yōu)解。在圖表動(dòng)態(tài)變化的情況下解決相似問(wèn)題時(shí)，他們相比模擬退火和遺傳算法方法有優(yōu)勢(shì)；蟻群算法可以連續(xù)運(yùn)行并適應(yīng)實(shí)時(shí)變化。這在網(wǎng)絡(luò)路由和城市交通系統(tǒng)中是有利的。 第一蟻群優(yōu)化算法被稱(chēng)為“螞蟻系統(tǒng)”，它旨在解決貨郎擔(dān)問(wèn)題，其目標(biāo)是要找到一系列城市的最短遍歷路線?？傮w算法

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

22、找高級(jí)解決方案的過(guò)程模仿了這一演變。n模擬退火（SA）是一個(gè)全局優(yōu)化相關(guān)的通過(guò)產(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ù)問(wèn)題、根據(jù)實(shí)例、根據(jù)當(dāng)前解的附近情況的特點(diǎn)自動(dòng)調(diào)整算法的自由參數(shù)。n禁忌搜索（ TS ）類(lèi)似于模擬退火，他們都是通過(guò)測(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)到元素包含于禁忌列表的解是禁止，禁忌列表隨著解遍歷解空間的過(guò)程而不斷更新。n人工免疫系統(tǒng)（AIS）算法仿照了脊椎動(dòng)物的免疫系統(tǒng)。n粒子群優(yōu)化（PSO ），群智能方法n引力搜索算法（ GSA ），群智能方法n蟻群聚類(lèi)方法（ ACCM中） ，這個(gè)方法利用了聚類(lèi)方法擴(kuò)展了蟻群優(yōu)化。n隨機(jī)傳播搜索（ SDS ），基于代理的概率全局搜索和優(yōu)化技術(shù)，最適合于將目標(biāo)函數(shù)分解成多個(gè)獨(dú)立的分布函數(shù)的優(yōu)化問(wèn)題。7.蟻群算法的應(yīng)用n應(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ù)分類(lèi)、數(shù)據(jù)

24、聚類(lèi)、模式識(shí)別、電信QoS管理、生物系統(tǒng)建模、流程規(guī)劃、信號(hào)處理、機(jī)器人控制、決策支持以及仿真和系統(tǒng)辯識(shí)等方面，群智能理論和方法為解決這類(lèi)應(yīng)用問(wèn)題提供了新的途徑。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)化問(wèn)題，并

25、取得了意想不到的收獲。多種研究表明，群智能在離散求解空間和連續(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)題。 7.蟻群算法的應(yīng)用蟻群算法在電信路由優(yōu)化中已取得了一定的應(yīng)用成果。HP公司和英國(guó)電信公司在90年代中后期都開(kāi)展了這方面的研究，設(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)過(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ì)和特性非常相似。7.蟻群算法的應(yīng)用基于群智能的聚類(lèi)算法起源于對(duì)蟻群蟻卵的分類(lèi)研究。Lumer和Faieta將Deneubourg提出將蟻巢分類(lèi)模型應(yīng)用于數(shù)據(jù)聚類(lèi)分析。其基本思想是將待聚類(lèi)數(shù)據(jù)隨機(jī)地散布到一個(gè)二維平面內(nèi)，然后將虛擬螞蟻分布到這個(gè)空間內(nèi)，并以隨機(jī)方式移動(dòng)，當(dāng)一只螞蟻遇到一個(gè)待聚類(lèi)數(shù)據(jù)時(shí)即將之拾起并繼續(xù)隨機(jī)運(yùn)動(dòng)，若運(yùn)動(dòng)