論文の概要: Solving Dynamic Graph Problems with Multi-Attention Deep Reinforcement Learning

• arxiv url: http://arxiv.org/abs/2201.04895v1
• Date: Thu, 13 Jan 2022 11:36:05 GMT
• ステータス: 処理完了
• システム内更新日: 2022-01-14 21:31:20.699491
• Title: Solving Dynamic Graph Problems with Multi-Attention Deep Reinforcement Learning
• Title（参考訳）: マルチアテンション深層強化学習による動的グラフ問題の解法
• Authors: Udesh Gunarathna, Renata Borovica-Gajic, Shanika Karunasekara, Egemen Tanin
• Abstract要約: 近年,NP-hardグラフ問題に対する解を見つけるためのディープラーニング技術が注目されている。 本稿では,グラフに基づく動的最適化問題の解法を学ぶために,GTA-RL (Graph Temporal Attention with Reinforcement Learning) という新しいアーキテクチャを提案する。
• 参考スコア（独自算出の注目度）: 1.3534683694551497
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graph problems such as traveling salesman problem, or finding minimal Steiner trees are widely studied and used in data engineering and computer science. Typically, in real-world applications, the features of the graph tend to change over time, thus, finding a solution to the problem becomes challenging. The dynamic version of many graph problems are the key for a plethora of real-world problems in transportation, telecommunication, and social networks. In recent years, using deep learning techniques to find heuristic solutions for NP-hard graph combinatorial problems has gained much interest as these learned heuristics can find near-optimal solutions efficiently. However, most of the existing methods for learning heuristics focus on static graph problems. The dynamic nature makes NP-hard graph problems much more challenging to learn, and the existing methods fail to find reasonable solutions. In this paper, we propose a novel architecture named Graph Temporal Attention with Reinforcement Learning (GTA-RL) to learn heuristic solutions for graph-based dynamic combinatorial optimization problems. The GTA-RL architecture consists of an encoder capable of embedding temporal features of a combinatorial problem instance and a decoder capable of dynamically focusing on the embedded features to find a solution to a given combinatorial problem instance. We then extend our architecture to learn heuristics for the real-time version of combinatorial optimization problems where all input features of a problem are not known a prior, but rather learned in real-time. Our experimental results against several state-of-the-art learning-based algorithms and optimal solvers demonstrate that our approach outperforms the state-of-the-art learning-based approaches in terms of effectiveness and optimal solvers in terms of efficiency on dynamic and real-time graph combinatorial optimization.
• Abstract（参考訳）: トラベルセールスマン問題や最小のシュタイナー木の発見といったグラフ問題は、データ工学やコンピュータ科学において広く研究され、利用されている。 通常、現実世界のアプリケーションでは、グラフの機能は時間とともに変化する傾向があるため、問題に対する解決策を見つけることは困難になる。 多くのグラフ問題の動的なバージョンは、輸送、通信、ソーシャルネットワークにおける現実の問題の多さの鍵である。 近年、np型グラフ組合せ問題に対するヒューリスティックな解を見つけるためにディープラーニング技術を用いることで、これらの学習されたヒューリスティックは最適に近い解を効率的に見つけることができるため、多くの関心を集めている。 しかし、既存のヒューリスティックス学習手法のほとんどは静的グラフ問題に重点を置いている。 動的性質はNPハードグラフ問題を学習しにくくし、既存の手法では妥当な解を見つけることができない。 本稿では,グラフに基づく動的組合せ最適化問題に対するヒューリスティックな解を求めるために,グラフ時間注意強化学習(GTA-RL)という新しいアーキテクチャを提案する。 GTA-RLアーキテクチャは、組合せ問題インスタンスの時間的特徴を埋め込むことができるエンコーダと、組み込まれた特徴に動的に集中して与えられた組合せ問題インスタンスの解を見つけることができるデコーダとから構成される。 次に、私たちはアーキテクチャを拡張して、問題の全入力特徴が事前に知られておらず、むしろリアルタイムに学習される組合せ最適化問題のリアルタイムバージョンのヒューリスティックスを学びます。 いくつかの最先端学習に基づくアルゴリズムと最適解法に対する実験結果は、動的およびリアルタイムグラフの組合せ最適化における効率性の観点から、最先端学習に基づくアプローチよりも優れていることを示す。

関連論文リスト

