Upgrade to Pro — share decks privately, control downloads, hide ads and more …

VRPを深層強化学習で解く

 VRPを深層強化学習で解く

Transcript

  1. 1 動機 • VehicleRoutingProblem(VRP)の派⽣問題を解き実⽤化するに当たって強化学習が有効そう ◦ ノード数nが増えても⾼速に解きたい ▪ OR-Tools◦,強化学習◎ ◦ 制約を少し破ることになっても,解を出すことを優先したい(ロバスト性が欲しい)

    ▪ OR-Tools×,強化学習◎ ◦ ⼊ってくる注⽂の分布など統計的な要素にも対応可能したい(Dynamic VRPなど) ▪ OR-Tools×,強化学習◎ ◦ その他,特殊な問題設定が加わっても柔軟に対応できるようにしたい ▪ OR-Tools△,強化学習◦(追学習の必要あり) • 今回は,VRPの問題設定を拡張し,尚且つ,強化学習で⾼速に学習させる所を⽬標にする ※OR-Toolsにも,上手く枠組みに落とし込めれば,良い解を手軽に高速に求められるという利点はある
  2. 2 参考にした論⽂ • 強化学習でTSPとVRPを学習させ,OR-Toolsよりも良い性能を出すことに成功した論⽂ ◦ Solve routing problems with a

    residual edge-graph attention neural network [Kun Lei, Neurocomputing, Volume 508, 2022, Pages 79-98] ▪ https://www.sciencedirect.com/science/article/abs/pii/S092523122200978X ◦ github ▪ https://github.com/Lei-Kun/DRL-and-graph-neural-network-for-routing-problems • 具体的にOR-Toolsよりどれくらい改善したか(結果の⼀部を抜粋) ◦ TSP - ノード数50 ▪ OR-Tools opt gap = 1.83% ▪ 強化学習 opt gap = 0.98% (実⾏時間4.0秒)
  3. 3 学習の全体像 dataset GNN (Encoder) AttentionNetwork (Decoder) episodeのstep数くり返す step毎にcontextとmaskを更新 Softmax

    dataset 評価関数 Reinforce 特徴ベクトル 評価値 step数分, 各actionの確率を 出力 actions 各actionの確率 loss 誤差逆伝搬 keyword : GraphNeuralNetwork(GNN), Transformer, Reinforce
  4. 4 問題設定の表現 • いわゆるシミュレータ(状態遷移のdynamics)は存在しない ◦ 問題を固定のdatasetとしてstaticに表現している ◦ contextとmaskはdynamicに更新している(配列演算で⾼速に計算している) • datasetが持つ情報

    ◦ nodeの特徴量(⼈数,位置など) ◦ edgeの特徴量(ノード間の距離など) • contextが持つ情報 → 既に選択したnodeのindex(選択した順番も保持) • maskが持つ情報 → 次に選択可能なnodeのindex • 評価関数 → 移動距離に反⽐例する値 全て配列演算で表現すれば, GPU-CPU間の通信が不要
  5. 5 今回⾏ったアップデート • この論⽂のコードを出発点として以下のアップデートを加えてみた ◦ 問題設定 ▪ VRPに時間枠制約を加えた • datasetにnode同⼠が接続しているか否かの情報を追加

    • maskを計算するときにnode同⼠の接続の有無を考慮 ▪ ノードを全て回らなくても良いという設定を加えた(node選択) • あるnode(終端node)を選択したら,残りのstepをスキップする • 評価関数も⼈数に⽐例する値にした ◦ 訓練の⾼速化 ▪ 複数GPUでの並列学習
  6. 6 複数GPUの並列処理による学習の⾼速化 PytorchのDistributedDataParallel(DDP)を用いた → https://pytorch.org/tutorials/intermediate/ddp_tutorial.html GPU0 GPU3 GPU1 GPU2 model

    model model model all_reduce関数で lossを取集 重み更新 ※GPU0視点で描いたが,残りのGPUも同じことを行う 各episodeの初めに barrier関数を実行し て同期を取る modelの重み自体はGPU間でやり取りされず,各GPU内で更新される