論文の概要: Self-Adaptive Ising Machines for Constrained Optimization
- arxiv url: http://arxiv.org/abs/2501.04971v1
- Date: Thu, 09 Jan 2025 05:02:50 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-01-10 14:00:44.037165
- Title: Self-Adaptive Ising Machines for Constrained Optimization
- Title(参考訳): 制約付き最適化のための自己適応型イジングマシン
- Authors: Corentin Delacour,
- Abstract要約: 制約のラグランジュ緩和を用いてエネルギー景観を形作る自己適応型IMを提案し, 罰則の事前調整を回避する。
我々は,多次元クナップサック問題 (MKP) と二次クナップサック問題 (QKP) でアルゴリズムをベンチマークし,後者は線形制約を持つイジング問題である。
その結果,探索中にエネルギー環境に適応することで,制約付き最適化のためにIMを高速化できることが示唆された。
- 参考スコア(独自算出の注目度): 0.4450107621124637
- License:
- Abstract: Ising machines (IM) are physics-inspired alternatives to von Neumann architectures for solving hard optimization tasks. By mapping binary variables to coupled Ising spins, IMs can naturally solve unconstrained combinatorial optimization problems such as finding maximum cuts in graphs. However, despite their importance in practical applications, constrained problems remain challenging to solve for IMs that require large quadratic energy penalties to ensure the correspondence between energy ground states and constrained optimal solutions. To relax this requirement, we propose a self-adaptive IM that iteratively shapes its energy landscape using a Lagrange relaxation of constraints and avoids prior tuning of penalties. Using a probabilistic-bit (p-bit) IM emulated in software, we benchmark our algorithm with multidimensional knapsack problems (MKP) and quadratic knapsack problems (QKP), the latter being an Ising problem with linear constraints. For QKP with 300 variables, the proposed algorithm finds better solutions than state-of-the-art IMs such as Fujitsu's Digital Annealer and requires 7,500x fewer samples. Our results show that adapting the energy landscape during the search can speed up IMs for constrained optimization.
- Abstract(参考訳): イジングマシン (Ising Machine, IIM) は、ハード最適化タスクを解くための、フォン・ノイマンのアーキテクチャに代わる物理に着想を得た代替品である。
二項変数を結合したイジングスピンにマッピングすることで、IMはグラフの最大カットを見つけるなどの制約のない組合せ最適化問題を自然に解くことができる。
しかし、実際的な応用において重要であるにもかかわらず、エネルギー基底状態と制約された最適解との対応を確保するために2次エネルギーの2次ペナルティを必要とするIMの解決は依然として困難である。
この要求を緩和するために,制約のラグランジュ緩和を用いてエネルギー景観を反復的に形成し,罰則の事前調整を回避する自己適応型IMを提案する。
ソフトウェアでエミュレートされた確率的ビット(pビット)IMを用いて,多次元クナップサック問題 (MKP) と二次クナップサック問題 (QKP) でアルゴリズムをベンチマークし,後者は線形制約を持つイジング問題である。
300変数のQKPの場合、提案アルゴリズムは富士通のDigital Annealerのような最先端のIMよりも優れた解を見つけ、サンプルは7,500倍少ない。
その結果,探索中にエネルギー環境に適応することで,制約付き最適化のためにIMを高速化できることが示唆された。
関連論文リスト
- Non-Myopic Multi-Objective Bayesian Optimization [64.31753000439514]
多目的最適化問題を解くために、有限水平逐次実験設計の問題を考察する。
この問題は、材料設計を含む多くの現実世界の応用で発生する。
我々はMOO問題に対する最初の非ミオピック手法を提案する。
論文 参考訳(メタデータ) (2024-12-11T04:05:29Z) - Optimized QUBO formulation methods for quantum computing [0.4999814847776097]
実世界の金融シナリオにインスパイアされたNPハード最適化問題に対して,我々の手法を適用する方法について述べる。
2つのD波量子異方体にこの問題の事例を提出し、これらのシナリオで使用される標準手法と新しい手法の性能を比較した。
論文 参考訳(メタデータ) (2024-06-11T19:59:05Z) - Multiobjective variational quantum optimization for constrained
problems: an application to Cash Management [45.82374977939355]
本稿では,変分量子アルゴリズムを用いた制約付き最適化問題の解法を提案する。
我々は、キャッシュマネジメント問題という、金融の極めて関連性の高い現実世界の問題について、我々の提案を検証した。
実験の結果, 実現したソリューションのコスト, 特に局所最小値の回避に関して, 大幅な改善が見られた。
論文 参考訳(メタデータ) (2023-02-08T17:09:20Z) - Fermionic Quantum Approximate Optimization Algorithm [11.00442581946026]
制約付き最適化問題を解くためのフェルミオン量子近似最適化アルゴリズム(FQAOA)を提案する。
FQAOAは、フェルミオン粒子数保存を用いて、QAOAを通して本質的にそれらを強制する制約問題に対処する。
制約付きハミルトニアン問題に対して、運転者ハミルトニアンを設計するための体系的なガイドラインを提供する。
論文 参考訳(メタデータ) (2023-01-25T18:36:58Z) - Symmetric Tensor Networks for Generative Modeling and Constrained
Combinatorial Optimization [72.41480594026815]
ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。
これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。
本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
論文 参考訳(メタデータ) (2022-11-16T18:59:54Z) - Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。
これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。
本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
論文 参考訳(メタデータ) (2022-02-17T18:59:20Z) - Offline Model-Based Optimization via Normalized Maximum Likelihood
Estimation [101.22379613810881]
データ駆動最適化の問題を検討し、一定の点セットでクエリのみを与えられた関数を最大化する必要がある。
この問題は、関数評価が複雑で高価なプロセスである多くの領域に現れる。
我々は,提案手法を高容量ニューラルネットワークモデルに拡張可能なトラクタブル近似を提案する。
論文 参考訳(メタデータ) (2021-02-16T06:04:27Z) - TIGER: Topology-aware Assignment using Ising machines Application to
Classical Algorithm Tasks and Quantum Circuit Gates [2.4047296366832307]
ゲートベースの量子コンピューティングでは、トポロジー的な方法でタスクをゲートにマップすることを目的とするマッピング問題が存在する。
既存のタスクアプローチは、物理最適化アルゴリズムのいずれかに基づいており、異なるスピードとソリューション品質のトレードオフを提供する。
本稿では,Ising マシンを用いてトポロジ対応の代入問題を解くアルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-09-21T19:46:59Z) - Max-value Entropy Search for Multi-Objective Bayesian Optimization with
Constraints [44.25245545568633]
航空電力システム設計の応用においては、運動温度とセル電圧の比しきい値を満たすとともに、総エネルギーと質量をトレードオフする設計を見出す必要がある。
本稿では,制約付き多目的最適化のためのem Max-value Entropy Search (MESMOC) と呼ばれる新しい手法を提案する。
MESMOCは、出力空間エントロピーに基づく取得関数を使用して、評価のための入力のシーケンスを効率的に選択し、高品質なパリトセットソリューションを明らかにする。
論文 参考訳(メタデータ) (2020-09-01T05:00:01Z) - Convergence of adaptive algorithms for weakly convex constrained
optimization [59.36386973876765]
モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。
我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
論文 参考訳(メタデータ) (2020-06-11T17:43:19Z) - Cross Entropy Hyperparameter Optimization for Constrained Problem
Hamiltonians Applied to QAOA [68.11912614360878]
QAOA(Quantum Approximate Optimization Algorithm)のようなハイブリッド量子古典アルゴリズムは、短期量子コンピュータを実用的に活用するための最も奨励的なアプローチの1つである。
このようなアルゴリズムは通常変分形式で実装され、古典的な最適化法と量子機械を組み合わせて最適化問題の優れた解を求める。
本研究では,クロスエントロピー法を用いてランドスケープを形作り,古典的パラメータがより容易により良いパラメータを発見でき,その結果,性能が向上することを示す。
論文 参考訳(メタデータ) (2020-03-11T13:52:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。