蟻群算法ppt課件(2)(編輯修改稿)
2025-05-26 03:40 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 所有弧都進(jìn)行的，不于螞蟻數(shù)量相關(guān)。這種增強(qiáng)過(guò)程中進(jìn)行的信息素更新稱為離線的信息素更新。 在 STEP 3中，蟻群永遠(yuǎn)記憶到目前為止的最優(yōu)解。27 — 基于圖的蟻群系統(tǒng)（ GBAS） 6/12可以驗(yàn)證，下式滿足：即 是一個(gè)隨機(jī)矩陣。四個(gè)城市的非對(duì)稱 TSP問(wèn)題，距離矩陣和城市圖示如下：28 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng) （ GBAS） 7/12假設(shè)共 4只螞蟻，所有螞蟻都從城市 A出發(fā)，揮發(fā)因子 。此時(shí)，觀察 GBAS的計(jì)算過(guò)程。 矩陣共有 12條弧，初始信息素記憶矩陣為：29 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS） 8/12執(zhí)行 GBAS算法的步驟 2，假設(shè)螞蟻的行走路線分別為：當(dāng)前最優(yōu)解為 ，這個(gè)解是截止到當(dāng)前的最優(yōu)解，碰巧是實(shí)際最優(yōu)解30 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS） 9/12按算法步驟 3的信息素更新規(guī)則，得到更新矩陣這是第一次外循環(huán)結(jié)束的狀態(tài)。31 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS） 10/12重復(fù)外循環(huán)，由于上一次得到的 W2已經(jīng)是全局最優(yōu)解，因此按算法步驟 3的信息素更新規(guī)則，無(wú)論螞蟻如何行走，都只是對(duì) W2路線上的城市信息素進(jìn)行增強(qiáng)，其他的城市信息素進(jìn)行揮發(fā)。得到更新矩陣這是第一次外循環(huán)結(jié)束的狀態(tài)。32 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS） 11/12重復(fù)外循環(huán)，由于 W2全局最優(yōu)解， GBAS只記錄第一個(gè)最優(yōu)解，因此一但得到了全局最優(yōu)解，信息素的更新將不再依賴于以群的行走路線，而只是不斷增強(qiáng)最優(yōu)路線的信息素，同時(shí)進(jìn)行揮發(fā)。第三次外循環(huán)后得到的信息素矩陣為：33 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS） 12/12 螞蟻以一定的概率從城市 i到城市 j進(jìn)行轉(zhuǎn)移，信息素的更新在 STEP 3 完成，并隨 K而 變化。假設(shè)第 K次外循環(huán)后得到信息素矩陣 ，得到當(dāng)前最優(yōu)解 。第 K次循環(huán)前的信息素和最優(yōu)解為 ，經(jīng)過(guò)第 K次外循環(huán)后，得到 。由于螞蟻的一步轉(zhuǎn)移概率是隨機(jī)的，從 到 也是隨機(jī)的，是一個(gè)馬爾可夫過(guò)程。34 一般蟻群算法的框架一般蟻群算法的框架和 GBAS基本相同，有三個(gè)組成部分：n 蟻群的活動(dòng)n 信息素的揮發(fā)n 信息素的增強(qiáng)主要體現(xiàn)在前面的算法中步驟 2和步驟 3中的轉(zhuǎn)移概率公式和信息素更新公式。35 蟻群優(yōu)化算法 — 算法模型和收斂性分析 馬氏過(guò)程的收斂定義 GBAS算法的收斂性分析 其他算法及收斂性分析36 馬氏過(guò)程的收斂定義蟻群優(yōu)化算法的每步迭代對(duì)應(yīng)隨機(jī)變量其中 為信息素痕跡； 為 n城市的一個(gè)排列，最多有 個(gè)狀態(tài)。第 s只螞蟻在第 k輪轉(zhuǎn)移只由 決定，這個(gè)螞蟻行走的路徑和 一起，共同決定了 ，再通過(guò)信息素的更新原則可以進(jìn)一步得到 。 的變化僅由 決定，而與先前的狀態(tài)無(wú)關(guān)，這是一個(gè)典型的馬爾可夫過(guò)程。 定義 ：若一個(gè)馬爾可夫過(guò)程 ，對(duì)任意給定的 滿足 則稱馬爾可夫過(guò)程 依概率 1收斂到 。37 GBAS算法的收斂性分析 1/8 定理 滿足 指定條件 的馬爾可夫過(guò)程 依概率 1收斂到 ,其中 為一條最優(yōu)路徑 , 定義為 : 證明分析 : 蟻群算法中 ,一但達(dá)到全局最優(yōu) ,由 只記錄第一個(gè)最優(yōu)解 .證明分三部分 :u 證明以概率 1達(dá)到一個(gè)最優(yōu)路徑u 證明 (1)上式成立u 證明以概率 1收斂到一個(gè)最優(yōu)路徑38 GBAS算法的收斂性分析 2/8 證明以概率 1到達(dá)一個(gè)最優(yōu)路徑 對(duì)于最優(yōu)路徑 ,令 為蟻群中的一個(gè)螞蟻在第 k次外循環(huán)后第一次走到最優(yōu)路徑 的事件 . 表示僅第 k次外循環(huán)沒(méi)有走到 的事件 ,但前 k1次可能走到過(guò)這條最優(yōu)路徑 . 永遠(yuǎn)不會(huì)被走到的事件為 ,其概率為 :39 GBAS算法的收斂性分析 3/8 任意給定的固定弧 (i,j),在第 k次循環(huán)后 ,其信息素值的下界可以計(jì)算出：40 GBAS算法的收斂性分析 4/8令 ,任何一個(gè)固定節(jié)點(diǎn)最多有 (n1)后續(xù)節(jié)點(diǎn) ,并且其弧上的信息素值都小于 1或者等于 :蟻群中的一只螞蟻在第 次循環(huán)走到路徑 W* 的概率為一個(gè)蟻群中至少有一只螞蟻，因此這是一個(gè)蟻群到達(dá)最優(yōu)路徑的一個(gè)下界 . 上式右側(cè)與 k無(wú)關(guān) 41 GBAS算法的收斂性分析 5/8 則取對(duì)數(shù)有從而得到42 GBAS算法的收斂性分析 6/8 證明右式成立 隨機(jī)過(guò)程 以概率 1達(dá)到一條最優(yōu)路徑 .當(dāng)某條最優(yōu)路徑 Z在第 k次循環(huán)被首次走到后 ,在第 k+1輪循環(huán)按信息素的更新原則 ,可以用歸納法證明 ,對(duì)于任意43 GBAS算法的收斂性分析 7/8由于級(jí)數(shù) 是發(fā)散的 ,可知 .因此 ,當(dāng) 時(shí) ,在第 K輪迭代之后 ,該弧永遠(yuǎn)不再被加強(qiáng) ,從而有 也既 弧上的信息素之和將趨于 0.對(duì)于信息素的更新公式 (2),可以歸納證明(6)式的第二項(xiàng)與 (i,j)弧無(wú)關(guān) ,結(jié)合 (7)式可得 的極限存在 ,且所有的極限之和為 44 GBAS算法的收斂性分析 8/8 結(jié)合前兩部分討論 ,當(dāng) Xn首次到達(dá)最優(yōu)路徑后 ,對(duì)于任何最優(yōu)路徑上的弧 ,(1)式的轉(zhuǎn)移概率 ,即 依概率 1收斂到 .45 其他算法及收斂性分析 1/4 MAXMIN蟻群優(yōu)化算法指定揮發(fā)系數(shù)不隨時(shí)間變化 ,這是和GBAS算法不同的一點(diǎn) ,改變了信息素?fù)]發(fā)和增強(qiáng)的規(guī)則 (9)式 ，同時(shí)給出一
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1