論文の概要: Pointerformer: Deep Reinforced Multi-Pointer Transformer for the Traveling Salesman Problem

• arxiv url: http://arxiv.org/abs/2304.09407v1
• Date: Wed, 19 Apr 2023 03:48:32 GMT
• ステータス: 処理完了
• システム内更新日: 2023-04-20 15:27:13.957554
• Title: Pointerformer: Deep Reinforced Multi-Pointer Transformer for the Traveling Salesman Problem
• Title（参考訳）: Pointerformer: トラベリングセールスマン問題のためのディープ強化マルチポインタートランス
• Authors: Yan Jin, Yuandong Ding, Xuanhao Pan, Kun He, Li Zhao, Tao Qin, Lei Song, Jiang Bian
• Abstract要約: トラベリングセールスマン問題(TSP)は、もともと輸送と物流の領域で発生した古典的な経路最適化問題である。 近年, 深層強化学習は高い推論効率のため, TSP の解法として採用されている。 本稿では,多点変換器をベースとした新しいエンドツーエンドDRL手法であるPointerformerを提案する。
• 参考スコア（独自算出の注目度）: 67.32731657297377
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Traveling Salesman Problem (TSP), as a classic routing optimization problem originally arising in the domain of transportation and logistics, has become a critical task in broader domains, such as manufacturing and biology. Recently, Deep Reinforcement Learning (DRL) has been increasingly employed to solve TSP due to its high inference efficiency. Nevertheless, most of existing end-to-end DRL algorithms only perform well on small TSP instances and can hardly generalize to large scale because of the drastically soaring memory consumption and computation time along with the enlarging problem scale. In this paper, we propose a novel end-to-end DRL approach, referred to as Pointerformer, based on multi-pointer Transformer. Particularly, Pointerformer adopts both reversible residual network in the encoder and multi-pointer network in the decoder to effectively contain memory consumption of the encoder-decoder architecture. To further improve the performance of TSP solutions, Pointerformer employs both a feature augmentation method to explore the symmetries of TSP at both training and inference stages as well as an enhanced context embedding approach to include more comprehensive context information in the query. Extensive experiments on a randomly generated benchmark and a public benchmark have shown that, while achieving comparative results on most small-scale TSP instances as SOTA DRL approaches do, Pointerformer can also well generalize to large-scale TSPs.
• Abstract（参考訳）: トラベリングセールスマン問題(TSP)は、もともと輸送と物流の領域で発生する古典的な経路最適化問題であり、製造業や生物学など幅広い分野において重要な課題となっている。 近年,高い推論効率のため,深層強化学習(DRL)がTSPの解法として採用されている。 それでも、既存のエンドツーエンドのDRLアルゴリズムは、小さなTSPインスタンスでしかうまく動作せず、メモリ消費が劇的に増加し、計算時間が増大すると共に、大規模に一般化することができない。 本稿では,多点変換器をベースとした新しいエンドツーエンドDRL手法であるPointerformerを提案する。 特に、pointerformerはエンコーダの可逆的残差ネットワークとデコーダのマルチポイントネットワークの両方を採用し、エンコーダ-デコーダアーキテクチャのメモリ消費を効果的に抑えている。 TSPソリューションの性能をさらに向上するため、Pointerformerでは、トレーニングと推論の段階でTSPの対称性を探求する機能拡張手法と、クエリにより包括的なコンテキスト情報を含む拡張されたコンテキスト埋め込みアプローチの両方を採用している。 ランダムに生成されたベンチマークと公開ベンチマークの大規模な実験により、SOTA DRLアプローチと同様に、ほとんどの小規模TSPインスタンスで比較結果が得られたが、Pointerformerは大規模TSPにもうまく一般化できることを示した。

関連論文リスト

• Deep Reinforcement Learning for Traveling Purchaser Problems [63.37136587778153]
  旅行購入問題(TPP)は幅広いアプリケーションにおいて重要な最適化問題である。 本稿では,ルート構築と購入計画を個別に扱う,深層強化学習(DRL)に基づく新しいアプローチを提案する。 メタラーニング戦略を導入することで、大規模なTPPインスタンス上で安定してポリシーネットワークをトレーニングすることができる。
  論文  参考訳（メタデータ） (2024-04-03T05:32:10Z)
