論文の概要: 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アプローチよりも優れた解を得たが、トレーニングに必要な観察ははるかに少ない。
我々のアプローチの実装は公開される予定だ。
関連論文リスト
- An Efficient Learning-based Solver Comparable to Metaheuristics for the
Capacitated Arc Routing Problem [67.92544792239086]
我々は,高度メタヒューリスティックスとのギャップを著しく狭めるため,NNベースの解法を導入する。
まず,方向対応型注意モデル(DaAM)を提案する。
第2に、教師付き事前学習を伴い、堅牢な初期方針を確立するための教師付き強化学習スキームを設計する。
論文 参考訳(メタデータ) (2024-03-11T02:17:42Z) - 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) - Socio-cognitive Optimization of Time-delay Control Problems using
Evolutionary Metaheuristics [89.24951036534168]
メタヒューリスティックス(Metaheuristics)は、古典的なアプローチでは解決できない難解な問題を解くために使用される普遍的な最適化アルゴリズムである。
本稿では,キャストに基づく新しい社会認知メタヒューリスティックの構築を目標とし,このアルゴリズムのいくつかのバージョンを時間遅延システムモデルの最適化に適用する。
論文 参考訳(メタデータ) (2022-10-23T22:21:10Z) - Sample-Efficient, Exploration-Based Policy Optimisation for Routing
Problems [2.6782615615913348]
本稿では,エントロピーに基づく新しい強化学習手法を提案する。
さらに、我々は、期待したリターンを最大化する、政治以外の強化学習手法を設計する。
我々のモデルは様々な経路問題に一般化可能であることを示す。
論文 参考訳(メタデータ) (2022-05-31T09:51:48Z) - Multi-Agent Deep Reinforcement Learning in Vehicular OCC [14.685237010856953]
我々は車載OCCにおけるスペクトル効率最適化手法を提案する。
我々は最適化問題をマルコフ決定プロセス(MDP)としてモデル化し、オンラインで適用可能なソリューションの利用を可能にする。
提案手法の性能を広範囲なシミュレーションにより検証し,提案手法の様々な変種とランダムな手法との比較を行った。
論文 参考訳(メタデータ) (2022-05-05T14:25:54Z) - Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。
本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
論文 参考訳(メタデータ) (2022-01-28T05:53:28Z) - 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) - Reinforcement Learning for Combinatorial Optimization: A Survey [12.323976053967066]
最適化問題を解決する多くの伝統的なアルゴリズムは、解決を逐次構築する手工芸品を使用する。
強化学習(Reinforcement Learning, RL)は、エージェントを監督的または自己監督的な方法で訓練することにより、これらの検索を自動化する優れた代替手段を提案する。
論文 参考訳(メタデータ) (2020-03-07T16:19:45Z) - Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
我々は,数千の候補アルゴリズムの固定セットを考慮に入れた,極端なアルゴリズム選択(XAS)の設定を提案する。
我々は、XAS設定に対する最先端のAS技術の適用性を評価し、Dyadic特徴表現を利用したアプローチを提案する。
論文 参考訳(メタデータ) (2020-01-29T09:40:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。