蟻群算法簡(jiǎn)述

關(guān)于蟻群算法簡(jiǎn)述第1頁，講稿共36頁，2023年5月2日，星期三1.蟻群算法的提出算法的提出 蟻群算法（AntColonyOptimization,ACO），又稱螞蟻算法——一種用來在圖中尋找優(yōu)化路徑的機(jī)率型算法。 它由MarcoDorigo于1992年在他的博士論文“Antsystem:optimizationbyacolonyofcooperatingagents”中提出，其靈感來源于螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為。最早用于解決著名的旅行商問題(TSP,travelingsalesmanproblem)。第2頁，講稿共36頁，2023年5月2日，星期三1.蟻群算法的提出概念原型 各個(gè)螞蟻在沒有事先告訴他們食物在什么地方的前提下開始尋找食物。 當(dāng)一只找到食物以后，它會(huì)向環(huán)境釋放一種揮發(fā)性分泌物pheromone(稱為信息素,該物質(zhì)隨著時(shí)間的推移會(huì)逐漸揮發(fā)消失，信息素濃度的大小表征路徑的遠(yuǎn)近)來實(shí)現(xiàn)的，吸引其他的螞蟻過來，這樣越來越多的螞蟻會(huì)找到食物。 有些螞蟻并沒有象其它螞蟻一樣總重復(fù)同樣的路，他們會(huì)另辟蹊徑，如果另開辟的道路比原來的其他道路更短，那么，漸漸地，更多的螞蟻被吸引到這條較短的路上來。 最后，經(jīng)過一段時(shí)間運(yùn)行，就可能會(huì)出現(xiàn)一條最短的路徑被大多數(shù)螞蟻重復(fù)著。第3頁，講稿共36頁，2023年5月2日，星期三1.蟻群算法的提出基本原理

蟻群算法是對(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)象：某一路徑上走過的螞蟻越多，則后來者選擇該路徑的概率就越大。第4頁，講稿共36頁，2023年5月2日，星期三1.蟻群算法的提出簡(jiǎn)化的螞蟻尋食過程

螞蟻從A點(diǎn)出發(fā)，速度相同，食物在D點(diǎn)，可能隨機(jī)選擇路線ABD或ACD。假設(shè)初始時(shí)每條分配路線一只螞蟻，每個(gè)時(shí)間單位行走一步，本圖為經(jīng)過9個(gè)時(shí)間單位時(shí)的情形：走ABD的螞蟻到達(dá)終點(diǎn)，而走ACD的螞蟻剛好走到C點(diǎn)，為一半路程。第5頁，講稿共36頁，2023年5月2日，星期三1.蟻群算法的提出

本圖為從開始算起，經(jīng)過18個(gè)時(shí)間單位時(shí)的情形：走ABD的螞蟻到達(dá)終點(diǎn)后得到食物又返回了起點(diǎn)A，而走ACD的螞蟻剛好走到D點(diǎn)。第6頁，講稿共36頁，2023年5月2日，星期三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í)間單位后，兩條線路上的信息素單位積累為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)。第7頁，講稿共36頁，2023年5月2日，星期三1.蟻群算法的提出人工蟻群算法 基于以上蟻群尋找食物時(shí)的最優(yōu)路徑選擇問題，可以構(gòu)造人工蟻群，來解決最優(yōu)化問題，如TSP問題。 人工蟻群中把具有簡(jiǎn)單功能的工作單元看作螞蟻。二者的相似之處在于都是優(yōu)先選擇信息素濃度大的路徑。較短路徑的信息素濃度高，所以能夠最終被所有螞蟻選擇，也就是最終的優(yōu)化結(jié)果。 兩者的區(qū)別在于人工蟻群有一定的記憶能力，能夠記憶已經(jīng)訪問過的節(jié)點(diǎn)。同時(shí)，人工蟻群再選擇下一條路徑的時(shí)候是按一定算法規(guī)律有意識(shí)地尋找最短路徑，而不是盲目的。例如在TSP問題中，可以預(yù)先知道當(dāng)前城市到下一個(gè)目的地的距離。第8頁，講稿共36頁，2023年5月2日，星期三1.蟻群算法的提出1)標(biāo)有距離的路徑圖2)在0時(shí)刻，路徑上沒有信息素累積，螞蟻選擇路徑為任意3)在1時(shí)刻，路徑上信息素堆積，短邊信息素多與長(zhǎng)邊，所以螞蟻更傾向于選擇ABCDE第9頁，講稿共36頁，2023年5月2日，星期三2.蟻群算法的特征

