《ch2智能理論--蟻群算法PPT課件02》由會(huì)員分享，可在線閱讀，更多相關(guān)《ch2智能理論--蟻群算法PPT課件02（29頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、蟻群優(yōu)化算法起源20世紀(jì)90年代，意大利學(xué)者Dorigo等人從生物進(jìn)化的機(jī)制中受到啟發(fā)，通過模擬自然界螞蟻搜索路徑的行為，提出一種新型的模擬進(jìn)化算法蟻群算法，它是群智能理論研究領(lǐng)域的一種主要算法。用該方法求解TSP問題、分配問題、job-shop調(diào)度問題取得了較好的試驗(yàn)結(jié)果。雖然研究時(shí)間不長(zhǎng)，但是目前的研究顯示出，蟻群算法在求解復(fù)雜優(yōu)化問題（特別是離散優(yōu)化問題）方面有一定優(yōu)勢(shì)，表明它是一種有發(fā)展前景的算法。 蟻群優(yōu)化算法應(yīng)用領(lǐng)域蟻群算法能夠用于解決大多數(shù)優(yōu)化問題或者能夠被轉(zhuǎn)化為優(yōu)化求解的問題。目前，其應(yīng)用領(lǐng)域已擴(kuò)展到 多目標(biāo)優(yōu)化 數(shù)據(jù)分類 數(shù)據(jù)聚類 模式識(shí)別 生物系統(tǒng)建模流程規(guī)劃信號(hào)處理機(jī)器人

2、控制決策支持仿真和系統(tǒng)辯識(shí) 蟻群優(yōu)化算法研究背景群智能理論研究領(lǐng)域有兩種主要的算法： 蟻群算法(Ant Colony Optimization, ACO)對(duì)螞蟻群落食物采集過程的模擬已成功應(yīng)用于許多離散優(yōu)化問題。 微粒群算法(Particle Swarm Optimization, PSO) 起源于對(duì)簡(jiǎn)單社會(huì)系統(tǒng)的模擬。最初模擬鳥群覓食的過程，后來發(fā)現(xiàn)它是一種很好的優(yōu)化工具。 蟻群優(yōu)化算法研究背景群智能依靠的是概率搜索算法。雖然概率搜索算法通常要采用較多的評(píng)價(jià)函數(shù)，但與梯度法及傳統(tǒng)的演化算法相比，主要優(yōu)點(diǎn)為： 無(wú)集中控制約束，不會(huì)因個(gè)別個(gè)體的故障影響整個(gè)問題的求解，確保了系統(tǒng)具備更強(qiáng)的魯棒性

3、以非直接的信息交流方式確保了系統(tǒng)的擴(kuò)展性 并行分布式算法模型，可充分利用多處理器 對(duì)問題定義的連續(xù)性無(wú)特殊要求 算法實(shí)現(xiàn)簡(jiǎn)單 蟻群優(yōu)化算法研究背景群智能方法的易于實(shí)現(xiàn)體現(xiàn)在： 算法中僅涉及各種基本的數(shù)學(xué)操作 數(shù)據(jù)處理過程對(duì)CPU和內(nèi)存的要求不高 只需要目標(biāo)函數(shù)的輸出值，不需要它的梯度信息。 蟻群優(yōu)化算法研究背景已完成的群智能理論和應(yīng)用方法研究證明 群智能方法能夠有效解決大多數(shù)全局優(yōu)化問題 群智能潛在的并行性和分布式特點(diǎn)為處理大量的、以數(shù)據(jù)庫(kù)形式存在的數(shù)據(jù)提供了技術(shù)保證。無(wú)論從理論研究還是應(yīng)用研究的角度分析，群智能理論及其應(yīng)用研究都是有重要學(xué)術(shù)意義和現(xiàn)實(shí)價(jià)值。 蟻群優(yōu)化算法研究現(xiàn)狀從Dorigo

