楊寧_智能運籌創新應用_watermark.pdf

《楊寧_智能運籌創新應用_watermark.pdf》由會員分享，可在線閱讀，更多相關《楊寧_智能運籌創新應用_watermark.pdf（43頁珍藏版）》請在三個皮匠報告上搜索。

1、智能運籌創新應用中國科學院自動化研究所群體決策智能團隊楊寧郵箱：目錄智能運籌研究背景1智能運籌算法應用3智能優化算法研究2外賣配送智能交通排產系統供應鏈建筑設計智能運籌研究背景應用場景金融決策求解時間長無法在大規模問題使用速度比精確求解快，但求解精度低需要大量對具體問題的研究和試錯很難獲得最優的標簽可行性、自適應性、可泛化性智能運籌研究背景運籌優化問題求解方法智能運籌研究背景強化學習在運籌優化中的應用智能運籌研究背景代表性研究 Manchanda,et al.Learning Heuristics over Large Graphs via Deep Reinforcement Learnin

2、g,NeurIPS,2020.Stooke,et al.Responsive Safety in Reinforcement Learning by PID Lagrangian Methods,PMLR,2020.Tang Y,et al.Reinforcement Learning for Integer Programming:Learning to Cut,PMLR,2020 Li B,et al.Large language models for supply chain optimizationJ.arXiv,2023.目錄智能運籌研究背景1智能運籌算法應用3智能優化算法研究2智能

3、優化算法研究智能優化算法評測數學模型應用問題求解器AI方法線性整數規劃TSP,TSPTWConcorde,GurobiCNN-Transformer,Pointerformer,bab-dqn,Safe RL(PDO,PPOLag,CPO)VRP,VRPTW,CVRPORTools,SCIP,COPTNeuRewriter混合整數規劃庫存Gurobi,SCIPDNN-SMEIO割平面問題,set coveringhierarchical sequence model(HEM)Retro Branching，Hybrid-learn2branchProfit for Portfoliobab-d

4、qn0100002000030000eil51berlin52 kroA100求解距離ConcordeGurobitsp50_CNNtsp100_CNNPointerformer_50Pointerformer_10000.511.52eil51berlin52 kroA100求解時間GurobiBeamsearch_50Beamsearch_100Pointerformer_50Pointerformer_100橫坐標：數據集縱坐標：求解的最小距離橫坐標：數據集縱坐標：求解的時間智能優化算法研究TSP,CVRP問題05101520253035求解時間OR-toolsSCIPCOPT02000

5、40006000800010000120001400016000求解距離OR-ToolsSCIPCOPT橫坐標：數據集縱坐標：求解的最小距離橫坐標：數據集縱坐標：求解的時間CVRP問題TSP問題在TSP問題上，每種算法的求解性能相似，Gurobi的收斂速度遠遠大于其他算法。在CVRP問題上，OR-Tools的收斂性和收斂速度均優于其他算法，SCIP和COPT的均達到最大求解時間橫坐標：數據集縱坐標：求解的最小距離橫坐標：數據集縱坐標：求解的時間智能優化算法研究VRPTW,割平面問題橫坐標：數據集縱坐標：求解時間橫坐標：數據集縱坐標：求解時間割平面問題VRPTW問題020040060080010

6、0012001400C101C201R101R201R202求解時間OR-ToolsSCIPCOPT020040060080010001200140016001800C101C201R101R201R202求解距離OR-ToolsSCIPCOPT0100200300400MIPLIB2017輸入量1000*輸出量1000Retro BranchingHybrid-learn2branch傳統方法010203040MIPLIB2017輸入量500*輸出量1000Retro BranchingHybrid-learn2branch傳統方法在VRPTW問題上，OR-Tools的收斂性和收斂速度均優于

7、其他算法，對于R201數據集，SCIP和COPT求解器無解對于R202數據集，SCIP求解器無解在割平面問題上，Retro Branching收斂速度大于Hybrid-learn2branch大于傳統算法。智能優化算法研究大語言模型在運籌學中的應用 求解時間和求解質量 評估不同求解器或算法運籌優化的關注點 模型構建時的語音理解和推理能力 準確辨別問題并部署合適的Python庫 prompt設計（建模、求解、糾錯等）AI agent 設計 數學建模的Fine-tuning運籌優化大語言模型的關注點評估大模型解決運籌學問題能力的算法流程智能優化算法研究大語言模型在運籌學中的應用生成7種運籌學問題G