蟻群算法采用了分布式正反饋并行計(jì)算機(jī)制,易于與其他方法結(jié)合,并具有較強(qiáng)的魯棒性。（1）其原理是一種正反饋機(jī)制或稱增強(qiáng)型學(xué)習(xí)系統(tǒng)；它通過信息素的不斷更新達(dá)到最終收斂于最優(yōu)路徑上；（2）它是一種通用型隨機(jī)優(yōu)化方法；但人工螞蟻決不是對(duì)實(shí)際螞蟻的一種簡(jiǎn)單模擬，它融進(jìn)了人類的智能；（3）它是一種分布式的優(yōu)化方法；不僅適合目前的串行計(jì)算機(jī)，而且適合未來的并行計(jì)算機(jī)；（4）它是一種全局優(yōu)化的方法；不僅可用于求解單目標(biāo)優(yōu)化問題，而且可用于求解多目標(biāo)優(yōu)化問題；（5）它是一種啟發(fā)式算法；計(jì)算復(fù)雜性為O(NC*m*n2)，其中NC是迭代次數(shù)，m是螞蟻數(shù)目，n是目的節(jié)點(diǎn)數(shù)目。第10頁，講稿共36頁，2023年5月2日，星期三2.蟻群算法的特征下面是對(duì)蟻群算法的進(jìn)行過程中采用的規(guī)則進(jìn)行的一些說明。范圍 螞蟻觀察到的范圍是一個(gè)方格世界，螞蟻有一個(gè)參數(shù)為速度半徑（一般是3），那么它能觀察到的范圍就是3*3個(gè)方格世界，并且能移動(dòng)的距離也在這個(gè)范圍之內(nèi)。環(huán)境 螞蟻所在的環(huán)境是一個(gè)虛擬的世界，其中有障礙物，有別的螞蟻，還有信息素，信息素有兩種，一種是找到食物的螞蟻灑下的食物信息素，一種是找到窩的螞蟻灑下的窩的信息素。每個(gè)螞蟻都僅僅能感知它范圍內(nèi)的環(huán)境信息。環(huán)境以一定的速率讓信息素消失。覓食規(guī)則 在每只螞蟻能感知的范圍內(nèi)尋找是否有食物，如果有就直接過去。否則看是否有信息素，并且比較在能感知的范圍內(nèi)哪一點(diǎn)的信息素最多，這樣，它就朝信息素多的地方走，并且每只螞蟻都會(huì)以小概率犯錯(cuò)誤，從而并不是往信息素最多的點(diǎn)移動(dòng)。螞蟻找窩的規(guī)則和上面一樣，只不過它對(duì)窩的信息素做出反應(yīng)，而對(duì)食物信息素沒反應(yīng)。第11頁，講稿共36頁，2023年5月2日，星期三2.蟻群算法的特征移動(dòng)規(guī)則 每只螞蟻都朝向信息素最多的方向移，并且，當(dāng)周圍沒有信息素指引的時(shí)候，螞蟻會(huì)按照自己原來運(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ì)盡量避開。避障規(guī)則 如果螞蟻要移動(dòng)的方向有障礙物擋住，它會(huì)隨機(jī)的選擇另一個(gè)方向，并且有信息素指引的話，它會(huì)按照覓食的規(guī)則行為。信息素規(guī)則 每只螞蟻在剛找到食物或者窩的時(shí)候撒發(fā)的信息素最多，并隨著它走遠(yuǎn)的距離，播撒的信息素越來越少。 根據(jù)這幾條規(guī)則，螞蟻之間并沒有直接的關(guān)系，但是每只螞蟻都和環(huán)境發(fā)生交互，而通過信息素這個(gè)紐帶，實(shí)際上把各個(gè)螞蟻之間關(guān)聯(lián)起來了。比如，當(dāng)一只螞蟻找到了食物，它并沒有直接告訴其它螞蟻這兒有食物，而是向環(huán)境播撒信息素，當(dāng)其它的螞蟻經(jīng)過它附近的時(shí)候，就會(huì)感覺到信息素的存在，進(jìn)而根據(jù)信息素的指引找到了食物。第12頁，講稿共36頁，2023年5月2日，星期三2.蟻群算法的特征基本蟻群算法流程圖（詳細(xì)）1.在初始狀態(tài)下，一群螞蟻外出，此時(shí)沒有信息素，那么各自會(huì)隨機(jī)的選擇一條路徑。

