論文の概要: Unsupervised Learning for Solving the Travelling Salesman Problem

• arxiv url: http://arxiv.org/abs/2303.10538v2
• Date: Wed, 10 Apr 2024 05:59:10 GMT
• ステータス: 処理完了
• システム内更新日: 2024-04-11 19:55:03.956408
• Title: Unsupervised Learning for Solving the Travelling Salesman Problem
• Title（参考訳）: トラベリングセールスマン問題の解決のための教師なし学習
• Authors: Yimeng Min, Yiwei Bai, Carla P. Gomes,
• Abstract要約: 旅行セールスマン問題(TSP)を解決するための教師なし学習フレームワークUTSPを提案する。 我々は、代理損失を用いてグラフニューラルネットワーク(GNN)を訓練する。GNNは、各エッジが最適経路の一部である確率を表すヒートマップを出力する。 次に、熱マップに基づいて最終予測を生成するために局所探索を適用する。
• 参考スコア（独自算出の注目度）: 28.62497359169851
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We propose UTSP, an unsupervised learning (UL) framework for solving the Travelling Salesman Problem (TSP). We train a Graph Neural Network (GNN) using a surrogate loss. The GNN outputs a heat map representing the probability for each edge to be part of the optimal path. We then apply local search to generate our final prediction based on the heat map. Our loss function consists of two parts: one pushes the model to find the shortest path and the other serves as a surrogate for the constraint that the route should form a Hamiltonian Cycle. Experimental results show that UTSP outperforms the existing data-driven TSP heuristics. Our approach is parameter efficient as well as data efficient: the model takes $\sim$ 10\% of the number of parameters and $\sim$ 0.2\% of training samples compared with reinforcement learning or supervised learning methods.
• Abstract（参考訳）: 本稿では,トラベリングセールスマン問題(TSP)を解決するための,教師なし学習(UL)フレームワークUTSPを提案する。 代理損失を用いてグラフニューラルネットワーク(GNN)を訓練する。 GNNは、各エッジが最適経路の一部である確率を表すヒートマップを出力する。 次に、熱マップに基づいて最終予測を生成するために局所探索を適用する。 我々の損失関数は2つの部分から構成される: 1つは最短経路を見つけるためにモデルをプッシュし、もう1つはルートがハミルトンサイクルを形成するべきであるという制約の代用として機能する。 実験の結果,UTSPは既存のデータ駆動型TSPヒューリスティックよりも優れていた。 我々のアプローチはパラメータ効率とデータ効率である:モデルはパラメータの数を$\sim$10\%、トレーニングサンプルを$\sim$0.2\%、強化学習や教師付き学習法と比較して$\sim$0.2\%を取る。

関連論文リスト

• Finding Hamiltonian cycles with graph neural networks [0.0]
  我々は、ErdHos-Rnyiのランダムグラフ上でハミルトン周期を予測するために、小さなメッセージパスグラフニューラルネットワークを訓練する。 このモデルは、より大きなグラフサイズによく一般化され、元の8倍の大きさのグラフでも妥当な性能を維持する。
  論文  参考訳（メタデータ） (2023-06-10T21:18:31Z)
• TransPath: Learning Heuristics For Grid-Based Pathfinding via Transformers [64.88759709443819]
  探索の効率を顕著に向上させると考えられる,インスタンス依存のプロキシを学習することを提案する。 私たちが最初に学ぶことを提案するプロキシは、補正係数、すなわち、インスタンスに依存しないコスト・ツー・ゴの見積もりと完璧な見積もりの比率である。 第2のプロキシはパス確率であり、グリッドセルが最も短いパスに横たわっている可能性を示している。
  論文  参考訳（メタデータ） (2022-12-22T14:26:11Z)
• Learning to Learn with Generative Models of Neural Network Checkpoints [71.06722933442956]
  ニューラルネットワークのチェックポイントのデータセットを構築し,パラメータの生成モデルをトレーニングする。 提案手法は,幅広い損失プロンプトに対するパラメータの生成に成功している。 我々は、教師付きおよび強化学習における異なるニューラルネットワークアーキテクチャとタスクに本手法を適用した。
  論文  参考訳（メタデータ） (2022-09-26T17:59:58Z)
