論文の概要: Optimization by Parallel Quasi-Quantum Annealing with Gradient-Based Sampling
- arxiv url: http://arxiv.org/abs/2409.02135v2
- Date: Wed, 02 Oct 2024 13:11:08 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-10-03 15:17:50.507178
- Title: Optimization by Parallel Quasi-Quantum Annealing with Gradient-Based Sampling
- Title(参考訳): 勾配型サンプリングによる並列準量子アニーリングの最適化
- Authors: Yuma Ichikawa, Yamato Arai,
- Abstract要約: 本研究では、連続緩和による勾配に基づく更新と準量子アナリング(QQA)を組み合わせた別のアプローチを提案する。
数値実験により,本手法はiSCOと学習型解法に匹敵する性能を有する汎用解法であることが示された。
- 参考スコア(独自算出の注目度): 0.0
- License:
- Abstract: Learning-based methods have gained attention as general-purpose solvers due to their ability to automatically learn problem-specific heuristics, reducing the need for manually crafted heuristics. However, these methods often face scalability challenges. To address these issues, the improved Sampling algorithm for Combinatorial Optimization (iSCO), using discrete Langevin dynamics, has been proposed, demonstrating better performance than several learning-based solvers. This study proposes a different approach that integrates gradient-based update through continuous relaxation, combined with Quasi-Quantum Annealing (QQA). QQA smoothly transitions the objective function, starting from a simple convex function, minimized at half-integral values, to the original objective function, where the relaxed variables are minimized only in the discrete space. Furthermore, we incorporate parallel run communication leveraging GPUs to enhance exploration capabilities and accelerate convergence. Numerical experiments demonstrate that our method is a competitive general-purpose solver, achieving performance comparable to iSCO and learning-based solvers across various benchmark problems. Notably, our method exhibits superior speed-quality trade-offs for large-scale instances compared to iSCO, learning-based solvers, commercial solvers, and specialized algorithms.
- Abstract(参考訳): 学習ベースの手法は、問題固有のヒューリスティックを自動学習する能力により、汎用的な解法として注目を集めており、手作業によるヒューリスティックスの必要性が軽減されている。
しかし、これらの手法はスケーラビリティの課題に直面することが多い。
これらの問題に対処するために、離散ランゲヴィン力学を用いた改良された組合せ最適化アルゴリズム(iSCO)が提案され、学習ベースの解法よりも優れた性能を示している。
本研究は, 連続緩和による勾配に基づく更新と準量子アニーリング(QQA)を組み合わせた別のアプローチを提案する。
QQAは、半積分値で最小化される単純な凸関数から、緩和された変数が離散空間でのみ最小化される元の目的関数へと、目的関数を円滑に遷移させる。
さらに、GPUを利用した並列実行通信を導入し、探索能力を高め、収束を加速する。
数値実験により,本手法は,iSCOや学習に基づく様々なベンチマーク問題に匹敵する性能を達成し,競争力のある汎用解法であることを実証した。
特に,本手法は,iSCO,学習型解法,商用解法,特殊アルゴリズムと比較して,大規模インスタンスの高速なトレードオフが優れている。
関連論文リスト
- ODE-based Learning to Optimize [28.380622776436905]
我々は、慣性系とヘッセン駆動制振方程式(ISHD)を統合した包括的枠組みを提案する。
収束・安定条件を考慮した停止時間を最小化することを目的とした新しい学習法(L2O)を定式化する。
本フレームワークの実証検証は,多種多様な最適化問題に対する広範な数値実験を通じて行われる。
論文 参考訳(メタデータ) (2024-06-04T06:39:45Z) - Sample-Efficient Multi-Agent RL: An Optimization Perspective [103.35353196535544]
一般関数近似に基づく汎用マルコフゲーム(MG)のためのマルチエージェント強化学習(MARL)について検討した。
汎用MGに対するマルチエージェントデカップリング係数(MADC)と呼ばれる新しい複雑性尺度を導入する。
我々のアルゴリズムは既存の研究に匹敵するサブリニアな後悔を与えることを示す。
論文 参考訳(メタデータ) (2023-10-10T01:39: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) - Federated Conditional Stochastic Optimization [110.513884892319]
条件付き最適化は、不変学習タスク、AUPRC、AMLなど、幅広い機械学習タスクで見られる。
本稿では,分散フェデレーション学習のためのアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-10-04T01:47:37Z) - Federated Compositional Deep AUC Maximization [58.25078060952361]
本研究では,曲線(AUC)のスコアを直接最適化することにより,不均衡なデータに対する新しいフェデレート学習法を開発した。
私たちの知る限りでは、このような好ましい理論的な結果を達成した最初の作品である。
論文 参考訳(メタデータ) (2023-04-20T05:49:41Z) - Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。
微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
論文 参考訳(メタデータ) (2023-02-24T18:41:48Z) - A Study of Scalarisation Techniques for Multi-Objective QUBO Solving [0.0]
量子および量子に着想を得た最適化アルゴリズムは、学術ベンチマークや実世界の問題に適用した場合に有望な性能を示す。
しかし、QUBOソルバは単目的解法であり、複数の目的による問題の解法をより効率的にするためには、そのような多目的問題を単目的問題に変換する方法を決定する必要がある。
論文 参考訳(メタデータ) (2022-10-20T14:54:37Z) - Sample-Efficient, Exploration-Based Policy Optimisation for Routing
Problems [2.6782615615913348]
本稿では,エントロピーに基づく新しい強化学習手法を提案する。
さらに、我々は、期待したリターンを最大化する、政治以外の強化学習手法を設計する。
我々のモデルは様々な経路問題に一般化可能であることを示す。
論文 参考訳(メタデータ) (2022-05-31T09:51:48Z) - USCO-Solver: Solving Undetermined Stochastic Combinatorial Optimization
Problems [9.015720257837575]
入力-解対のサンプルから高品質な最適化解を推定することを目的として,空間間の回帰を考察する。
基礎学習にはPAC-Bayesianフレームワークを用いて学習エラー分析を行う。
我々は,合成データセットと実世界のデータセットの両方において,古典的な問題に対する高い励振実験結果を得た。
論文 参考訳(メタデータ) (2021-07-15T17:59:08Z) - Certificates of quantum many-body properties assisted by machine
learning [0.0]
本稿では,緩和技術の力と深層強化学習を組み合わせた新しい手法を提案する。
本研究は,多くの移動系の基底状態エネルギーを求める文脈において,本手法の生存可能性について述べる。
我々は、量子情報処理の分野における他の一般的な応用へのアプローチを一般化するためのツールを提供する。
論文 参考訳(メタデータ) (2021-03-05T17:47:26Z) - Combining Deep Learning and Optimization for Security-Constrained
Optimal Power Flow [94.24763814458686]
セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。
SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。
本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
論文 参考訳(メタデータ) (2020-07-14T12:38:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。