蟻群算法概述

《蟻群算法概述》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、蟻群算法（AntColonyOptimization，ACO）蟻群算法的由來(lái)：螞蟻是地球上最常見(jiàn)、數(shù)量最多的昆蟲(chóng)種類之一，常常成群結(jié)隊(duì)地出現(xiàn)在人類的日常生活環(huán)境中。這些昆蟲(chóng)的群體生物智能特征，引起了一些學(xué)者的注意。意大利學(xué)者M(jìn).Dorigo，V.Maniezzo等人在觀察螞蟻的覓食習(xí)性時(shí)發(fā)現(xiàn)，螞蟻總能找到巢穴與食物源之間的最短路徑。經(jīng)研究發(fā)現(xiàn)，螞蟻的這種群體協(xié)作功能是通過(guò)一種遺留在其來(lái)往路徑上的叫做信息素(Pheromone)的揮發(fā)性化學(xué)物質(zhì)來(lái)進(jìn)行通信和協(xié)調(diào)的?；瘜W(xué)通信是螞蟻采取的基本信息交流方式之一，在螞蟻的生活習(xí)性中起著重要的作用。通過(guò)對(duì)螞蟻

2、覓食行為的研究，他們發(fā)現(xiàn)，整個(gè)蟻群就是通過(guò)這種信息素進(jìn)行相互協(xié)作，形成正反饋，從而使多個(gè)路徑上的螞蟻都逐漸聚集到最短的那條路徑上。這樣，M.Dorigo等人于1991年首先提出了蟻群算法。其主要特點(diǎn)就是：通過(guò)正反饋、分布式協(xié)作來(lái)尋找最優(yōu)路徑。這是一種基于種群尋優(yōu)的啟發(fā)式搜索算法。它充分利用了生物蟻群能通過(guò)個(gè)體間簡(jiǎn)單的信息傳遞，搜索從蟻巢至食物間最短路徑的集體尋優(yōu)特征，以及該過(guò)程與旅行商問(wèn)題求解之間的相似性。得到了具有NP難度的旅行商問(wèn)題的最優(yōu)解答。同時(shí)，該算法還被用于求解Job-Shop調(diào)度問(wèn)題、二次指派問(wèn)題以及多維背包問(wèn)題等，顯示了其適用于組合

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

4、群會(huì)找出最優(yōu)路徑。螞蟻從A點(diǎn)出發(fā)，速度相同，食物在D點(diǎn)，可能隨機(jī)選擇路線ABD或ACD。假設(shè)初始時(shí)每條分配路線一只螞蟻，每個(gè)時(shí)間單位行走一步，本圖為經(jīng)過(guò)9個(gè)時(shí)間單位時(shí)的情形：走ABD的螞蟻到達(dá)終點(diǎn)，而走ACD的螞蟻剛好走到C點(diǎn)，為一半路程。三：簡(jiǎn)化的螞蟻尋食過(guò)程簡(jiǎn)化的螞蟻尋食過(guò)程本圖為從開(kāi)始算起，經(jīng)過(guò)18個(gè)時(shí)間單位時(shí)的情形：走ABD的螞蟻到達(dá)終點(diǎn)后得到食物又返回了起點(diǎn)A，而走ACD的螞蟻剛好走到D點(diǎn)。簡(jiǎn)化的螞蟻尋食過(guò)程假設(shè)螞蟻每經(jīng)過(guò)一處所留下的信息素為一個(gè)單位，則經(jīng)過(guò)36個(gè)時(shí)間單位后，所有開(kāi)始一起出發(fā)的螞蟻都經(jīng)過(guò)不同路徑從D點(diǎn)取得了食物，此時(shí)AB

5、D的路線往返了2趟，每一處的信息素為4個(gè)單位，而ACD的路線往返了一趟，每一處的信息素為2個(gè)單位，其比值為2：1。尋找食物的過(guò)程繼續(xù)進(jìn)行，則按信息素的指導(dǎo)，蟻群在ABD路線上增派一只螞蟻（共2只），而ACD路線上仍然為一只螞蟻。再經(jīng)過(guò)36個(gè)時(shí)間單位后，兩條線路上的信息素單位積累為12和4，比值為3：1。若按以上規(guī)則繼續(xù)，蟻群在ABD路線上再增派一只螞蟻（共3只），而ACD路線上仍然為一只螞蟻。再經(jīng)過(guò)36個(gè)時(shí)間單位后，兩條線路上的信息素單位積累為24和6，比值為4：1。若繼續(xù)進(jìn)行，則按信息素的指導(dǎo)，最終所有的螞蟻會(huì)放棄ACD路線，而都選擇ABD路線

6、。這也就是正反饋效應(yīng)。四：自然蟻群與人工蟻群算法基于以上蟻群尋找食物時(shí)的最優(yōu)路徑選擇問(wèn)題，可以構(gòu)造人工蟻群，來(lái)解決最優(yōu)化問(wèn)題，如TSP問(wèn)題。人工蟻群中把具有簡(jiǎn)單功能的工作單元看作螞蟻。二者的相似之處在于都是優(yōu)先選擇信息素濃度大的路徑。較短路徑的信息素濃度高，所以能夠最終被所有螞蟻選擇，也就是最終的優(yōu)化結(jié)果。兩者的區(qū)別在于人工蟻群有一定的記憶能力，能夠記憶已經(jīng)訪問(wèn)過(guò)的節(jié)點(diǎn)。同時(shí)，人工蟻群再選擇下一條路徑的時(shí)候是按一定算法規(guī)律有意識(shí)地尋找最短路徑，而不是盲目的。例如在TSP問(wèn)題中，可以預(yù)先知道當(dāng)前城市到下一個(gè)目的地的距離。五：蟻群算法與TSP問(wèn)題TS

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

8、過(guò)程中，或者找到一個(gè)解后，會(huì)評(píng)估該解或解的一部分的優(yōu)化程度，并把評(píng)價(jià)信息保存在相關(guān)連接的信息素中。蟻群算法有兩個(gè)階段：適應(yīng)階段和協(xié)作階段