論文の概要: DAN: Decentralized Attention-based Neural Network to Solve the MinMax Multiple Traveling Salesman Problem

• arxiv url: http://arxiv.org/abs/2109.04205v1
• Date: Thu, 9 Sep 2021 12:26:04 GMT
• ステータス: 処理完了
• システム内更新日: 2021-09-10 14:04:13.261643
• Title: DAN: Decentralized Attention-based Neural Network to Solve the MinMax Multiple Traveling Salesman Problem
• Title（参考訳）: DAN:MinMaxのマルチトラベリングセールスマン問題を解決する分散型アテンションベースニューラルネットワーク
• Authors: Yuhong Cao and Zhanhong Sun and Guillaume Sartoretti
• Abstract要約: 我々は、DANと呼ばれるMinMax mTSPを解くために、分散注意に基づくニューラルネットワーク手法を導入する。 DANでは、エージェントは、他のエージェントの将来の決定を予測することによって、ツアーを共同で構築するための完全に分散されたポリシーを学ぶ。 我々は50から1000の都市、5から20のエージェントを含む小規模から大規模mTSPインスタンスで実験を行い、最先端のベースラインと比較した。
• 参考スコア（独自算出の注目度）: 5.137147284997655
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The multiple traveling salesman problem (mTSP) is a well-known NP-hard problem with numerous real-world applications. In particular, this work addresses MinMax mTSP, where the objective is to minimize the max tour length (sum of Euclidean distances) among all agents. The mTSP is normally considered as a combinatorial optimization problem, but due to its computational complexity, search-based exact and heuristic algorithms become inefficient as the number of cities increases. Encouraged by the recent developments in deep reinforcement learning (dRL), this work considers the mTSP as a cooperative task and introduces a decentralized attention-based neural network method to solve the MinMax mTSP, named DAN. In DAN, agents learn fully decentralized policies to collaboratively construct a tour, by predicting the future decisions of other agents. Our model relies on the Transformer architecture, and is trained using multi-agent RL with parameter sharing, which provides natural scalability to the numbers of agents and cities. We experimentally demonstrate our model on small- to large-scale mTSP instances, which involve 50 to 1000 cities and 5 to 20 agents, and compare against state-of-the-art baselines. For small-scale problems (fewer than 100 cities), DAN is able to closely match the performance of the best solver available (OR Tools, a meta-heuristic solver) given the same computation time budget. In larger-scale instances, DAN outperforms both conventional and dRL-based solvers, while keeping computation times low, and exhibits enhanced collaboration among agents.
• Abstract（参考訳）: マルチトラベルセールスマン問題(mTSP)は、多くの現実世界の応用においてよく知られたNPハード問題である。 特に、この研究はMinMax mTSPに対処し、すべてのエージェント間の最大ツアー距離(ユークリッド距離の仮定)を最小化することを目的としている。 mTSPは通常、組合せ最適化問題と見なされるが、その計算複雑性のため、都市数が増加するにつれて、検索に基づく正確かつヒューリスティックなアルゴリズムは非効率になる。 近年の深層強化学習(dRL)の発展により、この研究はmTSPを協調作業とみなし、DANと呼ばれるMinMax mTSPを解決するために、分散された注意に基づくニューラルネットワーク手法を導入している。 DANでは、エージェントは、他のエージェントの将来の決定を予測することによって、ツアーを共同で構築するための完全に分散されたポリシーを学ぶ。 我々のモデルはTransformerアーキテクチャに依存し、パラメータ共有を備えたマルチエージェントRLを用いて訓練されており、エージェントや都市の数に自然なスケーラビリティを提供する。 我々は50から1000の都市、5から20のエージェントを含む小規模から大規模mTSPインスタンスで実験を行い、最先端のベースラインと比較した。 小規模の問題(100都市未満)では、DANは同じ計算時間予算を与えられた最高の解法(またはメタヒューリスティック解法)の性能と密に一致させることができる。 大規模インスタンスでは、DANは計算時間を低く保ちながら従来の解法とdRLベースの解法より優れており、エージェント間のコラボレーションが強化されている。

関連論文リスト

• Learning Emergence of Interaction Patterns across Independent RL Agents in Multi-Agent Environments [3.0284592792243794]
  ボトムアップネットワーク(BUN)は、マルチエージェントの集合を統一エンティティとして扱う。 協調ナビゲーションやトラヒックコントロールなどのタスクを含む,さまざまな協調型マルチエージェントシナリオに対する実証的な評価は,BUNが計算コストを大幅に削減したベースライン手法よりも優れていることを一貫して証明している。
  論文  参考訳（メタデータ） (2024-10-03T14:25:02Z)