• Less Is More - On the Importance of Sparsification for Transformers and Graph Neural Networks for TSP [8.317022421446639]
  本稿では,旅行セールスマン問題(TSP)の最も関連性の高い部分のみにエンコーダを集中させるデータ前処理手法を提案する。 本稿では,GNNの適切なスパーシフィケーションとアンサンブルによって,アーキテクチャ全体の性能が大幅に向上することを示す。
  論文  参考訳（メタデータ） (2024-03-25T20:16:16Z)
• Stop Regressing: Training Value Functions via Classification for Scalable Deep RL [109.44370201929246]
  分類的クロスエントロピーを用いた値関数のトレーニングにより,様々な領域における性能とスケーラビリティが向上することを示す。 例えば、SoftMoEによるAtari 2600ゲームでのシングルタスクRL、大規模ResNetによるAtariでのマルチタスクRL、Q-トランスフォーマーによるロボット操作、検索なしでチェスをプレイする、高容量トランスフォーマーによる言語エージェントWordleタスクなどがある。
  論文  参考訳（メタデータ） (2024-03-06T18:55:47Z)
• RegFormer: An Efficient Projection-Aware Transformer Network for Large-Scale Point Cloud Registration [73.69415797389195]
  本稿では,大規模クラウドアライメントのためのエンドツーエンドトランス (RegFormer) ネットワークを提案する。 具体的には、プロジェクション対応階層変換器を提案し、長距離依存を捕捉し、外乱をフィルタする。 我々の変圧器は線形複雑であり、大規模シーンでも高い効率が保証される。
  論文  参考訳（メタデータ） (2023-03-22T08:47:37Z)
• Iterative Soft Shrinkage Learning for Efficient Image Super-Resolution [91.3781512926942]
  画像超解像(SR)は、CNNからトランスフォーマーアーキテクチャへの広範なニューラルネットワーク設計を目撃している。 本研究は,市販のネットワーク設計を生かし,基礎となる計算オーバーヘッドを低減するため,超高解像度イテレーションにおけるネットワークプルーニングの可能性について検討する。 本研究では, ランダムネットワークのスパース構造を最適化し, 重要でない重みを小さめに微調整することにより, 反復型軟収縮率(ISS-P)法を提案する。
  論文  参考訳（メタデータ） (2023-03-16T21:06:13Z)
• 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)
• Improving Generalization of Deep Reinforcement Learning-based TSP Solvers [19.29028564568974]
  本稿では,ディープラーニングアーキテクチャとDRL学習方法を含むMAGICという新しいアプローチを提案する。 マルチレイヤパーセプトロン,グラフニューラルネットワーク,アテンションモデルを統合したアーキテクチャでは,旅行セールスマンソリューションを逐次生成するポリシを定義している。 1) DRLポリシー更新をローカル検索とインターリーブし(新しいローカル検索技術を用いて)、(2) 新たなシンプルなベースラインを使用し、(3) 勾配学習を適用した。
  論文  参考訳（メタデータ） (2021-10-06T15:16:19Z)
• Learning to Optimise General TSP Instances [2.6782615615913348]
  トラベリングセールスマン問題(TSP)は古典的な最適化問題である。 ディープラーニングはメタラーニングに成功し、過去の問題解決活動が将来のインスタンスを最適化する方法を学ぶのに役立つ。 本稿では,多種多様なTSP問題を解くための学習に基づく新しいアプローチを提案する。
  論文  参考訳（メタデータ） (2020-10-23T07:37:16Z)
• OverNet: Lightweight Multi-Scale Super-Resolution with Overscaling Network [3.6683231417848283]
  SISRを任意のスケールで1つのモデルで解くための,深層でも軽量な畳み込みネットワークであるOverNetを紹介した。 我々のネットワークは、従来の手法よりも少ないパラメータを使用しながら、標準ベンチマークにおいて、過去の最先端結果よりも優れていることを示す。
  論文  参考訳（メタデータ） (2020-08-05T22:10:29Z)

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

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