智能算法之蟻群算法

1、蟻群算法陳華2010-9Macro Dorigo 1992年，意大利學(xué)者MDorigo在他的博士論文中引入蟻群算法，其靈感來源于螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為。通過對這種行為的模擬，提出來一種新型的模擬進化算法 蟻群算法。目前，蟻群算法已經(jīng)是群智能理論研究領(lǐng)域的一種主要算法。算法背景3AC4AC5AC6蟻群算法原理 蟻群算法是對自然界螞蟻的尋徑方式進行模似而得出的一種仿生算法。螞蟻在運動過程中，能夠在它所經(jīng)過的路徑上留下一種稱之為外激素(pheromone)的物質(zhì)進行信息傳遞，而且螞蟻在運動過程中能夠感知這種物質(zhì)，并以此指導(dǎo)自己的運動方向，因此由大量螞蟻組成的蟻群集體行為便表現(xiàn)出一種信息正

2、反饋現(xiàn)象：某一路徑上走過的螞蟻越多，則后來者選擇該路徑的概率就越大。 7蟻群算法原理 為了說明蟻群算法的原理，先簡要介紹一下螞蟻搜尋食物的具體過程。在蟻群尋找食物時，它們總能找到一條從食物到巢穴之間的最優(yōu)路徑。這是因為螞蟻在尋找路徑時會在路徑上釋放出一種特殊的信息素。當(dāng)它們碰到一個還沒有走過的路口時，就隨機地挑選一條路徑前行，與此同時釋放出與路徑長度有關(guān)的信息素。路徑越長，釋放的激索濃度越低，當(dāng)后來的螞蟻再次碰到這個路口的時候，選擇激素濃度較高路徑概率就會相對較大，這樣形成一個正反饋。最優(yōu)路徑上的激索濃度越來越大，而其它的路徑上激素濃度卻會隨著時間的流逝而消減，最終整個蟻群會找出最優(yōu)路徑。8簡

3、化的螞蟻尋食過程 螞蟻從A點出發(fā)，速度相同，食物在D點，可能隨機選擇路線ABD或ACD。假設(shè)初始時每條分配路線一只螞蟻，每個時間單位行走一步，本圖為經(jīng)過9個時間單位時的情形：走ABD的螞蟻到達終點，而走ACD的螞蟻剛好走到C點，為一半路程。9簡化的螞蟻尋食過程 本圖為從開始算起，經(jīng)過18個時間單位時的情形：走ABD的螞蟻到達終點后得到食物又返回了起點A，而走ACD的螞蟻剛好走到D點。10簡化的螞蟻尋食過程 假設(shè)螞蟻每經(jīng)過一處所留下的信息素為一個單位，則經(jīng)過36個時間單位后，所有開始一起出發(fā)的螞蟻都經(jīng)過不同路徑從D點取得了食物，此時ABD的路線往返了2趟，每一處的信息素為4個單位，而 ACD的路

4、線往返了一趟，每一處的信息素為2個單位，其比值為2：1。 尋找食物的過程繼續(xù)進行，則按信息素的指導(dǎo)，蟻群在ABD路線上增派一只螞蟻（共2只），而ACD路線上仍然為一只螞蟻。再經(jīng)過36個時間單位后，兩條線路上的信息素單位積累為12和4，比值為3：1。 若按以上規(guī)則繼續(xù)，蟻群在ABD路線上再增派一只螞蟻（共3只），而ACD路線上仍然為一只螞蟻。再經(jīng)過36個時間單位后，兩條線路上的信息素單位積累為24和6，比值為4：1。 若繼續(xù)進行，則按信息素的指導(dǎo)，最終所有的螞蟻會放棄ACD路線，而都選擇ABD路線。這也就是前面所提到的正反饋效應(yīng)。11自然蟻群與人工蟻群算法 基于以上蟻群尋找食物時的最優(yōu)路徑選擇問

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

