論文の概要: Graph Reinforcement Learning for Operator Selection in the ALNS
Metaheuristic
- arxiv url: http://arxiv.org/abs/2302.14678v1
- Date: Tue, 28 Feb 2023 15:39:42 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-01 15:47:28.298000
- Title: Graph Reinforcement Learning for Operator Selection in the ALNS
Metaheuristic
- Title(参考訳): ALNSメタヒューリスティックにおける演算子選択のためのグラフ強化学習
- Authors: Syu-Ning Johnn, Victor-Alexandru Darvariu, Julia Handl, Joerg Kalcsics
- Abstract要約: 我々はマルコフ決定過程として作用素の選択を定式化する。
本稿では,ディープ強化学習とグラフニューラルネットワークに基づく実践的アプローチを提案する。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: ALNS is a popular metaheuristic with renowned efficiency in solving
combinatorial optimisation problems. However, despite 16 years of intensive
research into ALNS, whether the embedded adaptive layer can efficiently select
operators to improve the incumbent remains an open question. In this work, we
formulate the choice of operators as a Markov Decision Process, and propose a
practical approach based on Deep Reinforcement Learning and Graph Neural
Networks. The results show that our proposed method achieves better performance
than the classic ALNS adaptive layer due to the choice of operator being
conditioned on the current solution. We also discuss important considerations
such as the size of the operator portfolio and the impact of the choice of
operator scales. Notably, our approach can also save significant time and
labour costs for handcrafting problem-specific operator portfolios.
- Abstract(参考訳): ALNSは、組合せ最適化問題の解法において有名な効率性を持つメタヒューリスティックである。
しかし、ALNSに関する16年間の研究にもかかわらず、組込み適応層が演算子を効率よく選択できるかどうかについては未解決のままである。
本研究では,マルコフ決定過程として演算子の選択を定式化し,Deep Reinforcement Learning と Graph Neural Networks に基づく実践的アプローチを提案する。
その結果,提案手法は従来のALNS適応層よりも高い性能を達成できることがわかった。
また,演算子ポートフォリオのサイズや演算子スケールの選択の影響など,重要な考察についても論じる。
特に,本手法は,問題固有の運用ポートフォリオを手作りする上で,多大な時間と労力を節約できる。
関連論文リスト
- An Efficient Learning-based Solver Comparable to Metaheuristics for the
Capacitated Arc Routing Problem [67.92544792239086]
我々は,高度メタヒューリスティックスとのギャップを著しく狭めるため,NNベースの解法を導入する。
まず,方向対応型注意モデル(DaAM)を提案する。
第2に、教師付き事前学習を伴い、堅牢な初期方針を確立するための教師付き強化学習スキームを設計する。
論文 参考訳(メタデータ) (2024-03-11T02:17:42Z) - Deep Reinforcement Learning for Picker Routing Problem in Warehousing [0.6562256987706128]
本稿では、強化学習を用いて学習したピッカーツアーをモデル化するための注意に基づくニューラルネットワークを提案する。
提案手法の重要な利点は,経路の複雑さを低減できるオプションを提供することである。
論文 参考訳(メタデータ) (2024-02-05T21:25:45Z) - Adaptive operator selection utilising generalised experience [0.8287206589886879]
強化学習(Reinforcement Learning, RL)は, 高度に効果的な適応的な選択システムをカスタマイズし, 形成する方法として提案されている。
本稿では,RLをベースとした新たなアプローチを提案し,今後の利用経験の獲得,処理,活用のための汎用的なフレームワークの開発を支援する。
論文 参考訳(メタデータ) (2023-12-04T00:27:59Z) - Online Control of Adaptive Large Neighborhood Search using Deep
Reinforcement Learning [7.4746628878102195]
本稿では,バニラを選択し,パラメータを調整し,探索過程における受入基準を制御する,深層強化学習(DRL)アプローチを提案する。
IJCAIコンペティションで用いられる重みと時間窓を用いた時間依存オリエンテーリング問題において,提案手法の評価を行った。
論文 参考訳(メタデータ) (2022-11-01T21:33:46Z) - Learning to Optimize Permutation Flow Shop Scheduling via Graph-based
Imitation Learning [70.65666982566655]
置換フローショップスケジューリング(PFSS)は製造業で広く使われている。
我々は,より安定かつ正確に収束を加速する専門家主導の模倣学習を通じてモデルを訓練することを提案する。
我々のモデルのネットワークパラメータはわずか37%に減少し、エキスパートソリューションに対する我々のモデルの解のギャップは平均6.8%から1.3%に減少する。
論文 参考訳(メタデータ) (2022-10-31T09:46:26Z) - Improved Algorithms for Neural Active Learning [74.89097665112621]
非パラメトリックストリーミング設定のためのニューラルネットワーク(NN)ベースの能動学習アルゴリズムの理論的および経験的性能を改善する。
本研究では,SOTA(State-of-the-art (State-the-art)) 関連研究で使用されるものよりも,アクティブラーニングに適する人口減少を最小化することにより,2つの後悔の指標を導入する。
論文 参考訳(メタデータ) (2022-10-02T05:03:38Z) - Meta-Wrapper: Differentiable Wrapping Operator for User Interest
Selection in CTR Prediction [97.99938802797377]
クリックスルー率(CTR)予測は、ユーザーが商品をクリックする確率を予測することを目的としており、リコメンデーションシステムにおいてますます重要になっている。
近年,ユーザの行動からユーザの興味を自動的に抽出する深層学習モデルが大きな成功を収めている。
そこで我々は,メタラッパー(Meta-Wrapper)と呼ばれるラッパー手法の枠組みに基づく新しい手法を提案する。
論文 参考訳(メタデータ) (2022-06-28T03:28:15Z) - Learning To Cut By Looking Ahead: Cutting Plane Selection via Imitation
Learning [80.45697245527019]
我々は、最良限の改善をもたらすカットを明示的に目指している欲求選択規則が、カット選択に対して強い決定を下すことを示す。
本研究では,頭頂部の専門家を対象とした模擬学習のための新しいニューラルアーキテクチャ(NeuralCut)を提案する。
論文 参考訳(メタデータ) (2022-06-27T16:07:27Z) - RoMA: Robust Model Adaptation for Offline Model-based Optimization [115.02677045518692]
入力出力クエリの静的データセットからブラックボックス目的関数を最大化する入力を探索する問題を考える。
この問題を解決するための一般的なアプローチは、真の客観的関数を近似するプロキシモデルを維持することである。
ここでの大きな課題は、検索中に逆最適化された入力を避ける方法である。
論文 参考訳(メタデータ) (2021-10-27T05:37:12Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。