論文の概要: Reinforcement Learning to Solve NP-hard Problems: an Application to the CVRP

• arxiv url: http://arxiv.org/abs/2201.05393v1
• Date: Fri, 14 Jan 2022 11:16:17 GMT
• ステータス: 処理完了
• システム内更新日: 2022-01-17 13:57:37.318154
• Title: Reinforcement Learning to Solve NP-hard Problems: an Application to the CVRP
• Title（参考訳）: NPハード問題を解決する強化学習--CVRPへの応用
• Authors: Leo Ardon
• Abstract要約: 古典的最適化問題の解法として強化学習(Reinforcement Learning, RL)を応用した。 最も有望なRLアプローチの2つを、ベンチマークインスタンスのセットで従来の問題解決手法と比較する。 最良解を返さないにもかかわらず、RLアプローチは従来の解法よりも多くの利点があることがわかった。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we evaluate the use of Reinforcement Learning (RL) to solve a classic combinatorial optimization problem: the Capacitated Vehicle Routing Problem (CVRP). We formalize this problem in the RL framework and compare two of the most promising RL approaches with traditional solving techniques on a set of benchmark instances. We measure the different approaches with the quality of the solution returned and the time required to return it. We found that despite not returning the best solution, the RL approach has many advantages over traditional solvers. First, the versatility of the framework allows the resolution of more complex combinatorial problems. Moreover, instead of trying to solve a specific instance of the problem, the RL algorithm learns the skills required to solve the problem. The trained policy can then quasi instantly provide a solution to an unseen problem without having to solve it from scratch. Finally, the use of trained models makes the RL solver by far the fastest, and therefore make this approach more suited for commercial use where the user experience is paramount. Techniques like Knowledge Transfer can also be used to improve the training efficiency of the algorithm and help solve bigger and more complex problems.
• Abstract（参考訳）: 本稿では,従来の組合せ最適化問題であるcvrp(capacitated vehicle routing problem)を解くための強化学習(rl)の利用について評価する。 我々は、この問題をRLフレームワークで形式化し、最も有望な2つのRLアプローチと、ベンチマークインスタンスのセットにおける従来の解法技術を比較した。 返却されたソリューションの品質と返却に必要な時間で、さまざまなアプローチを測定します。 最良解を返さないにもかかわらず、RLアプローチは従来の解法よりも多くの利点があることがわかった。 まず、フレームワークの汎用性により、より複雑な組合せ問題の解決が可能になる。 さらに、rlアルゴリズムは、問題の特定のインスタンスを解決しようとするのではなく、問題解決に必要なスキルを学習する。 訓練されたポリシーは、スクラッチから解決する必要なしに、すぐに目に見えない問題の解決策を提供することができる。 最後に、トレーニングされたモデルを使用することで、RLソルバははるかに高速になり、ユーザエクスペリエンスが最重要となる商用用途にこのアプローチが適している。 知識伝達のような技術は、アルゴリズムのトレーニング効率を改善し、より大きく複雑な問題を解決するのに役立つ。

関連論文リスト

• Multiobjective Vehicle Routing Optimization with Time Windows: A Hybrid Approach Using Deep Reinforcement Learning and NSGA-II [52.083337333478674]
  本稿では、時間窓を用いた多目的車両ルーティング問題(MOVRPTW)に対処するために、ウェイト・アウェア・ディープ・強化学習(WADRL)手法を提案する。 WADRLの結果を最適化するために非支配的ソート遺伝的アルゴリズム-II (NSGA-II) 法を用いる。
  論文  参考訳（メタデータ） (2024-07-18T02:46:06Z)
• Transform then Explore: a Simple and Effective Technique for Exploratory Combinatorial Optimization with Reinforcement Learning [11.531786269804707]
  グラフ上の最適化問題(COP)を解決するためのゲージ変換(GT)手法を提案する。 GTは非常にシンプルで、10行未満のPythonコードで実装でき、ほとんどの強化学習モデルに適用できる。 GTを用いた従来のRLモデルでは,MaxCut問題に対して最先端の性能が得られた。
  論文  参考訳（メタデータ） (2024-04-06T15:31:17Z)
