解決最優路徑問題的妙招-蟻群ACO算法

解決最優路徑問題的妙招-蟻群ACO算法

解決最優路徑問題的妙招-蟻群ACO算法 [教學影片]


資料來源: https://www.youtube.com/watch?v=IP4Fe_flXeU&list=PLMR7Ew8pMhddjFOdY9-9m9gy2YEmz1kq5&index=4

https://zh.wikipedia.org/wiki/%E8%9A%81%E7%BE%A4%E7%AE%97%E6%B3%95


相關問題敘述

    TSP商務路徑演算法:每個節點只能走一次,找出最短路徑,其組合種類(N-1)!/2


    蟻群演算法(Ant Colony Optimization,ACO),又稱螞蟻演算法,是一種用來在圖中尋找最佳化路徑的機率型演算法。它由Marco Dorigo於1992年在他的博士論文「Ant system: optimization by a colony of cooperating agents」中提出,其靈感來源於螞蟻在尋找食物過程中發現路徑的行為。蟻群演算法是一種類比進化演算法,初步的研究表明該演算法具有許多優良的性質。針對PID控制器參數最佳化設計問題,將蟻群演算法設計的結果與遺傳演算法設計的結果進行了比較,數值仿真結果表明,蟻群演算法具有一種新的類比進化最佳化方法的有效性和應用價值。


應用

    蟻群最佳化演算法已應用於許多組合最佳化問題,包括蛋白質摺疊或路由車輛的二次分配問題,很多衍生的方法已經應用於實變數動力學問題,隨機問題,多目標並列的實現。它也被用旅行推銷員問題的擬最佳解。在圖表動態變化的情況下解決相似問題時,他們相比類比退火演算法和遺傳演算法方法有優勢;蟻群演算法可以連續執行並適應即時變化。這在網路路由和城市交通系統中是有利的。

    第一蟻群最佳化演算法被稱為「螞蟻系統」,它旨在解決推銷員問題,其目標是要找到一系列城市的最短遍歷路線。總體演算法相對簡單,它基於一組螞蟻,每隻完成一次城市間的遍歷。在每個階段,螞蟻根據一些規則選擇從一個城市移動到另一個:它必須存取每個城市一次;一個越遠的城市被選中的機會越少(能見度更低);在兩個城市邊際的一邊形成的資訊素越濃烈,這邊被選擇的概率越大;如果路程短的話,已經完成旅程的螞蟻會在所有走過的路徑上沉積更多資訊素,每次迭代後,資訊素軌跡揮發。

    排程問題
        車間作業排程問題(JSP)

        開放式車間排程問題(OSP)

        排列流水車間問題(PFSP)

        單機總延遲時間問題(SMTTP)

        單機總加權延遲問題(SMTWTP)

        資源受限專案排程問題(RCPSP)

    車間組排程問題(GSP)

        附帶依賴安裝時間順序的單機總延遲問題(SMTTPDST)

        附帶順序相依設定/轉換時間的多階段流水車間排程問題(MFSP)

    車輛路徑問題
        限量車輛路徑問題(CVRP)

        多站車輛路徑問題(MDVRP)

        周期車輛路徑問題(PVRP)

        分批配送車輛路徑問題(SDVRP)

        隨機車輛路徑問題(SVRP)

        裝貨配送的車輛路徑問題(VRPPD)

        帶有時間窗的車輛路徑問題(VRPTW)

        依賴時間的時間窗車輛路徑問題(TDVRPTW)

        帶時間窗和複合服務員工的車輛路徑問題(VRPTWMS)

    分配問題
        二次分配問題(QAP)

        廣義分配問題(GAP)

        頻率分配問題(FAP)

        冗餘分配問題(RAP)

    設定問題
        覆蓋設定問題(SCP)

        分割區設定問題(SPP)

        約束重量的樹圖劃分問題(WCGTPP)

        加權弧L-基數樹問題(AWlCTP)

        多背包問題(MKP)

        最大獨立集問題(MIS)

    其他
        面向關係的網路路由

        無連接網路路由

        資料探勘

        專案排程中的貼現現金流

        分散式資訊檢索

        網格工作流排程問題

        圖像處理

        系統辨識

        蛋白質摺疊

        電子電路設計

發表迴響

你的電子郵件位址並不會被公開。 必要欄位標記為 *