論文の概要: Generative Modeling for Robust Deep Reinforcement Learning on the Traveling Salesman Problem

• arxiv url: http://arxiv.org/abs/2508.08718v1
• Date: Tue, 12 Aug 2025 08:04:16 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-13 21:07:34.342805
• Title: Generative Modeling for Robust Deep Reinforcement Learning on the Traveling Salesman Problem
• Title（参考訳）: 旅行セールスマン問題におけるロバストな深層強化学習のための生成モデル
• Authors: Michael Li, Eric Bae, Christopher Haberland, Natasha Jaques,
• Abstract要約: ラストマイル配送を動的にリルートするといった現実世界のロジスティクス問題では、高速な推論時間で解決を要求される。 ニューラルネットワークは、訓練された合成データを超えた一般化に苦慮していることを示す。 我々は,ジェネレーティブ・サンプリング(COGS)を用いたコンビニショナル・オプティマイゼーションを行い,生成型トラベリングセールスマン問題モデルからトレーニングデータをサンプリングした。
• 参考スコア（独自算出の注目度）: 5.627942507745463
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Traveling Salesman Problem (TSP) is a classic NP-hard combinatorial optimization task with numerous practical applications. Classic heuristic solvers can attain near-optimal performance for small problem instances, but become computationally intractable for larger problems. Real-world logistics problems such as dynamically re-routing last-mile deliveries demand a solver with fast inference time, which has led researchers to investigate specialized neural network solvers. However, neural networks struggle to generalize beyond the synthetic data they were trained on. In particular, we show that there exist TSP distributions that are realistic in practice, which also consistently lead to poor worst-case performance for existing neural approaches. To address this issue of distribution robustness, we present Combinatorial Optimization with Generative Sampling (COGS), where training data is sampled from a generative TSP model. We show that COGS provides better data coverage and interpolation in the space of TSP training distributions. We also present TSPLib50, a dataset of realistically distributed TSP samples, which tests real-world generalization ability without conflating this issue with instance size. We evaluate our method on various synthetic datasets as well as TSPLib50, and compare to state-of-the-art neural baselines. We demonstrate that COGS improves distribution robustness, with most performance gains coming from worst-case scenarios.
• Abstract（参考訳）: トラベリングセールスマン問題(TSP)は、古典的なNPハード組合せ最適化タスクであり、多くの実用的応用がある。 古典的ヒューリスティック解法は、小さな問題の場合では最適に近い性能が得られるが、より大きな問題では計算的に難解になる。 ラストマイル配送を動的にリルートするといった現実世界のロジスティクス問題は、高速な推論時間で解決器を必要とするため、研究者は特殊なニューラルネットワーク解決器を調べるようになった。 しかし、ニューラルネットワークは、訓練された合成データを超えた一般化に苦慮している。 特に、実際に現実的なTSP分布が存在することが示され、既存のニューラルネットワークに対する最悪の性能が一貫して低下している。 分散ロバスト性の問題に対処するために,生成的TSPモデルからトレーニングデータをサンプリングする,ジェネレーティブサンプリングを用いたコンビネーティブ最適化(COGS)を提案する。 我々は,TSPトレーニング分布の空間において,COGSがより良いデータカバレッジと補間を提供することを示す。 また,現実的に分散されたTSPサンプルのデータセットであるTSPLib50を,この問題をインスタンスサイズと混同することなく実世界の一般化能力をテストする。 我々は、TSPLib50と同様に、様々な合成データセット上で評価を行い、最先端の神経ベースラインと比較した。 我々はCOGSが分布の堅牢性を改善することを実証し、ほとんどの性能は最悪のシナリオによるものであることを示した。

関連論文リスト

• SimpleDeepSearcher: Deep Information Seeking via Web-Powered Reasoning Trajectory Synthesis [89.99161034065614]
  Retrieval-augmented Generation (RAG) システムは複雑なディープ検索シナリオにおいて高度な大規模言語モデル(LLM)を持つ。 既存のアプローチでは、高品質なトレーニングトラジェクトリが欠如し、分散ミスマッチに苦しむ、重要な制限に直面しています。 本稿では,複雑なトレーニングパラダイムではなく,戦略的データエンジニアリングによるギャップを埋めるフレームワークであるSimpleDeepSearcherを紹介する。
  論文  参考訳（メタデータ） (2025-05-22T16:05:02Z)
