論文の概要: A Graph Neural Network-Based QUBO-Formulated Hamiltonian-Inspired Loss
Function for Combinatorial Optimization using Reinforcement Learning
- arxiv url: http://arxiv.org/abs/2308.13978v2
- Date: Thu, 28 Sep 2023 13:08:22 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-29 19:58:40.692915
- Title: A Graph Neural Network-Based QUBO-Formulated Hamiltonian-Inspired Loss
Function for Combinatorial Optimization using Reinforcement Learning
- Title（参考訳）: グラフニューラルネットワークに基づく強化学習を用いた組合せ最適化のためのQUBO型ハミルトン型損失関数
- Authors: Redwan Ahmed Rizvee, Md. Mosaddek Khan
- Abstract要約: ハミルトニアン函数は、最適化の文脈において目的関数として使用されるQUBO問題を定式化するためにしばしば用いられる。
汎用的なスケーラブルなフレームワークであるPI-GNNは、単純なグラフニューラルネットワーク(GNN)アーキテクチャに基づいて、グラフ上の組合せ最適化(CO)問題に対処するために提案されている。
実験では,PI-GNN法と比較して最大44%改善した。
- 参考スコア（独自算出の注目度）: 1.566437882635872
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Quadratic Unconstrained Binary Optimization (QUBO) is a generic technique to
model various NP-hard combinatorial optimization problems in the form of binary
variables. The Hamiltonian function is often used to formulate QUBO problems
where it is used as the objective function in the context of optimization.
Recently, PI-GNN, a generic scalable framework, has been proposed to address
the Combinatorial Optimization (CO) problems over graphs based on a simple
Graph Neural Network (GNN) architecture. Their novel contribution was a generic
QUBO-formulated Hamiltonian-inspired loss function that was optimized using
GNN. In this study, we address a crucial issue related to the aforementioned
setup especially observed in denser graphs. The reinforcement learning-based
paradigm has also been widely used to address numerous CO problems. Here we
also formulate and empirically evaluate the compatibility of the
QUBO-formulated Hamiltonian as the generic reward function in the Reinforcement
Learning paradigm to directly integrate the actual node projection status
during training as the form of rewards. In our experiments, we observed up to
44% improvement in the RL-based setup compared to the PI-GNN algorithm. Our
implementation can be found in
https://github.com/rizveeredwan/learning-graph-structure.
- Abstract（参考訳）: Quadratic Unconstrained Binary Optimization (QUBO) は、NP-hard組合せ最適化問題をバイナリ変数の形でモデル化する一般的な手法である。
ハミルトニアン函数は、最適化の文脈において目的関数として使用されるQUBO問題を定式化するためにしばしば用いられる。
近年,単純なグラフニューラルネットワーク(GNN)アーキテクチャに基づくグラフ上での組合せ最適化(CO)問題に対処するために,汎用スケーラブルフレームワークであるPI-GNNが提案されている。
彼らの新しい貢献は、GNNを用いて最適化されたQUBO形式のハミルトン型損失関数である。
本研究では,高密度グラフで特に観察される上記の設定に関する重要な問題に対処する。
強化学習に基づくパラダイムは、多くのCO問題に対処するために広く使われている。
ここでは,強化学習パラダイムの汎用報酬関数としてquboによるハミルトニアンの適合性を定式化し,経験的に評価し,トレーニング中のノード投影状態を報酬の形式として直接統合する。
実験では,PI-GNN法と比較して最大44%改善した。
実装はhttps://github.com/rizveeredwan/learning-graph-structureにあります。
関連論文リスト
- Enhancing GNNs Performance on Combinatorial Optimization by Recurrent Feature Update [0.09986418756990156]
本稿では,組合せ最適化(CO)問題を効率よく解くために,GNNのパワーを活用して,QRF-GNNと呼ぶ新しいアルゴリズムを提案する。
QUBO緩和による損失関数の最小化による教師なし学習に依存している。
実験の結果、QRF-GNNは既存の学習ベースアプローチを大幅に上回り、最先端の手法に匹敵することがわかった。
論文 参考訳（メタデータ） (2024-07-23T13:34:35Z) - Decision-focused Graph Neural Networks for Combinatorial Optimization [62.34623670845006]
最適化問題に取り組むための新たな戦略は、従来のアルゴリズムに代わるグラフニューラルネットワーク(GNN)の採用である。
GNNや従来のアルゴリズムソルバがCOの領域で人気が高まっているにもかかわらず、それらの統合利用とエンドツーエンドフレームワークにおけるそれらの相関について限定的な研究がなされている。
我々は、GNNを利用してCO問題に補助的なサポートで対処する決定に焦点を当てたフレームワークを導入する。
論文 参考訳（メタデータ） (2024-06-05T22:52:27Z) - Combinatorial Optimization with Automated Graph Neural Networks [28.19349828026972]
NP-hard CO 問題,すなわち textbfAutoGNP を解決するために,textbfAUTOmated textbfGNN のクラスを新たに提案する。
AutoGNPの考え方は、グラフニューラルアーキテクチャ検索アルゴリズムを使用して、与えられたNPハード最適化問題に対して最適なGNNを自動的に見つけることである。
論文 参考訳（メタデータ） (2024-06-05T02:43:41Z) - Hamiltonian-based Quantum Reinforcement Learning for Neural Combinatorial Optimization [2.536162003546062]
量子コンピューティング(QC)とニューラル最適化(NCO)の交差点におけるアプローチとして,ハミルトニアンの量子強化学習(QRL)を導入する。
我々のアンサーゼは、ハードウェア効率のよいアンサーゼと比較して、良好なトレーサビリティ特性を示す一方で、以前の研究とは異なり、グラフベースの問題に制限されない。
本研究では,ハミルトニアンのQRLの性能を多種多様な最適化問題で評価し,本手法の適用可能性を実証し,QAOAと比較する。
論文 参考訳（メタデータ） (2024-05-13T14:36:22Z) - A Graph Neural Network-Based QUBO-Formulated Hamiltonian-Inspired Loss
Function for Combinatorial Optimization using Reinforcement Learning [1.325953054381901]
グラフニューラルネットワーク(GNN)を用いた新しいモンティカルロ木探索手法を提案する。
PI-GNNに関連する行動パターンを特定し,その性能向上のための戦略を考案する。
また、RL法とQUBO法で定式化されたハミルトニアンとの橋渡しにも着目する。
論文 参考訳（メタデータ） (2023-11-27T19:33:14Z) - Neural Improvement Heuristics for Graph Combinatorial Optimization
Problems [49.85111302670361]
本稿では,ノード,エッジ,あるいはその両方に情報をエンコードするグラフベースの問題を扱う新しいニューラル改善(NI)モデルを提案する。
提案モデルは,各地区の操作の選択を誘導する丘登頂に基づくアルゴリズムの基本的な構成要素として機能する。
論文 参考訳（メタデータ） (2022-06-01T10:35:29Z) - GPN: A Joint Structural Learning Framework for Graph Neural Networks [36.38529113603987]
グラフ構造と下流タスクを同時に学習するGNNベースの共同学習フレームワークを提案する。
本手法は,この課題を解決するためのGNNベースの二段階最適化フレームワークである。
論文 参考訳（メタデータ） (2022-05-12T09:06:04Z) - A Unified View on Graph Neural Networks as Graph Signal Denoising [49.980783124401555]
グラフニューラルネットワーク(GNN)は,グラフ構造化データの学習表現において顕著に普及している。
本研究では,代表的GNNモデル群における集約過程を,グラフ記述問題の解法とみなすことができることを数学的に確立する。
UGNNから派生した新しいGNNモデルADA-UGNNをインスタンス化し、ノード間の適応的滑らかさでグラフを処理する。
論文 参考訳（メタデータ） (2020-10-05T04:57:18Z) - Multipole Graph Neural Operator for Parametric Partial Differential
Equations [57.90284928158383]
物理系をシミュレーションするためのディープラーニングベースの手法を使用する際の大きな課題の1つは、物理ベースのデータの定式化である。
線形複雑度のみを用いて、あらゆる範囲の相互作用をキャプチャする、新しいマルチレベルグラフニューラルネットワークフレームワークを提案する。
実験により, 離散化不変解演算子をPDEに学習し, 線形時間で評価できることを確認した。
論文 参考訳（メタデータ） (2020-06-16T21:56:22Z) - Binarized Graph Neural Network [65.20589262811677]
我々は二項化グラフニューラルネットワークを開発し、二項化ネットワークパラメータを用いてノードのバイナリ表現を学習する。
提案手法は既存のGNNベースの埋め込み手法にシームレスに統合できる。
実験により、提案された二項化グラフニューラルネットワーク、すなわちBGNは、時間と空間の両方の観点から、桁違いに効率的であることが示されている。
論文 参考訳（メタデータ） (2020-04-19T09:43:14Z) - Graph Ordering: Towards the Optimal by Learning [69.72656588714155]
グラフ表現学習は、ノード分類、予測、コミュニティ検出など、多くのグラフベースのアプリケーションで顕著な成功を収めている。
しかし,グラフ圧縮やエッジ分割などのグラフアプリケーションでは,グラフ表現学習タスクに還元することは極めて困難である。
本稿では,このようなアプリケーションの背後にあるグラフ順序付け問題に対して,新しい学習手法を用いて対処することを提案する。
論文 参考訳（メタデータ） (2020-01-18T09:14:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。