• Is Stochastic Gradient Descent Near Optimal? [0.0]
  本研究では,多数のサンプルとクエリの総数を用いて,勾配勾配勾配の誤差が小さいことを示す。 このことは、SGDがJoen & Van Roy (arXiv:2203.00246) の情報理論的なサンプル複雑性境界を計算的に効率よく達成していることを示唆している。
  論文  参考訳（メタデータ） (2022-09-18T18:26:43Z)
• Unsupervised Training for Neural TSP Solver [2.9398911304923447]
  本稿では,トラベリングセールスマン問題を解決するための教師なし学習手法を提案する。 我々は、TSPの整数線型プログラムを緩和して、正しいインスタンスラベルを必要としない損失関数を構築する。 私たちのアプローチは、強化学習よりも安定しており、トレーニングも簡単です。
  論文  参考訳（メタデータ） (2022-07-27T17:33:29Z)
• Provably Efficient Offline Reinforcement Learning with Trajectory-Wise Reward [66.81579829897392]
  我々はPessimistic vAlue iteRaTionとrEward Decomposition (PARTED)という新しいオフライン強化学習アルゴリズムを提案する。 PartEDは、最小2乗ベースの報酬再分配を通じて、ステップごとのプロキシ報酬に軌道を分解し、学習したプロキシ報酬に基づいて悲観的な値を実行する。 私たちの知る限りでは、PartEDは、トラジェクティブな報酬を持つ一般のMDPにおいて、証明可能な効率のよい最初のオフラインRLアルゴリズムである。
  論文  参考訳（メタデータ） (2022-06-13T19:11:22Z)
• Dual Lottery Ticket Hypothesis [71.95937879869334]
  Lottery Ticket hypothesis (LTH)は、スパースネットワークトレーニングを調査し、その能力を維持するための新しい視点を提供する。 本稿では,LTHの当選チケットをトレーニング可能なサブネットワークとして,その性能をベンチマークとして検討する。 本稿では,簡単なスパースネットワークトレーニング戦略であるランダムスパースネットワークトランスフォーメーション(RST)を提案し,DLTHを裏付ける。
  論文  参考訳（メタデータ） (2022-03-08T18:06:26Z)
• Distributionally Robust Semi-Supervised Learning Over Graphs [68.29280230284712]
  グラフ構造化データに対する半教師付き学習(SSL)は、多くのネットワークサイエンスアプリケーションに現れる。 グラフ上の学習を効率的に管理するために,近年,グラフニューラルネットワーク(GNN)の変種が開発されている。 実際に成功したにも拘わらず、既存の手法のほとんどは、不確実な結節属性を持つグラフを扱うことができない。 ノイズ測定によって得られたデータに関連する分布の不確実性によっても問題が発生する。 分散ロバストな学習フレームワークを開発し,摂動に対する定量的ロバスト性を示すモデルを訓練する。
  論文  参考訳（メタデータ） (2021-10-20T14:23:54Z)
• A Generative Graph Method to Solve the Travelling Salesman Problem [1.552282932199974]
  我々は,旅行セールスマン問題(TSP)を概ね解決するために,生成的アプローチである新しいグラフ学習ネットワーク(GLN)を提案する。 GLNモデルは、トレーニングデータセットとしてTSPインスタンスのパターンを直接学習し、グラフプロパティをエンコードし、異なるノードの埋め込みをマージして、最適なツアーを出力する。
  論文  参考訳（メタデータ） (2020-07-09T17:23:55Z)
• Fast Learning of Graph Neural Networks with Guaranteed Generalizability: One-hidden-layer Case [93.37576644429578]
  グラフニューラルネットワーク(GNN)は、グラフ構造化データから実際に学習する上で、近年大きな進歩を遂げている。 回帰問題と二項分類問題の両方に隠れ層を持つGNNの理論的に基底的な一般化可能性解析を行う。
  論文  参考訳（メタデータ） (2020-06-25T00:45:52Z)

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

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