蟻群算法pt課件

1、蟻群算法Yuehui ChenSchool of Inform. Sci. and Eng.University of Jinan, 2011http:/12蟻群優(yōu)化算法起源 20世紀(jì)90年代意大利學(xué)者M(jìn)Dorigo，VManiezzo，AColorni等從生物進(jìn)化的機(jī)制中受到啟發(fā)，通過模擬自然界螞蟻搜索路徑的行為，提出來一種新型的模擬進(jìn)化算法 蟻群算法，是群智能理論研究領(lǐng)域的一種主要算法。用該方法求解TSP問題、分配問題、job-shop調(diào)度問題，取得了較好的試驗(yàn)結(jié)果雖然研究時(shí)間不長，但是現(xiàn)在的研究顯示出，蟻群算法在求解復(fù)雜優(yōu)化問題（特別是離散優(yōu)化問題）方面有一定優(yōu)勢，表明它是一種有發(fā)展前景

2、的算法3蟻群優(yōu)化算法研究背景 群智能理論研究領(lǐng)域有兩種主要的算法：蟻群算法(Ant Colony Optimization, ACO)和微粒群算法（Particle Swarm Optimization, PSO）。前者是對螞蟻群落食物采集過程的模擬，已成功應(yīng)用于許多離散優(yōu)化問題。微粒群算法也是起源于對簡單社會(huì)系統(tǒng)的模擬，最初是模擬鳥群覓食的過程，但后來發(fā)現(xiàn)它是一種很好的優(yōu)化工具。 4蟻群優(yōu)化算法研究背景與大多數(shù)基于梯度的應(yīng)用優(yōu)化算法不同，群智能依靠的是概率搜索算法。雖然概率搜索算法通常要采用較多的評(píng)價(jià)函數(shù)，但是與梯度方法及傳統(tǒng)的演化算法相比，其優(yōu)點(diǎn)還是顯著的 ，主要表現(xiàn)在以下幾個(gè)方面：1 無

3、集中控制約束，不會(huì)因個(gè)別個(gè)體的故障影響整個(gè)問題 的求解，確保了系統(tǒng)具備更強(qiáng)的魯棒性 2 以非直接的信息交流方式確保了系統(tǒng)的擴(kuò)展性 3 并行分布式算法模型，可充分利用多處理器 4 對問題定義的連續(xù)性無特殊要求 5 算法實(shí)現(xiàn)簡單 5蟻群優(yōu)化算法研究背景 群智能方法易于實(shí)現(xiàn)，算法中僅涉及各種基本的數(shù)學(xué)操作，其數(shù)據(jù)處理過程對CPU和內(nèi)存的要求也不高。而且，這種方法只需目標(biāo)函數(shù)的輸出值，而無需其梯度信息。已完成的群智能理論和應(yīng)用方法研究證明群智能方法是一種能夠有效解決大多數(shù)全局優(yōu)化問題的新方法。更為重要是，群智能潛在的并行性和分布式特點(diǎn)為處理大量的以數(shù)據(jù)庫形式存在的數(shù)據(jù)提供了技術(shù)保證。無論是從理論研究還

4、是應(yīng)用研究的角度分析，群智能理論及其應(yīng)用研究都是具有重要學(xué)術(shù)意義和現(xiàn)實(shí)價(jià)值的。 6蟻群優(yōu)化算法概念1 蟻群算法原理2 簡化的螞蟻尋食過程3 自然蟻群與人工蟻群算法4 蟻群算法與TSP問題5 初始的蟻群優(yōu)化算法基于圖的蟻群系統(tǒng)（GBAS）6 一般蟻群算法的框架71 蟻群算法原理 蟻群算法是對自然界螞蟻的尋徑方式進(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)象：某一路徑上走過的螞蟻越多，則后來者