• iMTSP: Solving Min-Max Multiple Traveling Salesman Problem with Imperative Learning [8.747306544853961]
  MTSP(Min-Max Multiple Traveling Salesman)問題の検討 目標は、最長ツアーの長さを最小化しながら、各エージェントが一括してすべての都市を訪れるツアーを見つけることである。 我々は、命令型MTSP(iMTSP)と呼ばれる、新しい自己教師型双方向エンドツーエンド学習フレームワークを導入する。
  論文  参考訳（メタデータ） (2024-05-01T02:26:13Z)
• MASP: Scalable GNN-based Planning for Multi-Agent Navigation [17.788592987873905]
  エージェント数の多いナビゲーションタスクのための目標条件付き階層型プランナを提案する。 また、グラフニューラルネットワーク(GNN)を活用し、エージェントと目標間の相互作用をモデル化し、目標達成を改善する。 その結果、MASPは古典的な計画ベースの競合やRLベースラインよりも優れていた。
  論文  参考訳（メタデータ） (2023-12-05T06:05:04Z)
• Learning RL-Policies for Joint Beamforming Without Exploration: A Batch Constrained Off-Policy Approach [1.0080317855851213]
  本稿では,ネットワークにおけるパラメータキャンセル最適化の問題点について考察する。 探索と学習のために実世界でアルゴリズムをデプロイすることは、探索せずにデータによって達成できることを示す。
  論文  参考訳（メタデータ） (2023-10-12T18:36:36Z)
• 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)
• Centralized Model and Exploration Policy for Multi-Agent RL [13.661446184763117]
  部分的に観察可能な完全協調型マルチエージェント設定(Dec-POMDP)での強化学習は、現実世界の多くの課題に対処するために使用できる。 Dec-POMDPの現在のRLアルゴリズムは、サンプルの複雑さに悩まされている。 モデルベースアルゴリズムであるMARCOを3つの協調通信タスクで提案し、サンプル効率を最大20倍改善する。
  論文  参考訳（メタデータ） (2021-07-14T00:34:08Z)
• Efficient Model-Based Multi-Agent Mean-Field Reinforcement Learning [89.31889875864599]
  マルチエージェントシステムにおける学習に有効なモデルベース強化学習アルゴリズムを提案する。 我々の理論的な貢献は、MFCのモデルベース強化学習における最初の一般的な後悔の限界である。 コア最適化問題の実用的なパラメトリゼーションを提供する。
  論文  参考訳（メタデータ） (2021-07-08T18:01:02Z)
• Adaptive Stochastic ADMM for Decentralized Reinforcement Learning in Edge Industrial IoT [106.83952081124195]
  強化学習 (Reinforcement Learning, RL) は, 意思決定および最適制御プロセスのための有望な解法として広く研究されている。 本稿では,Adaptive ADMM (asI-ADMM)アルゴリズムを提案する。 実験の結果,提案アルゴリズムは通信コストやスケーラビリティの観点から技術状況よりも優れており,複雑なIoT環境に適応できることがわかった。
  論文  参考訳（メタデータ） (2021-06-30T16:49:07Z)
• Communication-Efficient Distributed Stochastic AUC Maximization with Deep Neural Networks [50.42141893913188]
  本稿では,ニューラルネットワークを用いた大規模AUCのための分散変数について検討する。 我々のモデルは通信ラウンドをはるかに少なくし、理論上はまだ多くの通信ラウンドを必要としています。 いくつかのデータセットに対する実験は、我々の理論の有効性を示し、我々の理論を裏付けるものである。
  論文  参考訳（メタデータ） (2020-05-05T18:08:23Z)
• F2A2: Flexible Fully-decentralized Approximate Actor-critic for Cooperative Multi-agent Reinforcement Learning [110.35516334788687]
  分散マルチエージェント強化学習アルゴリズムは複雑なアプリケーションでは実践的でないことがある。 本稿では,大規模で汎用的なマルチエージェント設定を扱える,柔軟な完全分散型アクター批判型MARLフレームワークを提案する。 当社のフレームワークは,大規模環境におけるスケーラビリティと安定性を実現し,情報伝達を低減できる。
  論文  参考訳（メタデータ） (2020-04-17T14:56:29Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。