論文の概要: A Generative Graph Method to Solve the Travelling Salesman Problem

• arxiv url: http://arxiv.org/abs/2007.04949v1
• Date: Thu, 9 Jul 2020 17:23:55 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-12 04:25:04.995267
• Title: A Generative Graph Method to Solve the Travelling Salesman Problem
• Title（参考訳）: トラベリングセールスマン問題の解法のための生成グラフ法
• Authors: Amal Nammouchi, Hakim Ghazzai, and Yehia Massoud
• Abstract要約: 我々は,旅行セールスマン問題(TSP)を概ね解決するために,生成的アプローチである新しいグラフ学習ネットワーク(GLN)を提案する。 GLNモデルは、トレーニングデータセットとしてTSPインスタンスのパターンを直接学習し、グラフプロパティをエンコードし、異なるノードの埋め込みをマージして、最適なツアーを出力する。
• 参考スコア（独自算出の注目度）: 1.552282932199974
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Travelling Salesman Problem (TSP) is a challenging graph task in combinatorial optimization that requires reasoning about both local node neighborhoods and global graph structure. In this paper, we propose to use the novel Graph Learning Network (GLN), a generative approach, to approximately solve the TSP. GLN model learns directly the pattern of TSP instances as training dataset, encodes the graph properties, and merge the different node embeddings to output node-to-node an optimal tour directly or via graph search technique that validates the final tour. The preliminary results of the proposed novel approach proves its applicability to this challenging problem providing a low optimally gap with significant computation saving compared to the optimal solution.
• Abstract（参考訳）: トラベリングセールスマン問題(TSP)は、局所ノード近傍とグローバルグラフ構造の両方の推論を必要とする組合せ最適化における挑戦的なグラフタスクである。 本稿では,生成的手法である新しいグラフ学習ネットワーク(gln)を用いて,tspの近似解法を提案する。 GLNモデルは、トレーニングデータセットとしてTSPインスタンスのパターンを直接学習し、グラフプロパティをエンコードし、各ノードの埋め込みをマージして、ノードからノードへの最適なツアーを直接出力するか、最終ツアーを検証するグラフ検索技術を介して行う。 提案手法の予備結果は, 最適解と比較し, 計算量を大幅に節約し, 最適ギャップの少ない課題に適用可能であることを証明した。

関連論文リスト

• A GAN Approach for Node Embedding in Heterogeneous Graphs Using Subgraph Sampling [35.94125831564648]
  我々の研究は、グラフニューラルネットワーク(GNN)を用いた異種グラフのクラス不均衡問題に対処する。 本稿では,GAN(Generative Adversarial Networks)とGNN(Greative Adversarial Networks)の長所を結合し,データセットを効果的にバランスさせる合成ノードとエッジを作成する手法を提案する。
  論文  参考訳（メタデータ） (2023-12-11T16:52:20Z)
• Symmetry-preserving graph attention network to solve routing problems at multiple resolutions [1.9304772860080408]
  問題解決のために,最初の完全同変モデルとトレーニングを導入する。 入力グラフのマルチスケール構造を捉えることが不可欠である。 本稿では,Equi Graph Attention Network (mEGAT) アーキテクチャと組み合わせたマルチレゾリューション方式を提案する。
  論文  参考訳（メタデータ） (2023-10-24T06:22:20Z)
• VN-Solver: Vision-based Neural Solver for Combinatorial Optimization over Graphs [6.457205049532316]
  ニューラルネットワークはグラフパターンをテキスト化することによってグラフ最適化問題を解決することができるのか? この結果から,このようなビジョンベース手法の性能は,非自明なだけでなく,最先端の行列ベース手法に匹敵するものであり,データ駆動型最適化解法の開発に新たな道を開くことが示唆された。
  論文  参考訳（メタデータ） (2023-08-06T18:33:11Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。 効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。 グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2023-06-14T09:21:15Z)
• Deep Manifold Learning with Graph Mining [80.84145791017968]
  グラフマイニングのための非段階的決定層を持つ新しいグラフ深層モデルを提案する。 提案モデルでは,現行モデルと比較して最先端性能を実現している。
  論文  参考訳（メタデータ） (2022-07-18T04:34:08Z)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  最適グラフ構造を学習するための二段階最適化手法を提案する。 また、時間的複雑さをさらに軽減するために、低ランク近似モデルについても検討する。
  論文  参考訳（メタデータ） (2022-05-06T03:37:00Z)
• GLAN: A Graph-based Linear Assignment Network [29.788755291070462]
  深層グラフネットワークに基づく学習可能な線形代入問題の解法を提案する。 合成データセットによる実験結果から,本手法は最先端のベースラインよりも優れていることがわかった。 また,提案手法を一般的なマルチオブジェクトトラッキング(MOT)フレームワークに組み込んで,エンド・ツー・エンドでトラッカーをトレーニングする。
  論文  参考訳（メタデータ） (2022-01-05T13:18:02Z)
• Learnable Graph Matching: Incorporating Graph Partitioning with Deep Feature Learning for Multiple Object Tracking [58.30147362745852]
  フレーム間のデータアソシエーションは、Multiple Object Tracking(MOT)タスクの中核にある。 既存の手法は、主にトラックレットとフレーム内検出の間のコンテキスト情報を無視する。 そこで本研究では,学習可能なグラフマッチング手法を提案する。
  論文  参考訳（メタデータ） (2021-03-30T08:58:45Z)
• Iterative Deep Graph Learning for Graph Neural Networks: Better and Robust Node Embeddings [53.58077686470096]
  グラフ構造とグラフ埋め込みを協調的かつ反復的に学習するための、エンドツーエンドのグラフ学習フレームワーク、すなわち、IDGL(Iterative Deep Graph Learning)を提案する。 実験の結果,提案したIDGLモデルは,最先端のベースラインを一貫して上回る,あるいは一致させることができることがわかった。
  論文  参考訳（メタデータ） (2020-06-21T19:49:15Z)
• Graph Ordering: Towards the Optimal by Learning [69.72656588714155]
  グラフ表現学習は、ノード分類、予測、コミュニティ検出など、多くのグラフベースのアプリケーションで顕著な成功を収めている。 しかし,グラフ圧縮やエッジ分割などのグラフアプリケーションでは,グラフ表現学習タスクに還元することは極めて困難である。 本稿では,このようなアプリケーションの背後にあるグラフ順序付け問題に対して,新しい学習手法を用いて対処することを提案する。
  論文  参考訳（メタデータ） (2020-01-18T09:14:16Z)

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

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