2.在下一個(gè)狀態(tài)，每只螞蟻到達(dá)了不同的點(diǎn)，從初始點(diǎn)到這些點(diǎn)之間留下了信息素，螞蟻繼續(xù)走，已經(jīng)到達(dá)目標(biāo)的螞蟻開始返回，與此同時(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)路徑。第13頁，講稿共36頁，2023年5月2日，星期三3.蟻群算法的數(shù)學(xué)模型一般蟻群算法的框架主要有三個(gè)組成部分：蟻群的活動(dòng)；信息素的揮發(fā)；信息素的增強(qiáng)；主要體現(xiàn)在轉(zhuǎn)移概率公式和信息素更新公式。第14頁，講稿共36頁，2023年5月2日，星期三3.蟻群算法的數(shù)學(xué)模型蟻群算法數(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)移概率如式所示：第15頁，講稿共36頁，2023年5月2日，星期三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)一周，且在一定程度上影響算法收斂速度的信息素總量；Lk表示本次循環(huán)中，螞蟻k所走路段的長(zhǎng)度。第16頁，講稿共36頁，2023年5月2日，星期三3.蟻群算法的數(shù)學(xué)模型蟻群的規(guī)模和停止規(guī)則蟻群大小:

一般情況下蟻群中螞蟻的個(gè)數(shù)不超過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)化問題（目標(biāo)最小化）的一個(gè)下界和一個(gè)誤差值，當(dāng)算法得到的目標(biāo)值同下界之差小于給定的誤差值時(shí)，算法終止。第17頁，講稿共36頁，2023年5月2日，星期三4.蟻群算法的模型類型

根據(jù)信息素更新策略的不同,M.Dorigo曾提出3種不同的基本蟻群算法模型,其差別在于Δτkij(t)求法的不同,即:Ant-Cycle模型Ant-Quantity模型Ant-Density模型 其中Ant-antity模型和Ant-Density模型利用的是局部信息;而Ant-Cycle模型利用的是整體信息,在求解TSP時(shí)性能較好,因此通常采用Ant-Cycle模型作為蟻群算法的基本模型。第18頁，講稿共36頁，2023年5月2日，星期三4.蟻群算法的模型類型Ant-Cycle模型式中，Q表示信息素強(qiáng)度，它在一定程度上影響算法的收斂速度；Lk表示第k只螞蟻在本次循環(huán)中所走路徑的總長(zhǎng)度。第19頁，講稿共36頁，2023年5月2日，星期三4.蟻群算法的模型類型Ant-Quantity模型

Ant-Density模型第20頁，講稿共36頁，2023年5月2日，星期三4.蟻群算法的模型類型區(qū)別 后兩個(gè)式子中利用的是局部信息，即螞蟻完成一步后更新路徑上的信息素；而第一個(gè)式中利用的是全局信息，即螞蟻完成一個(gè)循環(huán)后更新所有路徑上的信息素，在求解TSP時(shí)性能較好，因此通常采用第一個(gè)模型作為蟻群算法的基本模型。第21頁，講稿共36頁，2023年5月2日，星期三4.蟻群算法的模型類型下面是一些最常用的變異蟻群算法1.精英螞蟻系統(tǒng) 全局最優(yōu)解決方案在每個(gè)迭代以及其他所有的螞蟻的沉積信息素。2.最大最小螞蟻系統(tǒng)（MMAS） 添加的最大和最小的信息素量[τmax，τmin]，只有全局最佳或迭代最好的巡邏沉積的信息素。所有的邊緣都被初始化為τmax并且當(dāng)接近停滯時(shí)重新初始化為τmax。3.蟻群系統(tǒng) 蟻群系統(tǒng)已被提出。4.基于排序的螞蟻系統(tǒng)（ASrank） 所有解決方案都根據(jù)其長(zhǎng)度排名。然后為每個(gè)解決方案衡量信息素的沉積量，最短路徑相比較長(zhǎng)路徑的解沉積了更多的信息素。5.連續(xù)正交蟻群（COAC）

