論文の概要: 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と呼ばれる深層強化学習法を提案する。 そこで,提案手法は,探索の状態に基づいて,どの操作を選択して高い長期報酬を得るか,すなわち基礎となる最適化問題に対する優れた解を求めることを目的としている。 提案手法は,確率重みと時間窓を用いた時間依存オリエンテーリング問題を用いて評価する。 提案手法は, 大規模探索における演算子を適応的に選択する手法を効果的に学習し, 大規模問題事例の少ない観察で学習しながら, 最先端の機械学習手法と比較して競争力のある結果が得られることを示す。

関連論文リスト

• 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)
• 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)
• Reinforcement Learning for Combinatorial Optimization: A Survey [12.323976053967066]
  最適化問題を解決する多くの伝統的なアルゴリズムは、解決を逐次構築する手工芸品を使用する。 強化学習(Reinforcement Learning, RL)は、エージェントを監督的または自己監督的な方法で訓練することにより、これらの検索を自動化する優れた代替手段を提案する。
  論文  参考訳（メタデータ） (2020-03-07T16:19:45Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。