論文の概要: Graph Reinforcement Learning for Combinatorial Optimization: A Survey and Unifying Perspective
- arxiv url: http://arxiv.org/abs/2404.06492v1
- Date: Tue, 9 Apr 2024 17:45:25 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-10 13:42:03.011779
- Title: Graph Reinforcement Learning for Combinatorial Optimization: A Survey and Unifying Perspective
- Title（参考訳）: 組合せ最適化のためのグラフ強化学習 : 調査と統一的視点
- Authors: Victor-Alexandru Darvariu, Stephen Hailes, Mirco Musolesi,
- Abstract要約: 我々は、強化学習の試行錯誤パラダイムを用いて、より良い意思決定戦略を発見する。
この研究は、パフォーマンスアルゴリズムが典型的に知られていない非標準グラフ問題に焦点を当てている。
- 参考スコア（独自算出の注目度）: 6.199818486385127
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Graphs are a natural representation for systems based on relations between connected entities. Combinatorial optimization problems, which arise when considering an objective function related to a process of interest on discrete structures, are often challenging due to the rapid growth of the solution space. The trial-and-error paradigm of Reinforcement Learning has recently emerged as a promising alternative to traditional methods, such as exact algorithms and (meta)heuristics, for discovering better decision-making strategies in a variety of disciplines including chemistry, computer science, and statistics. Despite the fact that they arose in markedly different fields, these techniques share significant commonalities. Therefore, we set out to synthesize this work in a unifying perspective that we term Graph Reinforcement Learning, interpreting it as a constructive decision-making method for graph problems. After covering the relevant technical background, we review works along the dividing line of whether the goal is to optimize graph structure given a process of interest, or to optimize the outcome of the process itself under fixed graph structure. Finally, we discuss the common challenges facing the field and open research questions. In contrast with other surveys, the present work focuses on non-canonical graph problems for which performant algorithms are typically not known and Reinforcement Learning is able to provide efficient and effective solutions.
- Abstract（参考訳）: グラフは、接続されたエンティティ間の関係に基づくシステムの自然な表現である。
離散構造に対する関心の過程に関連する客観的関数を考える際に生じる組合せ最適化問題は、解空間の急速な成長によってしばしば困難である。
強化学習の試行錯誤パラダイムは、化学、計算機科学、統計学など、さまざまな分野におけるより良い意思決定戦略を発見するための、正確なアルゴリズムや(メタ)ヒューリスティックスといった従来の手法に代わる有望な代替手段として最近登場した。
それらが著しく異なる分野で生じたという事実にもかかわらず、これらの技術は重要な共通点を共有している。
そこで我々は,この研究をグラフ強化学習(Graph Reinforcement Learning)と呼ぶ統一的な視点で合成し,グラフ問題の構築的意思決定手法として解釈した。
関連する技術的背景を網羅した後、関心のあるグラフ構造を最適化するか、あるいは固定されたグラフ構造の下でプロセス自体の結果を最適化するかを、目的の分割線に沿って検討する。
最後に、この分野に直面する共通課題と研究課題について論じる。
他の調査とは対照的に、本研究では、パフォーマンスアルゴリズムが一般的に知られていない非標準グラフ問題に焦点を当て、強化学習は効率的かつ効果的なソリューションを提供することができる。
関連論文リスト
- Decision-focused Graph Neural Networks for Combinatorial Optimization [62.34623670845006]
最適化問題に取り組むための新たな戦略は、従来のアルゴリズムに代わるグラフニューラルネットワーク(GNN)の採用である。
GNNや従来のアルゴリズムソルバがCOの領域で人気が高まっているにもかかわらず、それらの統合利用とエンドツーエンドフレームワークにおけるそれらの相関について限定的な研究がなされている。
我々は、GNNを利用してCO問題に補助的なサポートで対処する決定に焦点を当てたフレームワークを導入する。
論文 参考訳（メタデータ） (2024-06-05T22:52:27Z) - GASE: Graph Attention Sampling with Edges Fusion for Solving Vehicle Routing Problems [6.084414764415137]
車両のルーティング問題を解決するためにEdges Fusionフレームワークを用いた適応型グラフ注意サンプリングを提案する。
提案手法は,既存の手法を2.08%-6.23%上回り,より強力な一般化能力を示す。
論文 参考訳（メタデータ） (2024-05-21T03:33:07Z) - A Novel Differentiable Loss Function for Unsupervised Graph Neural
Networks in Graph Partitioning [5.22145960878624]
グラフ分割問題はNPハードプロブレムとして認識される。
グラフ分割問題を解決するために,教師なしグラフニューラルネットワークを用いた新しいパイプラインを導入する。
我々は、現代の最先端技術に対する我々の方法論を厳格に評価し、メトリクス(カットとバランス)に重点を置いています。
論文 参考訳（メタデータ） (2023-12-11T23:03:17Z) - 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) - A Differentiable Approach to Combinatorial Optimization using Dataless
Neural Networks [20.170140039052455]
我々は、ソリューションを生成するニューラルネットワークのトレーニングにデータを必要としないという、根本的に異なるアプローチを提案する。
特に、最適化問題をニューラルネットワークに還元し、データレストレーニングスキームを用いて、それらのパラメータが関心の構造をもたらすように、ネットワークのパラメータを洗練する。
論文 参考訳（メタデータ） (2022-03-15T19:21:31Z) - Solving Dynamic Graph Problems with Multi-Attention Deep Reinforcement
Learning [1.3534683694551497]
近年,NP-hardグラフ問題に対する解を見つけるためのディープラーニング技術が注目されている。
本稿では,グラフに基づく動的最適化問題の解法を学ぶために,GTA-RL (Graph Temporal Attention with Reinforcement Learning) という新しいアーキテクチャを提案する。
論文 参考訳（メタデータ） (2022-01-13T11:36:05Z) - A Bi-Level Framework for Learning to Solve Combinatorial Optimization on
Graphs [91.07247251502564]
本稿では,2つの世界の長所を結合するハイブリッドな手法を提案する。この手法では,グラフを最適化する上層学習手法とバイレベルフレームワークを開発する。
このような二段階のアプローチは、元のハードCOでの学習を単純化し、モデルキャパシティの需要を効果的に軽減することができる。
論文 参考訳（メタデータ） (2021-06-09T09:18:18Z) - Deep Reinforcement Learning of Graph Matching [63.469961545293756]
ノードとペアの制約下でのグラフマッチング(GM)は、最適化からコンピュータビジョンまでの領域におけるビルディングブロックである。
GMのための強化学習ソルバを提案する。
rgmはペアワイズグラフ間のノード対応を求める。
本手法は,フロントエンドの特徴抽出と親和性関数学習に焦点をあてるという意味において,従来のディープグラフマッチングモデルと異なる。
論文 参考訳（メタデータ） (2020-12-16T13:48:48Z) - GraphOpt: Learning Optimization Models of Graph Formation [72.75384705298303]
本稿では,グラフ構造形成の暗黙的モデルを学ぶエンドツーエンドフレームワークを提案し,その基盤となる最適化機構を明らかにする。
学習した目的は、観測されたグラフプロパティの説明として機能し、ドメイン内の異なるグラフを渡すために自分自身を貸すことができる。
GraphOptは、グラフ内のリンク生成をシーケンシャルな意思決定プロセスとして、最大エントロピー逆強化学習アルゴリズムを用いて解決する。
論文 参考訳（メタデータ） (2020-07-07T16:51:39Z) - Differentiable Causal Discovery from Interventional Data [141.41931444927184]
本稿では、介入データを活用可能なニューラルネットワークに基づく理論的基盤化手法を提案する。
提案手法は,様々な環境下での美術品の状態と良好に比較できることを示す。
論文 参考訳（メタデータ） (2020-07-03T15:19:17Z) - Learning Combinatorial Optimization on Graphs: A Survey with
Applications to Networking [2.817395666721831]
グラフ上の最適化問題を解くための既存のアプローチは、アルゴリズムで各問題を設計する必要がある。
我々は,通信分野に特化して,学習に関わる構造を整理し,比較する。
論文 参考訳（メタデータ） (2020-05-22T09:45:36Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。