《ch2智能理論-蟻群算法》由會員分享，可在線閱讀，更多相關(guān)《ch2智能理論-蟻群算法（29頁珍藏版）》請在裝配圖網(wǎng)上搜索。

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

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

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

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

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

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

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

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

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

10、兩類參數(shù)決定：信息素值、可見度(即先驗值)。信息素的更新有2種方式： l揮發(fā)所有路徑上信息素以一定比率減少l增強(qiáng)給評價值“好”(有螞蟻?zhàn)哌^)的邊增加信息素 基于圖的蟻群系統(tǒng)(GBAS)STEP 0 對n個城市的TSP問題，l城市間的距離矩陣為：(dij)nnl給TSP圖中的每一條弧(i, j)賦信息素初值：ij(0)=1/|A|l |A|：表示圖中弧(i, j)的數(shù)目 ，即矩陣(dij)nn中不為零的數(shù)；l設(shè)有m只螞蟻工作，都從同一城市i 0出發(fā)l當(dāng)前最好解是：w*=(1, 2, , n)l目標(biāo)函數(shù)： 1,2,., , ,N n A i j i j N 11 l ln i ilf w d 基于

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

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

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

14、部分。 關(guān)于信息素l信息素的更新分為離線和在線兩種方式。離線方式（同步更新方式）主要思想是在若干只螞蟻完成n個城市的訪問后，統(tǒng)一對殘留信息進(jìn)行更新處理。在線更新（異步更新方式）螞蟻每走一步，立即回溯并且更新行走路徑上的信息素。 基于圖的蟻群系統(tǒng)(GBAS)l四個城市的非對稱TSP問題 0 1 0.5 11 0 1 11.5 5 0 11 1 1 0ijD d 基于圖的蟻群系統(tǒng)（GBAS）l設(shè)共有4只螞蟻，都從城市A出發(fā)l揮發(fā)因子l初始信息素記憶矩陣為：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 1

15、2 1 12 0 基于圖的蟻群系統(tǒng)（GBAS）l執(zhí)行GBAS算法的步驟2，設(shè)螞蟻的行走路線分別為：第一只w1：ABCDAf(w1)=4第二只w2：ACDBAf(w1)=3.5第三只w3：ADCBAf(w1)=8第四只w4：ABDCAf(w1)=4.5 l當(dāng)前最優(yōu)解為w2也是截止到當(dāng)前的最優(yōu)解。 基于圖的蟻群系統(tǒng)（GBAS）l更新信息素矩陣第一次外循環(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

16、 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）l重復(fù)外循環(huán)，由于w2已經(jīng)是全局最優(yōu)解，因此按STEP3的信息素更新規(guī)則，無論螞蟻如何行走，都只是對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