論文の概要: Solving the Traveling Salesperson Problem with Precedence Constraints by
Deep Reinforcement Learning
- arxiv url: http://arxiv.org/abs/2207.01443v1
- Date: Mon, 4 Jul 2022 14:31:47 GMT
- ステータス: 処理完了
- システム内更新日: 2022-07-05 20:34:40.712268
- Title: Solving the Traveling Salesperson Problem with Precedence Constraints by
Deep Reinforcement Learning
- Title(参考訳): 深層強化学習による先行制約付きトラベリングセールスパーソン問題の解決
- Authors: Christian L\"owens, Muhammad Inaam Ashraf, Alexander Gembus, Genesis
Cuizon, Jonas K. Falkner, Lars Schmidt-Thieme
- Abstract要約: 本研究は, 深層強化学習(DRL)を用いた優先制約付きトラベリングセールスパーソン問題(TSPPC)の解を提案する。
これらのアプローチに共通しているのは、マルチヘッドアテンション層に基づくグラフモデルの利用である。
- 参考スコア(独自算出の注目度): 59.14935871979047
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This work presents solutions to the Traveling Salesperson Problem with
precedence constraints (TSPPC) using Deep Reinforcement Learning (DRL) by
adapting recent approaches that work well for regular TSPs. Common to these
approaches is the use of graph models based on multi-head attention (MHA)
layers. One idea for solving the pickup and delivery problem (PDP) is using
heterogeneous attentions to embed the different possible roles each node can
take. In this work, we generalize this concept of heterogeneous attentions to
the TSPPC. Furthermore, we adapt recent ideas to sparsify attentions for better
scalability. Overall, we contribute to the research community through the
application and evaluation of recent DRL methods in solving the TSPPC.
- Abstract(参考訳): 本研究は, 先行制約付きトラベリングセールスパーソン問題 (TSPPC) に対して, 従来のTSPによく適合する近年のアプローチを適用し, DRL(Deep Reinforcement Learning) を用いた解決法を提案する。
これらのアプローチに共通するのは、マルチヘッドアテンション(mha)層に基づくグラフモデルの利用である。
ピックアップ・アンド・デリバリ問題(pdp)を解決するひとつのアイデアは、各ノードが取り得るさまざまな役割を組み込むために、異種注意を使用することである。
本研究では、TSPPCに対する異種注意の概念を一般化する。
さらに、より優れたスケーラビリティのために注意をそらすために、最近のアイデアを適応させます。
TSPPCの解決における最近のDRL手法の適用と評価を通じて,研究コミュニティに貢献する。
関連論文リスト
- Learn to Tour: Operator Design For Solution Feasibility Mapping in Pickup-and-delivery Traveling Salesman Problem [12.34897099691387]
本稿では,旅行セールスマン問題(TSP)の学習方法を提案する。
1対1のピックアップ・アンド・デリバリノードのシーケンスで一番短いツアーを見つける。
PDTSPでは、各ピックアップノードを対応する配信ノードの前に訪問しなければならないという優先的な制約を満たさなければならない。
論文 参考訳(メタデータ) (2024-04-17T15:05:51Z) - Leveraging Constraint Programming in a Deep Learning Approach for Dynamically Solving the Flexible Job-Shop Scheduling Problem [1.3927943269211593]
本稿では,制約プログラミング(CP)をディープラーニング(DL)ベースの方法論に統合し,両者の利点を活用することを目的とする。
本稿では,CP が生成する最適解を用いて DL モデルを訓練し,高品質なデータからモデルを学習する手法を提案する。
我々のハイブリッドアプローチは3つの公開FJSSPベンチマークで広範囲にテストされ、5つの最先端DRLアプローチよりも優れた性能を示している。
論文 参考訳(メタデータ) (2024-03-14T10:16:57Z) - Decoupled Prioritized Resampling for Offline RL [114.73666323173204]
オフライン強化学習のためのオフライン優先体験再生(OPER)を提案する。
OPERは、高度に反転する遷移を優先するように設計された優先順位関数のクラスを備えており、トレーニング中により頻繁に訪問することができる。
優先順位関数のクラスは行動ポリシーの改善を誘導し、この改善されたポリシーに制約された場合、ポリシー制約付きオフラインRLアルゴリズムによりより良い解が得られる可能性が示唆された。
論文 参考訳(メタデータ) (2023-06-08T17:56:46Z) - Pointerformer: Deep Reinforced Multi-Pointer Transformer for the
Traveling Salesman Problem [67.32731657297377]
トラベリングセールスマン問題(TSP)は、もともと輸送と物流の領域で発生した古典的な経路最適化問題である。
近年, 深層強化学習は高い推論効率のため, TSP の解法として採用されている。
本稿では,多点変換器をベースとした新しいエンドツーエンドDRL手法であるPointerformerを提案する。
論文 参考訳(メタデータ) (2023-04-19T03:48:32Z) - 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) - A Survey of Meta-Reinforcement Learning [69.76165430793571]
我々は,メタRLと呼ばれるプロセスにおいて,機械学習問題自体として,より優れたRLアルゴリズムを開発した。
本稿では,タスク分布の存在と各タスクに利用可能な学習予算に基づいて,高レベルでメタRL研究をクラスタ化する方法について議論する。
RL実践者のための標準ツールボックスにメタRLを組み込むことの道程について,オープンな問題を提示することによって,結論を下す。
論文 参考訳(メタデータ) (2023-01-19T12:01:41Z) - On the Use of Quality Diversity Algorithms for The Traveling Thief
Problem [11.590506672325668]
現実世界の最適化では、いくつかのサブプロブレムが相互作用し、主要な問題を形成するのが一般的である。
本稿では,旅行セールスパーソン問題(TSP)とクナップサック問題(KP)の相互依存性を品質多様性(QD)アプローチを用いて検討する。
論文 参考訳(メタデータ) (2021-12-16T05:08:39Z) - Learning Collaborative Policies to Solve NP-hard Routing Problems [13.13675711285772]
本稿では,学習協調政策(LCP)と呼ばれる新しい階層的問題解決戦略を提案する。
2つの反復DRLポリシー(シードとリバイザ)を使って、ほぼ最適解を効果的に見つけることができる。
広汎な実験により,提案した2都市連携方式は,NP-ハードルーティング問題に対する単都市DRLフレームワークよりも改善されることが示された。
論文 参考訳(メタデータ) (2021-10-26T19:46:21Z) - Heterogeneous Attentions for Solving Pickup and Delivery Problem via
Deep Reinforcement Learning [14.627657852087994]
我々は、ノードを自動的に選択する深層強化学習におけるポリシーを強化するために、異種注意機構と統合された新しいニューラルネットワークを活用する。
特に、不均一な注意機構は、優先制約を考慮してノードの役割ごとに注意を規定する。
提案手法は,最先端および深層学習モデルより優れ,各分布と問題サイズによく対応している。
論文 参考訳(メタデータ) (2021-10-06T10:16:07Z) - Deep Policy Dynamic Programming for Vehicle Routing Problems [89.96386273895985]
本稿では,学習ニューラルの強みと動的プログラミングアルゴリズムの強みを組み合わせた深層ポリシー動的プログラミング(d pdp)を提案する。
D PDPは、例の解からエッジを予測するために訓練されたディープニューラルネットワークから派生したポリシーを使用して、DP状態空間を優先し、制限する。
本研究では,旅行セールスマン問題 (TSP) と車両ルーティング問題 (VRP) の枠組みを評価し,ニューラルネットワークが(制限された)DPアルゴリズムの性能を向上させることを示す。
論文 参考訳(メタデータ) (2021-02-23T15:33:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。