• Decision-focused Graph Neural Networks for Combinatorial Optimization [62.34623670845006]
  最適化問題に取り組むための新たな戦略は、従来のアルゴリズムに代わるグラフニューラルネットワーク(GNN)の採用である。 GNNや従来のアルゴリズムソルバがCOの領域で人気が高まっているにもかかわらず、それらの統合利用とエンドツーエンドフレームワークにおけるそれらの相関について限定的な研究がなされている。 我々は、GNNを利用してCO問題に補助的なサポートで対処する決定に焦点を当てたフレームワークを導入する。
  論文  参考訳（メタデータ） (2024-06-05T22:52:27Z)
• Graph Reinforcement Learning for Combinatorial Optimization: A Survey and Unifying Perspective [6.199818486385127]
  我々は、強化学習の試行錯誤パラダイムを用いて、より良い意思決定戦略を発見する。 この研究は、パフォーマンスアルゴリズムが典型的に知られていない非標準グラフ問題に焦点を当てている。
  論文  参考訳（メタデータ） (2024-04-09T17:45:25Z)
• Graph Q-Learning for Combinatorial Optimization [44.8086492019594]
  グラフニューラルネットワーク(GNN)は,グラフデータの予測と推論の問題を解くのに有効であることが示されている。 本稿では,GNNを組合せ最適化問題に適用できることを示す。
  論文  参考訳（メタデータ） (2024-01-11T01:15:28Z)
• Symmetry-preserving graph attention network to solve routing problems at multiple resolutions [1.9304772860080408]
  問題解決のために,最初の完全同変モデルとトレーニングを導入する。 入力グラフのマルチスケール構造を捉えることが不可欠である。 本稿では,Equi Graph Attention Network (mEGAT) アーキテクチャと組み合わせたマルチレゾリューション方式を提案する。
  論文  参考訳（メタデータ） (2023-10-24T06:22:20Z)
• GIF: A General Graph Unlearning Strategy via Influence Function [63.52038638220563]
  Graph Influence Function (GIF)は、削除されたデータにおける$epsilon$-massの摂動に応答してパラメータの変化を効率的に正確に推定できる、モデルに依存しない未学習の手法である。 我々は,4つの代表的GNNモデルと3つのベンチマークデータセットについて広範な実験を行い,未学習の有効性,モデルの有用性,未学習効率の観点からGIFの優位性を正当化する。
  論文  参考訳（メタデータ） (2023-04-06T03:02:54Z)
• Learnable Graph Matching: A Practical Paradigm for Data Association [74.28753343714858]
  これらの問題に対処するための一般的な学習可能なグラフマッチング法を提案する。 提案手法は,複数のMOTデータセット上での最先端性能を実現する。 画像マッチングでは,一般的な屋内データセットであるScanNetで最先端の手法より優れている。
  論文  参考訳（メタデータ） (2023-03-27T17:39:00Z)
• 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)
• A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs [91.07247251502564]
  本稿では,2つの世界の長所を結合するハイブリッドな手法を提案する。この手法では,グラフを最適化する上層学習手法とバイレベルフレームワークを開発する。 このような二段階のアプローチは、元のハードCOでの学習を単純化し、モデルキャパシティの需要を効果的に軽減することができる。
  論文  参考訳（メタデータ） (2021-06-09T09:18:18Z)
• 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)
• Learning to Solve Combinatorial Optimization Problems on Real-World Graphs in Linear Time [12.43303621344215]
  専門知識のないグラフ上での最適化問題を解くための新しいフレームワークを開発する。 本手法は,グラフのラベル付きトレーニングセット上で強化学習を用いてグラフニューラルネットワークを訓練する。 最適性ギャップが 1 に近い 2 つのNP-ハード問題に対して,本手法がよく一般化可能であることを示す。
  論文  参考訳（メタデータ） (2020-06-06T01:35:45Z)
• Learning fine-grained search space pruning and heuristics for combinatorial optimization [5.72274610208488]
  本稿では,機械学習技術を利用して正確な最適化アルゴリズムをスケールアップするフレームワークを提案する。 我々のフレームワークは、問題インスタンスのサイズを減らすために、要素を刈り取るという比較的単純なタスクを学習します。 我々のフレームワークは入力グラフのかなりの部分を取り除き、なおも最大傾きのほとんどを検出可能であることを示す。
  論文  参考訳（メタデータ） (2020-01-05T13:10:39Z)

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

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