COAC的信息素沉積機(jī)制能使螞蟻協(xié)作而有效地尋解。利用正交設(shè)計(jì)方法，在可行域的螞蟻可以使用增大的全局搜索能力和精度，快速、高效地探索他們選擇的區(qū)域。正交設(shè)計(jì)方法和自適應(yīng)半徑調(diào)整方法也可推廣到其他優(yōu)化算法中，在解決實(shí)際問題施展更大的威力。第22頁，講稿共36頁，2023年5月2日，星期三5.蟻群算法的優(yōu)缺點(diǎn)蟻群算法的優(yōu)點(diǎn)：蟻群算法與其他啟發(fā)式算法相比，在求解性能上，具有很強(qiáng)的魯棒性（對(duì)基本蟻群算法模型稍加修改，便可以應(yīng)用于其他問題）和搜索較好解的能力。蟻群算法是一種基于種群的進(jìn)化算法，具有本質(zhì)并行性，易于并行實(shí)現(xiàn)。蟻群算法很容易與多種啟發(fā)式算法結(jié)合，以改善算法性能。第23頁，講稿共36頁，2023年5月2日，星期三5.蟻群算法的優(yōu)缺點(diǎn)蟻群算法存在的問題：TSP問題是一類經(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ù)的條件下很難達(dá)到這種情況。 另一方面，在其它的實(shí)際應(yīng)用中，如圖像處理中尋求最優(yōu)模板問題，我們并不要求所有的螞蟻都找到最優(yōu)模板，而只需要一只找到最優(yōu)模板即可。如果要求所有的螞蟻都找到最優(yōu)模板，反而影響了計(jì)算效率。 蟻群算法收斂速度慢、易陷入局部最優(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)更好的解。第24頁，講稿共36頁，2023年5月2日，星期三6.蟻群算法所解決的問題調(diào)度問題車間作業(yè)調(diào)度問題（JSP）開放式車間調(diào)度問題（OSP）排列流水車間問題（PFSP）單機(jī)總延遲時(shí)間問題（SMTTP）單機(jī)總加權(quán)延遲問題（SMTWTP）資源受限項(xiàng)目調(diào)度問題（RCPSP）車間組調(diào)度問題（GSP）附帶依賴安裝時(shí)間順序的單機(jī)總延遲問題（SMTTPDST）附帶順序相依設(shè)置/轉(zhuǎn)換時(shí)間的多階段流水車間調(diào)度問題（MFSP）車輛路徑問題限量車輛路徑問題（CVRP）多站車輛路徑問題（MDVRP）周期車輛路徑問題（PVRP）分批配送車輛路徑問題（SDVRP）隨機(jī)車輛路徑問題（SVRP）裝貨配送的車輛路徑問題（VRPPD）帶有時(shí)間窗的車輛路徑問題（VRPTW）依賴時(shí)間的時(shí)間窗車輛路徑問題（TDVRPTW）帶時(shí)間窗和復(fù)合服務(wù)員工的車輛路徑問題（VRPTWMS）第25頁，講稿共36頁，2023年5月2日，星期三6.蟻群算法所解決的問題分配問題二次分配問題（QAP）廣義分配問題（GAP）頻率分配問題（FAP）冗余分配問題（RAP）設(shè)置問題覆蓋設(shè)置問題（SCP）分區(qū)設(shè)置問題（SPP）約束重量的樹圖劃分問題（WCGTPP）加權(quán)弧L-基數(shù)樹問題（AWlCTP）多背包問題（MKP）最大獨(dú)立集問題（MIS）其他面向關(guān)系的網(wǎng)絡(luò)路由無連接網(wǎng)絡(luò)路由數(shù)據(jù)挖掘項(xiàng)目調(diào)度中的貼現(xiàn)現(xiàn)金流分布式信息檢索網(wǎng)格工作流調(diào)度問題圖像處理系統(tǒng)識(shí)別蛋白質(zhì)折疊電子電路設(shè)計(jì)第26頁，講稿共36頁，2023年5月2日，星期三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算法相對(duì)簡(jiǎn)單，它基于一組螞蟻，每只完成一次城市間的遍歷。在每個(gè)階段，螞蟻根據(jù)一些規(guī)則選擇從一個(gè)城市移動(dòng)到另一個(gè)：它必須訪問每個(gè)城市一次;一個(gè)越遠(yuǎn)的城市被選中的機(jī)會(huì)越少（能見度更低）;在兩個(gè)城市邊際的一邊形成的信息素越濃烈，這邊被選擇的概率越大;如果路程短的話，已經(jīng)完成旅程的螞蟻會(huì)在所有走過的路徑上沉積更多信息素，每次迭代后，信息素軌跡揮發(fā)。第27頁，講稿共36頁，2023年5月2日，星期三6.蟻群算法所解決的問題在實(shí)驗(yàn)和應(yīng)用中，蟻群算法有他的優(yōu)勢(shì)也有自己的劣勢(shì)，但若與其他方法相結(jié)合，也能對(duì)解決問題的可行性和有效性有一定的幫助。下面列出與蟻群算法相關(guān)的方法遺傳算法（GA）支持一系列的解決方案。解的合并或突變?cè)黾恿私饧渲匈|(zhì)量低劣的解被丟棄，尋找高級(jí)解決方案的過程模仿了這一演變。模擬退火（SA）是一個(gè)全局優(yōu)化相關(guān)??的通過產(chǎn)生當(dāng)前解的相鄰解來遍歷搜索空間的技術(shù)。高級(jí)的相鄰解總是可接受的。低級(jí)的相鄰解可能會(huì)根據(jù)基于質(zhì)量和溫度參數(shù)德差異的概率被接受。溫度參數(shù)隨著算法的進(jìn)程被修改以改變搜索的性質(zhì)。反作用搜索優(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ù)。禁忌搜索（TS）類似于模擬退火，他們都是通過測(cè)試獨(dú)立解的突變來遍歷解空間的。而模擬退火算法對(duì)于一個(gè)獨(dú)立解只生成一個(gè)突變，禁忌搜索會(huì)產(chǎn)生許多變異解并且移動(dòng)到產(chǎn)生的解中的符合度最低的一個(gè)。為了防止循環(huán)并且促進(jìn)在解空間中的更大進(jìn)展，由部分或完整的解組建維系了一個(gè)禁忌列表。移動(dòng)到元素包含于禁忌列表的解是禁止，禁忌列表隨著解遍歷解空間的過程而不斷更新。人工免疫系統(tǒng)（AIS）算法仿照了脊椎動(dòng)物的免疫系統(tǒng)。粒子群優(yōu)化（PSO），群智能方法引力搜索算法（GSA），群智能方法蟻群聚類方法（ACCM中），這個(gè)方法利用了聚類方法擴(kuò)展了蟻群優(yōu)化。隨機(jī)傳播搜索（SDS），基于代理的概率全局搜索和優(yōu)化技術(shù)，最適合于將目標(biāo)函數(shù)分解成多個(gè)獨(dú)立的分布函數(shù)的優(yōu)化問題。第28頁，講稿共36頁，2023年5月2日，星期三7.蟻群算法的應(yīng)用應(yīng)用領(lǐng)域 蟻群算法能夠被用于解決大多數(shù)優(yōu)化問題或者能夠轉(zhuǎn)化為優(yōu)化求解的問題。 現(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)用問題提供了新的途徑。第29頁，講稿共36頁，2023年5月2日，星期三7.蟻群算法的應(yīng)用蟻群算法的模型改進(jìn)及其應(yīng)用 近年來,國(guó)內(nèi)外學(xué)者在蟻群算法的模型改進(jìn)和應(yīng)用方面做了大量的工作,其共同目的是在合理時(shí)間復(fù)雜度的限制條件下,盡可能提高蟻群算法在一定空間復(fù)雜度下的尋優(yōu)能力,從而改善蟻群算法的全局收斂性,并拓寬蟻群算法的應(yīng)用領(lǐng)域。(部分的蟻群算法改進(jìn)模型及其應(yīng)用情況--附Pr-1)第30頁，講稿共36頁，2023年5月2日，星期三7.蟻群算法的應(yīng)用蟻群優(yōu)化算法應(yīng)用現(xiàn)狀 隨著群智能理論和應(yīng)用算法研究的不斷發(fā)展，研究者已嘗試著將其用于各種工程優(yōu)化問題，并取得了意想不到的收獲。多種研究表明，群智能在離散求解空間和連續(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)化問題。

第31頁，講稿共36頁，2023年5月2日，星期三7.蟻群算法的應(yīng)用

蟻群算法在電信路由優(yōu)化中已取得了一定的應(yīng)用成果。HP公司和英國(guó)電信公司在90年代中后期都開展了這方面的研究，設(shè)計(jì)了蟻群路由算法（AntColonyRouting,ACR）。每只螞蟻就像蟻群優(yōu)化算法中一樣，根據(jù)它在網(wǎng)絡(luò)上的經(jīng)驗(yàn)與性能，動(dòng)態(tài)更新路由表項(xiàng)。如果一只螞蟻因?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í)