4、在90年代最早提出蟻群算法-螞蟻系統(tǒng)(Ant System, AS)，并將其應(yīng)用于解決TSP問題開始，基本的蟻群算法得到了不斷的發(fā)展和完善，并在其他許多實(shí)際優(yōu)化問題求解中進(jìn)一步得到了驗(yàn)證。AS改進(jìn)版 共同點(diǎn)：增強(qiáng)螞蟻搜索過程中對(duì)最優(yōu)解的探索能力 差異：搜索控制策略 蟻群優(yōu)化算法研究現(xiàn)狀最初提出的AS有三種版本：Ant-density、Ant-quantity、Ant-cycle前兩種算法中，螞蟻在兩個(gè)位置節(jié)點(diǎn)間每移動(dòng)一次后即更新信息素。 Ant-cycle中，所有螞蟻都完成了自己的行程后，才對(duì)信息素進(jìn)行更新，而且每個(gè)螞蟻所釋放的信息素被表達(dá)為反映相應(yīng)行程質(zhì)量的函數(shù)。 與其它各種通用的啟發(fā)式算法

5、相比，在不大于75城市的TSP中，它們的求解能力比較理想。但是當(dāng)問題規(guī)模擴(kuò)展時(shí)，AS的解題能力大幅度下降。 蟻群優(yōu)化算法研究現(xiàn)狀其后的ACO研究工作主要都集中在AS性能的改進(jìn)方面。較早的一種改進(jìn)是精英策略(Elitist Strategy)，其思想是： 在算法開始后，對(duì)所有已發(fā)現(xiàn)的最好路徑給予額外增強(qiáng)，并將隨后與之對(duì)應(yīng)的行程記為Tgb(全局最優(yōu)行程)，當(dāng)進(jìn)行信息素更新時(shí)，對(duì)這些行程予以加權(quán)，同時(shí)將經(jīng)過這些行程的螞蟻記為“精英”，從而增大較好行程的選擇機(jī)會(huì)。 這種改進(jìn)型算法能以更快的速度獲得更好的解。但是若選擇的精英過多，則算法會(huì)由于較早收斂于局部次優(yōu)解，而導(dǎo)致搜索的過早停滯。 螞蟻尋食過程尋找

6、路徑時(shí)，在路徑上釋放出一種特殊的信息素。碰到?jīng)]有走過的路口，隨機(jī)挑選一條路徑，并釋放出與路徑長(zhǎng)度有關(guān)的信息素。路徑越長(zhǎng)，釋放的激素濃度越低。后來的螞蟻再次碰到這個(gè)路口的時(shí)候，選擇激素濃度較高路徑概率相對(duì)較大。 正反饋：最優(yōu)路徑上激素濃度越來越大，其它路徑上激素濃度隨時(shí)間的流逝而消減。最終整個(gè)蟻群找出最優(yōu)路徑。 簡(jiǎn)化的螞蟻尋食過程 螞蟻從A點(diǎn)出發(fā)，速度相同，食物在D點(diǎn)?？呻S機(jī)選擇的路線：ABD或ACD。設(shè)初始時(shí)每條路線分配一只螞蟻，每單位時(shí)間行走一步上圖為經(jīng)過9個(gè)時(shí)間單位時(shí)的情形：走ABD的螞蟻到達(dá)終點(diǎn)，而走ACD的螞蟻剛好走到C點(diǎn)，為一半路程。 簡(jiǎn)化的螞蟻尋食過程本圖為從開始算起，經(jīng)過18個(gè)時(shí)

7、間單位時(shí)的情形： 走ABD的螞蟻到達(dá)終點(diǎn)后得到食物又返回了起點(diǎn)A走ACD的螞蟻剛好走到D點(diǎn)。 簡(jiǎn)化的螞蟻尋食過程設(shè)螞蟻每經(jīng)過一處所留下的信息素為一個(gè)單位。36個(gè)時(shí)間單位后，所有開始一起出發(fā)的螞蟻都經(jīng)過不同路徑從D點(diǎn)取得了食物。 ABD的路線往返了2趟，每一處的信息素為4個(gè)單位 ACD的路線往返了1趟，每一處的信息素為2個(gè)單位 信息素比值為2:1 按信息素指導(dǎo)，蟻群在ABD路線上增派一只螞蟻(共2只)，ACD路線上仍然是一只螞蟻。 簡(jiǎn)化的螞蟻尋食過程72個(gè)時(shí)間單位后，兩條線路上的信息素單位積累為12和4，比值為3:1。若按以上規(guī)則繼續(xù)，蟻群在ABD路線上再增派一只螞蟻(共3只)，ACD路線上仍然

