蟻群算法與函數(shù)優(yōu)化課件

1、蟻群算法與函數(shù)優(yōu)化主講人：王同偉1蟻群算法原理螞蟻在運(yùn)動過程中，能夠在它所經(jīng)過的路徑上留下一種稱之為外激素或者信息素(pheromone)的物質(zhì)進(jìn)行信息傳遞，而且螞蟻在運(yùn)動過程中能夠感知這種物質(zhì)，并以此指導(dǎo)自己的運(yùn)動方向，因此由大量螞蟻組成的蟻群集體行為便表現(xiàn)出一種信息正反饋現(xiàn)象：某一路徑上走過的螞蟻越多，則后來者選擇該路徑的概率就越大。22簡化的螞蟻尋食過程3 螞蟻從A點(diǎn)出發(fā)，速度相同，食物在D點(diǎn)，可能隨機(jī)選擇路線ABD或ACD。假設(shè)初始時每條分配路線一只螞蟻，每個時間單位行走一步，本圖為經(jīng)過9個時間單位時的情形：走ABD的螞蟻到達(dá)終點(diǎn)，而走ACD的螞蟻剛好走到C點(diǎn)，為一半路程。4 本圖為從

2、開始算起，經(jīng)過18個時間單位時的情形：走ABD的螞蟻到達(dá)終點(diǎn)后得到食物又返回了起點(diǎn)A，而走ACD的螞蟻剛好走到D點(diǎn)。 假設(shè)螞蟻每經(jīng)過一處所留下的信息素為一個單位，則經(jīng)過36個時間單位后所有開始一起出發(fā)的螞蟻都經(jīng)過不同路徑從D點(diǎn)取得了食物，此時ABD的路線往返了2趟，每一處的信息素為4個單位，而 ACD的路線往返了一趟，每一處的信息素為2個單位，其比值為2：1。若按以上規(guī)則繼續(xù)，蟻群在ABD路線上再增派一只螞蟻（共3只），而ACD路線上仍然為一只螞蟻。再經(jīng)過36個時間單位后，兩條線路上的信息素單位積累為24和6，比值為4：1。若繼續(xù)進(jìn)行，則按信息素的指導(dǎo)，最終所有的螞蟻會放棄ACD路線，而都選擇

3、ABD路線。這也就是前面所提到的正反饋效應(yīng)。53 螞蟻的覓食策略61、等長二元橋?qū)嶒?yàn) 蟻穴通過雙支橋與食物相連，而橋的兩個分支長度相等，而且兩個分支上最初沒有信息素。然后，將螞蟻置于可以自由地在蟻穴和食物源之間移動的狀態(tài)，觀察選擇兩個分支的螞蟻的比例。結(jié)果如圖(b)顯示，經(jīng)過最初的一個短暫的震蕩階段，螞蟻向著一條相同的路徑前進(jìn)。7圖 1 等長雙橋?qū)嶒?yàn) S. Goss 8 等人給出了上述實(shí)驗(yàn)的概率模型。首先，假定橋上殘留的外激素量與過去一段時間經(jīng)過該橋的螞蟻數(shù)成正比（這意味著不考慮外激素蒸發(fā)的情況）；其次，某一時刻螞蟻按橋上外激素量的多少來選擇某座橋，即螞蟻選擇某座橋的概率與經(jīng)過該橋的螞蟻數(shù)成正

4、比。當(dāng)所有 m 只螞蟻都經(jīng)過兩座橋以后，設(shè) Am、Bm分別為經(jīng)過 A 橋和 B 橋的螞蟻數(shù)（Am + Bm = m），則第 m+1 只螞蟻選擇 A 橋的概率為：9 公式表明：往A走的螞蟻越多，選擇分支A的概率就越高“n”決定選擇公式的非線性程度。（n越大，信息素多一點(diǎn)的分支選擇概率越高）“k”表示對未標(biāo)記的分支的吸引程度。（k越大，越多的信息素使選擇非隨機(jī)化）()1()()niABnniikAPPkAkB 2、不等長雙橋?qū)嶒?yàn)：圖2 (a)為螞蟻經(jīng)過不等長雙橋開始覓食；圖2 (b)顯示絕大多數(shù)螞蟻選擇較短的橋；圖2 (c)顯示最終有80%一100%的螞蟻選擇較短的橋。1011圖 2 不等長雙橋?qū)?/p>

5、驗(yàn)在非對稱雙橋?qū)嶒?yàn)中，由于初始波動的擴(kuò)大，螞蟻常常會選擇最短的路徑;先回蟻巢的螞蟻在最短分支上走了兩次(從蟻穴到食物源，再回到蟻穴)。所以這些螞蟻回來后不久，在短分支上有更多的信息素，從而誘使巢中同伴選擇短分支。實(shí)驗(yàn)表明，通過初始波動的擴(kuò)大，最終選擇短分支的幾率隨著兩個分支的長度比的增加而增長。由此可見，在非對稱雙橋?qū)嶒?yàn)中，初始波動對勝出分支橋(即較多螞蟻選擇的橋)的影響減小，而占主導(dǎo)作用的是隨機(jī)信息素的引導(dǎo)行為。12 基于以上蟻群尋找食物時的最優(yōu)路徑選擇問題，可以構(gòu)造人工蟻群，來解決最優(yōu)化問題人工蟻群中把具有簡單功能的工作單元看作螞蟻。二者的相似之處在于都是優(yōu)先選擇信息素濃度大的路徑。較短路

6、徑的信息素濃度高，所以能夠最終被所有螞蟻選擇，也就是最終的優(yōu)化結(jié)果。 兩者的區(qū)別在于人工蟻群有一定的記憶能力，能夠記憶已經(jīng)訪問過的節(jié)點(diǎn)。同時，人工蟻群再選擇下一條路徑的時候是按一定算法規(guī)律有意識地尋找最短路徑，而不是盲目的。例如在TSP問題中，可以預(yù)先知道當(dāng)前城市到下一個目的地的距離。134蟻群現(xiàn)象螞蟻正常行進(jìn)，沒有遇到任何障礙，一路暢通。螞蟻正常行進(jìn)，突然環(huán)境變換，增加了障礙物蟻群以同等概率選擇各條路徑，緊接著，隨著時間的增加較短路徑信息濃度高，選擇該路徑的螞蟻逐漸增多。螞蟻?zhàn)罱K繞過障礙物，找到最優(yōu)路徑。5螞蟻簡單規(guī)則兩方面1多樣性：螞蟻在覓食的時候路線不一，隨機(jī)性的向著某個方向方向走，打破常規(guī)，進(jìn)行創(chuàng)新。2正反饋：優(yōu)化的路線不斷被保存并加大自身概率，保證了相對優(yōu)良的信息能夠被保存下來。 多樣性保證了系統(tǒng)的創(chuàng)新能力，正反饋保證了優(yōu)良特性能夠得到強(qiáng)化，兩者要恰到好處的結(jié)合。6.蟻群算法求最優(yōu) 目標(biāo)函數(shù)： =cos(2*pi.*x).*cos(2.*pi.*y).*exp(-(x.2+y.2)/10) 其中x,y-1,1