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

蟻群算法與函數(shù)優(yōu)化主講人：王同偉蟻群算法與函數(shù)優(yōu)化主講人：王同偉11蟻群算法原理螞蟻在運(yùn)動(dòng)過(guò)程中，能夠在它所經(jīng)過(guò)的路徑上留下一種稱之為外激素或者信息素(pheromone)的物質(zhì)進(jìn)行信息傳遞，而且螞蟻在運(yùn)動(dòng)過(guò)程中能夠感知這種物質(zhì)，并以此指導(dǎo)自己的運(yùn)動(dòng)方向，因此由大量螞蟻組成的蟻群集體行為便表現(xiàn)出一種信息正反饋現(xiàn)象：某一路徑上走過(guò)的螞蟻越多，則后來(lái)者選擇該路徑的概率就越大。21蟻群算法原理螞蟻在運(yùn)動(dòng)過(guò)程中，能夠在它所經(jīng)過(guò)的路徑上留下一22簡(jiǎn)化的螞蟻尋食過(guò)程3螞蟻從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)，為一半路程。2簡(jiǎn)化的螞蟻尋食過(guò)程334本圖為從開(kāi)始算起，經(jīng)過(guò)18個(gè)時(shí)間單位時(shí)的情形：走ABD的螞蟻到達(dá)終點(diǎn)后得到食物又返回了起點(diǎn)A，而走ACD的螞蟻剛好走到D點(diǎn)。44假設(shè)螞蟻每經(jīng)過(guò)一處所留下的信息素為一個(gè)單位，則經(jīng)過(guò)36個(gè)時(shí)間單位后所有開(kāi)始一起出發(fā)的螞蟻都經(jīng)過(guò)不同路徑從D點(diǎn)取得了食物，此時(shí)ABD的路線往返了2趟，每一處的信息素為4個(gè)單位，而ACD的路線往返了一趟，每一處的信息素為2個(gè)單位，其比值為2：1。若按以上規(guī)則繼續(xù)，蟻群在ABD路線上再增派一只螞蟻（共3只），而ACD路線上仍然為一只螞蟻。再經(jīng)過(guò)36個(gè)時(shí)間單位后，兩條線路上的信息素單位積累為24和6，比值為4：1。若繼續(xù)進(jìn)行，則按信息素的指導(dǎo)，最終所有的螞蟻會(huì)放棄ACD路線，而都選擇ABD路線。這也就是前面所提到的正反饋效應(yīng)。5假設(shè)螞蟻每經(jīng)過(guò)一處所留下的信息素為一個(gè)單位，則經(jīng)過(guò)36個(gè)時(shí)53螞蟻的覓食策略61、等長(zhǎng)二元橋?qū)嶒?yàn)

蟻穴通過(guò)雙支橋與食物相連，而橋的兩個(gè)分支長(zhǎng)度相等，而且兩個(gè)分支上最初沒(méi)有信息素。然后，將螞蟻置于可以自由地在蟻穴和食物源之間移動(dòng)的狀態(tài)，觀察選擇兩個(gè)分支的螞蟻的比例。結(jié)果如圖(b)顯示，經(jīng)過(guò)最初的一個(gè)短暫的震蕩階段，螞蟻向著一條相同的路徑前進(jìn)。3螞蟻的覓食策略61、等長(zhǎng)二元橋?qū)嶒?yàn)67圖1等長(zhǎng)雙橋?qū)嶒?yàn)7圖1等長(zhǎng)雙橋?qū)嶒?yàn)7

S.Goss[8]等人給出了上述實(shí)驗(yàn)的概率模型。首先，假定橋上殘留的外激素量與過(guò)去一段時(shí)間經(jīng)過(guò)該橋的螞蟻數(shù)成正比（這意味著不考慮外激素蒸發(fā)的情況）；其次，某一時(shí)刻螞蟻按橋上外激素量的多少來(lái)選擇某座橋，即螞蟻選擇某座橋的概率與經(jīng)過(guò)該橋的螞蟻數(shù)成正比。當(dāng)所有m只螞蟻都經(jīng)過(guò)兩座橋以后，設(shè)Am、Bm分別為經(jīng)過(guò)A橋和B橋的螞蟻數(shù)（Am+Bm=m），則第m+1只螞蟻選擇A橋的概率為：

89

