現(xiàn)代優(yōu)化算法-蟻群算法

《現(xiàn)代優(yōu)化算法-蟻群算法》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、現(xiàn)代智能優(yōu)化算法顏學(xué)峰實(shí)驗(yàn)十六樓415房間Email：xfyan@ecust.edu.cnTel:64253254(o)、13671876906華東理工大學(xué)信息學(xué)院自動(dòng)化研究所二○○八年十月現(xiàn)代智能優(yōu)化算法模擬退火遺傳算法蟻群優(yōu)化算法蟻群優(yōu)化算法—螞蟻生物行為螞蟻搬家，天要下雨。螞蟻群體行為。相互協(xié)作的一群螞蟻可以戰(zhàn)勝比自己強(qiáng)壯的昆蟲，并把它搬回巢；而單個(gè)螞蟻則不能。相互協(xié)作的一群螞蟻可以很容易找到從蟻巢到食物源的最短路徑，而單個(gè)螞蟻則不能。此外，螞蟻還能夠適應(yīng)環(huán)境的變化，例如在蟻群的運(yùn)動(dòng)路線上突然出現(xiàn)障礙物時(shí)，它們能夠很快地重新找到最優(yōu)路徑。——不但引起

2、昆蟲學(xué)家，而且也引起數(shù)學(xué)及計(jì)算機(jī)方面的專家和工程師的興趣。蟻群優(yōu)化算法—螞蟻生物行為昆蟲學(xué)家通過(guò)大量的研究發(fā)現(xiàn)：螞蟻個(gè)體之間是通過(guò)信息交流達(dá)到找到從蟻巢到食物源的最短路徑的目的。螞蟻個(gè)體通過(guò)在其所經(jīng)過(guò)的路上留下一種稱之為“信息素”（pheromone）或“跡”的物質(zhì)來(lái)實(shí)現(xiàn)與同伴之間的信息傳遞。隨后的螞蟻遇到信息素時(shí)，不僅能檢測(cè)出該物質(zhì)的存在以及量的多少，而且可根據(jù)信息素的濃度來(lái)指導(dǎo)自己對(duì)前進(jìn)方向的選擇。蟻群優(yōu)化算法—螞蟻生物行為信息素隨著時(shí)間的推移會(huì)逐漸揮發(fā)掉，于是路徑的長(zhǎng)短及其螞蟻的多少就對(duì)殘余信息素的強(qiáng)度產(chǎn)生影響，反過(guò)來(lái)信息素的強(qiáng)弱又指導(dǎo)著其它螞蟻的行

3、動(dòng)方向。因此，某一路徑上走過(guò)的螞蟻越多，則后來(lái)者選擇該路徑的概率就越大。這就構(gòu)成了螞蟻群體行為表現(xiàn)出的一種信息正反饋現(xiàn)象，并實(shí)現(xiàn)找到蟻巢到食物源的最短路徑。蟻群優(yōu)化算法—螞蟻生物行為蟻群實(shí)現(xiàn)找到蟻巢到食物源的最短路徑示意圖障礙物ABCDEHd=1d=1d=0.5d=0.5圖1圖1中設(shè)A是蟻巢，E是食物源，H、C為障礙物，由于障礙物的存在，由A外出覓食或由E返回巢穴的螞蟻只能經(jīng)由H或C到達(dá)目的地。BH和HD距離為1單位，BC和DC距離為0.5單位。假設(shè)螞蟻以“1單位長(zhǎng)度/單位時(shí)間”的速度往返于A和E，每經(jīng)過(guò)一個(gè)單位時(shí)間各有30只螞蟻離開A和E到達(dá)B和D。蟻群