5、選擇該路徑的概率就越大。 為了說明蟻群算法的原理，先簡要介紹一下螞蟻搜尋食物的具體過程。在蟻群尋找食物時(shí)，它們總能找到一條從食物到巢穴之間的最優(yōu)路徑。這是因?yàn)槲浵佋趯ふ衣窂綍r(shí)會(huì)在路徑上釋放出一種特殊的信息素。當(dāng)它們碰到一個(gè)還沒有走過的路口時(shí)就隨機(jī)地挑選一條路徑前行。與此同時(shí)釋放出與路徑長度有關(guān)的信息素。路徑越長，釋放的激索濃度越低.當(dāng)后來的螞蟻再次碰到這個(gè)路口的時(shí)候選擇激素濃度較高路徑概率就會(huì)相對較大。這樣形成一個(gè)正反饋。最優(yōu)路徑上的激索濃度越來越大而其它的路徑上激素濃度卻會(huì)隨著時(shí)間的流逝而消減。最終整個(gè)蟻群會(huì)找出最優(yōu)路徑。82 簡化的螞蟻尋食過程螞蟻從A點(diǎn)出發(fā)，速度相同，食物在D點(diǎn)，可能隨機(jī)

6、選擇路線ABD或ACD。假設(shè)初始時(shí)每條分配路線一只螞蟻，每個(gè)時(shí)間單位行走一步，本圖為經(jīng)過9個(gè)時(shí)間單位時(shí)的情形：走ABD的螞蟻到達(dá)終點(diǎn)，而走ACD的螞蟻剛好走到C點(diǎn)，為一半路程。92 簡化的螞蟻尋食過程本圖為從開始算起，經(jīng)過18個(gè)時(shí)間單位時(shí)的情形：走ABD的螞蟻到達(dá)終點(diǎn)后得到食物又返回了起點(diǎn)A，而走ACD的螞蟻剛好走到D點(diǎn)。102 簡化的螞蟻尋食過程 假設(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。

7、尋找食物的過程繼續(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)。113 自然蟻群與人工蟻群算法 基于以上蟻群尋找食物時(shí)的最優(yōu)路徑選擇問題，可以構(gòu)造人工蟻群，來解決最優(yōu)化問題，如TSP問題。

8、 人工蟻群中把具有簡單功能的工作單元看作螞蟻。二者的相似之處在于都是優(yōu)先選擇信息素濃度大的路徑。較短路徑的信息素濃度高，所以能夠最終被所有螞蟻選擇，也就是最終的優(yōu)化結(jié)果。 兩者的區(qū)別在于人工蟻群有一定的記憶能力，能夠記憶已經(jīng)訪問過的節(jié)點(diǎn)。同時(shí)，人工蟻群再選擇下一條路徑的時(shí)候是按一定算法規(guī)律有意識(shí)地尋找最短路徑，而不是盲目的。例如在TSP問題中，可以預(yù)先知道當(dāng)前城市到下一個(gè)目的地的距離。124 蟻群算法與TSP問題TSP問題表示為一個(gè)N個(gè)城市的有向圖G=（N，A），其中城市之間距離目標(biāo)函數(shù)為 ，其中 為城市1,2，n的一個(gè)排列， 。134 蟻群算法與TSP問題 TSP問題的人工蟻群算法中，假設(shè)m

9、只螞蟻在圖的相鄰節(jié)點(diǎn)間移動(dòng)，從而協(xié)作異步地得到問題的解。每只螞蟻的一步轉(zhuǎn)移概率由圖中的每條邊上的兩類參數(shù)決定：1 信息素值，也稱信息素痕跡。2 可見度，即先驗(yàn)值。 信息素的更新方式有2種，一是揮發(fā)，也就是所有路徑上的信息素以一定的比率進(jìn)行減少，模擬自然蟻群的信息素隨時(shí)間揮發(fā)的過程；二是增強(qiáng)，給評(píng)價(jià)值“好”(有螞蟻?zhàn)哌^)的邊增加信息素。144 蟻群算法與TSP問題 螞蟻向下一個(gè)目標(biāo)的運(yùn)動(dòng)是通過一個(gè)隨機(jī)原則來實(shí)現(xiàn)的，也就是運(yùn)用當(dāng)前所在節(jié)點(diǎn)存儲(chǔ)的信息，計(jì)算出下一步可達(dá)節(jié)點(diǎn)的概率，并按此概率實(shí)現(xiàn)一步移動(dòng)，逐此往復(fù)，越來越接近最優(yōu)解。 螞蟻在尋找過程中，或者找到一個(gè)解后，會(huì)評(píng)估該解或解的一部分的優(yōu)化程度

