蟻群算法原理介紹

1、大 綱 蟻群算法的起源 蟻群行為描述 蟻群算法的基本思想 基本蟻群算法的系統(tǒng)學(xué)特征 TSP問題描述 基本蟻群算法的數(shù)學(xué)模型 基本蟻群算法的應(yīng)用舉例 總結(jié)蟻群算法起源蟻群算法起源蟻群算法蟻群算法(ant colony optimization, ACO)：Dorigo M于于1991年提出，其靈感來源于螞蟻年提出，其靈感來源于螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為。在尋找食物過程中發(fā)現(xiàn)路徑的行為。 通過模擬通過模擬自然界螞蟻搜索路徑的行為，提出來一種新型自然界螞蟻搜索路徑的行為，提出來一種新型的模擬進(jìn)化算法。的模擬進(jìn)化算法。TSP問題、分配問題、問題、分配問題、job-shop調(diào)度問題調(diào)度問題蟻群行

2、為描述蟻群行為描述CBEF3030AD蟻穴蟻穴食物源食物源d=1d=1d=0.5d=0.5ADCBEF303015151515釋放信息素與路徑長度成反比釋放信息素與路徑長度成反比蟻群行為描述蟻群行為描述ADCBEF303010102020ADCBEF30303030信息量大，路徑被選概率大信息量大，路徑被選概率大基本蟻群算法的機(jī)制原理基本蟻群算法的機(jī)制原理ADCBEF303015151515ADCBEF30303030路徑路徑BFC：螞蟻增加，信息量增加，路徑被選擇的機(jī)率增加；：螞蟻增加，信息量增加，路徑被選擇的機(jī)率增加；路徑路徑BEC：時(shí)間增加，：時(shí)間增加，信息量減少，路徑被選擇的機(jī)率減小。

3、信息量減少，路徑被選擇的機(jī)率減小?；鞠伻核惴ǖ南到y(tǒng)學(xué)特征基本蟻群算法的系統(tǒng)學(xué)特征蟻群算法是一個(gè)系統(tǒng)蟻群算法是一個(gè)系統(tǒng)分布式計(jì)算分布式計(jì)算自組織自組織正反饋正反饋蟻群算法是一個(gè)系統(tǒng)蟻群算法是一個(gè)系統(tǒng)Bertalanffy L V： 系統(tǒng)可以確定為處于一定的相互關(guān)系中系統(tǒng)可以確定為處于一定的相互關(guān)系中并與環(huán)境發(fā)生關(guān)系的各組成部分（要素）的并與環(huán)境發(fā)生關(guān)系的各組成部分（要素）的綜合體。綜合體。多元性多元性 整體性整體性 相關(guān)性相關(guān)性 系統(tǒng)特征系統(tǒng)特征螞蟻的個(gè)體行為是系統(tǒng)的元素螞蟻的個(gè)體行為是系統(tǒng)的元素蟻群行為的相互影響蟻群行為的相互影響蟻群能完成個(gè)體完蟻群能完成個(gè)體完成不了的任務(wù)成不了的任務(wù)整體大

4、于部分之和整體大于部分之和蟻群算法滿足分布式計(jì)算蟻群算法滿足分布式計(jì)算分布式系統(tǒng)：依賴于個(gè)體行為，但并不單獨(dú)依賴于分布式系統(tǒng)：依賴于個(gè)體行為，但并不單獨(dú)依賴于每一個(gè)體的行為。每一個(gè)體的行為。在蟻群中，許多螞蟻都為共同目的進(jìn)行著同樣的工在蟻群中，許多螞蟻都為共同目的進(jìn)行著同樣的工作，而最終任務(wù)的完成不會(huì)由于某些個(gè)體（螞蟻）作，而最終任務(wù)的完成不會(huì)由于某些個(gè)體（螞蟻）的缺陷而受到影響。的缺陷而受到影響。蟻群算法具有自組織的特征蟻群算法具有自組織的特征系統(tǒng)外部系統(tǒng)外部系統(tǒng)內(nèi)部系統(tǒng)內(nèi)部組織行為組織行為他組織他組織自組織自組織自組織：在沒有外界作用自組織：在沒有外界作用下使得系統(tǒng)熵增加的組織下使得系統(tǒng)熵

5、增加的組織無序無序有序有序蟻群算法具有正反饋的特征蟻群算法具有正反饋的特征削弱未來行為削弱未來行為加強(qiáng)未來行為加強(qiáng)未來行為反饋反饋負(fù)反饋負(fù)反饋正反饋正反饋在蟻群中，在蟻群中，信息素的堆積信息素的堆積就是一個(gè)正反饋就是一個(gè)正反饋?zhàn)越M織是正反饋和負(fù)反饋的結(jié)合自組織是正反饋和負(fù)反饋的結(jié)合自組織自組織負(fù)反饋負(fù)反饋正反饋正反饋縮小搜索范圍縮小搜索范圍保持搜索范圍保持搜索范圍TSP描述描述TSP問題（問題（Traveling Salesman Problem）：）：即旅行商問題，是數(shù)學(xué)領(lǐng)域中著名問題之一。假設(shè)即旅行商問題，是數(shù)學(xué)領(lǐng)域中著名問題之一。假設(shè)有一個(gè)旅行商人要拜訪有一個(gè)旅行商人要拜訪N個(gè)城市，他必

