論文の概要: Small Shifts, Large Gains: Unlocking Traditional TSP Heuristic Guided-Sampling via Unsupervised Neural Instance Modification

• arxiv url: http://arxiv.org/abs/2602.00580v1
• Date: Sat, 31 Jan 2026 07:47:48 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-03 19:28:33.266276
• Title: Small Shifts, Large Gains: Unlocking Traditional TSP Heuristic Guided-Sampling via Unsupervised Neural Instance Modification
• Title（参考訳）: 小シフト, 大規模利得: 教師なしニューラルインスタンス修正による従来のTSPヒューリスティックガイドサンプリングの解錠
• Authors: Wei Huang, Hanchen Wang, Dong Wen, Wenjie Zhang,
• Abstract要約: トラベリングセールスマン問題(TSP)は、ルート計画において最も代表的なNPハード問題の一つである。 伝統的なツアーコンストラクタは計算的に効率的であり、非常に実用的であるが、その決定論的行動は探索を制限し、しばしば局所最適化につながる。 我々は,従来の決定論的ツアーコンストラクタにガイドサンプリング機能を持たせる新しいインスタンス修正フレームワークであるTSP-MDFを提案する。
• 参考スコア（独自算出の注目度）: 11.245517821932152
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Traveling Salesman Problem (TSP) is one of the most representative NP-hard problems in route planning and a long-standing benchmark in combinatorial optimization. Traditional heuristic tour constructors, such as Farthest or Nearest Insertion, are computationally efficient and highly practical, but their deterministic behavior limits exploration and often leads to local optima. In contrast, neural-based heuristic tour constructors alleviate this issue through guided-sampling and typically achieve superior solution quality, but at the cost of extensive training and reliance on ground-truth supervision, hindering their practical use. To bridge this gap, we propose TSP-MDF, a novel instance modification framework that equips traditional deterministic heuristic tour constructors with guided-sampling capability. Specifically, TSP-MDF introduces a neural-based instance modifier that strategically shifts node coordinates to sample multiple modified instances, on which the base traditional heuristic tour constructor constructs tours that are mapped back to the original instance, allowing traditional tour constructors to explore higher-quality tours and escape local optima. At the same time, benefiting from our instance modification formulation, the neural-based instance modifier can be trained efficiently without any ground-truth supervision, ensuring the framework maintains practicality. Extensive experiments on large-scale TSP benchmarks and real-world benchmarks demonstrate that TSP-MDF significantly improves the performance of traditional heuristics tour constructors, achieving solution quality comparable to neural-based heuristic tour constructors, but with an extremely short training time.
• Abstract（参考訳）: トラベリングセールスマン問題(TSP)はルート計画における最も代表的なNPハード問題の1つであり、組合せ最適化における長年のベンチマークである。 FarthestやNearest Insertionのような伝統的なヒューリスティックなツアーコンストラクタは、計算的に効率的であり、非常に実用的であるが、その決定論的行動は探索を制限し、しばしば局所的な最適化につながる。 対照的に、ニューラルネットワークによるヒューリスティックなツアーコンストラクタは、ガイドサンプリングによってこの問題を緩和し、ソリューションの品質を向上するが、大規模なトレーニングと地道監督への依存により、彼らの実践的使用を妨げている。 このギャップを埋めるために、従来の決定論的ヒューリスティックツアーコンストラクタにガイドサンプリング機能を持たせる新しいインスタンス修正フレームワークであるTSP-MDFを提案する。 具体的には、TSP-MDFは、ノード座標を戦略的に複数の修正されたインスタンスにシフトさせるニューラルベースのインスタンス修飾器を導入し、そこでは、従来のヒューリスティックツアーコンストラクタが元のインスタンスにマップされたツアーを構築し、従来のツアーコンストラクタが高品質なツアーを探索し、ローカルオプティマから逃れることを可能にする。 同時に、私たちのインスタンス修正の定式化の恩恵を受けながら、ニューラルネットワークベースのインスタンス修飾器は、基礎的な監督なしに効率的に訓練することができ、フレームワークが実用性を維持することを保証する。 大規模TSPベンチマークと実世界のベンチマークによる大規模な実験により、TSP-MDFは従来のヒューリスティックスツアーコンストラクタの性能を大幅に改善し、ニューラルベースヒューリスティックツアーコンストラクタに匹敵するソリューション品質を実現するが、非常に短いトレーニング時間で達成できることが示された。

