解決最優路徑問題的妙招-蟻群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）

    其他
        面向關係的網路路由

        無連接網路路由

        資料探勘

        專案排程中的貼現現金流

        分散式資訊檢索

        網格工作流排程問題

        圖像處理

        系統辨識

        蛋白質摺疊

        電子電路設計