論文の概要: IDEQ: an improved diffusion model for the TSP

• arxiv url: http://arxiv.org/abs/2412.13858v1
• Date: Wed, 18 Dec 2024 13:52:50 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-19 16:48:53.380608
• Title: IDEQ: an improved diffusion model for the TSP
• Title（参考訳）: IDEQ: TSPのための改良された拡散モデル
• Authors: Mickael Basson, Philippe Preux,
• Abstract要約: IDEQは、トラベリングセールスマン問題の制約された構造を活用することで、ソリューションの品質を向上させる。 IDEQ は DIFUSCO や T2TCO に関して, 都市数に比例して, ばらつきが低く, スケールアップも良好である。
• 参考スコア（独自算出の注目度）: 7.297345802761503
• License:
• Abstract: We investigate diffusion models to solve the Traveling Salesman Problem. Building on the recent DIFUSCO and T2TCO approaches, we propose IDEQ. IDEQ improves the quality of the solutions by leveraging the constrained structure of the state space of the TSP. Another key component of IDEQ consists in replacing the last stages of DIFUSCO curriculum learning by considering a uniform distribution over the Hamiltonian tours whose orbits by the 2-opt operator converge to the optimal solution as the training objective. Our experiments show that IDEQ improves the state of the art for such neural network based techniques on synthetic instances. More importantly, our experiments show that IDEQ performs very well on the instances of the TSPlib, a reference benchmark in the TSP community: it closely matches the performance of the best heuristics, LKH3, being even able to obtain better solutions than LKH3 on 2 instances of the TSPlib defined on 1577 and 3795 cities. IDEQ obtains 0.3% optimality gap on TSP instances made of 500 cities, and 0.5% on TSP instances with 1000 cities. This sets a new SOTA for neural based methods solving the TSP. Moreover, IDEQ exhibits a lower variance and better scales-up with the number of cities with regards to DIFUSCO and T2TCO.
• Abstract（参考訳）: トラベリングセールスマン問題を解決するための拡散モデルについて検討する。 近年のDIFUSCOとT2TCOのアプローチに基づいてIDEQを提案する。 IDEQは、TSPの状態空間の制約された構造を活用することで、ソリューションの品質を改善します。 IDEQのもう一つの重要な構成要素は、2オプト作用素による軌道が最適解に収束するハミルトンツアー上の均一分布を考慮することでDIFUSCOカリキュラム学習の最終段階を置き換えることである。 実験の結果,IDEQは合成インスタンスに基づくニューラルネットワーク技術における最先端技術の改善を図っている。 さらに重要なことは、我々の実験は、IDEQがTSPコミュニティのリファレンスベンチマークであるTSPlibのインスタンスで非常によく機能していることを示しています。これは、最高のヒューリスティックであるLKH3のパフォーマンスと密接に一致し、1577年と3795の都市で定義されたTSPlibのインスタンスでLKH3よりも優れたソリューションを得ることができることを示しています。 IDEQは500都市からなるTSPインスタンスで0.3%、1000都市のTSPインスタンスで0.5%の最適性ギャップを得る。 これにより、TSPを解くニューラルネットワークメソッドのための新しいSOTAが設定される。 さらに、IDEQは、DIFUSCOやT2TCOに関して、都市数に比例して、より低いばらつきとスケールアップを示す。

関連論文リスト

• FusionLLM: A Decentralized LLM Training System on Geo-distributed GPUs with Adaptive Compression [55.992528247880685]
  分散トレーニングは、システム設計と効率に関する重要な課題に直面します。 大規模深層ニューラルネットワーク(DNN)のトレーニング用に設計・実装された分散トレーニングシステムFusionLLMを提案する。 本システムと手法は,収束性を確保しつつ,ベースライン法と比較して1.45～9.39倍の高速化を実現可能であることを示す。
  論文  参考訳（メタデータ） (2024-10-16T16:13:19Z)
• Learn to Tour: Operator Design For Solution Feasibility Mapping in Pickup-and-delivery Traveling Salesman Problem [12.34897099691387]
  本稿では,旅行セールスマン問題(TSP)の学習方法を提案する。 1対1のピックアップ・アンド・デリバリノードのシーケンスで一番短いツアーを見つける。 PDTSPでは、各ピックアップノードを対応する配信ノードの前に訪問しなければならないという優先的な制約を満たさなければならない。
  論文  参考訳（メタデータ） (2024-04-17T15:05:51Z)