• MARLIN: Soft Actor-Critic based Reinforcement Learning for Congestion Control in Real Networks [63.24965775030673]
  そこで本研究では,汎用的な渋滞制御(CC)アルゴリズムを設計するための新しい強化学習(RL)手法を提案する。 我々の解であるMARLINは、Soft Actor-Criticアルゴリズムを用いてエントロピーとリターンの両方を最大化する。 我々は,MARLINを実ネットワーク上で訓練し,実ミスマッチを克服した。
  論文  参考訳（メタデータ） (2023-02-02T18:27:20Z)
• Solving the vehicle routing problem with deep reinforcement learning [0.0]
  本稿では,NP-Hard 問題のクラスに属する有名な問題である Vehicle Routing Problem (VRP) に対する RL の適用について述べる。 第2フェーズでは、アクターと批評家の背後にあるニューラルアーキテクチャが確立され、畳み込みニューラルネットワークに基づいたニューラルアーキテクチャを採用することが選択された。 広範囲なインスタンスで行った実験では、アルゴリズムが優れた一般化能力を持ち、短時間で良い解に達することが示されている。
  論文  参考訳（メタデータ） (2022-07-30T12:34:26Z)
• Meta Reinforcement Learning with Successor Feature Based Context [51.35452583759734]
  本稿では,既存のメタRLアルゴリズムと競合する性能を実現するメタRL手法を提案する。 本手法は,複数のタスクに対して同時に高品質なポリシーを学習するだけでなく,短時間のトレーニングで新しいタスクに迅速に適応できる。
  論文  参考訳（メタデータ） (2022-07-29T14:52:47Z)
• Solving the Traveling Salesperson Problem with Precedence Constraints by Deep Reinforcement Learning [59.14935871979047]
  本研究は, 深層強化学習(DRL)を用いた優先制約付きトラベリングセールスパーソン問題(TSPPC)の解を提案する。 これらのアプローチに共通しているのは、マルチヘッドアテンション層に基づくグラフモデルの利用である。
  論文  参考訳（メタデータ） (2022-07-04T14:31:47Z)
• Solving the capacitated vehicle routing problem with timing windows using rollouts and MAX-SAT [4.873362301533824]
  車両ルーティングはNPハード最適化問題のよく知られたクラスである。 最近の強化学習の取り組みは有望な代替手段である。 本稿では,強化学習,政策展開,満足度を組み合わせたハイブリッドアプローチを提案する。
  論文  参考訳（メタデータ） (2022-06-14T06:27:09Z)
• Sample-Efficient, Exploration-Based Policy Optimisation for Routing Problems [2.6782615615913348]
  本稿では,エントロピーに基づく新しい強化学習手法を提案する。 さらに、我々は、期待したリターンを最大化する、政治以外の強化学習手法を設計する。 我々のモデルは様々な経路問題に一般化可能であることを示す。
  論文  参考訳（メタデータ） (2022-05-31T09:51:48Z)
• Combining Pessimism with Optimism for Robust and Efficient Model-Based Deep Reinforcement Learning [56.17667147101263]
  実世界のタスクでは、強化学習エージェントはトレーニング中に存在しない状況に遭遇する。 信頼性を確保するため、RLエージェントは最悪の状況に対して堅牢性を示す必要がある。 本稿では,Robust Hallucinated Upper-Confidence RL (RH-UCRL)アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-03-18T16:50:17Z)
• SUNRISE: A Simple Unified Framework for Ensemble Learning in Deep Reinforcement Learning [102.78958681141577]
  SUNRISEは単純な統一アンサンブル法であり、様々な非政治的な深層強化学習アルゴリズムと互換性がある。 SUNRISEは, (a) アンサンブルに基づく重み付きベルマンバックアップと, (b) 最上位の自信境界を用いて行動を選択する推論手法を統合し, 効率的な探索を行う。
  論文  参考訳（メタデータ） (2020-07-09T17:08:44Z)
• Reinforcement Learning for Combinatorial Optimization: A Survey [12.323976053967066]
  最適化問題を解決する多くの伝統的なアルゴリズムは、解決を逐次構築する手工芸品を使用する。 強化学習(Reinforcement Learning, RL)は、エージェントを監督的または自己監督的な方法で訓練することにより、これらの検索を自動化する優れた代替手段を提案する。
  論文  参考訳（メタデータ） (2020-03-07T16:19:45Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。