論文の概要: 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適応層よりも高い性能を達成できることがわかった。
また,演算子ポートフォリオのサイズや演算子スケールの選択の影響など,重要な考察についても論じる。
特に,本手法は,問題固有の運用ポートフォリオを手作りする上で,多大な時間と労力を節約できる。
関連論文リスト
- Dynamic operator management in meta-heuristics using reinforcement learning: an application to permutation flowshop scheduling problems [0.3495246564946556]
本研究では,メタヒューリスティックスにおける探索演算子のポートフォリオを動的に管理する強化学習に基づくフレームワークを開発する。
動的に更新されたポートフォリオから最も適切な演算子を選択するために、Qラーニングに基づく適応演算子選択機構を用いる。
提案するフレームワークの性能は,置換フローホップスケジューリング問題への適用を通して解析する。
論文 参考訳(メタデータ) (2024-08-27T08:38:17Z) - Memory-Enhanced Neural Solvers for Efficient Adaptation in Combinatorial Optimization [6.713974813995327]
本稿では、メモリを活用してニューラルネットワークの適応性を向上させるアプローチであるMementOを提案する。
我々は,大規模インスタンス上で全RL自動回帰解法をトレーニングし,MementOが拡張可能で,データ効率がよいことを示す。
全体として、MementOは評価された12のタスクのうち11に最先端のタスクをプッシュすることができる。
論文 参考訳(メタデータ) (2024-06-24T08:18:19Z) - Decision-focused Graph Neural Networks for Combinatorial Optimization [62.34623670845006]
最適化問題に取り組むための新たな戦略は、従来のアルゴリズムに代わるグラフニューラルネットワーク(GNN)の採用である。
GNNや従来のアルゴリズムソルバがCOの領域で人気が高まっているにもかかわらず、それらの統合利用とエンドツーエンドフレームワークにおけるそれらの相関について限定的な研究がなされている。
我々は、GNNを利用してCO問題に補助的なサポートで対処する決定に焦点を当てたフレームワークを導入する。
論文 参考訳(メタデータ) (2024-06-05T22:52:27Z) - Switchable Decision: Dynamic Neural Generation Networks [98.61113699324429]
本稿では,各データインスタンスのリソースを動的に割り当てることで,推論を高速化するスイッチブルな決定を提案する。
提案手法は, 同一の精度を維持しながら, 推論時のコスト低減に有効である。
論文 参考訳(メタデータ) (2024-05-07T17:44:54Z) - An Efficient Learning-based Solver Comparable to Metaheuristics for the
Capacitated Arc Routing Problem [67.92544792239086]
我々は,高度メタヒューリスティックスとのギャップを著しく狭めるため,NNベースの解法を導入する。
まず,方向対応型注意モデル(DaAM)を提案する。
第2に、教師付き事前学習を伴い、堅牢な初期方針を確立するための教師付き強化学習スキームを設計する。
論文 参考訳(メタデータ) (2024-03-11T02:17:42Z) - Constrained Multi-objective Optimization with Deep Reinforcement Learning Assisted Operator Selection [28.088046969822543]
本研究では,Deep Reinforcement Learningを支援するオンラインオペレータ選択フレームワークを提案する。
提案手法は,現在の状況に応じて個体群の改善を最大化する演算子を適応的に選択することができる。
このフレームワークは4つの人気のあるCMOEAに組み込まれ、42のベンチマーク問題で評価されている。
論文 参考訳(メタデータ) (2024-01-15T09:51:19Z) - Adaptive operator selection utilising generalised experience [0.8287206589886879]
強化学習(Reinforcement Learning, RL)は, 高度に効果的な適応的な選択システムをカスタマイズし, 形成する方法として提案されている。
本稿では,RLをベースとした新たなアプローチを提案し,今後の利用経験の獲得,処理,活用のための汎用的なフレームワークの開発を支援する。
論文 参考訳(メタデータ) (2023-12-04T00:27:59Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。