6、須選擇所要個(gè)城市，他必須選擇所要走的路徑，路徑的限制是走的路徑，路徑的限制是每個(gè)城市只能拜訪一次，每個(gè)城市只能拜訪一次，而且最后要回到原來出發(fā)的城市而且最后要回到原來出發(fā)的城市。路徑的選擇目標(biāo)。路徑的選擇目標(biāo)是要求得的路徑路程為所有路徑之中的是要求得的路徑路程為所有路徑之中的最小值最小值。ATSP的目的的目的Hamilton圈圈TSP數(shù)學(xué)語言描述數(shù)學(xué)語言描述有向圖：有向圖：給定一個(gè)有向圖給定一個(gè)有向圖 的三元組為的三元組為 ，其，其中中 是一個(gè)非空集合，其元素稱為有向圖的是一個(gè)非空集合，其元素稱為有向圖的結(jié)點(diǎn)結(jié)點(diǎn) ； 是一個(gè)集合，其元素稱為有向圖的是一個(gè)集合，其元素稱為有向圖的弧段，弧段， 是

7、從是從 到到 上的一個(gè)映射（函數(shù)）上的一個(gè)映射（函數(shù)）一個(gè)一個(gè) 有向圖有向圖 ，可簡記為，可簡記為 D),(fEVVfVV ED),(EVETSP描述描述TSP：設(shè)設(shè) 是是 個(gè)城市的集合，個(gè)城市的集合， 是集合是集合 中元素兩兩連中元素兩兩連接的集合，接的集合， 是是 的的Euclidean距離，即距離，即)()(22yyxxdjijiijcccnC,21nCCLccljiij,), 2 , 1,(njidijlijC1C2C3CnLij基本蟻群算法的數(shù)學(xué)模型基本蟻群算法的數(shù)學(xué)模型 ：TSP的規(guī)模的規(guī)模 ：蟻群中螞蟻總數(shù)目，：蟻群中螞蟻總數(shù)目， ： 次循環(huán)次循環(huán) 上的殘留信息量的集合上的殘留信

8、息量的集合 ：禁忌表：禁忌表 ：狀態(tài)轉(zhuǎn)移概率：狀態(tài)轉(zhuǎn)移概率 ：在初始時(shí)刻各條路徑上的信息：在初始時(shí)刻各條路徑上的信息量相等量相等niitmb1)(nmCtccjiij,)(stijcon)0(t)(tPkij), 2 , 1(tabumkklij基本蟻群算法的數(shù)學(xué)模型基本蟻群算法的數(shù)學(xué)模型allowedkj，若，否則 0allowedisisijijkstt)() 1()() 1()(tPkij信息啟發(fā)式因子:期望啟發(fā)式因子:dijij1基本蟻群算法的數(shù)學(xué)模型基本蟻群算法的數(shù)學(xué)模型)()()1 () 1(tttijijij ：揮發(fā)系數(shù)：揮發(fā)系數(shù) ：信息素殘留因子：信息素殘留因子1)()(1tt

9、mkkijij) 1(tkijLkQ0信息素更新策略YesNo輸輸出出程程序序計(jì)計(jì)算算結(jié)結(jié)果果結(jié)結(jié)束束按按照照公公式式進(jìn)進(jìn)行行信信息息素素更更新新滿滿足足結(jié)結(jié)束束條條件件？螞螞蟻蟻k=k+1開開始始初初始始化化迭迭代代次次數(shù)數(shù)N=N+1 螞螞蟻蟻k=1按按照照狀狀態(tài)態(tài)轉(zhuǎn)轉(zhuǎn)移移概概率率公公式式選選擇擇下下一一個(gè)個(gè)城城市市修修改改禁禁忌忌表表螞螞蟻蟻總總數(shù)數(shù)？NoYes螞蟻圖的蟻群系統(tǒng)（GBAS）可以驗(yàn)證，下式滿足：即 是一個(gè)隨機(jī)矩陣。( )k( , )( )1,0iji jAkk 四個(gè)城市的非對稱TSP問題，距離矩陣和城市圖示如下：010.511011()1.55011110ijDd2.2.5

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

11、A f WWABDCA f W第一只第二只第三只第四只2.2.5 初始的蟻群優(yōu)化算法基于圖的蟻群系統(tǒng)（GBAS）按算法步驟3的信息素更新規(guī)則，得到更新矩陣這是第一次外循環(huán)結(jié)束的狀態(tài)。01 241 61 241 601 241 24(1)(1)1 241 1201 61 241 61 240ij2.2.5 初始的蟻群優(yōu)化算法基于圖的蟻群系統(tǒng)（GBAS）重復(fù)外循環(huán)，由于上一次得到的W2已經(jīng)是全局最優(yōu)解，因此按算法步驟3的信息素更新規(guī)則，無論螞蟻如何行走，都只是對W2路線上的城市信息素進(jìn)行增強(qiáng)，其他的城市信息素進(jìn)行揮發(fā)。得到更新矩陣這是第一次外循環(huán)結(jié)束的狀態(tài)。01 485 241 485 2401 481 48(2)(2)1 481 4805 241 485 241 480ij2.2.5 初始的蟻群優(yōu)化算法基于圖的蟻群系統(tǒng)（GBAS）重復(fù)外循環(huán)，由于W2全局最優(yōu)解，GBAS只記錄第一個(gè)最優(yōu)解，因此一但得到了全局最優(yōu)解，信息素的更新將不再依賴于以群的行走路線，而只是不斷增強(qiáng)最優(yōu)路線的信息素，同時(shí)進(jìn)行揮發(fā)。第三次外循環(huán)后得到的信息素矩陣為：01 9611 481 9611 4801 961 96(3)(3)1 961 96011 481 9611 481 960ij2.2.5 初始的蟻群優(yōu)化算法基于圖的蟻群系統(tǒng)（GBAS） 螞蟻以一定的概率從城市i到城市j進(jìn)行轉(zhuǎn)移，信息