論文の概要: CARSS: Cooperative Attention-guided Reinforcement Subpath Synthesis for
Solving Traveling Salesman Problem
- arxiv url: http://arxiv.org/abs/2312.15412v1
- Date: Sun, 24 Dec 2023 05:25:43 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-27 18:01:29.642571
- Title: CARSS: Cooperative Attention-guided Reinforcement Subpath Synthesis for
Solving Traveling Salesman Problem
- Title(参考訳): CARSS:旅行セールスマン問題の解決のための協調注意誘導強化サブパス合成
- Authors: Yuchen Shi, Congying Han, Tiande Guo
- Abstract要約: 本稿では,旅行セールスマン問題(TSP)に対処する新しいアプローチであるCARSSを紹介する。
CARSSはTSP解決プロセスを「サブパス生成」と「サブパス統合」の2つの異なる相乗的ステップに分解する
実証実験により、CARSSは単一エージェントの代替よりも優れていることが示された。
- 参考スコア(独自算出の注目度): 4.190087134771218
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper introduces CARSS (Cooperative Attention-guided Reinforcement
Subpath Synthesis), a novel approach to address the Traveling Salesman Problem
(TSP) by leveraging cooperative Multi-Agent Reinforcement Learning (MARL).
CARSS decomposes the TSP solving process into two distinct yet synergistic
steps: "subpath generation" and "subpath merging." In the former, a cooperative
MARL framework is employed to iteratively generate subpaths using multiple
agents. In the latter, these subpaths are progressively merged to form a
complete cycle. The algorithm's primary objective is to enhance efficiency in
terms of training memory consumption, testing time, and scalability, through
the adoption of a multi-agent divide and conquer paradigm. Notably, attention
mechanisms play a pivotal role in feature embedding and parameterization
strategies within CARSS. The training of the model is facilitated by the
independent REINFORCE algorithm. Empirical experiments reveal CARSS's
superiority compared to single-agent alternatives: it demonstrates reduced GPU
memory utilization, accommodates training graphs nearly 2.5 times larger, and
exhibits the potential for scaling to even more extensive problem sizes.
Furthermore, CARSS substantially reduces testing time and optimization gaps by
approximately 50% for TSP instances of up to 1000 vertices, when compared to
standard decoding methods.
- Abstract(参考訳): 本稿では, 協調型マルチエージェント強化学習(MARL)を活用して, トラベリングセールスマン問題(TSP)に対処する新しいアプローチであるCARSS(Cooperative Attention-guided Reinforcement Subpath Synthesis)を紹介する。
cars は tsp の解法を "subpath generation" と "subpath merge" の2つの異なる相乗的ステップに分解する。
前者では、協調的なMARLフレームワークを使用して、複数のエージェントを用いてサブパスを反復的に生成する。
後者では、これらのサブパスは徐々に統合され、完全なサイクルを形成する。
このアルゴリズムの主な目的は、マルチエージェント分割計算パラダイムを採用することにより、メモリ消費、テスト時間、スケーラビリティのトレーニングにおける効率性を高めることである。
特に注意機構は、CARSS内の特徴埋め込みとパラメータ化戦略において重要な役割を果たす。
モデルのトレーニングは、独立したREINFORCEアルゴリズムによって促進される。
これはGPUメモリ使用量の削減を示し、トレーニンググラフを2.5倍の規模に収容し、さらに広範な問題サイズへのスケーリングの可能性を示している。
さらにCARSSは、標準的な復号法と比較して、最大1000頂点のTSPインスタンスに対して、テスト時間と最適化ギャップを約50%削減する。
関連論文リスト
- CHASE: Learning Convex Hull Adaptive Shift for Skeleton-based Multi-Entity Action Recognition [10.045163723630159]
CHASEはサンプル適応正規化法として機能し、濃度間分布の相違を緩和する。
このアプローチはシングルエンタリティのバックボーンにシームレスに適応し、マルチエンタリティシナリオにおけるパフォーマンスを向上します。
論文 参考訳(メタデータ) (2024-10-09T17:55:43Z) - SHERL: Synthesizing High Accuracy and Efficient Memory for Resource-Limited Transfer Learning [63.93193829913252]
本稿では,リソース制限シナリオに対するSHERLと呼ばれる革新的なMETL戦略を提案する。
初期経路では、中間出力は反冗長動作によって統合される。
遅延ルートでは、最小限の遅延事前トレーニングされたレイヤを利用することで、メモリオーバーヘッドのピーク需要を軽減できる。
論文 参考訳(メタデータ) (2024-07-10T10:22:35Z) - Multimodal Learned Sparse Retrieval with Probabilistic Expansion Control [66.78146440275093]
学習検索(LSR)は、クエリとドキュメントを疎語彙ベクトルにエンコードするニューラルネットワークのファミリーである。
テキスト画像検索に焦点をあて,マルチモーダル領域へのLSRの適用について検討する。
LexLIPやSTAIRのような現在のアプローチでは、大規模なデータセットで複雑なマルチステップのトレーニングが必要です。
提案手法は, 密度ベクトルを凍結密度モデルからスパース語彙ベクトルへ効率的に変換する。
論文 参考訳(メタデータ) (2024-02-27T14:21:56Z) - Enhancing Column Generation by Reinforcement Learning-Based
Hyper-Heuristic for Vehicle Routing and Scheduling Problems [9.203492057735074]
カラム生成(CG)は変数を動的に生成することで大規模問題を解決する重要な手法である。
CGの性能を高めるために,RLHHと呼ばれる強化学習に基づく超ヒューリスティックフレームワークを提案する。
論文 参考訳(メタデータ) (2023-10-15T00:05:50Z) - Inter-Cell Network Slicing With Transfer Learning Empowered Multi-Agent
Deep Reinforcement Learning [6.523367518762879]
ネットワークスライシングにより、オペレータは共通の物理インフラ上で多様なアプリケーションを効率的にサポートできる。
ネットワーク展開の恒常的に増大する密度化は、複雑で非自明な細胞間干渉を引き起こす。
複数の深層強化学習(DRL)エージェントを用いたDIRPアルゴリズムを開発し,各セルの資源分配を協調的に最適化する。
論文 参考訳(メタデータ) (2023-06-20T14:14:59Z) - 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) - Travel the Same Path: A Novel TSP Solving Strategy [0.0]
我々は、必要に応じて適切な選択を行う決定論的アルゴリズムを支援する模倣学習フレームワークについて検討する。
我々は、模倣学習フレームワークの下で訓練されたグラフニューラルネットワークの強力な一般化能力を示す。
論文 参考訳(メタデータ) (2022-10-12T03:56:37Z) - Low-rank Optimal Transport: Approximation, Statistics and Debiasing [51.50788603386766]
フロゼットボン2021ローランで提唱された低ランク最適輸送(LOT)アプローチ
LOTは興味のある性質と比較した場合、エントロピー正則化の正当な候補と見なされる。
本稿では,これらの領域のそれぞれを対象とし,計算OTにおける低ランクアプローチの影響を補強する。
論文 参考訳(メタデータ) (2022-05-24T20:51:37Z) - Decoupled and Memory-Reinforced Networks: Towards Effective Feature
Learning for One-Step Person Search [65.51181219410763]
歩行者検出と識別サブタスクを1つのネットワークで処理するワンステップ方式を開発しました。
現在のワンステップアプローチには2つの大きな課題があります。
本稿では,これらの問題を解決するために,分離メモリ強化ネットワーク(DMRNet)を提案する。
論文 参考訳(メタデータ) (2021-02-22T06:19:45Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。