論文の概要: Operator Selection in Adaptive Large Neighborhood Search using Deep
Reinforcement Learning
- arxiv url: http://arxiv.org/abs/2211.00759v1
- Date: Tue, 1 Nov 2022 21:33:46 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-03 12:27:12.133291
- Title: Operator Selection in Adaptive Large Neighborhood Search using Deep
Reinforcement Learning
- Title(参考訳): 深層強化学習を用いた適応型大近所探索におけるオペレータ選択
- Authors: Robbert Reijnen, Yingqian Zhang, Hoong Chuin Lau, Zaharah Bukhsh
- Abstract要約: Adaptive Large Neighborhood Search (ALNS) は、探索プロセス中に演算子を適応的に選択するために提案されている。
本稿では,Deep Reinforced Adaptive Large Neighborhood Searchという,Deep Reinforcement Learningに基づく手法を提案する。
提案手法は,大規模近傍探索のための演算子を適応的に選択する戦略を効果的に学習することを示す。
- 参考スコア(独自算出の注目度): 7.4746628878102195
- License: http://creativecommons.org/publicdomain/zero/1.0/
- Abstract: Large Neighborhood Search (LNS) is a popular heuristic for solving
combinatorial optimization problems. LNS iteratively explores the neighborhoods
in solution spaces using destroy and repair operators. Determining the best
operators for LNS to solve a problem at hand is a labor-intensive process.
Hence, Adaptive Large Neighborhood Search (ALNS) has been proposed to
adaptively select operators during the search process based on operator
performances of the previous search iterations. Such an operator selection
procedure is a heuristic, based on domain knowledge, which is ineffective with
complex, large solution spaces. In this paper, we address the problem of
selecting operators for each search iteration of ALNS as a sequential decision
problem and propose a Deep Reinforcement Learning based method called Deep
Reinforced Adaptive Large Neighborhood Search. As such, the proposed method
aims to learn based on the state of the search which operation to select to
obtain a high long-term reward, i.e., a good solution to the underlying
optimization problem. The proposed method is evaluated on a time-dependent
orienteering problem with stochastic weights and time windows. Results show
that our approach effectively learns a strategy that adaptively selects
operators for large neighborhood search, obtaining competitive results compared
to a state-of-the-art machine learning approach while trained with much fewer
observations on small-sized problem instances.
- Abstract(参考訳): LNS(Large Neighborhood Search)は組合せ最適化問題の解法として人気がある。
LNSは、破壊と修復演算子を用いて、解空間内の近傍を反復的に探索する。
LNSが手前の問題を解決するのに最適な演算子を決定することは、労働集約的なプロセスである。
したがって,前回の探索回数の演算性能に基づいて,探索過程中の演算子を適応的に選択するための適応型大規模近傍探索 (alns) が提案されている。
このような演算子選択手順は、複雑で大きな解空間では有効ではない、ドメイン知識に基づくヒューリスティックである。
本稿では,ALNSの各探索繰り返しに対する演算子を逐次決定問題として選択する問題に対処し,Deep Reinforced Adaptive Large Neighhood Searchと呼ばれる深層強化学習法を提案する。
そこで,提案手法は,探索の状態に基づいて,どの操作を選択して高い長期報酬を得るか,すなわち基礎となる最適化問題に対する優れた解を求めることを目的としている。
提案手法は,確率重みと時間窓を用いた時間依存オリエンテーリング問題を用いて評価する。
提案手法は, 大規模探索における演算子を適応的に選択する手法を効果的に学習し, 大規模問題事例の少ない観察で学習しながら, 最先端の機械学習手法と比較して競争力のある結果が得られることを示す。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。