論文の概要: An Efficient Diffusion-based Non-Autoregressive Solver for Traveling Salesman Problem

• arxiv url: http://arxiv.org/abs/2501.13767v1
• Date: Thu, 23 Jan 2025 15:47:04 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-24 15:57:37.229939
• Title: An Efficient Diffusion-based Non-Autoregressive Solver for Traveling Salesman Problem
• Title（参考訳）: 効率的な拡散型非自己回帰解法によるトラベリングセールスマン問題の解法
• Authors: Mingzhao Wang, You Zhou, Zhiguang Cao, Yubin Xiao, Xuan Wu, Wei Pang, Yuan Jiang, Hui Yang, Peng Zhao, Yuanshu Li,
• Abstract要約: 本稿では,トラベリングセールスマン問題に適した効率の良い反復型拡散モデルであるDEITSPを提案する。 本稿では,制御された離散雑音付加プロセスと自己整合性強化を統合した一段階拡散モデルを提案する。 また、ノードとエッジのモダリティから特徴の抽出と融合を促進するために、デュアルモダリティグラフ変換器を設計する。
• 参考スコア（独自算出の注目度）: 21.948190231334088
• License:
• Abstract: Recent advances in neural models have shown considerable promise in solving Traveling Salesman Problems (TSPs) without relying on much hand-crafted engineering. However, while non-autoregressive (NAR) approaches benefit from faster inference through parallelism, they typically deliver solutions of inferior quality compared to autoregressive ones. To enhance the solution quality while maintaining fast inference, we propose DEITSP, a diffusion model with efficient iterations tailored for TSP that operates in a NAR manner. Firstly, we introduce a one-step diffusion model that integrates the controlled discrete noise addition process with self-consistency enhancement, enabling optimal solution prediction through simultaneous denoising of multiple solutions. Secondly, we design a dual-modality graph transformer to bolster the extraction and fusion of features from node and edge modalities, while further accelerating the inference with fewer layers. Thirdly, we develop an efficient iterative strategy that alternates between adding and removing noise to improve exploration compared to previous diffusion methods. Additionally, we devise a scheduling framework to progressively refine the solution space by adjusting noise levels, facilitating a smooth search for optimal solutions. Extensive experiments on real-world and large-scale TSP instances demonstrate that DEITSP performs favorably against existing neural approaches in terms of solution quality, inference latency, and generalization ability. Our code is available at $\href{https://github.com/DEITSP/DEITSP}{https://github.com/DEITSP/DEITSP}$.
• Abstract（参考訳）: ニューラルモデルにおける最近の進歩は、手作りの工学に頼らずに、旅行セールスマン問題(TSP)を解くことにかなり有望であることを示している。 しかしながら、非自己回帰的(NAR)アプローチは、並列性による推論の高速化から恩恵を受けるが、一般的には、自己回帰的アプローチに比べて品質が劣るソリューションを提供する。 高速な推論を維持しながら解の質を高めるために,提案する分散モデルDEITSPを提案する。 まず,制御された離散雑音付加プロセスと自己整合性強化を統合した一段階拡散モデルを導入し,複数解の同時分解による最適解予測を実現する。 第二に、ノードとエッジのモダリティから特徴の抽出と融合を促進し、さらに少ない層で推論を加速するデュアルモダリティグラフ変換器を設計する。 第3に,従来の拡散法に比べて探索性を高めるため,ノイズの追加と除去を交互に行う効率的な反復法を開発する。 さらに,ノイズレベルを調整し,最適解のスムーズな探索を容易にすることで,解空間を段階的に洗練するスケジューリングフレームワークを考案した。 実世界のTSPインスタンスと大規模TSPインスタンスの大規模な実験により、DeITSPはソリューションの品質、推論レイテンシ、一般化能力の観点から、既存のニューラルネットワークアプローチに対して好適に機能することが示された。 私たちのコードは$\href{https://github.com/DEITSP/DEITSP}{https://github.com/DEITSP/DEITSP}$で利用可能です。

関連論文リスト

• DiP-GO: A Diffusion Pruner via Few-step Gradient Optimization [22.546989373687655]
  本稿では,よりインテリジェントで微分可能なプルーナーを用いて,効率的な拡散モデルを導出する新しいプルーニング法を提案する。 提案手法はSD-1.5の4.4倍の高速化を実現し,従来の最先端手法よりも優れていた。
  論文  参考訳（メタデータ） (2024-10-22T12:18:24Z)
• DiffSG: A Generative Solver for Network Optimization with Diffusion Model [75.27274046562806]
  拡散生成モデルはより広い範囲の解を考えることができ、学習パラメータによるより強力な一般化を示す。 拡散生成モデルの本質的な分布学習を利用して高品質な解を学習する新しいフレームワークを提案する。
  論文  参考訳（メタデータ） (2024-08-13T07:56:21Z)
• CoSIGN: Few-Step Guidance of ConSIstency Model to Solve General INverse Problems [3.3969056208620128]
  我々は, 高い復元品質を維持しつつ, 推論ステップの境界を1-2 NFEに推し進めることを提案する。 本手法は拡散型逆問題解法における新しい最先端技術を実現する。
  論文  参考訳（メタデータ） (2024-07-17T15:57:50Z)
• DiffuSolve: Diffusion-based Solver for Non-convex Trajectory Optimization [9.28162057044835]
  最適軌道局所は非線形および高次元力学系において計算コストが高い。 本稿では,非次元オプティマ問題に対するDiffuに基づく一般モデルを提案する。 また,新たな制約付き拡散モデルであるDiff+を提案する。
  論文  参考訳（メタデータ） (2024-02-22T03:52:17Z)
• Gradient Sparsification for Efficient Wireless Federated Learning with Differential Privacy [25.763777765222358]
  フェデレートラーニング(FL)により、分散クライアントは、生データを互いに共有することなく、機械学習モデルを協調的にトレーニングできる。 モデルのサイズが大きくなるにつれて、送信帯域の制限によるトレーニングのレイテンシが低下し、個人情報が劣化すると同時に、差分プライバシ(DP)保護を使用する。 我々は、収束性能を犠牲にすることなく、トレーニング効率を向上させるために、FLフレームワーク無線チャネルのスペース化を提案する。
  論文  参考訳（メタデータ） (2023-04-09T05:21:15Z)
• Learning to Optimize Permutation Flow Shop Scheduling via Graph-based Imitation Learning [70.65666982566655]
  置換フローショップスケジューリング(PFSS)は製造業で広く使われている。 我々は,より安定かつ正確に収束を加速する専門家主導の模倣学習を通じてモデルを訓練することを提案する。 我々のモデルのネットワークパラメータはわずか37%に減少し、エキスパートソリューションに対する我々のモデルの解のギャップは平均6.8%から1.3%に減少する。
  論文  参考訳（メタデータ） (2022-10-31T09:46:26Z)
• Neural Stochastic Dual Dynamic Programming [99.80617899593526]
  我々は、問題インスタンスを断片的線形値関数にマッピングすることを学ぶトレーニング可能なニューラルモデルを導入する。 $nu$-SDDPは、ソリューションの品質を犠牲にすることなく、問題解決コストを大幅に削減できる。
  論文  参考訳（メタデータ） (2021-12-01T22:55:23Z)
• Joint inference and input optimization in equilibrium networks [68.63726855991052]
  ディープ均衡モデル(Deep equilibrium model)は、従来のネットワークの深さを予測し、代わりに単一の非線形層の固定点を見つけることによってネットワークの出力を計算するモデルのクラスである。 この2つの設定の間には自然なシナジーがあることが示されています。 この戦略は、生成モデルのトレーニングや、潜時符号の最適化、デノベートやインペインティングといった逆問題に対するトレーニングモデル、対逆トレーニング、勾配に基づくメタラーニングなど、様々なタスクにおいて実証される。
  論文  参考訳（メタデータ） (2021-11-25T19:59:33Z)
• Non-Gradient Manifold Neural Network [79.44066256794187]
  ディープニューラルネットワーク(DNN)は通常、勾配降下による最適化に数千のイテレーションを要します。 非次最適化に基づく新しい多様体ニューラルネットワークを提案する。
  論文  参考訳（メタデータ） (2021-06-15T06:39:13Z)
• Communication-Efficient Distributed Stochastic AUC Maximization with Deep Neural Networks [50.42141893913188]
  本稿では,ニューラルネットワークを用いた大規模AUCのための分散変数について検討する。 我々のモデルは通信ラウンドをはるかに少なくし、理論上はまだ多くの通信ラウンドを必要としています。 いくつかのデータセットに対する実験は、我々の理論の有効性を示し、我々の理論を裏付けるものである。
  論文  参考訳（メタデータ） (2020-05-05T18:08:23Z)

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

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