論文の概要: POMO: Policy Optimization with Multiple Optima for Reinforcement
Learning
- arxiv url: http://arxiv.org/abs/2010.16011v3
- Date: Tue, 13 Jul 2021 05:20:17 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-01 17:01:57.284694
- Title: POMO: Policy Optimization with Multiple Optima for Reinforcement
Learning
- Title(参考訳): pomo: 強化学習のためのマルチオプティマによるポリシー最適化
- Authors: Yeong-Dae Kwon, Jinho Choo, Byoungjip Kim, Iljoo Yoon, Youngjune Gwon,
Seungjai Min
- Abstract要約: 本稿では,マルチプルオプティマス(POMO)を用いたポリシー最適化について紹介する。
POMOは、幅広いCO問題に適用可能であり、CO溶液の表現における対称性を利用するように設計されている。
我々は,旅行セールスマン(TSP),キャパシタンドカールーティング(CVRP),0-1knapsack(KP)の3つの一般的なNPハード問題を解くことで,POMOの有効性を実証した。
- 参考スコア(独自算出の注目度): 8.819672165548477
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In neural combinatorial optimization (CO), reinforcement learning (RL) can
turn a deep neural net into a fast, powerful heuristic solver of NP-hard
problems. This approach has a great potential in practical applications because
it allows near-optimal solutions to be found without expert guides armed with
substantial domain knowledge. We introduce Policy Optimization with Multiple
Optima (POMO), an end-to-end approach for building such a heuristic solver.
POMO is applicable to a wide range of CO problems. It is designed to exploit
the symmetries in the representation of a CO solution. POMO uses a modified
REINFORCE algorithm that forces diverse rollouts towards all optimal solutions.
Empirically, the low-variance baseline of POMO makes RL training fast and
stable, and it is more resistant to local minima compared to previous
approaches. We also introduce a new augmentation-based inference method, which
accompanies POMO nicely. We demonstrate the effectiveness of POMO by solving
three popular NP-hard problems, namely, traveling salesman (TSP), capacitated
vehicle routing (CVRP), and 0-1 knapsack (KP). For all three, our solver based
on POMO shows a significant improvement in performance over all recent learned
heuristics. In particular, we achieve the optimality gap of 0.14% with TSP100
while reducing inference time by more than an order of magnitude.
- Abstract(参考訳): neural combinatorial optimization(co)では、強化学習(rl)はディープニューラルネットワークをnp-hard問題の高速で強力なヒューリスティックな解法に変換する。
このアプローチは、相当量のドメイン知識を持つ専門家ガイドなしで、最適に近いソリューションを見つけることができるため、実用的なアプリケーションにおいて大きな可能性を持っている。
このようなヒューリスティックな解法を構築するためのエンドツーエンドアプローチである多重最適化(POMO)を導入する。
POMOは幅広いCO問題に適用できる。
CO溶液の表現における対称性を利用するように設計されている。
POMOは、修正されたREINFORCEアルゴリズムを使用して、様々なロールアウトを全ての最適なソリューションに強制する。
実証的に、POMOの低分散ベースラインはRLトレーニングを高速かつ安定にし、従来のアプローチに比べて局所最小値に耐性がある。
また,POMOをうまく対応させる拡張型推論手法も導入した。
我々は,旅行セールスマン(TSP),キャパシタンドカールーティング(CVRP),0-1knapsack(KP)の3つの一般的なNPハード問題を解くことで,POMOの有効性を実証した。
これら3つの問題に対して、POMOに基づく解法は、最近の学習ヒューリスティックスよりも性能が大幅に向上したことを示している。
特に,tsp100で0.14%の最適性差を達成し,推定時間を1桁以上削減した。
関連論文リスト
- An Efficient Learning-based Solver Comparable to Metaheuristics for the
Capacitated Arc Routing Problem [67.92544792239086]
我々は,高度メタヒューリスティックスとのギャップを著しく狭めるため,NNベースの解法を導入する。
まず,方向対応型注意モデル(DaAM)を提案する。
第2に、教師付き事前学習を伴い、堅牢な初期方針を確立するための教師付き強化学習スキームを設計する。
論文 参考訳(メタデータ) (2024-03-11T02:17:42Z) - Moco: A Learnable Meta Optimizer for Combinatorial Optimization [5.359176539960004]
Mocoは、現在の検索状態から抽出された特徴に基づいて、ソリューション構築手順を更新するグラフニューラルネットワークを学習する。
このメタトレーニング手順は、検索予算などの情報を得た探索手順中に見つかった全体的なベストソリューションをターゲットにしている。
Mocoは完全に学習可能なメタで、特定のローカル検索や分解の問題を一切利用しない。
論文 参考訳(メタデータ) (2024-02-07T14:41:17Z) - Faster Stochastic Variance Reduction Methods for Compositional MiniMax
Optimization [50.10952609321302]
合成ミニマックス最適化は、さまざまな機械学習領域において重要な課題である。
構成最小最適化の現在の方法は、最適以下の複雑さや、大きなバッチサイズに大きく依存することによって悩まされている。
本稿では,Nested STOchastic Recursive Momentum (NSTORM)と呼ばれる新しい手法を提案する。
論文 参考訳(メタデータ) (2023-08-18T14:57:21Z) - DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization [51.517956081644186]
グラフベースの拡散フレームワークであるDIFUSCOを導入する。
本フレームワークは, NPC問題を離散0, 1ベクトル最適化問題とみなす。
MIS問題に対して、DIFUSCOは、挑戦的なSATLIBベンチマークにおいて、以前の最先端のニューラルソルバよりも優れている。
論文 参考訳(メタデータ) (2023-02-16T11:13:36Z) - Learning Adaptive Evolutionary Computation for Solving Multi-Objective
Optimization Problems [3.3266268089678257]
本稿では, 深層強化学習(DRL)を用いた適応パラメータ制御とMOEAを統合したフレームワークを提案する。
DRLポリシは、最適化中のソリューションに対する突然変異の強度と確率を決定する値を適応的に設定するように訓練されている。
学習されたポリシーは転送可能であることを示す。つまり、単純なベンチマーク問題で訓練されたポリシーは、複雑な倉庫最適化問題を解決するために直接適用可能である。
論文 参考訳(メタデータ) (2022-11-01T22:08:34Z) - Online Control of Adaptive Large Neighborhood Search using Deep
Reinforcement Learning [7.4746628878102195]
本稿では,バニラを選択し,パラメータを調整し,探索過程における受入基準を制御する,深層強化学習(DRL)アプローチを提案する。
IJCAIコンペティションで用いられる重みと時間窓を用いた時間依存オリエンテーリング問題において,提案手法の評価を行った。
論文 参考訳(メタデータ) (2022-11-01T21:33:46Z) - Learning to Optimize Permutation Flow Shop Scheduling via Graph-based
Imitation Learning [70.65666982566655]
置換フローショップスケジューリング(PFSS)は製造業で広く使われている。
我々は,より安定かつ正確に収束を加速する専門家主導の模倣学習を通じてモデルを訓練することを提案する。
我々のモデルのネットワークパラメータはわずか37%に減少し、エキスパートソリューションに対する我々のモデルの解のギャップは平均6.8%から1.3%に減少する。
論文 参考訳(メタデータ) (2022-10-31T09:46:26Z) - Multi-Agent Deep Reinforcement Learning in Vehicular OCC [14.685237010856953]
我々は車載OCCにおけるスペクトル効率最適化手法を提案する。
我々は最適化問題をマルコフ決定プロセス(MDP)としてモデル化し、オンラインで適用可能なソリューションの利用を可能にする。
提案手法の性能を広範囲なシミュレーションにより検証し,提案手法の様々な変種とランダムな手法との比較を行った。
論文 参考訳(メタデータ) (2022-05-05T14:25:54Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳(メタデータ) (2020-09-28T15:22:24Z) - A Hybrid Framework Using a QUBO Solver For Permutation-Based
Combinatorial Optimization [5.460573052311485]
本稿では,高性能な2次非制約バイナリ最適化器を用いて,大規模な置換に基づく問題を解くためのハイブリッドフレームワークを提案する。
通常はビット数に制限があるQUBOソルバを使用する際の課題を克服する手法を提案する。
論文 参考訳(メタデータ) (2020-09-27T07:15:25Z) - Self-Directed Online Machine Learning for Topology Optimization [58.920693413667216]
自己指向型オンライン学習最適化は、ディープニューラルネットワーク(DNN)と有限要素法(FEM)計算を統合している。
本アルゴリズムは, コンプライアンスの最小化, 流体構造最適化, 伝熱促進, トラス最適化の4種類の問題によって検証された。
その結果, 直接使用法と比較して計算時間を2~5桁削減し, 実験で検証した全ての最先端アルゴリズムより優れていた。
論文 参考訳(メタデータ) (2020-02-04T20:00:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。