4、優(yōu)化算法—螞蟻生物行為蟻群實(shí)現(xiàn)找到蟻巢到食物源的最短路徑示意圖障礙物ABCDEH15151515初始時(shí)，各有30只螞蟻在B和D點(diǎn)遇到障礙物，開始選擇路徑。由于此時(shí)路徑上無(wú)跡，螞蟻便以相同的概率隨機(jī)地走兩條路中的任意一條，因而15只選往H，15只選往C（圖2）。經(jīng)過(guò)一個(gè)單位時(shí)間以后，路徑BHD被15只螞蟻爬過(guò)，而路徑BCD上則被30只螞蟻爬過(guò)，BCD上的信息量是BHD上信息量的兩倍。圖2蟻群優(yōu)化算法—螞蟻生物行為蟻群實(shí)現(xiàn)找到蟻巢到食物源的最短路徑示意圖障礙物ABCDEH10102020圖3此時(shí)，又有30只螞蟻離開B和D，于是20只選擇往C方向，而另外10只則

5、選往H（圖3）。這樣，更多的信息量被留在更短的路徑BCD上。隨著時(shí)間的推移和上述過(guò)程的重復(fù)，短路徑上的信息量便以更快的速度增長(zhǎng)，于是會(huì)有越來(lái)越多的螞蟻選擇這條短路徑，以致最終完全選擇這條短路徑BCD。相對(duì)弱小，功能并不強(qiáng)大的個(gè)體是完成復(fù)雜的工作。蟻群優(yōu)化算法—算法提出一個(gè)著名的組合優(yōu)化問(wèn)題：旅行商問(wèn)題（TSP,travelingsalesmanproblem），一個(gè)商人欲到n個(gè)城市推銷商品，每個(gè)兩個(gè)城市i和j之間的距離為dij，如何選擇一條道路使得商人每個(gè)城市走一遍后回到起點(diǎn)且所走路徑最短。蟻群優(yōu)化算法—算法提出一般旅行商問(wèn)題TSP，數(shù)學(xué)模型描述：選擇ij

6、路線為1，否則為0避免產(chǎn)生回路走入城市j只有一次從城市i出發(fā)只有一次蟻群優(yōu)化算法—算法提出例子，一般旅行商TSP問(wèn)題的解。ABDEC如圖所示，從A城市出發(fā)回到A城市一個(gè)TSP問(wèn)題的解是ABCEDA，即圖中紅色線條路徑。這個(gè)解滿足以上四個(gè)約束條件。蟻群優(yōu)化算法—算法提出NP問(wèn)題：至今為止，還沒有一個(gè)有能求得最優(yōu)解的多項(xiàng)式時(shí)間算法的組合優(yōu)化問(wèn)題稱為NP問(wèn)題。TSP問(wèn)題就是一個(gè)著名的NP問(wèn)題。在如何解決這個(gè)問(wèn)題方面已經(jīng)有了大量的研究。這其中包括遺傳算法，退火算法，動(dòng)態(tài)規(guī)劃等等。蟻群優(yōu)化算法—算法提出TSP問(wèn)題與蟻群尋徑行為比較：TSP問(wèn)題蟻群尋徑行為解路徑尋優(yōu)過(guò)

7、程選擇路徑最短路徑（最優(yōu)解）最短路徑蟻群優(yōu)化算法—算法提出在20世紀(jì)90年代，意大利學(xué)者Dorigo等人從生物進(jìn)化的機(jī)理中受到啟發(fā)，通過(guò)模擬自然界螞蟻尋徑的行為，提出了一種全新的模擬進(jìn)化算法，蟻群優(yōu)化算法。并用該方法求解TSP問(wèn)題（及其他組合優(yōu)化問(wèn)題，如分配問(wèn)題、Job-shop調(diào)度問(wèn)題等），取得了一系列較好的實(shí)驗(yàn)結(jié)果。蟻群優(yōu)化算法—算法提出蟻群優(yōu)化算法的核心思想有三條：第一，選擇機(jī)制：跡越多的路徑，被選中的概率越大；第二，跡更新機(jī)制：路徑越短，跡增加越快；第三，協(xié)作機(jī)制：個(gè)體之間通過(guò)跡進(jìn)行信息交流。蟻群優(yōu)化算法—算法流程蟻群優(yōu)化算法實(shí)現(xiàn)（以TSP問(wèn)題為例

8、）：第一步，初始化，將m只螞蟻放入到n個(gè)隨機(jī)選擇的城市中。第二步，