論文の概要: Sample-Efficient, Exploration-Based Policy Optimisation for Routing
Problems
- arxiv url: http://arxiv.org/abs/2205.15656v1
- Date: Tue, 31 May 2022 09:51:48 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-01 14:52:16.228232
- Title: Sample-Efficient, Exploration-Based Policy Optimisation for Routing
Problems
- Title（参考訳）: ルーティング問題に対するサンプル効率・探索型政策最適化
- Authors: Nasrin Sultana, Jeffrey Chan, Tabinda Sarwar, A. K. Qin
- Abstract要約: 本稿では,エントロピーに基づく新しい強化学習手法を提案する。
さらに、我々は、期待したリターンを最大化する、政治以外の強化学習手法を設計する。
我々のモデルは様々な経路問題に一般化可能であることを示す。
- 参考スコア（独自算出の注目度）: 2.6782615615913348
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Model-free deep-reinforcement-based learning algorithms have been applied to
a range of
COPs~\cite{bello2016neural}~\cite{kool2018attention}~\cite{nazari2018reinforcement}.
However, these approaches suffer from two key challenges when applied to
combinatorial problems: insufficient exploration and the requirement of many
training examples of the search space to achieve reasonable performance.
Combinatorial optimisation can be complex, characterised by search spaces with
many optimas and large spaces to search and learn. Therefore, a new method is
needed to find good solutions that are more efficient by being more sample
efficient. This paper presents a new reinforcement learning approach that is
based on entropy. In addition, we design an off-policy-based reinforcement
learning technique that maximises the expected return and improves the sample
efficiency to achieve faster learning during training time. We systematically
evaluate our approach on a range of route optimisation tasks typically used to
evaluate learning-based optimisation, such as the such as the Travelling
Salesman problems (TSP), Capacitated Vehicle Routing Problem (CVRP). In this
paper, we show that our model can generalise to various route problems, such as
the split-delivery VRP (SDVRP), and compare the performance of our method with
that of current state-of-the-art approaches. The Empirical results show that
the proposed method can improve on state-of-the-art methods in terms of
solution quality and computation time and generalise to problems of different
sizes.
- Abstract（参考訳）: モデルのない深層強化に基づく学習アルゴリズムは、COPs~\cite{bello2016neural}〜\cite{kool2018attention}〜\cite{nazari2018reinforcement}の範囲に適用されている。
しかし、これらのアプローチは組合せ問題に適用する際の2つの重要な課題に直面している: 不十分な探索と、合理的な性能を達成するために検索空間の多くの訓練例の必要性である。
組合せ最適化は複雑で、探索と学習のための多くの最適化と大きな空間を持つ探索空間によって特徴づけられる。
そのため, より試料効率が良く, 優れた解を見つけるためには, 新たな方法が必要である。
本稿では,エントロピーに基づく新しい強化学習手法を提案する。
さらに,期待値の最大化とサンプル効率の向上による学習時間短縮を実現する,オフポリシーに基づく強化学習手法を考案した。
本手法は,tsp(traveling salesman problem)やcvrp(capacitated vehicle routing problem)など,学習に基づく最適化を評価するのに一般的に用いられる経路最適化タスクを体系的に評価する。
本稿では,分割配信VRP (SDVRP) などの経路問題を一般化し,提案手法の性能と現状技術との比較を行う。
実験の結果,提案手法は解の質と計算時間の観点から最先端の手法を改善し,異なる大きさの問題に一般化できることがわかった。
関連論文リスト
- Joint Demonstration and Preference Learning Improves Policy Alignment with Human Feedback [58.049113055986375]
我々は、報酬モデルとポリシーをトレーニングするために、AIHF(Alignment with Integrated Human Feedback)と呼ばれる単一ステージアプローチを開発する。
提案した手法は、一般的なアライメントアルゴリズムに容易に還元し、活用できる、効率的なアルゴリズムの集合を認めている。
本研究では,LLMにおけるアライメント問題と,MuJoCoにおけるロボット制御問題を含む広範な実験により,提案手法の有効性を実証する。
論文 参考訳（メタデータ） (2024-06-11T01:20:53Z) - Optimizing Solution-Samplers for Combinatorial Problems: The Landscape
of Policy-Gradient Methods [52.0617030129699]
本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。
我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。
本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
論文 参考訳（メタデータ） (2023-10-08T23:39:38Z) - Faster Stochastic Variance Reduction Methods for Compositional MiniMax
Optimization [50.10952609321302]
合成ミニマックス最適化は、さまざまな機械学習領域において重要な課題である。
構成最小最適化の現在の方法は、最適以下の複雑さや、大きなバッチサイズに大きく依存することによって悩まされている。
本稿では,Nested STOchastic Recursive Momentum (NSTORM)と呼ばれる新しい手法を提案する。
論文 参考訳（メタデータ） (2023-08-18T14:57:21Z) - 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) - Backpropagation of Unrolled Solvers with Folded Optimization [55.04219793298687]
ディープネットワークにおけるコンポーネントとしての制約付き最適化モデルの統合は、多くの専門的な学習タスクに有望な進歩をもたらした。
1つの典型的な戦略はアルゴリズムのアンローリングであり、これは反復解法の操作による自動微分に依存している。
本稿では,非ロール最適化の後方通過に関する理論的知見を提供し,効率よく解けるバックプロパゲーション解析モデルを生成するシステムに繋がる。
論文 参考訳（メタデータ） (2023-01-28T01:50:42Z) - Reinforcement Learning Methods for Wordle: A POMDP/Adaptive Control
Approach [0.3093890460224435]
我々は、新しい強化学習手法を用いて、人気のあるWordleパズルの解法に対処する。
Wordleパズルでは、比較的控えめな計算コストで最適に近いオンラインソリューション戦略が得られる。
論文 参考訳（メタデータ） (2022-11-15T03:46:41Z) - Online Control of Adaptive Large Neighborhood Search using Deep Reinforcement Learning [4.374837991804085]
DR-ALNSと呼ばれる深層強化学習に基づくアプローチを導入し、演算子を選択し、パラメータを調整し、検索全体を通して受け入れ基準を制御する。
提案手法は,IJCAIコンペティションで提示されたオリエンテーリングウェイトと時間窓の問題に対して評価する。
その結果,本手法はバニラALNSよりも優れており,ALNSはベイジアン最適化と2つの最先端DRLアプローチに適合していることがわかった。
論文 参考訳（メタデータ） (2022-11-01T21:33:46Z) - Deep Reinforcement Learning for Exact Combinatorial Optimization:
Learning to Branch [13.024115985194932]
本稿では、強化学習(RL)パラダイムを用いた最適化において、データラベリングと推論の問題を解決するための新しいアプローチを提案する。
我々は模倣学習を用いてRLエージェントをブートストラップし、PPO(Proximal Policy)を使用してグローバルな最適なアクションを探索する。
論文 参考訳（メタデータ） (2022-06-14T16:35:58Z) - An Overview and Experimental Study of Learning-based Optimization
Algorithms for Vehicle Routing Problem [49.04543375851723]
車両ルーティング問題(VRP)は典型的な離散最適化問題である。
多くの研究は、VRPを解決するための学習に基づく最適化アルゴリズムについて検討している。
本稿では、最近のこの分野の進歩を概観し、関連するアプローチをエンドツーエンドアプローチとステップバイステップアプローチに分割する。
論文 参考訳（メタデータ） (2021-07-15T02:13:03Z) - Learning Vehicle Routing Problems using Policy Optimisation [4.093722933440819]
最先端のアプローチは強化学習を使ってポリシーを学習し、学習ポリシーは擬似解法として機能する。
これらのアプローチは、あるケースでは優れた性能を示しているが、ルーティング問題に典型的な大きな検索空間を考えると、ポリシーの貧弱さに早すぎる可能性がある。
より多くのポリシーを提供することで探索を支援するエントロピー正規化強化学習(ERRL)を提案する。
論文 参考訳（メタデータ） (2020-12-24T14:18:56Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。