8、是一只螞蟻。再36個(gè)時(shí)間單位后，兩條線路上的信息素單位積累為24和6，比值為4：1。 若繼續(xù)進(jìn)行，按信息素指導(dǎo)，最終所有螞蟻會(huì)放棄ACD路線，都選擇ABD路線，這就是正反饋效應(yīng)。 自然蟻群與人工蟻群算法人工蟻群中把具有簡(jiǎn)單功能的工作單元看作螞蟻。相似處：優(yōu)先選擇信息素濃度大的路徑。較短路徑的信息素濃度高，所以能夠最終被所有螞蟻選擇，也就是最終的優(yōu)化結(jié)果。區(qū)別：人工蟻群能記憶已訪問過的節(jié)點(diǎn)，在選擇下條路徑時(shí)是按一定算法規(guī)律有意識(shí)地尋找最短路徑。 如，TSP問題中可預(yù)先知道當(dāng)前城市到下一個(gè)目的地的距離。 蟻群算法與TSP問題初始的蟻群算法是基于圖的蟻群算法(graph-based ant syst

9、em，GBAS)，2000年由Gutjahr在Future Generation Computing Systems提出。TSP問題表示為N個(gè)城市的有向圖：G=(N, A)目標(biāo)函數(shù) w=(i1, i2, , in)為城市1, 2, , n的一個(gè)排列 (dij)nn為城市間距離矩陣 1,2,., , ,N n A i j i j N 11 l ln i ilf w d 蟻群算法與TSP問題設(shè)m只螞蟻在圖的相鄰節(jié)點(diǎn)間移動(dòng)，協(xié)作異步地得到解。螞蟻計(jì)算出下一步所有可達(dá)節(jié)點(diǎn)的一步轉(zhuǎn)移概率，并按此概率實(shí)現(xiàn)一步移動(dòng)，依此往復(fù)。一步轉(zhuǎn)移概率由圖中每條邊上的兩類參數(shù)決定：信息素值、可見度(即先驗(yàn)值)。信息素的更

10、新有2種方式： 揮發(fā)所有路徑上信息素以一定比率減少增強(qiáng)給評(píng)價(jià)值“好”(有螞蟻?zhàn)哌^)的邊增加信息素 基于圖的蟻群系統(tǒng)(GBAS)STEP 0 對(duì)n個(gè)城市的TSP問題，城市間的距離矩陣為：(dij)nn給TSP圖中的每一條弧(i, j)賦信息素初值：ij(0)=1/|A| |A|：表示圖中弧(i, j)的數(shù)目 ，即矩陣(d ij)nn中不為零的數(shù)；設(shè)有m只螞蟻工作，都從同一城市i0出發(fā)當(dāng)前最好解是：w*=(1, 2, , n)目標(biāo)函數(shù)： 1,2,., , ,N n A i j i j N 11 l ln i ilf w d 基于圖的蟻群系統(tǒng)(GBAS)STEP 1 (外循環(huán)) 若滿足算法停止規(guī)則，

11、停止計(jì)算，輸出計(jì)算得到的最好解給定外循環(huán)的最大數(shù)目，表明有足夠的螞蟻工作；當(dāng)前最優(yōu)解連續(xù)K次相同而停止，K是給定的整數(shù)，表示算法已收斂；給定優(yōu)化問題的下界和誤差值，當(dāng)算法得到的目標(biāo)值同下界之差小于給定的誤差值時(shí)，算法終止。否則使螞蟻s(1sm)從起點(diǎn)i0出發(fā)，用L(s)表示螞蟻s行走的城市集合，初始L(s)為空集。 基于圖的蟻群系統(tǒng)(GBAS)STEP 2 (內(nèi)循環(huán)) 按螞蟻1sm的順序分別計(jì)算在城市i，若L(s)=N或l|(i, l)A, lL(s)=，完成螞蟻s的計(jì)算。否則，若T=l|(i, l)A, lL(s)-i0，以概率到達(dá)j，L(s)=L(s)j，il=j若L(s)N且T=，則到達(dá)