10、，并把評(píng)價(jià)信息保存在相關(guān)連接的信息素中。155 初始的蟻群優(yōu)化算法基于圖的蟻群系統(tǒng)（GBAS）初始的蟻群算法是基于圖的蟻群算法，graph-based ant system,簡稱為GBAS，是由Gutjahr W J在2000年的Future Generation Computing Systems提出的.算法步驟如下：STEP 0 對n個(gè)城市的TSP問題，城市間的距離矩陣為 ，給TSP圖中的每一條弧 賦信息素初值 ，假設(shè)m只螞蟻在工作，所有螞蟻都從同一城市 出發(fā)。當(dāng)前最好解是。165 初始的蟻群優(yōu)化算法基于圖的蟻群系統(tǒng)（GBAS）STEP 1 （外循環(huán)）如果滿足算法的停止規(guī)則，則停止計(jì)算并輸

11、出計(jì)算得到的最好解。否則使螞蟻s從起點(diǎn) 出發(fā)，用 表示螞蟻s行走的城市集合，初始 為空集， 。STEP 2 (內(nèi)循環(huán)) 按螞蟻 的順序分別計(jì)算。當(dāng)螞蟻在城市i，若 完成第s只螞蟻的計(jì)算。否則，若，則以概率，到達(dá)j， ；若則到達(dá)重復(fù)STEP 2。175 初始的蟻群優(yōu)化算法基于圖的蟻群系統(tǒng)（GBAS）STEP 3 對 ，若 ，按 中城市的順序計(jì)算路徑程度；若 ，路徑長度置為一個(gè)無窮大值（即不可達(dá)）。比較m只螞蟻中的路徑長度，記走最短路徑的螞蟻為t。若 ，則 。用如下公式對W路徑上的信息素痕跡加強(qiáng)，對其他路徑上的信息素進(jìn)行揮發(fā)。 得到新的 ，重復(fù)步驟STEP 1。185 初始的蟻群優(yōu)化算法基于圖的蟻

12、群系統(tǒng)（GBAS）在STEP 3 中，揮發(fā)因子 對于一個(gè)固定的 ，滿足并且 經(jīng)過k次揮發(fā)，非最優(yōu)路徑的信息素逐漸減少至消失。195初始的蟻群優(yōu)化算法基于圖的蟻群系統(tǒng)（GBAS） 以上算法中，在螞蟻的搜尋過程中，以信息素的概率分布來決定從城市i到城市j的轉(zhuǎn)移。 算法中包括信息素更新的過程 1 信息素?fù)]發(fā)（evaporation） 信息素痕跡的揮發(fā)過程是每個(gè)連接上的信息素痕跡的濃度自動(dòng)逐漸減弱的過程，由 表示，這個(gè)揮發(fā)過程主要用于避免算法過快地向局部最優(yōu)區(qū)域集中，有助于搜索區(qū)域的擴(kuò)展。 2 信息素增強(qiáng)（reinforcement）增強(qiáng)過程是蟻群優(yōu)化算法中可選的部分，稱為離線更新方式（還有在線更新方

13、式）。這種方式可以實(shí)現(xiàn)由單個(gè)螞蟻無法實(shí)現(xiàn)的集中行動(dòng)。也就是說，增強(qiáng)過程體現(xiàn)在觀察蟻群（m只螞蟻）中每只螞蟻所找到的路徑，并選擇其中最優(yōu)路徑上的弧進(jìn)行信息素的增強(qiáng)，揮發(fā)過程是所有弧都進(jìn)行的，不與螞蟻數(shù)量相關(guān)。這種增強(qiáng)過程中進(jìn)行的信息素更新稱為離線的信息素更新。 在STEP 3中，蟻群永遠(yuǎn)記憶到目前為止的最優(yōu)解。20圖的蟻群系統(tǒng)（GBAS）四個(gè)城市的非對稱TSP問題，距離矩陣和城市圖示如下：215 初始的蟻群優(yōu)化算法基于圖的蟻群系統(tǒng)（GBAS）假設(shè)共4只螞蟻，所有螞蟻都從城市A出發(fā)，揮發(fā)因子 。此時(shí)，觀察GBAS的計(jì)算過程。 矩陣共有12條弧，初始信息素記憶矩陣為：225 初始的蟻群優(yōu)化算法基于圖

