論文の概要: Revisit the Algorithm Selection Problem for TSP with Spatial Information Enhanced Graph Neural Networks

• arxiv url: http://arxiv.org/abs/2302.04035v1
• Date: Wed, 8 Feb 2023 13:14:20 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-09 16:30:30.953882
• Title: Revisit the Algorithm Selection Problem for TSP with Spatial Information Enhanced Graph Neural Networks
• Title（参考訳）: 空間情報強化グラフニューラルネットワークを用いたTSPのアルゴリズム選択問題の再検討
• Authors: Ya Song, Laurens Bliek, Yingqian Zhang
• Abstract要約: 本稿では,ユークリッド旅行セールスマン問題(TSP)のアルゴリズム選択問題を再検討する。 我々はGINESと呼ばれる新しいグラフニューラルネットワーク(GNN)を提案する。 GINESは都市の座標と都市間の距離を入力として取ります。 これは、1つのデータセットにおける従来の手作りの機能ベースのアプローチよりも優れている。
• 参考スコア（独自算出の注目度）: 4.084365114504618
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Algorithm selection is a well-known problem where researchers investigate how to construct useful features representing the problem instances and then apply feature-based machine learning models to predict which algorithm works best with the given instance. However, even for simple optimization problems such as Euclidean Traveling Salesman Problem (TSP), there lacks a general and effective feature representation for problem instances. The important features of TSP are relatively well understood in the literature, based on extensive domain knowledge and post-analysis of the solutions. In recent years, Convolutional Neural Network (CNN) has become a popular approach to select algorithms for TSP. Compared to traditional feature-based machine learning models, CNN has an automatic feature-learning ability and demands less domain expertise. However, it is still required to generate intermediate representations, i.e., multiple images to represent TSP instances first. In this paper, we revisit the algorithm selection problem for TSP, and propose a novel Graph Neural Network (GNN), called GINES. GINES takes the coordinates of cities and distances between cities as input. It is composed of a new message-passing mechanism and a local neighborhood feature extractor to learn spatial information of TSP instances. We evaluate GINES on two benchmark datasets. The results show that GINES outperforms CNN and the original GINE models. It is better than the traditional handcrafted feature-based approach on one dataset. The code and dataset will be released in the final version of this paper.
• Abstract（参考訳）: アルゴリズムの選択はよく知られた問題であり、研究者は問題インスタンスを表す有用な機能を構築し、特徴ベースの機械学習モデルを適用して、与えられたインスタンスで最適なアルゴリズムを予測する。 しかしながら、ユークリッド旅行セールスマン問題 (TSP) のような単純な最適化問題においても、問題インスタンスに汎用的で効果的な特徴表現がない。 TSPの重要な特徴は、広範なドメイン知識とソリューションの分析に基づいて、文献で比較的よく理解されている。 近年、畳み込みニューラルネットワーク(CNN)は、TSPのためのアルゴリズムを選択する一般的なアプローチとなっている。 従来の機能ベースの機械学習モデルと比較して、cnnは自動的な機能学習能力を持ち、ドメインの専門知識を必要としない。 しかし、TSPインスタンスを最初に表現するためには、中間表現、すなわち複数の画像を生成する必要がある。 本稿では,TSPのアルゴリズム選択問題を再検討し,GINESと呼ばれる新しいグラフニューラルネットワーク(GNN)を提案する。 GINESは都市の座標と都市間の距離を入力としている。 TSPインスタンスの空間情報を学習するための新しいメッセージパッシング機構と局所近傍特徴抽出器から構成される。 GINESを2つのベンチマークデータセットで評価する。 その結果,GINESはCNNやオリジナルのGINEモデルよりも優れていた。 従来の手作りの機能ベースのアプローチよりも優れているのです。 コードとデータセットは、この論文の最終バージョンでリリースされる。

関連論文リスト

• Unveiling the Power of Sparse Neural Networks for Feature Selection [60.50319755984697]
  スパースニューラルネットワーク(SNN)は、効率的な特徴選択のための強力なツールとして登場した。 動的スパーストレーニング(DST)アルゴリズムで訓練されたSNNは、平均して50%以上のメモリと55%以上のFLOPを削減できることを示す。 以上の結果から,DSTアルゴリズムで訓練したSNNによる特徴選択は,平均して50ドル以上のメモリと55%のFLOPを削減できることがわかった。
  論文  参考訳（メタデータ） (2024-08-08T16:48:33Z)
• Ensemble Quadratic Assignment Network for Graph Matching [52.20001802006391]
  グラフマッチングはコンピュータビジョンやパターン認識において一般的に用いられる技法である。 最近のデータ駆動型アプローチは、グラフマッチングの精度を著しく改善した。 データ駆動手法と従来の手法の利点を組み合わせたグラフニューラルネットワーク(GNN)に基づくアプローチを提案する。
  論文  参考訳（メタデータ） (2024-03-11T06:34:05Z)
