《OK蟻群算法》PPT課件

1、 蟻群算法Ant Colony Algorithm 1精選PPT1 蟻群優(yōu)化算法概念1.1 蟻群算法原理1.2 簡化的螞蟻尋食過程1.3 蟻群現(xiàn)象1.4 螞蟻簡單規(guī)則的兩個(gè)方面1.4 蟻群算法與TSP問題1.5 初始的蟻群優(yōu)化算法基于圖的蟻群系統(tǒng)（GBAS）2精選PPT1.1 蟻群算法原理 蟻群算法是對(duì)自然界螞蟻的尋徑方式進(jìn)行模似而得出的一種仿生算法。螞蟻在運(yùn)動(dòng)過程中，能夠在它所經(jīng)過的路徑上留下一種稱之為外激素(pheromone)的物質(zhì)進(jìn)行信息傳遞，而且螞蟻在運(yùn)動(dòng)過程中能夠感知這種物質(zhì)，并以此指導(dǎo)自己的運(yùn)動(dòng)方向，因此由大量螞蟻組成的蟻群集體行為便表現(xiàn)出一種信息正反饋現(xiàn)象：某一路徑上走過的螞蟻

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

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

4、2個(gè)單位，其比值為2：1。 尋找食物的過程繼續(xù)進(jìn)行，則按信息素的指導(dǎo)，蟻群在ABD路線上增派一只螞蟻（共2只），而ACD路線上仍然為一只螞蟻。再經(jīng)過36個(gè)時(shí)間單位后，兩條線路上的信息素單位積累為12和4，比值為3：1。7精選PPT 若按以上規(guī)則繼續(xù)，蟻群在ABD路線上再增派一只螞蟻（共3只），而ACD路線上仍然為一只螞蟻。再經(jīng)過36個(gè)時(shí)間單位后，兩條線路上的信息素單位積累為24和6，比值為4：1。 若繼續(xù)進(jìn)行，則按信息素的指導(dǎo)，最終所有的螞蟻會(huì)放棄ACD路線，而都選擇ABD路線。這是正反饋效應(yīng)。8精選PPT信息素的更新方式有2種： 一是揮發(fā)：也就是所有路徑上的信息素以一定的比率進(jìn)行減少，模擬自

5、然蟻群的信息素隨時(shí)間揮發(fā)的過程； 二是增強(qiáng)：給評(píng)價(jià)值“好”(有螞蟻?zhàn)哌^)的邊增加信息素。9精選PPT1.3 蟻群現(xiàn)象螞蟻正常行進(jìn)，突然環(huán)境變化，增加了障礙物10精選PPT蟻群現(xiàn)象：螞蟻以同等概率選擇各條路徑，緊接著，隨著時(shí)間的增 加較短路徑信息濃度高，選擇該路徑的螞蟻逐漸增多。11精選PPT蟻群現(xiàn)象：螞蟻?zhàn)罱K繞過障礙物找到最優(yōu)路徑12精選PPT1.4 螞蟻簡單規(guī)則的兩個(gè)方面：1多樣性：螞蟻在覓食的時(shí)候路線不一，隨 機(jī)性的向著某個(gè)方向行走，打破常規(guī)，進(jìn)行創(chuàng)新。2正反饋：優(yōu)化的路線不斷被保存并加大自身概率，保證了相對(duì)優(yōu)良的信息能夠被保存下來。 多樣性保證了系統(tǒng)的創(chuàng)新能力，正反饋保證了優(yōu)良特性能夠得

6、到強(qiáng)化，兩者要恰到好處的結(jié)合。 13精選PPT1.5 蟻群算法在TSP問題中的應(yīng)用旅行商問題，即TSP問題又譯為旅行推銷員問題、貨郎擔(dān)問題，是數(shù)學(xué)領(lǐng)域中著名問題之一。假設(shè)有一個(gè)旅行商人要拜訪n個(gè)城市，他必須選擇所要走的路徑，路經(jīng)的限制是每個(gè)城市只能拜訪一次，而且最后要回到原來出發(fā)的城市。路徑的選擇目標(biāo)是要求得的路徑路程為所有路徑之中的最小值。 14精選PPT算法步驟如下：15精選PPT16精選PPT17精選PPT18精選PPT按 的不同取法，可形成三種類型的螞蟻算法模型：（1）Ant-Circle System模型，有式中，Q為常量， 為第k只螞蟻在本次循環(huán)中所走路徑的長度。（2）Ant-Quantity System模型19精選PPT（3）Ant-Density System模型 很明顯在后兩種模型中，利用的都是局部信息，而第一種模型利用的是整體信息。這三種模型在求解不同問題時(shí)各有優(yōu)勢。20精選PPT21精選PPT22精選PPT23精選PPT24精選PPT這樣循環(huán)，最終得到了最優(yōu)路線。25精選PPT實(shí)際的概率公式：定義 為他