論文の概要: An Edge-Aware Graph Autoencoder Trained on Scale-Imbalanced Data for Traveling Salesman Problems

• arxiv url: http://arxiv.org/abs/2310.06543v2
• Date: Sat, 2 Mar 2024 07:53:46 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-05 20:21:42.694784
• Title: An Edge-Aware Graph Autoencoder Trained on Scale-Imbalanced Data for Traveling Salesman Problems
• Title（参考訳）: 巡回セールスマン問題に対するスケール不均衡データに基づくエッジアウェアグラフ自動エンコーダ
• Authors: Shiqing Liu, Xueming Yan, Yaochu Jin
• Abstract要約: 本研究では、トラベリングセールスマン問題(TSP)を解決するためのデータ駆動グラフ表現学習法を提案する。 残留ゲートエンコーダは遅延エッジ埋め込みを学習するために訓練され、次いでエッジ中心のデコーダでリンク予測をエンドツーエンドに出力する。 実験結果から,提案したエッジ対応グラフオートエンコーダモデルにより,高い競合性能が得られた。
• 参考スコア（独自算出の注目度）: 22.792870849003137
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In recent years, there has been a notable surge in research on machine learning techniques for combinatorial optimization. It has been shown that learning-based methods outperform traditional heuristics and mathematical solvers on the Traveling Salesman Problem (TSP) in terms of both performance and computational efficiency. However, most learning-based TSP solvers are primarily designed for fixed-scale TSP instances, and also require a large number of training samples to achieve optimal performance. To fill this gap, this work proposes a data-driven graph representation learning method for solving TSPs with various numbers of cities. Specifically, we formulate the TSP as a link prediction task and propose an edge-aware graph autoencoder (EdgeGAE) model that can solve TSPs by learning from various-scale samples with an imbalanced distribution. A residual gated encoder is trained to learn latent edge embeddings, followed by an edge-centered decoder to output link predictions in an end-to-end manner. Furthermore, we introduce an active sampling strategy into the training process to improve the model's generalization capability in large-scale scenarios. To investigate the model's practical applicability, we generate a scale-imbalanced dataset comprising 50,000 TSP instances ranging from 50 to 500 cities. The experimental results demonstrate that the proposed edge-aware graph autoencoder model achieves a highly competitive performance among state-of-the-art graph learning-based approaches in solving TSPs with various scales, implying its remarkable potential in dealing with practical optimization challenges.
• Abstract（参考訳）: 近年,組合せ最適化のための機械学習技術の研究が注目されている。 学習に基づく手法は,トラベリングセールスマン問題(TSP)における従来のヒューリスティックスや数学的解法よりも,性能と計算効率の両面で優れていることが示されている。 しかし、ほとんどの学習ベースのTSPソルバは、主に固定スケールのTSPインスタンス用に設計されており、最適なパフォーマンスを得るためには、多数のトレーニングサンプルを必要とする。 このギャップを埋めるために,様々な都市でtspを解決するためのデータ駆動グラフ表現学習手法を提案する。 具体的には、リンク予測タスクとしてTSPを定式化し、不均衡分布を持つ様々なスケールのサンプルから学習することでTSPを解くことができるエッジ認識グラフオートエンコーダ(EdgeGAE)モデルを提案する。 残留ゲートエンコーダは遅延エッジ埋め込みを学習するために訓練され、次いでエッジ中心のデコーダでリンク予測をエンドツーエンドに出力する。 さらに,大規模シナリオにおけるモデルの一般化能力を向上させるために,トレーニングプロセスにアクティブサンプリング戦略を導入する。 モデルの実用性を検討するため,50都市から500都市までの5万のTSPインスタンスからなるスケール不均衡データセットを生成する。 提案するエッジアウェアグラフオートエンコーダモデルは,tspを様々なスケールで解くための最先端グラフ学習手法と高い競合性能を実現し,実用的な最適化課題への対処の可能性を示す。

関連論文リスト

• Novel Representation Learning Technique using Graphs for Performance Analytics [0.0]
  本稿では,グラフニューラルネットワーク(GNN)技術の進歩を活用するために,パフォーマンスデータをグラフに変換する新しいアイデアを提案する。 ソーシャルネットワークのような他の機械学習アプリケーションドメインとは対照的に、グラフは提供されない。 我々は,GNNから生成された埋め込みの有効性を,単純なフィードフォワードニューラルネットワークによる回帰処理の性能評価に基づいて評価した。
  論文  参考訳（メタデータ） (2024-01-19T16:34:37Z)
• When Parameter-efficient Tuning Meets General-purpose Vision-language Models [65.19127815275307]
  PETALは、一意のモード近似技術によって達成される全パラメータの0.5%しか必要とせず、トレーニングプロセスに革命をもたらす。 実験の結果,PETALは現状の手法をほとんどのシナリオで上回るだけでなく,完全な微調整モデルよりも優れていることがわかった。
  論文  参考訳（メタデータ） (2023-12-16T17:13:08Z)
• Towards a Better Theoretical Understanding of Independent Subnetwork Training [56.24689348875711]
  独立サブネットワークトレーニング(IST)の理論的考察 ISTは、上記の問題を解決するための、最近提案され、非常に効果的である。 圧縮通信を用いた分散手法など,ISTと代替手法の基本的な違いを同定する。
  論文  参考訳（メタデータ） (2023-06-28T18:14:22Z)
• End-to-End Meta-Bayesian Optimisation with Transformer Neural Processes [52.818579746354665]
  本稿では,ニューラルネットワークを一般化し,トランスフォーマーアーキテクチャを用いて獲得関数を学習する,エンド・ツー・エンドの差別化可能な最初のメタBOフレームワークを提案する。 我々は、この強化学習(RL)によるエンドツーエンドのフレームワークを、ラベル付き取得データの欠如に対処できるようにします。
  論文  参考訳（メタデータ） (2023-05-25T10:58:46Z)
• Unifying Synergies between Self-supervised Learning and Dynamic Computation [53.66628188936682]
  SSLとDCのパラダイム間の相互作用に関する新しい視点を提示する。 SSL設定において、スクラッチから高密度かつゲートされたサブネットワークを同時に学習することは可能であることを示す。 密集エンコーダとゲートエンコーダの事前学習における共進化は、良好な精度と効率のトレードオフをもたらす。
  論文  参考訳（メタデータ） (2023-01-22T17:12:58Z)
• Offline Q-Learning on Diverse Multi-Task Data Both Scales And Generalizes [100.69714600180895]
  オフラインのQ-ラーニングアルゴリズムは、モデルキャパシティでスケールする強力なパフォーマンスを示す。 最大8000万のパラメータネットワークを用いて,40のゲームに対してほぼ人間に近いパフォーマンスで1つのポリシーをトレーニングする。 リターン条件付き教師付きアプローチと比較して、オフラインQラーニングはモデルキャパシティと同様にスケールし、特にデータセットが最適以下である場合にはパフォーマンスが向上する。
  論文  参考訳（メタデータ） (2022-11-28T08:56:42Z)
• 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)
• Learning to Sparsify Travelling Salesman Problem Instances [0.5985204759362747]
  プルーニングマシンラーニングを前処理のステップとして使用し、旅行セールスマンの問題をスパーシャライズするために正確なプログラミングアプローチを行います。 私たちの学習アプローチは、非常に少ないトレーニングデータを必要とし、数学的分析に適応可能です。
  論文  参考訳（メタデータ） (2021-04-19T14:35:14Z)

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

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