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

• arxiv url: http://arxiv.org/abs/2310.06543v1
• Date: Tue, 10 Oct 2023 11:42:49 GMT
• ステータス: 処理完了
• システム内更新日: 2023-10-11 15:47:02.741793
• Title: An Edge-Aware Graph Autoencoder Trained on Scale-Imbalanced Data for Travelling Salesman Problems
• Title（参考訳）: 巡回セールスマン問題に対するスケール不均衡データに基づくエッジアウェアグラフ自動エンコーダ
• Authors: Shiqing Liu, Xueming Yan, Yaochu Jin
• Abstract要約: 本研究では,旅行セールスマン問題(TSP)を様々な都市で解くことができるエッジ対応グラフオートエンコーダ(EdgeGAE)モデルを提案する。 我々は,50から500都市規模の5万のTSPインスタンスを含むベンチマークデータセットを生成する。 様々なスケールで異なる量のトレーニングデータを用いて実験を行い、提案したデータ駆動アプローチが高い競争性能を達成することを示す実験結果を得た。
• 参考スコア（独自算出の注目度）: 22.792870849003137
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Recent years have witnessed a surge in research on machine learning for combinatorial optimization since learning-based approaches can outperform traditional heuristics and approximate exact solvers at a lower computation cost. However, most existing work on supervised neural combinatorial optimization focuses on TSP instances with a fixed number of cities and requires large amounts of training samples to achieve a good performance, making them less practical to be applied to realistic optimization scenarios. This work aims to develop a data-driven graph representation learning method for solving travelling salesman problems (TSPs) with various numbers of cities. To this end, we propose an edge-aware graph autoencoder (EdgeGAE) model that can learn to solve TSPs after being trained on solution data of various sizes with an imbalanced distribution. We formulate the TSP as a link prediction task on sparse connected graphs. 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. To improve the model's generalization capability of solving large-scale problems, we introduce an active sampling strategy into the training process. In addition, we generate a benchmark dataset containing 50,000 TSP instances with a size from 50 to 500 cities, following an extremely scale-imbalanced distribution, making it ideal for investigating the model's performance for practical applications. We conduct experiments using different amounts of training data with various scales, and the experimental results demonstrate that the proposed data-driven approach achieves a highly competitive performance among state-of-the-art learning-based methods for solving TSPs.
• Abstract（参考訳）: 近年、機械学習による組合せ最適化の研究が急増している。これは学習に基づくアプローチが従来のヒューリスティックスよりも優れており、計算コストも低い。 しかしながら、教師付きニューラルコンビネータ最適化に関する既存の作業のほとんどは、一定の数の都市でtspインスタンスに焦点を当てており、優れたパフォーマンスを達成するために大量のトレーニングサンプルを必要とするため、現実的な最適化シナリオに適用するには実用的でない。 本研究の目的は,様々な都市でトラベリングセールスマン問題(TSP)を解くためのデータ駆動グラフ表現学習手法を開発することである。 そこで本稿では, エッジ対応グラフオートエンコーダ(EdgeGAE)モデルを提案する。 疎連結グラフ上でのリンク予測タスクとしてTSPを定式化する。 残留ゲートエンコーダは遅延エッジ埋め込みを学習するために訓練され、次いでエッジ中心のデコーダでリンク予測をエンドツーエンドに出力する。 大規模問題を解決するためのモデルの一般化能力を改善するため,トレーニングプロセスにアクティブサンプリング戦略を導入する。 さらに,50都市から500都市までの規模を持つ5万tspインスタンスを含むベンチマークデータセットを,非常に大規模にバランスの取れない分布に従って生成する。 本研究では,様々なスケールの異なるトレーニングデータを用いて実験を行い,提案手法がtspsの解法である最先端学習法において高い競合性能を達成できることを実証する。

関連論文リスト

• 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)

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

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