Fugu-MT 論文翻訳(概要): CHARME: A chain-based reinforcement learning approach for the minor embedding problem

論文の概要: CHARME: A chain-based reinforcement learning approach for the minor embedding problem

arxiv url: http://arxiv.org/abs/2406.07124v1
Date: Tue, 11 Jun 2024 10:12:10 GMT
ステータス: 処理完了
システム内更新日: 2024-06-12 16:34:54.450346
Title: CHARME: A chain-based reinforcement learning approach for the minor embedding problem
Title（参考訳）: CHARME:小さな埋め込み問題に対する連鎖型強化学習アプローチ
Authors: Hoang M. Ngo, Nguyen H K. Do, Minh N. Vu, Tamer Kahveci, My T. Thai,
Abstract要約: 本稿では,CHARME という名前の小さな埋め込み問題に対処するために,強化学習(RL)技術を利用した新しい手法を提案する。 CHARMEには、ポリシーモデリングのためのグラフニューラルネットワーク(GNN)アーキテクチャ、ソリューションの有効性を保証する状態遷移アルゴリズム、効果的なトレーニングのための順序探索戦略の3つの重要なコンポーネントが含まれている。詳細では、CHARME は Minorminer や ATOM のような高速な埋め込み法に比べて優れた解が得られる。
参考スコア（独自算出の注目度）: 16.24890195949869
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Quantum Annealing (QA) holds great potential for solving combinatorial optimization problems efficiently. However, the effectiveness of QA algorithms heavily relies on the embedding of problem instances, represented as logical graphs, into the quantum unit processing (QPU) whose topology is in form of a limited connectivity graph, known as the minor embedding Problem. Existing methods for the minor embedding problem suffer from scalability issues when confronted with larger problem sizes. In this paper, we propose a novel approach utilizing Reinforcement Learning (RL) techniques to address the minor embedding problem, named CHARME. CHARME includes three key components: a Graph Neural Network (GNN) architecture for policy modeling, a state transition algorithm ensuring solution validity, and an order exploration strategy for effective training. Through comprehensive experiments on synthetic and real-world instances, we demonstrate that the efficiency of our proposed order exploration strategy as well as our proposed RL framework, CHARME. In details, CHARME yields superior solutions compared to fast embedding methods such as Minorminer and ATOM. Moreover, our method surpasses the OCT-based approach, known for its slower runtime but high-quality solutions, in several cases. In addition, our proposed exploration enhances the efficiency of the training of the CHARME framework by providing better solutions compared to the greedy strategy.
Abstract（参考訳）: 量子アニーリング(QA)は組合せ最適化問題を効率的に解く大きな可能性を秘めている。しかし、QAアルゴリズムの有効性は、論理グラフとして表される問題インスタンスを量子単位処理(QPU)に埋め込むことに大きく依存している。組込み問題に対する既存の手法は、より大きな問題サイズに直面した場合、スケーラビリティの問題に悩まされる。本稿では,Reinforcement Learning(RL)技術を用いて,CHARMEという小さな埋め込み問題に対処する手法を提案する。 CHARMEには、ポリシーモデリングのためのグラフニューラルネットワーク(GNN)アーキテクチャ、ソリューションの有効性を保証する状態遷移アルゴリズム、効果的なトレーニングのための順序探索戦略の3つの重要なコンポーネントが含まれている。合成および実世界のインスタンスに関する総合的な実験を通して、提案した順序探索戦略と提案したRLフレームワークであるCHARMEの有効性を実証した。詳細では、CHARME は Minorminer や ATOM のような高速な埋め込み法に比べて優れた解が得られる。さらに,本手法は,実行が遅いが高品質なソリューションで知られているOCTベースのアプローチを,いくつかのケースで超越している。さらに,提案手法は,欲求戦略に比較して優れたソリューションを提供することにより,CHARMEフレームワークのトレーニング効率を向上させる。

関連論文リスト

