論文の概要: Pointer Networks with Q-Learning for OP Combinatorial Optimization
- arxiv url: http://arxiv.org/abs/2311.02629v2
- Date: Tue, 19 Mar 2024 09:15:36 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-21 00:20:56.817906
- Title: Pointer Networks with Q-Learning for OP Combinatorial Optimization
- Title(参考訳): OP Combinatorial OptimizationのためのQ-Learning付きポインタネットワーク
- Authors: Alessandro Barro,
- Abstract要約: オリエンテーアリング問題(OP)は、組合せ最適化(CO)においてユニークな課題を提示する
この研究はPointer Q-Network (PQN)を発表した。
この手法は、Ptr-NetsとQ-learningを組み合わせたもので、批判のみにより、組込みグラフ内で関係をキャプチャする能力に勝っている。
- 参考スコア(独自算出の注目度): 55.2480439325792
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The Orienteering Problem (OP) presents a unique challenge in Combinatorial Optimization (CO), emphasized by its widespread use in logistics, delivery, and transportation planning. Given the NP-hard nature of OP, obtaining optimal solutions is inherently complex. While Pointer Networks (Ptr-Nets) have exhibited prowess in various combinatorial tasks, their performance in the context of OP, and duties requiring focus on future return or exploration, leaves room for improvement. Recognizing the potency combining Reinforcement Learning (RL) methods with sequence-to-sequence models, this research unveils the Pointer Q-Network (PQN). This method combines Ptr-Nets and Q-learning, which, thanks to its critic only nature, outstands in its capability of capturing relationships within an embedded graph, a fundamental requirement in order to effectively address the specific challenges presented by OP. We explore the architecture and functionality of the PQN system, while showcasing its theoretical and practical advantages in terms of efficiency for combinatorial optimization problems such as the Orienteering Problem.
- Abstract(参考訳): オリエンテーリング問題(OP)は、物流、配送、輸送計画において広く使われていることを強調する、コンビニショナル最適化(CO)において、ユニークな課題を提示している。
OPのNPハードの性質を考えると、最適解を得るのは本質的に複雑である。
Pointer Networks (Ptr-Nets) は、様々な組合せタスク、OPの文脈におけるパフォーマンス、将来のリターンや探索に焦点をあてる義務に長けているが、改善の余地は残されている。
本研究は,強化学習(RL)法とシーケンス・ツー・シーケンス・モデルを組み合わせた有効性を認識し,Pointer Q-Network (PQN) を公表する。
この手法はPtr-NetsとQ-learningを組み合わせており、その批判的な性質のおかげで、OPが提示する特定の課題に効果的に対処するための基本的な要件である組込みグラフ内で関係をキャプチャする能力に優れている。
PQNシステムのアーキテクチャと機能について検討し、オリエンテーリング問題のような組合せ最適化問題の効率性の観点から理論的・実用的優位性を示す。
関連論文リスト
- An Efficient Learning-based Solver Comparable to Metaheuristics for the
Capacitated Arc Routing Problem [67.92544792239086]
我々は,高度メタヒューリスティックスとのギャップを著しく狭めるため,NNベースの解法を導入する。
まず,方向対応型注意モデル(DaAM)を提案する。
第2に、教師付き事前学習を伴い、堅牢な初期方針を確立するための教師付き強化学習スキームを設計する。
論文 参考訳(メタデータ) (2024-03-11T02:17:42Z) - Multi-Timescale Ensemble Q-learning for Markov Decision Process Policy
Optimization [21.30645601474163]
元々のQ-ラーニングは、非常に大きなネットワークにわたるパフォーマンスと複雑性の課題に悩まされている。
従来のQ-ラーニングに適応したモデルフリーアンサンブル強化学習アルゴリズムを提案する。
計算結果から,提案アルゴリズムは平均ポリシエラーを最大55%,実行時複雑性を最大50%削減できることがわかった。
論文 参考訳(メタデータ) (2024-02-08T08:08:23Z) - 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) - 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) - Neural Combinatorial Optimization: a New Player in the Field [69.23334811890919]
本稿では,ニューラルネットワークに基づくアルゴリズムの古典的最適化フレームワークへの導入に関する批判的分析を行う。
性能, 転送可能性, 計算コスト, 大規模インスタンスなど, これらのアルゴリズムの基本的側面を分析するために, 総合的研究を行った。
論文 参考訳(メタデータ) (2022-05-03T07:54:56Z) - A Differentiable Approach to Combinatorial Optimization using Dataless
Neural Networks [20.170140039052455]
我々は、ソリューションを生成するニューラルネットワークのトレーニングにデータを必要としないという、根本的に異なるアプローチを提案する。
特に、最適化問題をニューラルネットワークに還元し、データレストレーニングスキームを用いて、それらのパラメータが関心の構造をもたらすように、ネットワークのパラメータを洗練する。
論文 参考訳(メタデータ) (2022-03-15T19:21:31Z) - Sequential Information Design: Markov Persuasion Process and Its
Efficient Reinforcement Learning [156.5667417159582]
本稿では,逐次情報設計の新たなモデル,すなわちマルコフ説得過程(MPP)を提案する。
MPPのプランニングは、ミオピックレシーバーに同時に説得されるシグナルポリシーを見つけ、送信者の最適な長期累積ユーティリティを誘導する、というユニークな課題に直面している。
我々は,楽観主義と悲観主義の両原理の新たな組み合わせを特徴とする,実証可能な効率のよい非回帰学習アルゴリズム,Optimism-Pessimism Principle for Persuasion Process (OP4) を設計する。
論文 参考訳(メタデータ) (2022-02-22T05:41:43Z) - On the Difficulty of Generalizing Reinforcement Learning Framework for
Combinatorial Optimization [6.935838847004389]
現実の応用とグラフ上の組合せ最適化問題(COP)は、コンピュータサイエンスにおける標準的な課題である。
このアプローチの基本原理は、ノードのローカル情報とグラフ構造化データの両方を符号化するグラフニューラルネットワーク(GNN)をデプロイすることである。
我々は,クラウド上のセキュリティ対応電話機のクローン割り当てを古典的二次代入問題 (QAP) として,深層RLモデルが他の難題の解法に一般的に適用可能であるか否かを調査する。
論文 参考訳(メタデータ) (2021-08-08T19:12:04Z) - Reversible Action Design for Combinatorial Optimization with
Reinforcement Learning [35.50454156611722]
強化学習(rl)は、これらの問題に取り組むための新しいフレームワークとして最近登場した。
最先端の実証性能を示すだけでなく、様々な種類のCOPに一般化する汎用RLフレームワークを提案します。
論文 参考訳(メタデータ) (2021-02-14T18:05:42Z) - Constrained Combinatorial Optimization with Reinforcement Learning [0.30938904602244344]
本稿では,RL(Deep Reinforcement Learning)を用いた制約付き最適化問題に対処する枠組みを提案する。
我々は、その定式化における制約に対処するために、Neural Combinatorial Optimization(NCO)理論を拡張した。
その文脈では、ソリューションは環境との相互作用に基づいて反復的に構築されます。
論文 参考訳(メタデータ) (2020-06-22T03:13:07Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。