公式表明：往A走的螞蟻越多，選擇分支A的概率就越高“n”決定選擇公式的非線性程度。（n越大，信息素多一點(diǎn)的分支選擇概率越高）“k”表示對(duì)未標(biāo)記的分支的吸引程度。（k越大，越多的信息素使選擇非隨機(jī)化）992、不等長(zhǎng)雙橋?qū)嶒?yàn)：圖2(a)為螞蟻經(jīng)過(guò)不等長(zhǎng)雙橋開(kāi)始覓食；圖2(b)顯示絕大多數(shù)螞蟻選擇較短的橋；圖2(c)顯示最終有80%一100%的螞蟻選擇較短的橋。102、不等長(zhǎng)雙橋?qū)嶒?yàn)：101011圖2

不等長(zhǎng)雙橋?qū)嶒?yàn)11圖2不等長(zhǎng)雙橋?qū)嶒?yàn)11在非對(duì)稱雙橋?qū)嶒?yàn)中，由于初始波動(dòng)的擴(kuò)大，螞蟻常常會(huì)選擇最短的路徑;先回蟻巢的螞蟻在最短分支上走了兩次(從蟻穴到食物源，再回到蟻穴)。所以這些螞蟻回來(lái)后不久，在短分支上有更多的信息素，從而誘使巢中同伴選擇短分支。實(shí)驗(yàn)表明，通過(guò)初始波動(dòng)的擴(kuò)大，最終選擇短分支的幾率隨著兩個(gè)分支的長(zhǎng)度比的增加而增長(zhǎng)。由此可見(jiàn)，在非對(duì)稱雙橋?qū)嶒?yàn)中，初始波動(dòng)對(duì)勝出分支橋(即較多螞蟻選擇的橋)的影響減小，而占主導(dǎo)作用的是隨機(jī)信息素的引導(dǎo)行為。12在非對(duì)稱雙橋?qū)嶒?yàn)中，由于初始波動(dòng)的擴(kuò)大，螞蟻常常會(huì)選擇最短的12基于以上蟻群尋找食物時(shí)的最優(yōu)路徑選擇問(wèn)題，可以構(gòu)造人工蟻群，來(lái)解決最優(yōu)化問(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è)目的地的距離。13基于以上蟻群尋找食物時(shí)的最優(yōu)路徑選擇問(wèn)題，可以13134蟻群現(xiàn)象螞蟻正常行進(jìn)，沒(méi)有遇到任何障礙，一路暢通。4蟻群現(xiàn)象螞蟻正常行進(jìn)，沒(méi)有遇到任何障礙，一路暢通。14螞蟻正常行進(jìn)，突然環(huán)境變換，增加了障礙物螞蟻正常行進(jìn)，突然環(huán)境變換，增加了障礙物15蟻群以同等概率選擇各條路徑，緊接著，隨著時(shí)間的增加較短路徑信息濃度高，選擇該路徑的螞蟻逐漸增多。蟻群以同等概率選擇各條路徑，緊接著，隨著時(shí)間的增加較短路徑信16螞蟻?zhàn)罱K繞過(guò)障礙物，找到最優(yōu)路徑。螞蟻?zhàn)罱K繞過(guò)障礙物，找到最優(yōu)路徑。175螞蟻簡(jiǎn)單規(guī)則兩方面1多樣性：螞蟻在覓食的時(shí)候路線不一，隨機(jī)性的向著某個(gè)方向方向走，打破常規(guī)，進(jìn)行創(chuàng)新。2正反饋：優(yōu)化的路線不斷被保存并加大自身概率，保證了相對(duì)優(yōu)良的信息能夠被保存下來(lái)。

多樣性保證了系統(tǒng)的創(chuàng)新能力，正反饋保證了優(yōu)良特性能夠得到強(qiáng)化，兩者要恰到好處的結(jié)合。5螞蟻簡(jiǎn)單規(guī)則兩方面1多樣性：螞蟻在覓食的時(shí)候路線不一，隨機(jī)186.蟻群算法求最優(yōu)目標(biāo)函數(shù)：?=cos(2*pi.*x).*cos(2.*pi.*y).*exp(-((x.^2+y.^2)/10))其中x,y∈[-1,1]根據(jù)原理，各數(shù)值首先隨機(jī)分布在坐標(biāo)上如圖7，經(jīng)過(guò)多次搜索最終得到最優(yōu)解如圖8所得極