8、PT-4 and New Bing無約束優化問題（UOP）二次規劃問題（QPP）線性規劃問題（LPP）整數規劃問題（IPP）旅行商問題（TSP）背包問題（KP）車輛路徑問題（VRP）聚類優化問題編碼可視化智能優化算法研究大語言模型在運籌學中的應用GPT-3.5 和 GPT-4 準確度對比分析GPT-4 和 GPT-3.5 在數學建模中的表現GPT 在運籌學建模與求解中的應用GPT-4 和 GPT-3.5 在程序生成中的表現智能優化算法研究大語言模型在運籌學中的應用智能優化算法研究Multi-ORGPT 解決困難運籌學問題實例多智能體協作系統目錄智能運籌研究背景1智能運籌算法應用3智能優化算法研

9、究2智能運籌算法應用移動邊緣計算(MEC)系統云基礎設施邊緣服務器云臺微云智能交換機應用服務器智能路由器移動設備智能手機筆記本電腦傳感器網絡平板電腦智能載具智能健康檢測設備智能運籌算法應用移動邊緣計算系統AoI最小化在MEC系統中信息新鮮度最小化問題的挑戰：1.長時間內的最優卸載決策難以獲得2.MDP和DP算法受到維度詛咒的困擾3.信息新鮮度與兩個因素有關：任務產生時間、任務處理持續時長我們算法的貢獻：1.建模成多智能體Restless Multi-Arm Bandit問題，并構建了多層MDP2.證明多層MDP滿足Intra-indexability，并提出了nested index策略3.理

10、論和仿真均證明提出算法的漸近最優性系統模型特點：1.考慮多個用戶和多個邊緣服務器2.每個任務都可以卸載到任意服務器3.未完成的任務可以被丟棄或發送到另一個服務器繼續計算1 Chen S,Yang N,Zhang M,et al.Minimizing Age of Information for Mobile Edge Computing Systems:A Nested Index ApproachJ.IEEE WiOpt,2023.智能運籌算法應用多層MDP框架 將問題重新構造為Restless Multi-Arm Bandit問題，并建立了一個分層馬爾可夫決策過程（MDP）來描述MEC系統

11、的AoI的更新嵌套索引和多層閾值類型1 Chen S,Yang N,Zhang M,et al.Minimizing Age of Information for Mobile Edge Computing Systems:A Nested Index ApproachJ.IEEE WiOpt,2023.智能運籌算法應用Nested Index 策略1 Chen S,Yang N,Zhang M,et al.Minimizing Age of Information for Mobile Edge Computing Systems:A Nested Index ApproachJ.IEEE

12、WiOpt,2023.Intra-indexability特性保證了門限的唯一性Nested index衡量了不同層不同狀態，被改變的緊急程度智能運籌算法應用漸進最優性問題規模：1000個用戶，200個服務器1 Chen S,Yang N,Zhang M,et al.Minimizing Age of Information for Mobile Edge Computing Systems:A Nested Index ApproachJ.IEEE WiOpt,2023.理論和實驗上都驗證了nested index policy 不斷逼近松弛問題的最優解智能運籌算法應用多目標任務卸載任務卸載

13、在MEC系統中的難點：1.MEC網絡環境具有動態性和不確定性2.不同MEC網絡中用戶可能對延遲和能耗有不同的偏好我們的貢獻：1.設計了多目標強化學習（MORL）網絡架構2.設計一個狀態編碼方法來構建特征（狀態空間至少縮小10倍）3.設計了一個新型的獎勵函數，用于準確計算延遲和能耗的效用1 Yang N,Wen J,Zhang M,et al.Multi-objective Deep Reinforcement Learning for Mobile Edge ComputingJ.IEEE WiOpt,2023.智能運籌算法應用MORL問題描述找到帕累托前沿上的一點調整偏好以找到多個點偏好動作

14、 卸載決策狀態 任務、隊列和傳輸信息環境智能體目標1：延遲目標2：能量消耗最小化黃色區域，或最大化藍色區域尋找帕累托最優策略以最小化長期成本期望1 Yang N,Wen J,Zhang M,et al.Multi-objective Deep Reinforcement Learning for Mobile Edge ComputingJ.IEEE WiOpt,2023.智能運籌算法應用MORL算法框架多目標強化學習框架狀態信息：1.任務量2.數據速率3.CPU頻率4.執行任務數量5.邊緣服務器數量6.任務直方圖向量獎勵函數：1.能量消耗2.傳輸延遲1 Yang N,Wen J,Zhang

