論文の概要: 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問題を解決できることの予備的証拠を示す。

関連論文リスト

• 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)
• Towards a General GNN Framework for Combinatorial Optimization [14.257210124854863]
  本稿では,グラフ上のCO問題の解法として,複雑なフィルタバンクと局所的注意機構を活用する新しいGNNアーキテクチャを提案する。 提案手法が従来のGNNベースのCOソルバとどのように差別化され,最大傾き,最小支配セット,最大カット問題に効果的に適用可能であるかを示す。
  論文  参考訳（メタデータ） (2024-05-31T00:02:07Z)
• Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNets [86.43523688236077]
  組合せ最適化(CO)問題はしばしばNPハードであり、正確なアルゴリズムには及ばない。 GFlowNetsは、複合非正規化密度を逐次サンプリングする強力な機械として登場した。 本稿では,異なる問題に対してマルコフ決定プロセス(MDP)を設計し,条件付きGFlowNetを学習して解空間からサンプルを作成することを提案する。
  論文  参考訳（メタデータ） (2023-05-26T15:13:09Z)
• 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)
• 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)

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

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