1、a,1,蟻群算法的基本原理與改進(jìn),a,2,蟻群算法,蟻群算法(ant colony alogrithm)是一種模擬進(jìn)化算法。 蟻群算法（又稱為人工蟻群算法）是由意大利學(xué)者M(jìn).Dorigo，V.Mahiezzo，A.Colorni等人受到人們對(duì)自然界中真是蟻群集體行為的研究成果的啟發(fā)而首先提出來的。這個(gè)算法的主要目的是在圖中尋找優(yōu)化路徑的機(jī)率算法。 蟻群算法最早是為了解決TSP問題（即旅行商問題）。 TSP問題的要求：路徑的限制是每個(gè)城市只能拜訪一次；最后要回到原來出發(fā)的城市。求得的路徑路程為所有路徑之中的最小值。,a,3,概念原型 各個(gè)螞蟻在沒有事先告訴他們食物在什么地方的前提下開始尋找食物。

2、 當(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ù)著。,a,4,基本原理 蟻群算法是對(duì)自然界螞蟻的尋徑方式進(jìn)行模似而得出的一種仿生算法。 螞蟻在運(yùn)動(dòng)過程中，能夠在它所經(jīng)過的路徑上留下一種稱之為外激素(pheromone

3、)的物質(zhì)進(jìn)行信息傳遞，而且螞蟻在運(yùn)動(dòng)過程中能夠感知這種物質(zhì)，并以此指導(dǎo)自己的運(yùn)動(dòng)方向，因此由大量螞蟻組成的蟻群集體行為便表現(xiàn)出一種信息正反饋現(xiàn)象：某一路徑上走過的螞蟻越多，則后來者選擇該路徑的概率就越大。,a,5,假設(shè)以下條件： 每個(gè)時(shí)間單位有30只螞蟻（A-B） 每個(gè)時(shí)間單位有30只螞蟻（E-D） 螞蟻過后留下的外激素為1 初始時(shí)刻，路徑無信息存在且位于B和E可以隨機(jī)選擇路徑 HD = HB = 1 CD = CB = 0.5 圖中的數(shù)字表示距離,a,6,假設(shè)以下條件： 每個(gè)時(shí)間單位有30只螞蟻（A-B） 每個(gè)時(shí)間單位有30只螞蟻（E-D） 螞蟻過后留下的外激素為1 初始時(shí)刻，路徑無信息存在

4、且位于B和E可以隨機(jī)選擇路徑 HD = HB = 1 CD = CB = 0.5 備注： D-H D-C B-H B-C 圖中數(shù)字表示螞蟻的個(gè)數(shù),a,7,假設(shè)以下條件： 每個(gè)時(shí)間單位有30只螞蟻（A-B） 每個(gè)時(shí)間單位有30只螞蟻（E-D） 螞蟻過后留下的外激素為1 初始時(shí)刻，路徑無信息存在且位于B和E可以隨機(jī)選擇路徑 HD = HB = 1 CD = CB = 0.5 備注： D-H D-C B-H B-C 圖中數(shù)字表示螞蟻的個(gè)數(shù),a,8,下面以TSP為例說明基本蟻群算法模型。 首先將m只螞蟻隨機(jī)放置在n個(gè)城市，位于城市i的第k只螞蟻選擇下一個(gè)城市j的概率為:,a,9,螞蟻算法求解TSP,其

5、中： 表示邊（i，j）上的信息素濃度； 是啟發(fā)信息，d是城市i和j之間的距離； 和反映了信息素與啟發(fā)信息的相對(duì)重要性； 表示螞蟻k已經(jīng)訪問過的城市列表。 當(dāng)所有螞蟻完成周游后，按以下公式進(jìn)行信息素更新。,a,10,螞蟻算法求解TSP,其中：為小于1的常數(shù)，表示信息的持久性。,其中：Q為常數(shù)；lk表示第k只螞蟻在本次迭代中走過的路徑，Lk為路徑長(zhǎng)度。,a,11,求解TSP算法步驟,初始化 隨機(jī)放置螞蟻，為每只螞蟻建立禁忌表tabuk，將初始節(jié)點(diǎn)置入禁忌表中; 迭代過程 k=1 while k=ItCount do (執(zhí)行迭代) for i = 1 to m do (對(duì)m只螞蟻循環(huán)) for j