6、(iA n1,2,.,NNjinnijd)(nliilldwf11)(),(21niiiw11iin13蟻群算法與TSP問題 TSP問題的人工蟻群算法中，假設(shè)m只螞蟻在圖的相鄰節(jié)點間移動，從而協(xié)作異步地得到問題的解。每只螞蟻的一步轉(zhuǎn)移概率由圖中的每條邊上的兩類參數(shù)決定：1.信息素值，也稱信息素痕跡。2.可見度，即先驗值。 信息素的更新方式有2種，一是揮發(fā)，也就是所有路徑上的信息素以一定的比率進行減少，模擬自然蟻群的信息素隨時間揮發(fā)的過程；二是增強，給評價值“好”(有螞蟻走過)的邊增加信息素。14蟻群算法與TSP問題 螞蟻向下一個目標(biāo)的運動是通過一個隨機原則來實現(xiàn)的，也就是運用當(dāng)前所在節(jié)點存儲的

7、信息，計算出下一步可達節(jié)點的概率，并按此概率實現(xiàn)一步移動，逐此往復(fù)，越來越接近最優(yōu)解。 螞蟻在尋找過程中，或者找到一個解后，會評估該解或解的一部分的優(yōu)化程度，并把評價信息保存在相關(guān)連接的信息素中。15otherwise 0allowed if )(allowed)()(jtpjijijijijttkij),()()(ijntttntijij軌跡更新:Visibility: ij = 1/dij蟻群算法的計算流程表示軌跡的相對重要性表示能見度的相對重要性軌跡的持久性ij表示第K只螞蟻在本次循環(huán)中留在路徑ij上的信息量計算結(jié)果10城市TSP問題20城市TSP問題計算結(jié)果30城市TSP問題48城市T

8、SP問題連續(xù)蟻群算法 從上面可以看出，蟻群算法比較顯著的特點是：整個算法過程更適用于離散對象問題。在算法求解組合優(yōu)化問題過程中，路徑是離散和有限的路徑，螞蟻的每一步選擇都是在離散值中進行的。這一特點使得將蟻群算法直接應(yīng)用于一般常規(guī)的連續(xù)對象優(yōu)化問題存在一定的困難。 應(yīng)用蟻群算法求解連續(xù)對象優(yōu)化問題，目前的處理方法大致為: 1.將解空間的每一個分量分成許多小區(qū)間，這樣整個解空間被分成許多小多面體，將每個多面體看為一個節(jié)點，然后用人工螞蟻在這些節(jié)點之間行走最后找到最優(yōu)解。 2.在解空間中隨機生成一些螞蟻，每個螞蟻表示一個解，并構(gòu)成一個區(qū)域，根據(jù)螞蟻的評價值，可將這些區(qū)域分成優(yōu)勢區(qū)和劣勢區(qū)，劣勢區(qū)的螞蟻會按一定概率原則向優(yōu)勢區(qū)移動，直到所有螞蟻都移動到優(yōu)勢區(qū)。這類處理方法我們認(rèn)為己經(jīng)不是原本意義上的蟻群算法，其實質(zhì)是模擬了生態(tài)環(huán)境的一種宏觀演化過程。20 蟻群優(yōu)化算法參考書1蟻群算法及其應(yīng)用.李士勇.哈工大出版社 國內(nèi)首部蟻群算法的專著，系統(tǒng)地闡述蟻群算法的基本原理、基本蟻群算法及改進算法，蟻群算法與遺傳、免疫算法的融合，自適應(yīng)蟻群算法，并行蟻群算法，蟻群算法的收斂性與理論模型及其在優(yōu)化問題中的應(yīng)用。本書可供人工智能、計算機科學(xué)、信息科學(xué)、控制工程、管理工程、交通工程、網(wǎng)絡(luò)工程、智能優(yōu)化算法及智能自動化等領(lǐng)域的廣大師生和科技