蟻群算法PPT課件

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