12、i0，L(s)=L(s)i 0，il=i0重復(fù)STEP 2 110ij ijij l T k j Tkp j T 基于圖的蟻群系統(tǒng)(GBAS)STEP 3 對(duì)螞蟻1sm，若L(s)=N，按L(s)中城市的順序計(jì)算路徑長(zhǎng)度；若L(s)N，路徑長(zhǎng)度置為無(wú)窮大(即不可達(dá))。比較m只螞蟻的路徑長(zhǎng)度，記走最短路徑的螞蟻為t。若f(L(t)f(w*)，則w*=L(t) 修改信息素值對(duì)固定的K1，揮發(fā)因子k滿足：加強(qiáng)w*路徑上的信息素?fù)]發(fā)其他路徑上的信息素，經(jīng)過k次揮發(fā)，非最優(yōu)路徑的信息素逐漸減少至消失。 k=k+1，重復(fù)STEP 1 1111 1 ,1 1 ,kk ijij k ij k i j wwk

13、k i j w 是上的一條弧不是上的一條弧 1ln1 , ,ln 1k kkk k Kk 關(guān)于信息素螞蟻以信息素的概率分布來決定從城市i到j(luò)的轉(zhuǎn)移，信息素更新過程由兩部分組成 揮發(fā)每個(gè)連接上信息素逐漸減弱的過程由(1-k-1)ij(k-1)表示，該過程主要用于避免算法過快地向局部最優(yōu)區(qū)域集中，有助于搜索區(qū)域的擴(kuò)展。揮發(fā)過程是所有弧都進(jìn)行的，與螞蟻數(shù)量無(wú)關(guān)。 增強(qiáng)觀察蟻群中每只螞蟻找到的路徑，選擇最優(yōu)路徑上的弧進(jìn)行信息素增強(qiáng)，實(shí)現(xiàn)單個(gè)螞蟻無(wú)法實(shí)現(xiàn)的集中行動(dòng)。 增強(qiáng)過程是蟻群優(yōu)化算法中可選的部分。 關(guān)于信息素信息素的更新分為離線和在線兩種方式。 離線方式（同步更新方式）主要思想是在若干只螞蟻完成n

14、個(gè)城市的訪問后，統(tǒng)一對(duì)殘留信息進(jìn)行更新處理。 在線更新（異步更新方式）螞蟻每走一步，立即回溯并且更新行走路徑上的信息素。 基于圖的蟻群系統(tǒng)(GBAS)四個(gè)城市的非對(duì)稱TSP問題 0 1 0.5 11 0 1 11.5 5 0 11 1 1 0ijD d 基于圖的蟻群系統(tǒng)（GBAS）設(shè)共有4只螞蟻，都從城市A出發(fā)揮發(fā)因子初始信息素記憶矩陣為：1 , 1,2,32k k 0 1 12 1 12 1 121 12 0 1 12 1 120 1 12 1 12 0 1 121 12 1 12 1 12 0 基于圖的蟻群系統(tǒng)（GBAS）執(zhí)行GBAS算法的步驟2，設(shè)螞蟻的行走路線分別為：第一只w1：ABC

15、DAf(w1)=4第二只w2：ACDBAf(w1第三只w3：ADCBAf(w1)=8第四只w4：ABDCAf(w1 當(dāng)前最優(yōu)解為w2也是截止到當(dāng)前的最優(yōu)解。 基于圖的蟻群系統(tǒng)（GBAS）更新信息素矩陣 第一次外循環(huán)結(jié)束的狀態(tài) 1111 1 ,1 1 ,kk ijij k ij k i j wwk k i j w 是上的一條弧不是上的一條弧 0 1 24 1 6 1 241 6 0 1 24 1 241 1 24 1 12 0 1 61 24 1 6 1 24 0 0 1 12 1 12 1 121 12 0 1 12 1 120 1 12 1 12 0 1 121 12 1 12 1 12 01 , 1,2,32k k 基于圖的蟻群系統(tǒng)（GBAS）重復(fù)外循環(huán)，由于w2已經(jīng)是全局最優(yōu)解，因此按STEP3的信息素更新規(guī)則，無(wú)論螞蟻如何行走，都只是對(duì)w2路線上的城市信息素進(jìn)行增強(qiáng)，其他的城市信息素進(jìn)行揮發(fā)。得到更新矩陣 0 1 48 5 24 1 48 0 1 96 11 48 1 965 24 0 1 48 1 48 11 48 0 1 96 1 962 31 48 1 48 0 5 24 1 96 1 96 0 11 481 48 5 24 1 48 0 1 96 11 48 1 96 0