蟻群算法PPT課件

20 04 2020 1 來源于生物界的蟻群算法在車輛路徑問題 VRP 中的應用 學號 姓名 指導教師 20 04 2020 2 1 VRP的問題來源和研究現(xiàn)狀 論文要點 2 蟻群算法及其在VRP中的具體應用 3 VRP程序設計和求解分析 來源于生物界的蟻群算法在車輛路徑問題 VRP 中的應用 20 04 2020 3 1 VRP的問題來源和研究現(xiàn)狀 物流 Logistics 20 04 2020 4 通常意義下的VRP的提法為 已知一批客戶 每個客戶點的位置和貨物需求已知 車輛的負載能力一定 每輛車都從起點 depot 出發(fā) 完成若干客戶點的運送任務后再回到起點 假設每個客戶被而且只被訪問一次 每輛車所訪問的城市的需求總和不能超過車輛的負載能力 問題是使所有客戶需求都得到滿足 且總旅行成本最小 1 VRP的問題來源和研究現(xiàn)狀 車輛路徑問題 VehicleRoutingProblem 簡記VRP 是物流配送優(yōu)化中關鍵的一環(huán) 20 04 2020 5 VRP已經(jīng)被證明是NP hard問題目前提出的求解算法很多 20 04 2020 6 1 VRP的問題來源和研究現(xiàn)狀 求解方法 Solution 20 04 2020 7 2 蟻群算法及其在VRP中的具體應用 蟻群算法與VRP 20 04 2020 8 2 蟻群算法及其在VRP中的具體應用 螞蟻選擇最短路徑的原理 信息素 信息素濃度越高螞蟻越容易選擇 經(jīng)過時間越長信息素揮發(fā)越多螞蟻選擇較短路徑 20 04 2020 9 2 蟻群算法及其在VRP中的具體應用 代表路徑上的信息素濃度對選擇概率的影響 信息素濃度越高 選擇該路徑的機率就越大 故實際上就是蟻群的正反饋機制 吃午飯了 去一食堂還是二食堂呢 大家都去一食堂吃飯 我也去一食堂吧 代表路徑上的啟發(fā)因子 為路徑間的距離 即距離越小選擇該路徑的機率就越大 故啟發(fā)因子實際代表螞蟻的能見度 要吃午飯了 去一食堂還是二食堂呢 二食堂比較近 去二食堂吧 為隨機因子 即在選擇路徑時給與螞蟻適當擾動 要吃午飯了 今天到底是去一食堂還是二食堂呢 隨便選一個吧 20 04 2020 10 2 蟻群算法及其在VRP中的具體應用 對于蟻群算法中的等相關參數(shù) 的選擇 目前還沒有成熟的理論可供參考 一般只能通過實驗進行選擇 信息素揮發(fā) 本文中 信息素更新策略采用最大 最小螞蟻系統(tǒng)MMAS算法 因為經(jīng)大量學者實驗驗證 這種更新機制有較好的效果 20 04 2020 11 3 VRP程序設計和求解分析 本文求解VRP主要采取蟻群優(yōu)化2階段構造算法 AntConstructiveAlgorithm 即 第1階段 根據(jù)蟻群優(yōu)化準則 每次將一個不在線路上的點增加進線路 直到所有的點都被安排進線路為止 第2階段 將得到的可行解進行2 OPT變換優(yōu)化 20 04 2020 12 3 VRP程序設計和求解分析 第1階段 根據(jù)蟻群優(yōu)化準則 每次將一個不在線路上的點增加進線路 直到所有的點都被安排進線路為止 20 04 2020 13 3 VRP程序設計和求解分析 從當前點出發(fā) 根據(jù)選擇概率選擇下一個點 20 04 2020 14 3 VRP程序設計和求解分析 第2階段 將得到的可行解進行2 OPT變換優(yōu)化 2 opt原理 20 04 2020 15 3 VRP程序設計和求解分析 以上為程序設計原理 具體程序流程如下 BEGINDO FOR i 0 i 最大螞蟻組數(shù) i FOR j 0 reach 1 reach 最大節(jié)點數(shù) j j為螞蟻數(shù) 初始化一只螞蟻 即將一只螞蟻放到起點 WHILE 螞蟻沒有達到最大載重量且仍然有節(jié)點未經(jīng)訪問 螞蟻按照選擇概率公式 1 選擇下一節(jié)點 reach reach代表已經(jīng)訪問的節(jié)點數(shù) reach ant n i j 將這組螞蟻的螞蟻數(shù)記錄下來nextant 轉到下一組螞蟻 FOR i 0 i 最大螞蟻組數(shù) i FOR j 0 j 本組螞蟻數(shù) j 對每一只螞蟻進行2 opt交換 比較得到的解選擇本次循環(huán)得到的最好螞蟻 將其與全局最好解進行比較 按照全局最優(yōu)解根據(jù)公式 2 更新信息素nc WHILE nc NC 迭代結束 輸出最優(yōu)解 20 04 2020 16 3 VRP程序設計和求解分析 程序流程圖 20 04 2020 17 3 VRP程序設計和求解分析 為了檢驗算法的結果 求解實例全部采用osiris tuwien ac at網(wǎng)絡公布的CVRP測試問題 下載網(wǎng)址為 http osiris tuwien ac at wgarn VehicleRouting neo Problem 20Instances CVRPinstances html 各實例驗證結果如下 20 04 2020 18 3 VRP程序設計和求解分析 實例 A n33 k5 實驗時 取迭代次數(shù)為20次 選擇概率權重為信息素揮發(fā) 20 04 2020 19 3 VRP程序設計和求解分析 將表格數(shù)據(jù)畫圖得 20 04 2020 20 3 VRP程序設計和求解分析 得到的A n33 k5具體運輸路線 20 04 2020 21 謝謝觀賞 結束 20 04 2020 22 20 04 2020 23 分支定界法 BranchandBoundApproach 6 分支定界法是一種應用范圍很廣的搜索算法 它的基本思想是把給定問題分解為若干個較小的子問題 每個子問題又可繼續(xù)分解 直到子問題不能再分解或不能產(chǎn)生最優(yōu)解 根據(jù)問題的特點和不同的策略 把問題分解為子問題的過程稱之為分支 分支定界法求解VRP問題的基本思想是 以相應的不含整數(shù)約束的VRP問題 B 的最優(yōu)解為出發(fā)點 若此解是整數(shù)解 那么這個解就是原VRP問題 A 的最優(yōu)解 否則以B的非整數(shù)解的相鄰整數(shù)作附加條件 形成2個分支 即2個子問題 進行求解 若對上面2個子問題求出最優(yōu)解是整數(shù)解 則停止該子問題的分支 否則繼續(xù)分支求解 這種方法只能適用于求解小型VRP問題 Kolenatal曾利用此方法求解含時間窗約束的車輛巡回問題 發(fā)現(xiàn)當節(jié)點數(shù)擴大至12時 計算機有內存不足的現(xiàn)象產(chǎn)生 20 04 2020 24 割平面法 CuttingPlanesApproach 6 割平面法求解VRP問題 A 的基本思想是 在求解相應的不含整數(shù)約束的VRP問題 B 上 增加線性約束條件 幾何術語稱為割平面 以將B的可行域切割掉一部分 使其切割掉的部分只包含非整數(shù)解 沒有切割掉任何整數(shù)可行解 直到切割后得到的可行域有一個整數(shù)坐標的極點恰好是A的最優(yōu)解為止 由于割平面法求解時間過長 故不適用于大規(guī)模問題 20 04 2020 25 網(wǎng)絡流算法 NetworkFlowApproach 6 網(wǎng)絡流算法求解VRP問題的基本思想是 首先構建VRP問題的網(wǎng)絡模型 找到網(wǎng)絡中需調量最大的弧 然后通過調節(jié)弧流量或弧兩端節(jié)點上的位勢 來減少弧上的需調量 直至所有弧的需調量都等于零 由于網(wǎng)絡模型的頂點數(shù)目和邊的數(shù)目會顯著影響網(wǎng)絡流算法時間效率 所以這種算法只適用于小規(guī)模的VRP問題 20 04 2020 26 動態(tài)規(guī)劃方法 DynamicProgrammingApproach 6 動態(tài)規(guī)劃法求解VRP問題的基本思路是 將VRP問題視為一個階段的決策問題 進而將其轉化為依次求解具有遞推關系的單階段的決策問題 從而簡化計算過程 用這種方法可求得VRP的最優(yōu)解 但僅適用于較小規(guī)模的尋優(yōu)問題 此外 Fisher 1985 Jomstern 1986 Madsen 1990 Halse 1992 等人分別用