6、= 1 to n - 1 do (對(duì)n個(gè)城市循環(huán)) 根據(jù)式(1)，采用輪盤賭方法在窗口外選擇下一個(gè)城市j; 將j置入禁忌表,螞蟻轉(zhuǎn)移到j(luò); end for end for 計(jì)算每只螞蟻的路徑長(zhǎng)度; 根據(jù)式(2)更新所有螞蟻路徑上的信息量; k = k + 1; end while 輸出結(jié)果,結(jié)束算法.,a,12,基本蟻群算法流程,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ì)按照各條路徑上信息素的多少選擇路線

7、(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)路徑。,a,13,蟻群算法采用了分布式正反饋并行計(jì)算機(jī)制, 易于與其他方法結(jié)合, 并具有較強(qiáng)的魯棒性。 （1）其原理是一種正反饋機(jī)制或稱增強(qiáng)型學(xué)習(xí)系統(tǒng)；它通過信息素的不斷更新達(dá)到最終收斂于最優(yōu)路徑上；

8、（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ù)目。,a,14,下面是對(duì)蟻群算法的進(jìn)行過程中采用的規(guī)則進(jìn)行的一些說明。 范圍 螞蟻觀察到的范圍是一個(gè)方格世界，螞蟻有一個(gè)參數(shù)為速度半徑（一般是3），那么它能觀察到的范圍就是3*3個(gè)方格世界，并且能移動(dòng)的距離也

9、在這個(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)。,a,15,移動(dòng)規(guī)則 每只螞蟻都朝向信息素

10、最多的方向移，并且，當(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)一只螞

11、蟻找到了食物，它并沒有直接告訴其它螞蟻這兒有食物，而是向環(huán)境播撒信息素，當(dāng)其它的螞蟻經(jīng)過它附近的時(shí)候，就會(huì)感覺到信息素的存在，進(jìn)而根據(jù)信息素的指引找到了食物。,a,16,一般蟻群算法的框架主要有三個(gè)組成部分： 蟻群的活動(dòng)； 信息素的揮發(fā)； 信息素的增強(qiáng)； 主要體現(xiàn)在轉(zhuǎn)移概率公式和信息素更新公式。,a,17,蟻群的規(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)最

12、小化）的一個(gè)下界和一個(gè)誤差值，當(dāng)算法得到的目標(biāo)值同下界之差小于給定的誤差值時(shí)，算法終止。,a,18,蟻群算法的優(yōu)點(diǎn),蟻群算法與其他啟發(fā)式算法相比，在求解性能上，具有很強(qiáng)的魯棒性（對(duì)基本蟻群算法模型稍加修改，便可以應(yīng)用于其他問題）和搜索較好解的能力。 蟻群算法是一種基于種群的進(jìn)化算法，具有本質(zhì)并行性，易于并行實(shí)現(xiàn)。 蟻群算法很容易與多種啟發(fā)式算法結(jié)合，以改善算法性能。,a,19,蟻群算法存在的問題,TSP問題是一類經(jīng)典的組合優(yōu)化問題，即在給定城市個(gè)數(shù)和各城市之間距離的條件下，找到一條遍歷所有城市且每個(gè)城市只能訪問一次的總路程最短的路線。蟻群算法在TSP問題應(yīng)用中取得了良好的效果，但是也存在一些不

13、足： （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)更好的解。,a,20,算法改進(jìn),下面是一些最常用的變異蟻群算法 1.精英螞蟻系統(tǒng) 全局最優(yōu)解決方案在每個(gè)迭代以及其他所有的螞蟻的沉積信息素。 2.最大最小螞蟻系統(tǒng)（ MMAS） 添加的最大和最小的信息素量 max ， min ，只有全局最佳或迭代最好的巡邏沉積的信息素。所有的邊緣都被初始化為max并且當(dāng)接近停滯時(shí)重新初始化為max。 3.蟻群系統(tǒng) 蟻群系統(tǒng)已被提出。,a,21,4.基于排序的螞蟻系統(tǒng)（ A