• Sample Complexity of Algorithm Selection Using Neural Networks and Its Applications to Branch-and-Cut [1.4624458429745086]
  本研究は,最適な性能を持つ1つのアルゴリズムを選択するのではなく,インスタンスに基づいてアルゴリズムを選択することが可能となるような設定を考慮し,最近の研究を基礎にしている。 特に、代表的なインスタンスのサンプルが与えられた場合、問題のインスタンスをそのインスタンスの最も適切なアルゴリズムにマッピングするニューラルネットワークを学習する。 言い換えれば、ニューラルネットワークは混合整数最適化インスタンスを入力として取り、そのインスタンスの小さな分岐とカットツリーをもたらす決定を出力する。
  論文  参考訳（メタデータ） (2024-02-04T03:03:27Z)
• Towards Better Out-of-Distribution Generalization of Neural Algorithmic Reasoning Tasks [51.8723187709964]
  ニューラルネットワーク推論タスクのOOD一般化について検討する。 目標は、ディープニューラルネットワークを使用して入出力ペアからアルゴリズムを学ぶことである。
  論文  参考訳（メタデータ） (2022-11-01T18:33:20Z)
• Automated Algorithm Selection: from Feature-Based to Feature-Free Approaches [0.5801044612920815]
  本稿では,データ中に暗黙的なシーケンシャル情報がカプセル化されている最適化に適用可能な,アルゴリズム選択のための新しい手法を提案する。 我々は、よく知られた4つのドメインから選択して、オンラインビンパッキングのパッキングを予測するために、2種類のリカレントニューラルネットワークをトレーニングする。
  論文  参考訳（メタデータ） (2022-03-24T23:59:50Z)
• Learning to Sparsify Travelling Salesman Problem Instances [0.5985204759362747]
  プルーニングマシンラーニングを前処理のステップとして使用し、旅行セールスマンの問題をスパーシャライズするために正確なプログラミングアプローチを行います。 私たちの学習アプローチは、非常に少ないトレーニングデータを必要とし、数学的分析に適応可能です。
  論文  参考訳（メタデータ） (2021-04-19T14:35:14Z)
• Variational models for signal processing with Graph Neural Networks [3.5939555573102853]
  本稿では,ニューラルネットワークを用いた点雲の信号処理について述べる。 本研究では,このようなグラフニューラルネットワークの変分モデルを用いて,教師なし学習のためのグラフ上の信号を処理する方法を検討する。
  論文  参考訳（メタデータ） (2021-03-30T13:31:11Z)
• Solving Mixed Integer Programs Using Neural Networks [57.683491412480635]
  本稿では,mipソルバの2つのキーサブタスクに学習を適用し,高品質なジョイント変数割当を生成し,その割当と最適課題との客観的値の差を限定する。 提案手法は,ニューラルネットワークに基づく2つのコンポーネントであるニューラルダイバーディングとニューラルブランチを構築し,SCIPなどのベースMIPソルバで使用する。 2つのGoogle生産データセットとMIPLIBを含む6つの現実世界データセットに対するアプローチを評価し、それぞれに別々のニューラルネットワークをトレーニングする。
  論文  参考訳（メタデータ） (2020-12-23T09:33:11Z)
• Overcoming Catastrophic Forgetting in Graph Neural Networks [50.900153089330175]
  破滅的な忘れは、ニューラルネットワークが新しいタスクを学ぶ前に学んだ知識を「忘れる」傾向を指します。 本稿では,この問題を克服し,グラフニューラルネットワーク(GNN)における継続学習を強化するための新しいスキームを提案する。 私たちのアプローチの中心には、トポロジ認識重量保存(TWP)と呼ばれる汎用モジュールがあります。
  論文  参考訳（メタデータ） (2020-12-10T22:30:25Z)
• Deep Learning as a Competitive Feature-Free Approach for Automated Algorithm Selection on the Traveling Salesperson Problem [0.0]
  我々は、有名なユークリッド旅行セールスマン問題(TSP)に焦点を当てる。 私たちは1,000のノードでインスタンスを進化させ、そこではソルバがパフォーマンスプロファイルを強く示します。 特徴のないディープニューラルネットワークに基づくアプローチは、インスタンスの視覚的表現のみに基づいており、すでに古典的なASモデルの結果と一致していることを示す。
  論文  参考訳（メタデータ） (2020-06-29T12:15:35Z)
• FedPD: A Federated Learning Framework with Optimal Rates and Adaptivity to Non-IID Data [59.50904660420082]
  フェデレートラーニング(FL)は、分散データから学ぶための一般的なパラダイムになっています。 クラウドに移行することなく、さまざまなデバイスのデータを効果的に活用するために、Federated Averaging(FedAvg)などのアルゴリズムでは、"Computation then aggregate"(CTA)モデルを採用している。
  論文  参考訳（メタデータ） (2020-05-22T23:07:42Z)

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

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