論文の概要: GELD: A Unified Neural Model for Efficiently Solving Traveling Salesman Problems Across Different Scales

• arxiv url: http://arxiv.org/abs/2506.06634v1
• Date: Sat, 07 Jun 2025 03:00:05 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-10 21:10:47.044339
• Title: GELD: A Unified Neural Model for Efficiently Solving Traveling Salesman Problems Across Different Scales
• Title（参考訳）: GELD: 異なるスケールでのトラベリングセールスマン問題の効率的な解決のための統一ニューラルモデル
• Authors: Yubin Xiao, Di Wang, Rui Cao, Xuan Wu, Boyang Li, You Zhou,
• Abstract要約: 本稿では,旅行セールスマン問題の解法として,GELDというニューラルネットワークを用いた新しい解法を提案する。 GELDは軽量なグローバルビュー推論(GE)とヘビーウェイトなローカルビューデコーダ(LD)を統合し、埋め込み表現を充実させる。 合成データセットと実世界のデータセットの両方で実施された大規模な実験は、GELDが7つの最先端モデルより優れていることを示した。
• 参考スコア（独自算出の注目度）: 16.177833864654172
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Traveling Salesman Problem (TSP) is a well-known combinatorial optimization problem with broad real-world applications. Recent advancements in neural network-based TSP solvers have shown promising results. Nonetheless, these models often struggle to efficiently solve both small- and large-scale TSPs using the same set of pre-trained model parameters, limiting their practical utility. To address this issue, we introduce a novel neural TSP solver named GELD, built upon our proposed broad global assessment and refined local selection framework. Specifically, GELD integrates a lightweight Global-view Encoder (GE) with a heavyweight Local-view Decoder (LD) to enrich embedding representation while accelerating the decision-making process. Moreover, GE incorporates a novel low-complexity attention mechanism, allowing GELD to achieve low inference latency and scalability to larger-scale TSPs. Additionally, we propose a two-stage training strategy that utilizes training instances of different sizes to bolster GELD's generalization ability. Extensive experiments conducted on both synthetic and real-world datasets demonstrate that GELD outperforms seven state-of-the-art models considering both solution quality and inference speed. Furthermore, GELD can be employed as a post-processing method to significantly elevate the quality of the solutions derived by existing neural TSP solvers via spending affordable additional computing time. Notably, GELD is shown as capable of solving TSPs with up to 744,710 nodes, first-of-its-kind to solve this large size TSP without relying on divide-and-conquer strategies to the best of our knowledge.
• Abstract（参考訳）: トラベリングセールスマン問題 (TSP) は、幅広い現実世界の応用においてよく知られた組合せ最適化問題である。 ニューラルネットワークベースのTSPソルバの最近の進歩は、有望な結果を示している。 しかしながら、これらのモデルはしばしば、訓練済みのモデルパラメータのセットと同じセットを使用して、小規模と大規模両方のTSPを効率的に解決し、実用性を制限するのに苦労する。 この問題に対処するために,提案したグローバルアセスメントと改良された局所選択フレームワークに基づいて,GELDと呼ばれる新しいニューラルネットワークTSPソルバを導入する。 具体的には、GELDは軽量なグローバルビューエンコーダ(GE)とヘビーウェイトなローカルビューデコーダ(LD)を統合して、意思決定プロセスを加速しながら埋め込み表現を充実させる。 さらに、GELDには新しい低複雑さアテンション機構が組み込まれており、GELDはより大規模なTSPに対して低推論レイテンシとスケーラビリティを実現することができる。 さらに,GELDの一般化能力を高めるために,異なるサイズのトレーニングインスタンスを利用する2段階のトレーニング戦略を提案する。 合成データセットと実世界のデータセットの両方で実施された大規模な実験により、GELDはソリューションの品質と推論速度の両方を考慮して、7つの最先端モデルより優れていることが示された。 さらに、GELDを処理後方法として使用することで、既存のニューラルネットワークTSPソルバによって導出されるソリューションの品質を大幅に高めることができる。 特に、GELDは最大744,710ノードのTSPを解く能力を示しており、この大きなTSPを私たちの知識を最大限に活用するために、分割とクエリの戦略に頼らずに解決できる。

関連論文リスト

• LocalEscaper: A Weakly-supervised Framework with Regional Reconstruction for Scalable Neural TSP Solvers [14.238953745477193]
  LocalEscaperは、大規模トラベリングセールスマン問題(TSP)のための弱い教師付き学習フレームワークである SLとRLの両方の利点を効果的に組み合わせ、低品質なラベルを持つデータセットの効果的なトレーニングを可能にします。 最大5万の都市でTSPインスタンスを解決し、スケーラビリティと効率のベンチマークを新たに設定する。
  論文  参考訳（メタデータ） (2025-02-18T03:10:27Z)
• Cascaded Large-Scale TSP Solving with Unified Neural Guidance: Bridging Local and Population-based Search [23.528483405321975]
  UNiCSは、旅行セールスマン問題に対する新しい統合神経誘導型カスケード解決器である。 ステート・オブ・ザ・アーティカルなメソッドを一貫して上回り、ランタイムのアドバンテージはさまざまな予算で一貫しています。
  論文  参考訳（メタデータ） (2025-01-24T06:56:27Z)
• 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)
• Instance-Conditioned Adaptation for Large-scale Generalization of Neural Routing Solver [15.842155380912002]
  本稿では,ニューラル・ルーティング・ソルバの大規模一般化のための新しいインスタンス・コンディション・アダプタ・モデルを提案する。 提案手法は,非常に高速な推論時間で有望な結果が得られることを示す。
  論文  参考訳（メタデータ） (2024-05-03T08:00:19Z)
• LD-GAN: Low-Dimensional Generative Adversarial Network for Spectral Image Generation with Variance Regularization [72.4394510913927]
  ディープラーニング法はスペクトル画像(SI)計算タスクの最先端技術である。 GANは、データ分散から学習およびサンプリングすることで、多様な拡張を可能にする。 この種のデータの高次元性は、GANトレーニングの収束を妨げるため、GANベースのSI生成は困難である。 本稿では, オートエンコーダ訓練における低次元表現分散を制御し, GANで生成されたサンプルの多様性を高めるための統計正則化を提案する。
  論文  参考訳（メタデータ） (2023-04-29T00:25:02Z)
• Pointerformer: Deep Reinforced Multi-Pointer Transformer for the Traveling Salesman Problem [67.32731657297377]
  トラベリングセールスマン問題(TSP)は、もともと輸送と物流の領域で発生した古典的な経路最適化問題である。 近年, 深層強化学習は高い推論効率のため, TSP の解法として採用されている。 本稿では,多点変換器をベースとした新しいエンドツーエンドDRL手法であるPointerformerを提案する。
  論文  参考訳（メタデータ） (2023-04-19T03:48:32Z)
• 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)
• Model-Driven Beamforming Neural Networks [47.754731555563836]
  本稿では、一般データおよびモデル駆動ビームフォーミングニューラルネットワーク(BNN)を紹介する。 様々な学習戦略を示し、DLベースのBNNの複雑さの低減についても論じている。 また、BNNの汎用性を向上させるため、トレーニングセットの強化や伝達学習などの強化手法も提供する。
  論文  参考訳（メタデータ） (2020-01-15T12:50:09Z)

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

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