14、的蟻群系統(tǒng)（GBAS）執(zhí)行GBAS算法的步驟2，假設(shè)螞蟻的行走路線分別為：當(dāng)前最優(yōu)解為，這個(gè)解是截止到當(dāng)前的最優(yōu)解，碰巧是實(shí)際最優(yōu)解235 初始的蟻群優(yōu)化算法基于圖的蟻群系統(tǒng)（GBAS）按算法步驟3的信息素更新規(guī)則，得到更新矩陣這是第一次外循環(huán)結(jié)束的狀態(tài)。245 初始的蟻群優(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)。255 初始的蟻群優(yōu)化算法基于圖的蟻群系統(tǒng)（GBAS）重復(fù)外循環(huán)，由于W2全局最優(yōu)

15、解，GBAS只記錄第一個(gè)最優(yōu)解，因此一但得到了全局最優(yōu)解，信息素的更新將不再依賴于以群的行走路線，而只是不斷增強(qiáng)最優(yōu)路線的信息素，同時(shí)進(jìn)行揮發(fā)。第三次外循環(huán)后得到的信息素矩陣為：265 初始的蟻群優(yōu)化算法基于圖的蟻群系統(tǒng)（GBAS） 螞蟻以一定的概率從城市i到城市j進(jìn)行轉(zhuǎn)移，信息素的更新在STEP 3 完成，并隨K而變化。假設(shè)第K次外循環(huán)后得到信息素矩陣 ，得到當(dāng)前最優(yōu)解 。第K次循環(huán)前的信息素和最優(yōu)解為 ，經(jīng)過第K次外循環(huán)后，得到 。由于螞蟻的一步轉(zhuǎn)移概率是隨機(jī)的，從 到 也是隨機(jī)的，是一個(gè)馬爾可夫過程。276 一般蟻群算法的框架一般蟻群算法的框架和GBAS基本相同，有三個(gè)組成部分： 蟻群的

16、活動(dòng)； 信息素的揮發(fā)； 信息素的增強(qiáng)；主要體現(xiàn)在前面的算法中步驟2和步驟3中的轉(zhuǎn)移概率公式和信息素更新公式。28應(yīng)用蟻群算法用于計(jì)算機(jī)網(wǎng)絡(luò)路由參考文獻(xiàn)：計(jì)算機(jī)網(wǎng)絡(luò)中的組播路由算法 謝銀祥 29應(yīng)用 蟻群算法在電信路由優(yōu)化中已取得了一定的應(yīng)用成果。HP公司和英國電信公司在90年代中后期都開展了這方面的研究，設(shè)計(jì)了蟻群路由算法（Ant Colony Routing, ACR）。3031應(yīng)用蟻群算法用于聚類（蟻群蟻卵分類） 思想：把待聚類的數(shù)據(jù)隨機(jī)散布在一個(gè)平面上，放置若干只虛擬螞蟻使其在平面上隨機(jī)運(yùn)動(dòng)。當(dāng)一只螞蟻遇到一個(gè)數(shù)據(jù)時(shí)即拾起并繼續(xù)行走，在行走過程中，如果遇到附近的數(shù)據(jù)與背負(fù)的數(shù)據(jù)相似性高于設(shè)置的標(biāo)準(zhǔn)時(shí)則將數(shù)據(jù)放置在該位置，繼續(xù)移動(dòng)。重復(fù)以上過程即可實(shí)現(xiàn)數(shù)據(jù)聚類。3233T1T2T334蟻群優(yōu)化算法參考書1智能蟻群算法及應(yīng)用 吳啟迪 上?？萍汲霭嫔?從基本結(jié)構(gòu)、算法特點(diǎn)、改進(jìn)方法、突破途徑、實(shí)現(xiàn)模式及應(yīng)用模式等方面進(jìn)行了論述。主要