論文の概要: A Graph Neural Network-Based QUBO-Formulated Hamiltonian-Inspired Loss
Function for Combinatorial Optimization using Reinforcement Learning
- arxiv url: http://arxiv.org/abs/2311.16277v1
- Date: Mon, 27 Nov 2023 19:33:14 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-29 21:17:31.582498
- Title: A Graph Neural Network-Based QUBO-Formulated Hamiltonian-Inspired Loss
Function for Combinatorial Optimization using Reinforcement Learning
- Title（参考訳）: グラフニューラルネットワークに基づく強化学習を用いた組合せ最適化のためのQUBO型ハミルトン型損失関数
- Authors: Redwan Ahmed Rizvee, Raheeb Hasan and Md. Mosaddek Khan
- Abstract要約: グラフニューラルネットワーク(GNN)を用いた新しいモンティカルロ木探索手法を提案する。
PI-GNNに関連する行動パターンを特定し,その性能向上のための戦略を考案する。
また、RL法とQUBO法で定式化されたハミルトニアンとの橋渡しにも着目する。
- 参考スコア（独自算出の注目度）: 1.325953054381901
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Quadratic Unconstrained Binary Optimization (QUBO) is a generic technique to
model various NP-hard Combinatorial Optimization problems (CO) in the form of
binary variables. Ising Hamiltonian is used to model the energy function of a
system. QUBO to Ising Hamiltonian is regarded as a technique to solve various
canonical optimization problems through quantum optimization algorithms.
Recently, PI-GNN, a generic framework, has been proposed to address CO problems
over graphs based on Graph Neural Network (GNN) architecture. They introduced a
generic QUBO-formulated Hamiltonian-inspired loss function that was directly
optimized using GNN. PI-GNN is highly scalable but there lies a noticeable
decrease in the number of satisfied constraints when compared to
problem-specific algorithms and becomes more pronounced with increased graph
densities. Here, We identify a behavioral pattern related to it and devise
strategies to improve its performance. Another group of literature uses
Reinforcement learning (RL) to solve the aforementioned NP-hard problems using
problem-specific reward functions. In this work, we also focus on creating a
bridge between the RL-based solutions and the QUBO-formulated Hamiltonian. We
formulate and empirically evaluate the compatibility of the QUBO-formulated
Hamiltonian as the generic reward function in the RL-based paradigm in the form
of rewards. Furthermore, we also introduce a novel Monty Carlo Tree
Search-based strategy with GNN where we apply a guided search through manual
perturbation of node labels during training. We empirically evaluated our
methods and observed up to 44% improvement in the number of constraint
violations compared to the PI-GNN.
- Abstract（参考訳）: Quadratic Unconstrained Binary Optimization (QUBO) は、NP-hard Combinatorial Optimization problem (CO) をバイナリ変数の形でモデル化する一般的な手法である。
イジングハミルトニアンはシステムのエネルギー関数のモデル化に使用される。
QUBO to Ising Hamiltonian は量子最適化アルゴリズムによって様々な正準最適化問題を解く手法であると考えられている。
近年,グラフニューラルネットワーク(GNN)アーキテクチャに基づくグラフ上のCO問題に対処する汎用フレームワークPI-GNNが提案されている。
彼らは、GNNを直接最適化したQUBO形式のハミルトン型損失関数を導入した。
PI-GNNは非常にスケーラブルであるが、問題固有のアルゴリズムと比較して満足度制約の数が大幅に減少し、グラフ密度の増大とともにより顕著になる。
本稿では,それに関連する行動パターンを特定し,その性能向上のための戦略を考案する。
別の文献群では、前述のNPハード問題を問題固有報酬関数を用いて解くために強化学習(RL)を用いる。
この研究では、RL-ベースソリューションとQUBO-形式ハミルトニアンの間の橋渡しにも焦点をあてる。
我々は、QUBO形式ハミルトンの適合性を、報酬の形でRLに基づくパラダイムにおける一般的な報酬関数として定式化し、実証的に評価する。
さらに,GNNを用いた新しいモンティカルロ木探索手法を導入し,学習中のノードラベルの手動摂動によるガイド付き探索を行う。
提案手法を実証的に評価し,PI-GNNと比較して最大44%の制約違反数の改善が見られた。
関連論文リスト
- 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.566437882635872]
ハミルトニアン函数は、最適化の文脈において目的関数として使用されるQUBO問題を定式化するためにしばしば用いられる。
汎用的なスケーラブルなフレームワークであるPI-GNNは、単純なグラフニューラルネットワーク(GNN)アーキテクチャに基づいて、グラフ上の組合せ最適化(CO)問題に対処するために提案されている。
実験では,PI-GNN法と比較して最大44%改善した。
論文 参考訳（メタデータ） (2023-08-27T00:57:01Z) - On Representing Linear Programs by Graph Neural Networks [30.998508318941017]
グラフニューラルネットワーク(GNN)は最適化問題に適した機械学習モデルであると考えられている。
本稿では,線形プログラム(LP)問題にGNNを適用する理論的基礎を確立する。
適切に構築されたGNNは、幅広いクラスにおける各LPに対して、実現可能性、有界性、最適解を確実に予測できることを示す。
論文 参考訳（メタデータ） (2022-09-25T18:27:33Z) - Neural Improvement Heuristics for Graph Combinatorial Optimization
Problems [49.85111302670361]
本稿では,ノード,エッジ,あるいはその両方に情報をエンコードするグラフベースの問題を扱う新しいニューラル改善(NI)モデルを提案する。
提案モデルは,各地区の操作の選択を誘導する丘登頂に基づくアルゴリズムの基本的な構成要素として機能する。
論文 参考訳（メタデータ） (2022-06-01T10:35:29Z) - Meta-Solver for Neural Ordinary Differential Equations [77.8918415523446]
本研究では,ソルバ空間の変動がニューラルODEの性能を向上する方法について検討する。
解法パラメータ化の正しい選択は, 敵の攻撃に対するロバスト性の観点から, 神経odesモデルに大きな影響を与える可能性がある。
論文 参考訳（メタデータ） (2021-03-15T17:26:34Z) - Fast Learning of Graph Neural Networks with Guaranteed Generalizability:
One-hidden-layer Case [93.37576644429578]
グラフニューラルネットワーク(GNN)は、グラフ構造化データから実際に学習する上で、近年大きな進歩を遂げている。
回帰問題と二項分類問題の両方に隠れ層を持つGNNの理論的に基底的な一般化可能性解析を行う。
論文 参考訳（メタデータ） (2020-06-25T00:45:52Z) - Multipole Graph Neural Operator for Parametric Partial Differential
Equations [57.90284928158383]
物理系をシミュレーションするためのディープラーニングベースの手法を使用する際の大きな課題の1つは、物理ベースのデータの定式化である。
線形複雑度のみを用いて、あらゆる範囲の相互作用をキャプチャする、新しいマルチレベルグラフニューラルネットワークフレームワークを提案する。
実験により, 離散化不変解演算子をPDEに学習し, 線形時間で評価できることを確認した。
論文 参考訳（メタデータ） (2020-06-16T21:56:22Z) - Optimization and Generalization Analysis of Transduction through
Gradient Boosting and Application to Multi-scale Graph Neural Networks [60.22494363676747]
現在のグラフニューラルネットワーク(GNN)は、オーバースムーシング(over-smoothing)と呼ばれる問題のため、自分自身を深くするのは難しいことが知られている。
マルチスケールGNNは、オーバースムーシング問題を緩和するための有望なアプローチである。
マルチスケールGNNを含むトランスダクティブ学習アルゴリズムの最適化と一般化を保証する。
論文 参考訳（メタデータ） (2020-06-15T17:06:17Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。