• Learning-Based TSP-Solvers Tend to Be Overly Greedy [8.79364699260219]
  本研究では, ランダムに生成した学習型解法の性質を検証するため, 最近傍密度と呼ばれる統計的尺度を構築した。 学習に基づく解法の性能が、そのような拡張データに大きく依存していることを検証する。 要するに、学習ベースのTSPソルバの限界は、過度に欲求的になりがちであり、AIを活用した最適化ソルバに深く影響する可能性がある。
  論文  参考訳（メタデータ） (2025-02-02T12:06:13Z)
• DeepONet as a Multi-Operator Extrapolation Model: Distributed Pretraining with Physics-Informed Fine-Tuning [6.635683993472882]
  マルチオペレータ学習を実現するためのファインチューニング手法を提案する。 本手法は,事前学習における各種演算子からのデータを分散学習と組み合わせ,物理インフォームド手法によりゼロショット微調整が可能となる。
  論文  参考訳（メタデータ） (2024-11-11T18:58:46Z)
• An Edge-Aware Graph Autoencoder Trained on Scale-Imbalanced Data for Traveling Salesman Problems [22.792870849003137]
  本研究では、トラベリングセールスマン問題(TSP)を解決するためのデータ駆動グラフ表現学習法を提案する。 残留ゲートエンコーダは遅延エッジ埋め込みを学習するために訓練され、次いでエッジ中心のデコーダでリンク予測をエンドツーエンドに出力する。 実験結果から,提案したエッジ対応グラフオートエンコーダモデルにより,高い競合性能が得られた。
  論文  参考訳（メタデータ） (2023-10-10T11:42:49Z)
• Towards a Better Theoretical Understanding of Independent Subnetwork Training [56.24689348875711]
  独立サブネットワークトレーニング(IST)の理論的考察 ISTは、上記の問題を解決するための、最近提案され、非常に効果的である。 圧縮通信を用いた分散手法など,ISTと代替手法の基本的な違いを同定する。
  論文  参考訳（メタデータ） (2023-06-28T18:14:22Z)
• Pointerformer: Deep Reinforced Multi-Pointer Transformer for the Traveling Salesman Problem [67.32731657297377]
  トラベリングセールスマン問題(TSP)は、もともと輸送と物流の領域で発生した古典的な経路最適化問題である。 近年, 深層強化学習は高い推論効率のため, TSP の解法として採用されている。 本稿では,多点変換器をベースとした新しいエンドツーエンドDRL手法であるPointerformerを提案する。
  論文  参考訳（メタデータ） (2023-04-19T03:48:32Z)
• Truncated tensor Schatten p-norm based approach for spatiotemporal traffic data imputation with complicated missing patterns [77.34726150561087]
  本研究は, モード駆動繊維による3症例の欠失を含む, 4症例の欠失パターンについて紹介する。 本モデルでは, 目的関数の非性にもかかわらず, 乗算器の交互データ演算法を統合することにより, 最適解を導出する。
  論文  参考訳（メタデータ） (2022-05-19T08:37:56Z)
• Generalization of Neural Combinatorial Solvers Through the Lens of Adversarial Robustness [68.97830259849086]
  ほとんどのデータセットは単純なサブプロブレムのみをキャプチャし、おそらくは突発的な特徴に悩まされる。 本研究では, 局所的な一般化特性である対向ロバスト性について検討し, 厳密でモデル固有な例と突発的な特徴を明らかにする。 他のアプリケーションとは異なり、摂動モデルは知覚できないという主観的な概念に基づいて設計されているため、摂動モデルは効率的かつ健全である。 驚くべきことに、そのような摂動によって、十分に表現力のあるニューラルソルバは、教師あり学習で共通する正確さと悪質さのトレードオフの限界に悩まされない。
  論文  参考訳（メタデータ） (2021-10-21T07:28:11Z)
• Learning the Travelling Salesperson Problem Requires Rethinking Generalization [9.176056742068813]
  トラベリングセールスパーソン問題(TSP)のようなグラフ最適化問題に対するニューラルネットワークソルバのエンドツーエンドトレーニングは近年,関心が高まっている。 最先端の学習駆動アプローチは、自明に小さなサイズで訓練された場合、古典的な解法と密接に関係するが、実践的な規模で学習ポリシーを大規模に一般化することはできない。 この研究は、トレーニングで見られるものよりも大きいインスタンスへの一般化を促進する、原則化されたバイアス、モデルアーキテクチャ、学習アルゴリズムを特定するために、最近の論文を統一するエンドツーエンドのニューラルネットワークパイプラインを提示している。
  論文  参考訳（メタデータ） (2020-06-12T10:14:15Z)

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

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