15、M,et al.Multi-objective Deep Reinforcement Learning for Mobile Edge ComputingJ.IEEE WiOpt,2023.智能運籌算法應用MORL算法表現訓練集：包含50個偏好，間隔為0.02測試集：包含100個偏好，間隔為0.01多邊緣服務器我們考慮一個系統平衡算力和任務要求1 Yang N,Wen J,Zhang M,et al.Multi-objective Deep Reinforcement Learning for Mobile Edge ComputingJ.arXiv preprint arXiv:2307.1

16、4346,2023.智能運籌算法應用MORL算法表現邊緣服務器數量E=8，任務容量L=20Mbits算法性能評價：MORL：80.7 LinUCB：69.9啟發式方法：63.9 隨機策略：24.2我們的MORL方案分別提高了帕累托前沿的超體積15.5%，26.3%和233.1%1 Yang N,Wen J,Zhang M,et al.Multi-objective Deep Reinforcement Learning for Mobile Edge ComputingJ.arXiv preprint arXiv:2307.14346,2023.快速建設階段高效運營階段生產計劃型市場導向型我國

17、高速鐵路正在經歷轉變對列車運行圖編制效率和編制質量提出了更高要求，亟需在編制理論和應用技術層面尋找突破口編圖頻次增多，四季度+春暑運“4+2”編制模式列車運行圖編制質量和經濟評價為滿足客流需求，提出“一日一圖”的模式能力充分利用，精細化程度提升體現信息化智能化需求智能運籌算法應用鐵路運行圖技術背景 影響因素復雜且調整頻繁 各作業環節相互交互、依次推進，列車運行圖一體化鋪畫困難 本線列車運行線與跨線列車運行線的協調優化難題手工編制與調整技術自身的困難 列車運行圖的編制與調整問題是一個超大規模的、多目標組合優化的“NP-難”問題，具有組合“爆炸”特性，既有模型方法/計算技術在基本原理框架上難以勝任

18、既有計算技術實現自動編制與調整的困難智能運籌算法應用鐵路運行圖技術背景 構建并運用數學優化模型算法和智能化算法去自動地、高效地對一張列車運行初始方案進行調整、以達到指標優化的目的基于列車運行初始方案的智能調整 優化目標：最小化運行圖沖突個數 沖突圖生成：大約60輛列車；5個站；大約50個沖突 基礎動作集:增加列車、取消列車、增加停站、取消停站、向左平移、向右平移設計基礎動作集設計沖突消解算子集設計強化學習算法停站時間超出范圍運行時間超出范圍間隔時間不足超車運行圖智能調整需消解的四類沖突智能運籌算法應用算法流程在沖突列車左右各 max 的時間范圍內逐站搜索前 個最大的間隔時間；從這些站中挑選約束

19、最強的站，這里用間隔時間的均值評估，均值越小約束越強（圖中站）；模擬將沖突列車 插入挑選的站的前 個最大的間隔時間內，并保證滿足最小約束時間；根據最終目標函數的大小決定沖突列車 最后的位置。參數包括沖突列車，搜索時間范圍 max，每站挑選備用的最大間隔時間數量。智能運籌算法應用復雜沖突消解算子集環境狀態集合S策略集合獎勵R把線路區段內運行的所有列車分布（也即一張可能的但不一定可行的運行圖圖面）定義為一個環境狀態定義動作：41個算子（即41個動作）策略集合需要通過對相關數據的采樣和訓練得到動作集合A獎勵R主要用來對策略集合進行訓練和估計 復雜沖突消解算子的單步減少的沖突數量除以復雜沖突消解算子一

20、次當中調用過基本動作的次數作為復雜沖突消解算子的單步回報；其他算子采用后減少的沖突數量；無效算子，加入懲罰。智能運籌算法應用強化學習算法設計將熵加入算法中，提高算法的探索力度，防止過早收斂；利用啟發式算法對模型進行監督學習作為前期參數訓練；采用模型預熱策略，對測試時遇到的新環境進行若干輪預訓練，進行模型參數的微調；多策略群體決策。將多個不同環境難度訓練得到的不同策略組合到一起，從最終結果中選取最好的一個作為此時的測試環境的調圖方案。PPOPPO算法改進策略智能運籌算法應用算法改進陷入局部最優解的概率成功消解所有沖突的概率在500次擾動的情況下RL可完全消解所有沖突的概率為74%智能運籌算法應用

