現(xiàn)代優(yōu)化算法-蟻群算法-文庫吧資料
2025-05-18 09:48本頁面
【正文】 t到 t+n內(nèi)的訪問過程中，在 i到 j的路徑上留下的殘留信息濃度； Q ：為常量； Lk ：螞蟻 k在本次循環(huán)中所選擇路徑的總長度；如果沒有選擇 i到 j的路徑，則 kij??0?? kij?蟻群優(yōu)化算法 — 算法流程 跡更新機制 —— antdensity算法， 在每一只螞蟻完成下一個個城市的訪問后，對舊的信息進行削弱，將最新的螞蟻訪問路徑的信息加入 。 ??kiN??tPkij蟻群優(yōu)化算法 — 算法流程 跡更新機制， 為了避免殘留信息過多引起的殘留信息淹沒啟發(fā)信息的問題，在每一只螞蟻完成對所有 n個城市的訪問后（也即一個循環(huán)結(jié)束后）或每走一步（從一個城市到下一個城市后），必須對殘留信息進行更新處理， Morigo介紹三種跡更新機制： 1） antcycle算法 2） antdensity算法 3） antquantity算法 蟻群優(yōu)化算法 — 算法流程 跡更新機制 —— antcycle算法， 在每一只螞蟻完成對所有 n個城市的訪問后，對舊的信息進行削弱，將最新的螞蟻訪問路徑的信息加入 。 ??tij?ij?ijij d1??ijd ij?蟻群優(yōu)化算法 — 算法流程 選擇機制， 那么， t 時刻位于城市 i 的螞蟻 k 選擇城市 j 為目標城市的概率是： ? ?? ?? ??????kiNlililijijkijtttP????????kiNj ?：殘留信息的相對重要程度； ：啟發(fā)信息的相對重要程度； ：所有可能的目標城市，即還沒有訪問的城市。 蟻群優(yōu)化算法 — 算法流程 選擇機制，選擇下一個城市的依據(jù)主要是兩點： 1） t 時刻連接城市 i 和 j 的路徑上殘留信息（跡）的濃度 —— 。 第二步， 選擇機制： 每一只螞蟻每一步的行動是，根據(jù)一定的依據(jù)選擇下一個它還沒有訪問的城市； 第三步， 跡更新機制： 在完成一步（從一個城市到達另外一個城市）或者一個循環(huán)（完成對所有 n個城市的訪問）后，更新所有路徑上的殘留信息濃度。 蟻群優(yōu)化算法 — 算法提出 蟻群優(yōu)化算法的核心思想有三條： 第一，選擇機制：跡越多的路徑，被選中的概率越大； 第二，跡更新機制：路徑越短，跡增加越快； 第三，協(xié)作機制：個體之間通過跡進行信息交流。 蟻群優(yōu)化算法 — 算法提出 TSP問題與蟻群尋徑行為比較： TSP問題 蟻群尋徑行為 解 路徑 尋優(yōu)過程 選擇路徑 最短路徑（最優(yōu)解） 最短路徑 蟻群優(yōu)化算法 — 算法提出 在 20世紀 90年代 ， 意大利學(xué)者 Dorigo等人從生物進化的機理中受到啟發(fā) ， 通過模擬自然界螞蟻尋徑的行為 ，提出了一種全新的模擬進化算法 ， 蟻群優(yōu)化算法 。 在如何解決這個問題方面已經(jīng)有了大量的研究 。 蟻群優(yōu)化算法 — 算法提出 NP問題： 至今為止 ， 還沒有一個有能求得最優(yōu)解的多項式時間算法的組合優(yōu)化問題稱為 NP問題 。 A B D E C 如圖所示 ， 從 A城市出發(fā)回到 A城市一個 TSP問題的解是 ABCEDA， 即圖中紅色線條路徑 。 蟻群優(yōu)化算法 — 算法提出 一個著名的組合優(yōu)化問題： 旅行商問題
高考資料相關(guān)推薦
鄂ICP備17016276號-1