蟻群算法ppt課件(2)(編輯修改稿)

　

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