• Elucidating the solution space of extended reverse-time SDE for diffusion models [54.23536653351234]
  拡散モデル(DM)は、様々な生成的モデリングタスクにおいて強力な画像生成能力を示す。 その主な制限はサンプリング速度の遅いことであり、高品質な画像を生成するには数百から数千のシーケンシャルな機能評価が必要である。 サンプリングプロセスを拡張逆時間SDEとして定式化し、ODEやSDEへの事前探索を統一する。 我々は, 高速かつトレーニング不要なサンプル装置ER-SDE-rsを考案し, 全サンプル装置の最先端性能を実現した。
  論文  参考訳（メタデータ） (2023-09-12T12:27:17Z)
• Building the Bridge of Schr\"odinger: A Continuous Entropic Optimal Transport Benchmark [96.06787302688595]
  提案手法は, 基本真理 OT 解が構成によって知られている確率分布のペアを作成する方法である。 これらのベンチマークペアを使用して、既存のニューラルネットワーク EOT/SB ソルバが実際に EOT ソリューションをどれだけよく計算しているかをテストする。
  論文  参考訳（メタデータ） (2023-06-16T20:03:36Z)
• T-SciQ: Teaching Multimodal Chain-of-Thought Reasoning via Mixed Large Language Model Signals for Science Question Answering [59.63860993280275]
  大規模言語モデル(LLM)は、様々な自然言語処理(NLP)タスクにおいて例外的な性能を示した。 LLM信号を用いた科学質問応答の指導を目的とした,T-SciQと呼ばれる新しい手法を提案する。 提案手法は,ScienceQAベンチマークで96.18%の精度で,最先端のパフォーマンスを実現する。
  論文  参考訳（メタデータ） (2023-05-05T11:56:30Z)
• H-TSP: Hierarchically Solving the Large-Scale Travelling Salesman Problem [11.310986634385742]
  本稿では,大規模トラベリングセールスマン問題(TSP)に対処する階層的強化学習(H-TSP)に基づくエンドツーエンド学習フレームワークを提案する。 我々は,H-TSPがSOTA検索に匹敵する結果が得られることを示し,時間消費を2桁まで削減する(3.32s vs. 395.85s)。 ソリューションの品質に関してはまだSOTAの結果にギャップがあるが、H-TSPは実用的なアプリケーション、特にオンコールルーティングや乗車などの時間に敏感なアプリケーションに有用であると考えている。
  論文  参考訳（メタデータ） (2023-04-19T03:10:30Z)
• DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization [51.517956081644186]
  グラフベースの拡散フレームワークであるDIFUSCOを導入する。 本フレームワークは, NPC問題を離散0, 1ベクトル最適化問題とみなす。 MIS問題に対して、DIFUSCOは、挑戦的なSATLIBベンチマークにおいて、以前の最先端のニューラルソルバよりも優れている。
  論文  参考訳（メタデータ） (2023-02-16T11:13:36Z)
• Learning to Solve Travelling Salesman Problem with Hardness-adaptive Curriculum [42.28343071442175]
  本稿では,既存手法の10倍の精度でインスタンスを生成するハードネス適応型ジェネレータを提案する。 提案手法は, 最適性ギャップの観点から, 最先端モデルに対する大幅な改善を実現する。
  論文  参考訳（メタデータ） (2022-04-07T05:59:05Z)
• Two-Stream Consensus Network: Submission to HACS Challenge 2021 Weakly-Supervised Learning Track [78.64815984927425]
  弱い監督による時間的行動ローカライゼーションの目標は、ビデオの興味ある動作を時間的に特定し、分類することである。 この課題では,2ストリームコンセンサスネットワーク(TSCN)を主要なフレームワークとして採用しています。 この課題では,本手法が今後の学術研究のベースラインとなることを期待して,第2位にランクインした。
  論文  参考訳（メタデータ） (2021-06-21T03:36:36Z)
• Learning to Optimise General TSP Instances [2.6782615615913348]
  トラベリングセールスマン問題(TSP)は古典的な最適化問題である。 ディープラーニングはメタラーニングに成功し、過去の問題解決活動が将来のインスタンスを最適化する方法を学ぶのに役立つ。 本稿では,多種多様なTSP問題を解くための学習に基づく新しいアプローチを提案する。
  論文  参考訳（メタデータ） (2020-10-23T07:37:16Z)
• Towards Feature-free TSP Solver Selection: A Deep Learning Approach [35.05032046810422]
  トラベリングセールスマン問題(TSP)は古典的なNPハード問題であり、多くの分野や産業で広く応用されている。 本稿では,TSPソルバ選択のためのディープラーニングフレームワークであるCTASを提案する。
  論文  参考訳（メタデータ） (2020-06-01T04:48:36Z)

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

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