什么是人工智能算法65(編輯修改稿)
2025-03-11 14:26 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 陣。四個(gè)城市的非對(duì)稱(chēng) TSP問(wèn)題，距離矩陣和城市圖示如下：22初始的蟻群優(yōu)化算法 —基于圖的蟻群系統(tǒng)（ GBAS） 7/12假設(shè)共 4只螞蟻，所有螞蟻都從城市 A出發(fā)，揮發(fā)因子此時(shí)，觀察 GBAS的計(jì)算過(guò)程。 矩陣共有 12條弧，初始信息素記憶矩陣為：23初始的蟻群優(yōu)化算法 —基于圖的蟻群系統(tǒng)（ GBAS） 8/12執(zhí)行 GBAS算法的步驟 2，假設(shè)螞蟻的行走路線分別為：當(dāng)前最優(yōu)解為，這個(gè)解是截止到當(dāng)前的最優(yōu)解，碰巧是實(shí)際最優(yōu)解24初始的蟻群優(yōu)化算法 —基于圖的蟻群系統(tǒng)（ GBAS） 9/12按算法步驟 3的信息素更新規(guī)則，得到更新矩陣這是第一次外循環(huán)結(jié)束的狀態(tài)。25初始的蟻群優(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)。26初始的蟻群優(yōu)化算法 —基于圖的蟻群系統(tǒng)（ GBAS） 11/12重復(fù)外循環(huán)，由于 W2全局最優(yōu)解， GBAS只記錄第一個(gè)最優(yōu)解，因此一但得到了全局最優(yōu)解，信息素的更新將不再依賴(lài)于以群的行走路線，而只是不斷增強(qiáng)最優(yōu)路線的信息素，同時(shí)進(jìn)行揮發(fā)。第三次外循環(huán)后得到的信息素矩陣為：27初始的蟻群優(yōu)化算法 —基于圖的蟻群系統(tǒng)（ GBAS） 12/12螞蟻以一定的概率從城市 i到城市 j進(jìn)行轉(zhuǎn)移，信息素的更新在 STEP3完成，并隨 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ò)程。28一般蟻群算法的框架一般蟻群算法的框架和 GBAS基本相同，有三個(gè)組成部分：蟻群的活動(dòng)；信息素的揮發(fā)；信息素的增強(qiáng)；主要體現(xiàn)在前面的算法中步驟 2和步驟 3中的轉(zhuǎn)移概率公式和信息素更新公式。29蟻群優(yōu)化算法 —算法模型和收斂性分析馬氏過(guò)程的收斂定義GBAS算法的收斂性分析其他算法及收斂性分析30馬氏過(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ì)任意給定的 滿足則稱(chēng)馬爾可夫過(guò)程 依概率 1收斂到 31GBAS算法的收斂性分析 1/8定理 滿足 指定條件 的馬爾可夫過(guò)程 依概率 1收斂到 ,其中 為一條最優(yōu)路徑 ,定義為 :證明分析 :蟻群算法中 ,一但達(dá)到全局最優(yōu) ,由 只記錄第一個(gè)最優(yōu)解 .證明分三部分 :n 證明以概率 1達(dá)到一個(gè)最優(yōu)路徑n 證明 (1)上式成立n 證明以概率 1收斂到一個(gè)最優(yōu)路徑32GBAS算法的收斂性分析 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ì)被走到的事件為 ,其概率為 :33GBAS算法的收斂性分析 3/8任意給定的固定弧 (i,j),在第 k次循環(huán)后 ,其信息素值的下界可以計(jì)算出 .34GBAS算法的收斂性分析 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) ,35GBAS算法的收斂性分析 5/8則取對(duì)數(shù)有從而得到36GBAS算法的收斂性分析 6/8證明右式成
法律信息相關(guān)推薦
鄂ICP備17016276號(hào)-1