21、算法表現60輛列車左右；5個站；4類沖突；訓練時間一兩天；測試時間5分鐘以內；5分鐘消解完所有沖突沖突圖生成的方式是按照一定的比例選擇基礎動作集，進行部分線的調整來制造一部分沖突智能運籌算法應用優化結果可視化智能運籌算法應用優化結果可視化油田集合采購節點集合銷售節點1銷售節點2銷售節點3加工混油汽油1 1汽油2 2汽油3 3柴油2 2柴油1 1加工方案存儲上限存儲下限安全上限安全下限原油中轉集合煉廠集合成品油中轉集合省庫集合運輸量加工量智能運籌算法應用原油業務鏈模型大規模230多個節點2100多條道路復雜性節點間相互影響節點類型多不確定性供應量需求量加工量多目標庫存量運輸成本多約束流量平衡約束

22、(節點)汽柴油存儲約束發運量約束時空性路徑跨天運行智能運籌算法應用問題難點核心思想通過建立運籌算子層，進行中層決策，較少上層強化學習的優化難度，運籌算子經過了專家策略設計，易于得到局部最優解，通過序列決策選擇算子，能夠組合出更好的解決方案。優缺點1、進一步減少了求解空間。2、能夠快速得到較好的解決方案。3、運籌算子組需要手動設計，設計的好壞對性能影響大。原因通過強化學習-數學規劃雙層框架能有效降低學習維度，從更高的角度決策，指導算法得到方案，但是雙層框架仍需要決策較多連續變量，強化學習仍需要面對較大的動作空間。通過強化學習-運籌算子-數學規劃三層框架，能夠把連續動作空間轉化為離散動作空間，進一

23、步將問題簡化。智能運籌算法應用分層框架二提高庫存到安全線、減低庫存到安全線、維持庫存滿足5天需求、提高庫存到安全線保持儲量在安全庫存線內自下而上的順序優化：首先優化成品油庫存，以滿足需求。成品油庫存決定了加工量，牽動著煉廠的原油庫存，因此第二項考慮原油優化，以維持運營。煉廠的原油量關系到供應或轉運節點的運輸調配，由此第三優化項為轉運節點的庫存（目前供應節點不考慮庫存）。最后考慮運費優化，以得到在預警最小的前提下降低運費的方案煉廠成品油庫存煉廠原油庫存轉運節點庫存運費1、優先級 算子編號 對煉廠成品油的目標對煉廠原油庫存的目標對轉運節點的目標優化方法是否考慮運費1提高庫存到安全線滿足5天需求保持

24、在安全庫存內分段線性優化是2降低庫存到安全線滿足5天需求保持在安全庫存內分段線性優化是3維持庫存滿足5天需求保持在安全庫存內分段線性優化是4提高庫存到安全線提高庫存到安全線保持在安全庫存內分段線性優化是5降低庫存到安全線提高庫存到安全線保持在安全庫存內分段線性優化是6維持庫存提高庫存到安全線保持在安全庫存內分段線性優化是7提高庫存到安全線滿足5天需求保持在安全庫存內多目標序列優化是8降低庫存到安全線滿足5天需求保持在安全庫存內多目標序列優化是9維持庫存滿足5天需求保持在安全庫存內多目標序列優化是10提高庫存到安全線提高庫存到安全線保持在安全庫存內多目標序列優化是11降低庫存到安全線提高庫存到安

25、全線保持在安全庫存內多目標序列優化是12維持庫存提高庫存到安全線保持在安全庫存內多目標序列優化是智能運籌算法應用分層框架二庫存量距離目標庫存越近，懲罰值越小。庫存超出上下限時，懲罰值的增長率會提升。系數法：在使用分段線性優化方法的算子中，優先級越高的項目擁有越高的權重（相鄰優先級的權重差距為1001000倍），所有優化項的加權求和為總優化目標值。序列法：Gurobi求解器中內置了多目標序列優化方法，該方法優先優化高優先級的目標，然后在最優解集中選擇下一優先級目標的最優解。2、庫存與懲罰值關系圖：3、優先級實現方法：智能運籌算法應用分層框架二051015202530123456789101112131415161718192021222324252627282930預警數天東北區域預警數量分層框架一-PPO分層框架一-SAC分層框架三-PPO分層框架三-SAC方法分層框架一-PPO分層框架一-SAC分層框架三-PPO分層框架三-SACSAC求解質量(預警數)641571180 0求解時間(s)6.766.0675.0369.6869.68全產業鏈東北區域下游分牌號的業務場景下，采用分層框架三和PPO算法得到的求解質量最好，可將預警數降為0.0.因次在全國范圍采用分層框架三。智能運籌算法應用全產業鏈下游算法結果-東北區域智能運籌算法應用原油供應鏈智能決策算法謝謝！