論文の概要: Learning Collaborative Policies to Solve NP-hard Routing Problems
- arxiv url: http://arxiv.org/abs/2110.13987v1
- Date: Tue, 26 Oct 2021 19:46:21 GMT
- ステータス: 処理完了
- システム内更新日: 2021-10-28 13:09:34.598887
- Title: Learning Collaborative Policies to Solve NP-hard Routing Problems
- Title（参考訳）: NPハードルーティング問題を解決するための協調政策の学習
- Authors: Minsu Kim, Jinkyoo Park and Joungho Kim
- Abstract要約: 本稿では,学習協調政策(LCP)と呼ばれる新しい階層的問題解決戦略を提案する。
2つの反復DRLポリシー(シードとリバイザ)を使って、ほぼ最適解を効果的に見つけることができる。
広汎な実験により,提案した2都市連携方式は,NP-ハードルーティング問題に対する単都市DRLフレームワークよりも改善されることが示された。
- 参考スコア（独自算出の注目度）: 13.13675711285772
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Recently, deep reinforcement learning (DRL) frameworks have shown potential
for solving NP-hard routing problems such as the traveling salesman problem
(TSP) without problem-specific expert knowledge. Although DRL can be used to
solve complex problems, DRL frameworks still struggle to compete with
state-of-the-art heuristics showing a substantial performance gap. This paper
proposes a novel hierarchical problem-solving strategy, termed learning
collaborative policies (LCP), which can effectively find the near-optimum
solution using two iterative DRL policies: the seeder and reviser. The seeder
generates as diversified candidate solutions as possible (seeds) while being
dedicated to exploring over the full combinatorial action space (i.e., sequence
of assignment action). To this end, we train the seeder's policy using a simple
yet effective entropy regularization reward to encourage the seeder to find
diverse solutions. On the other hand, the reviser modifies each candidate
solution generated by the seeder; it partitions the full trajectory into
sub-tours and simultaneously revises each sub-tour to minimize its traveling
distance. Thus, the reviser is trained to improve the candidate solution's
quality, focusing on the reduced solution space (which is beneficial for
exploitation). Extensive experiments demonstrate that the proposed two-policies
collaboration scheme improves over single-policy DRL framework on various
NP-hard routing problems, including TSP, prize collecting TSP (PCTSP), and
capacitated vehicle routing problem (CVRP).
- Abstract（参考訳）: 近年、深層強化学習(DRL)フレームワークは、問題固有の専門知識のない旅行セールスマン問題(TSP)のようなNPハードルーティング問題を解く可能性を示している。
DRLは複雑な問題を解決するのに使えるが、DRLフレームワークは依然として最先端のヒューリスティックと競合するのに苦戦している。
本稿では,2つの反復型drlポリシ(シーダーとリバイザ)を用いて,最適に近い解を効果的に見つけることができる階層的問題解決戦略である学習協調政策(lcp)を提案する。
シーダーは、全組合せ作用空間(すなわち割当行動のシーケンス)を探索することに専念しながら、可能な限り多様化した候補解(シード)を生成する。
この目的のために、我々はシーダーのポリシーを、単純かつ効果的なエントロピー正規化報酬を用いて訓練し、シーダーが多様な解決策を見つけるように促す。
一方、リバイザはシーダーが生成する各候補解を修正し、全軌道をサブターに分割し、同時に各サブターを修正して走行距離を最小化する。
したがって、リバイザは、(利用に有利な)削減されたソリューション空間に焦点を当てて、候補ソリューションの品質を改善するために訓練される。
大規模実験により,TSP,PCTSP,キャパシタン化車両ルーティング問題(CVRP)など,NPハードルーティング問題に対する単一政治DRLフレームワークよりも優れた2都市協調方式が提案されている。
関連論文リスト
- Multiobjective Vehicle Routing Optimization with Time Windows: A Hybrid Approach Using Deep Reinforcement Learning and NSGA-II [52.083337333478674]
本稿では、時間窓を用いた多目的車両ルーティング問題(MOVRPTW)に対処するために、ウェイト・アウェア・ディープ・強化学習(WADRL)手法を提案する。
WADRLの結果を最適化するために非支配的ソート遺伝的アルゴリズム-II (NSGA-II) 法を用いる。
論文 参考訳（メタデータ） (2024-07-18T02:46:06Z) - Discovering Multiple Solutions from a Single Task in Offline Reinforcement Learning [51.00472376469131]
オフライン強化学習において,一つのタスクから複数の解を学習するアルゴリズムを提案する。
実験の結果,提案アルゴリズムはオフラインRLにおいて,定性的,定量的に複数の解を学習することがわかった。
論文 参考訳（メタデータ） (2024-06-10T03:25:49Z) - Combinatorial Optimization with Policy Adaptation using Latent Space Search [44.12073954093942]
本稿では,複雑なNPハード問題を解くために,パフォーマンスアルゴリズムを設計するための新しいアプローチを提案する。
我々の検索戦略は11の標準ベンチマークタスクにおける最先端のアプローチよりも優れていることを示す。
論文 参考訳（メタデータ） (2023-11-13T12:24:54Z) - 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) - Online Control of Adaptive Large Neighborhood Search using Deep Reinforcement Learning [4.374837991804085]
DR-ALNSと呼ばれる深層強化学習に基づくアプローチを導入し、演算子を選択し、パラメータを調整し、検索全体を通して受け入れ基準を制御する。
提案手法は,IJCAIコンペティションで提示されたオリエンテーリングウェイトと時間窓の問題に対して評価する。
その結果,本手法はバニラALNSよりも優れており,ALNSはベイジアン最適化と2つの最先端DRLアプローチに適合していることがわかった。
論文 参考訳（メタデータ） (2022-11-01T21:33:46Z) - Solving the Traveling Salesperson Problem with Precedence Constraints by
Deep Reinforcement Learning [59.14935871979047]
本研究は, 深層強化学習(DRL)を用いた優先制約付きトラベリングセールスパーソン問題(TSPPC)の解を提案する。
これらのアプローチに共通しているのは、マルチヘッドアテンション層に基づくグラフモデルの利用である。
論文 参考訳（メタデータ） (2022-07-04T14:31:47Z) - Reinforcement Learning to Solve NP-hard Problems: an Application to the
CVRP [0.0]
古典的最適化問題の解法として強化学習(Reinforcement Learning, RL)を応用した。
最も有望なRLアプローチの2つを、ベンチマークインスタンスのセットで従来の問題解決手法と比較する。
最良解を返さないにもかかわらず、RLアプローチは従来の解法よりも多くの利点があることがわかった。
論文 参考訳（メタデータ） (2022-01-14T11:16:17Z) - Semantic-Aware Collaborative Deep Reinforcement Learning Over Wireless
Cellular Networks [82.02891936174221]
複数のエージェントが無線ネットワーク上で協調できるコラボレーティブディープ強化学習(CDRL)アルゴリズムは有望なアプローチである。
本稿では,リソース制約のある無線セルネットワーク上で,意味的にリンクされたDRLタスクを持つ未学習エージェントのグループを効率的に協調させる,新しい意味認識型CDRL手法を提案する。
論文 参考訳（メタデータ） (2021-11-23T18:24:47Z) - Deep Policy Dynamic Programming for Vehicle Routing Problems [89.96386273895985]
本稿では,学習ニューラルの強みと動的プログラミングアルゴリズムの強みを組み合わせた深層ポリシー動的プログラミング(d pdp)を提案する。
D PDPは、例の解からエッジを予測するために訓練されたディープニューラルネットワークから派生したポリシーを使用して、DP状態空間を優先し、制限する。
本研究では,旅行セールスマン問題 (TSP) と車両ルーティング問題 (VRP) の枠組みを評価し,ニューラルネットワークが(制限された)DPアルゴリズムの性能を向上させることを示す。
論文 参考訳（メタデータ） (2021-02-23T15:33:57Z) - Learning Vehicle Routing Problems using Policy Optimisation [4.093722933440819]
最先端のアプローチは強化学習を使ってポリシーを学習し、学習ポリシーは擬似解法として機能する。
これらのアプローチは、あるケースでは優れた性能を示しているが、ルーティング問題に典型的な大きな検索空間を考えると、ポリシーの貧弱さに早すぎる可能性がある。
より多くのポリシーを提供することで探索を支援するエントロピー正規化強化学習(ERRL)を提案する。
論文 参考訳（メタデータ） (2020-12-24T14:18:56Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。