論文の概要: Graph Q-Learning for Combinatorial Optimization
- arxiv url: http://arxiv.org/abs/2401.05610v1
- Date: Thu, 11 Jan 2024 01:15:28 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-13 01:45:40.013783
- Title: Graph Q-Learning for Combinatorial Optimization
- Title(参考訳): 組合せ最適化のためのグラフq学習
- Authors: Victoria M. Dax, Jiachen Li, Kevin Leahy, Mykel J. Kochenderfer
- Abstract要約: グラフニューラルネットワーク(GNN)は,グラフデータの予測と推論の問題を解くのに有効であることが示されている。
本稿では,GNNを組合せ最適化問題に適用できることを示す。
- 参考スコア(独自算出の注目度): 44.8086492019594
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Graph-structured data is ubiquitous throughout natural and social sciences,
and Graph Neural Networks (GNNs) have recently been shown to be effective at
solving prediction and inference problems on graph data. In this paper, we
propose and demonstrate that GNNs can be applied to solve Combinatorial
Optimization (CO) problems. CO concerns optimizing a function over a discrete
solution space that is often intractably large. To learn to solve CO problems,
we formulate the optimization process as a sequential decision making problem,
where the return is related to how close the candidate solution is to
optimality. We use a GNN to learn a policy to iteratively build increasingly
promising candidate solutions. We present preliminary evidence that GNNs
trained through Q-Learning can solve CO problems with performance approaching
state-of-the-art heuristic-based solvers, using only a fraction of the
parameters and training time.
- Abstract(参考訳): グラフ構造化データは、自然科学や社会科学で広く利用されており、グラフニューラルネットワーク(GNN)はグラフデータの予測と推論の問題を解決するのに有効であることが最近示されている。
本稿では,GNN が Combinatorial Optimization (CO) 問題に応用可能であることを示す。
CO は、しばしば非常に大きい離散解空間上の関数を最適化する。
CO問題の解法を学習するために、最適化過程を逐次決定問題として定式化し、最適解が最適解にどの程度近いかに回帰する。
私たちは、GNNを使って、ますます有望な候補ソリューションを反復的に構築するポリシーを学びます。
本稿では,q-learningで学習したgnnが,パラメータとトレーニング時間のほんの一部を使って,最先端のヒューリスティックベースソルバに接近するパフォーマンスのco問題を解決できることの予備的証拠を示す。
関連論文リスト
- Robust Graph Neural Network based on Graph Denoising [10.564653734218755]
グラフニューラルネットワーク(GNN)は、非ユークリッドデータセットを扱う学習問題に対して、悪名高い代替手段として登場した。
本研究は,観測トポロジにおける摂動の存在を明示的に考慮した,GNNの堅牢な実装を提案する。
論文 参考訳(メタデータ) (2023-12-11T17:43:57Z) - A Graph Neural Network-Based QUBO-Formulated Hamiltonian-Inspired Loss
Function for Combinatorial Optimization using Reinforcement Learning [1.566437882635872]
ハミルトニアン函数は、最適化の文脈において目的関数として使用されるQUBO問題を定式化するためにしばしば用いられる。
汎用的なスケーラブルなフレームワークであるPI-GNNは、単純なグラフニューラルネットワーク(GNN)アーキテクチャに基づいて、グラフ上の組合せ最適化(CO)問題に対処するために提案されている。
実験では,PI-GNN法と比較して最大44%改善した。
論文 参考訳(メタデータ) (2023-08-27T00:57:01Z) - Let the Flows Tell: Solving Graph Combinatorial Optimization Problems
with GFlowNets [86.43523688236077]
組合せ最適化(CO)問題はしばしばNPハードであり、正確なアルゴリズムには及ばない。
GFlowNetsは、複合非正規化密度を逐次サンプリングする強力な機械として登場した。
本稿では,異なる問題に対してマルコフ決定プロセス(MDP)を設計し,条件付きGFlowNetを学習して解空間からサンプルを作成することを提案する。
論文 参考訳(メタデータ) (2023-05-26T15:13:09Z) - Improved Training of Physics-Informed Neural Networks with Model
Ensembles [81.38804205212425]
我々は、PINNを正しい解に収束させるため、解区間を徐々に拡大することを提案する。
すべてのアンサンブルのメンバーは、観測されたデータの近くで同じ解に収束する。
提案手法は, 得られた解の精度を向上させることができることを示す。
論文 参考訳(メタデータ) (2022-04-11T14:05:34Z) - 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) - On the Difficulty of Generalizing Reinforcement Learning Framework for
Combinatorial Optimization [6.935838847004389]
現実の応用とグラフ上の組合せ最適化問題(COP)は、コンピュータサイエンスにおける標準的な課題である。
このアプローチの基本原理は、ノードのローカル情報とグラフ構造化データの両方を符号化するグラフニューラルネットワーク(GNN)をデプロイすることである。
我々は,クラウド上のセキュリティ対応電話機のクローン割り当てを古典的二次代入問題 (QAP) として,深層RLモデルが他の難題の解法に一般的に適用可能であるか否かを調査する。
論文 参考訳(メタデータ) (2021-08-08T19:12:04Z) - A Bi-Level Framework for Learning to Solve Combinatorial Optimization on
Graphs [91.07247251502564]
本稿では,2つの世界の長所を結合するハイブリッドな手法を提案する。この手法では,グラフを最適化する上層学習手法とバイレベルフレームワークを開発する。
このような二段階のアプローチは、元のハードCOでの学習を単純化し、モデルキャパシティの需要を効果的に軽減することができる。
論文 参考訳(メタデータ) (2021-06-09T09:18:18Z) - Self-Directed Online Machine Learning for Topology Optimization [58.920693413667216]
自己指向型オンライン学習最適化は、ディープニューラルネットワーク(DNN)と有限要素法(FEM)計算を統合している。
本アルゴリズムは, コンプライアンスの最小化, 流体構造最適化, 伝熱促進, トラス最適化の4種類の問題によって検証された。
その結果, 直接使用法と比較して計算時間を2~5桁削減し, 実験で検証した全ての最先端アルゴリズムより優れていた。
論文 参考訳(メタデータ) (2020-02-04T20:00:28Z) - Optimizing Wireless Systems Using Unsupervised and
Reinforced-Unsupervised Deep Learning [96.01176486957226]
無線ネットワークにおけるリソース割り当てとトランシーバーは、通常最適化問題の解決によって設計される。
本稿では,変数最適化と関数最適化の両問題を解くための教師なし・教師なし学習フレームワークを紹介する。
論文 参考訳(メタデータ) (2020-01-03T11:01:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。