Optimization by Parallel Quasi-Quantum Annealing with Gradient-Based Sampling [0.0]
本研究では、連続緩和による勾配に基づく更新と準量子アナリング(QQA)を組み合わせた別のアプローチを提案する。数値実験により,本手法はiSCOと学習型解法に匹敵する性能を有する汎用解法であることが示された。
論文参考訳（メタデータ） (2024-09-02T12:55:27Z)
Decision-focused Graph Neural Networks for Combinatorial Optimization [62.34623670845006]
最適化問題に取り組むための新たな戦略は、従来のアルゴリズムに代わるグラフニューラルネットワーク(GNN)の採用である。 GNNや従来のアルゴリズムソルバがCOの領域で人気が高まっているにもかかわらず、それらの統合利用とエンドツーエンドフレームワークにおけるそれらの相関について限定的な研究がなされている。我々は、GNNを利用してCO問題に補助的なサポートで対処する決定に焦点を当てたフレームワークを導入する。
論文参考訳（メタデータ） (2024-06-05T22:52:27Z)
An Efficient Learning-based Solver Comparable to Metaheuristics for the Capacitated Arc Routing Problem [67.92544792239086]
我々は,高度メタヒューリスティックスとのギャップを著しく狭めるため,NNベースの解法を導入する。まず,方向対応型注意モデル(DaAM)を提案する。第2に、教師付き事前学習を伴い、堅牢な初期方針を確立するための教師付き強化学習スキームを設計する。
論文参考訳（メタデータ） (2024-03-11T02:17:42Z)
Boosting Fairness and Robustness in Over-the-Air Federated Learning [3.2088888904556123]
オーバー・ザ・エア・コンピューティングは5G以上の通信戦略である。 minmax最適化による公平性とロバスト性の提供を目的としたOver-the-Airフェデレーション学習アルゴリズムを提案する。
論文参考訳（メタデータ） (2024-03-07T12:03:04Z)
Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods [52.0617030129699]
本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
論文参考訳（メタデータ） (2023-10-08T23:39:38Z)
A Survey on Influence Maximization: From an ML-Based Combinatorial Optimization [2.9882027965916413]
影響最大化(IM)は、モバイルネットワーク、ソーシャルコンピューティング、レコメンデーションシステムで広く用いられる古典的な最適化問題である。主な課題は、IM問題のNP硬度と、影響力の広がりを推定する#P硬度である。我々は,関連する背景知識,基本原則,共通手法,応用研究の要約に重点を置いている。
論文参考訳（メタデータ） (2022-11-06T10:13:42Z)
Adaptive Discretization in Online Reinforcement Learning [9.560980936110234]
離散化に基づくアルゴリズムを設計する際の2つの大きな疑問は、離散化をどのように生成し、いつそれを洗練するかである。オンライン強化学習のための木に基づく階層分割手法の統一的理論的解析を行う。我々のアルゴリズムは操作制約に容易に適応し、我々の理論は3つの面のそれぞれに明示的な境界を与える。
論文参考訳（メタデータ） (2021-10-29T15:06:15Z)
Efficient Model-Based Multi-Agent Mean-Field Reinforcement Learning [89.31889875864599]
マルチエージェントシステムにおける学習に有効なモデルベース強化学習アルゴリズムを提案する。我々の理論的な貢献は、MFCのモデルベース強化学習における最初の一般的な後悔の限界である。コア最適化問題の実用的なパラメトリゼーションを提供する。
論文参考訳（メタデータ） (2021-07-08T18:01:02Z)
A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs [91.07247251502564]
本稿では,2つの世界の長所を結合するハイブリッドな手法を提案する。この手法では,グラフを最適化する上層学習手法とバイレベルフレームワークを開発する。このような二段階のアプローチは、元のハードCOでの学習を単純化し、モデルキャパシティの需要を効果的に軽減することができる。
論文参考訳（メタデータ） (2021-06-09T09:18:18Z)
Reversible Action Design for Combinatorial Optimization with Reinforcement Learning [35.50454156611722]
強化学習(rl)は、これらの問題に取り組むための新しいフレームワークとして最近登場した。最先端の実証性能を示すだけでなく、様々な種類のCOPに一般化する汎用RLフレームワークを提案します。
論文参考訳（メタデータ） (2021-02-14T18:05:42Z)
MineReduce: an approach based on data mining for problem size reduction [58.720142291102135]
本稿では,マイニングパターンを用いて問題サイズの削減を行うMineReduceという手法を提案する。異種車両ルーティング問題に対するMineReduceの適用について述べる。
論文参考訳（メタデータ） (2020-05-15T08:49:50Z)

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

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