論文の概要: Online Control of Adaptive Large Neighborhood Search using Deep
Reinforcement Learning
- arxiv url: http://arxiv.org/abs/2211.00759v2
- Date: Mon, 15 May 2023 09:10:27 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-17 00:24:26.459282
- Title: Online Control of Adaptive Large Neighborhood Search using Deep
Reinforcement Learning
- Title(参考訳): 深層強化学習を用いた適応型大近所探索のオンライン制御
- Authors: Robbert Reijnen, Yingqian Zhang, Hoong Chuin Lau, Zaharah Bukhsh
- Abstract要約: 本稿では,バニラを選択し,パラメータを調整し,探索過程における受入基準を制御する,深層強化学習(DRL)アプローチを提案する。
IJCAIコンペティションで用いられる重みと時間窓を用いた時間依存オリエンテーリング問題において,提案手法の評価を行った。
- 参考スコア(独自算出の注目度): 7.4746628878102195
- License: http://creativecommons.org/publicdomain/zero/1.0/
- Abstract: The Adaptive Large Neighborhood Search (ALNS) algorithm has shown
considerable success in solving complex combinatorial optimization problems
(COPs). ALNS selects various heuristics adaptively during the search process,
leveraging their strengths to find good solutions for optimization problems.
However, the effectiveness of ALNS depends on the proper configuration of its
selection and acceptance parameters. To address this limitation, we propose a
Deep Reinforcement Learning (DRL) approach that selects heuristics, adjusts
parameters, and controls the acceptance criteria during the search process. The
proposed method aims to learn, based on the state of the search, how to
configure the next iteration of the ALNS to obtain good solutions to the
underlying optimization problem. We evaluate the proposed method on a
time-dependent orienteering problem with stochastic weights and time windows,
used in an IJCAI competition. The results show that our approach outperforms
vanilla ALNS and ALNS tuned with Bayesian Optimization. In addition, it
obtained better solutions than two state-of-the-art DRL approaches, which are
the winning methods of the competition, with much fewer observations required
for training. The implementation of our approach will be made publicly
available.
- Abstract(参考訳): Adaptive Large Neighborhood Search (ALNS)アルゴリズムは複雑な組合せ最適化問題(COP)の解法においてかなりの成功を収めている。
ALNSは探索過程で様々なヒューリスティックを適応的に選択し、その強みを活用して最適化問題の優れた解を求める。
しかし,alnの有効性は選択パラメータと受け入れパラメータの適切な構成に依存する。
この制限に対処するために、ヒューリスティックスを選択し、パラメータを調整し、検索プロセス中の受け入れ基準を制御できるDeep Reinforcement Learning (DRL)アプローチを提案する。
提案手法は,探索の状況に基づいて,ALNSの次回のイテレーションを設定し,基礎となる最適化問題に対する優れた解を得る方法を学ぶことを目的としている。
ijcaiコンペティションにおいて,確率的重みと時間窓を用いた時間依存型オリエンテーリング問題に対する提案手法を評価した。
その結果,本手法はベイジアン最適化によりバニラALNSおよびALNSより優れていた。
さらに、競争の勝利方法である2つの最先端drlアプローチよりも優れた解を得たが、トレーニングに必要な観察ははるかに少ない。
我々のアプローチの実装は公開される予定だ。
関連論文リスト
- Scaling Combinatorial Optimization Neural Improvement Heuristics with Online Search and Adaptation [0.40964539027092917]
リミテッドロールアウトビームサーチ(Limited Rollout Beam Search, LRBS)を導入する。
LRBSは, 分散性能と大規模問題インスタンスへの一般化の両方を著しく向上させることを示す。
また、事前訓練された改善ポリシーのオフラインおよびオンライン適応に検索戦略を採用し、検索性能を向上させる。
論文 参考訳(メタデータ) (2024-12-13T14:25:27Z) - Learning Reward and Policy Jointly from Demonstration and Preference Improves Alignment [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) - Stepsize Learning for Policy Gradient Methods in Contextual Markov
Decision Processes [35.889129338603446]
ポリシーに基づくアルゴリズムは、モデルフリーRLにおいて最も広く採用されている手法の一つである。
彼らは、一連の不均一なタスクを達成するように頼まれたときに苦労する傾向があります。
メタMDPと呼ばれる新しい定式化を導入し、RLにおける任意のハイパーパラメータ選択問題を解くのに使うことができる。
論文 参考訳(メタデータ) (2023-06-13T12:58:12Z) - 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) - Reinforcement Learning Methods for Wordle: A POMDP/Adaptive Control
Approach [0.3093890460224435]
我々は、新しい強化学習手法を用いて、人気のあるWordleパズルの解法に対処する。
Wordleパズルでは、比較的控えめな計算コストで最適に近いオンラインソリューション戦略が得られる。
論文 参考訳(メタデータ) (2022-11-15T03:46:41Z) - Learning Adaptive Evolutionary Computation for Solving Multi-Objective
Optimization Problems [3.3266268089678257]
本稿では, 深層強化学習(DRL)を用いた適応パラメータ制御とMOEAを統合したフレームワークを提案する。
DRLポリシは、最適化中のソリューションに対する突然変異の強度と確率を決定する値を適応的に設定するように訓練されている。
学習されたポリシーは転送可能であることを示す。つまり、単純なベンチマーク問題で訓練されたポリシーは、複雑な倉庫最適化問題を解決するために直接適用可能である。
論文 参考訳(メタデータ) (2022-11-01T22:08:34Z) - Sample-Efficient, Exploration-Based Policy Optimisation for Routing
Problems [2.6782615615913348]
本稿では,エントロピーに基づく新しい強化学習手法を提案する。
さらに、我々は、期待したリターンを最大化する、政治以外の強化学習手法を設計する。
我々のモデルは様々な経路問題に一般化可能であることを示す。
論文 参考訳(メタデータ) (2022-05-31T09:51:48Z) - A Two-stage Framework and Reinforcement Learning-based Optimization
Algorithms for Complex Scheduling Problems [54.61091936472494]
本稿では、強化学習(RL)と従来の運用研究(OR)アルゴリズムを組み合わせた2段階のフレームワークを開発する。
スケジューリング問題は,有限マルコフ決定過程 (MDP) と混合整数計画過程 (mixed-integer programming process) の2段階で解決される。
その結果,本アルゴリズムは,アジャイルな地球観測衛星スケジューリング問題に対して,安定かつ効率的に十分なスケジューリング計画を得ることができた。
論文 参考訳(メタデータ) (2021-03-10T03:16:12Z) - Combining Deep Learning and Optimization for Security-Constrained
Optimal Power Flow [94.24763814458686]
セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。
SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。
本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
論文 参考訳(メタデータ) (2020-07-14T12:38:21Z) - SUNRISE: A Simple Unified Framework for Ensemble Learning in Deep
Reinforcement Learning [102.78958681141577]
SUNRISEは単純な統一アンサンブル法であり、様々な非政治的な深層強化学習アルゴリズムと互換性がある。
SUNRISEは, (a) アンサンブルに基づく重み付きベルマンバックアップと, (b) 最上位の自信境界を用いて行動を選択する推論手法を統合し, 効率的な探索を行う。
論文 参考訳(メタデータ) (2020-07-09T17:08:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。