関連論文リスト

• Experts-Guided Unbalanced Optimal Transport for ISP Learning from Unpaired and/or Paired Data [48.3649059876439]
  我々は、任意のISPアーキテクチャをペアモードとペアモードの両方でトレーニングできる教師なしのトレーニングフレームワークを導入する。 我々のフレームワークは、ターゲットのsRGBデータにおける外れ値に対して堅牢性を提供し、マップに著しくコストがかかる非定型サンプルを割引することができる。 実験の結果、我々のフレームワークは、ペアリングモードで訓練された場合、全てのメトリクスで元のペアリングメソッドのパフォーマンスを上回るが、未ペアリングモードは競合する量的および質的なパフォーマンスを同時に達成し、場合によっては、元のペアリングされたメソッドを上回っていることがわかった。
  論文  参考訳（メタデータ） (2025-12-05T11:27:36Z)
• TuckA: Hierarchical Compact Tensor Experts for Efficient Fine-Tuning [83.93651411533533]
  4つのキー特性を持つTucker Adaptation(TuckA)を導入する。 我々は,ルータのパラメータサイズを$L$の係数で削減する,効率的なバッチレベルルーティング機構を開発した。 自然言語理解、画像分類、数学的推論におけるベンチマーク実験は、TuckAの有効性を物語っている。
  論文  参考訳（メタデータ） (2025-11-10T09:03:16Z)
• Sculpting Features from Noise: Reward-Guided Hierarchical Diffusion for Task-Optimal Feature Transformation [18.670626228472877]
  DIFFTは報酬誘導型生成タスクとしてフィーチャートランスフォーメーションを再定義する。 構造的かつ離散的な特徴を生成し、機能内依存関係を保持しながら、並列な機能間生成を可能にする。 予測精度とロバスト性において、最先端のベースラインを一貫して上回り、トレーニングや推論時間を大幅に低下させる。
  論文  参考訳（メタデータ） (2025-05-21T06:18:42Z)
• Tuning-Free Structured Sparse PCA via Deep Unfolding Networks [5.931547772157972]
  教師なし特徴選択(UFS)のための新しいタイプのスパース主成分分析(PCA)を提案する。 解釈可能な深層展開ネットワークを使用して、反復最適化ステップをトレーニング可能なニューラルネットワークに変換する。 この革新は、従来の手法の経験的チューニング要求を効果的に回避し、正規化パラメータの自動学習を可能にする。
  論文  参考訳（メタデータ） (2025-02-28T08:32:51Z)
• End-to-End Meta-Bayesian Optimisation with Transformer Neural Processes [52.818579746354665]
  本稿では,ニューラルネットワークを一般化し,トランスフォーマーアーキテクチャを用いて獲得関数を学習する,エンド・ツー・エンドの差別化可能な最初のメタBOフレームワークを提案する。 我々は、この強化学習(RL)によるエンドツーエンドのフレームワークを、ラベル付き取得データの欠如に対処できるようにします。
  論文  参考訳（メタデータ） (2023-05-25T10:58:46Z)
• Pointerformer: Deep Reinforced Multi-Pointer Transformer for the Traveling Salesman Problem [67.32731657297377]
  トラベリングセールスマン問題(TSP)は、もともと輸送と物流の領域で発生した古典的な経路最適化問題である。 近年, 深層強化学習は高い推論効率のため, TSP の解法として採用されている。 本稿では,多点変換器をベースとした新しいエンドツーエンドDRL手法であるPointerformerを提案する。
  論文  参考訳（メタデータ） (2023-04-19T03:48:32Z)

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

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