2026-03-14T16:31:23Z https://ipsj.ixsq.nii.ac.jp/oai

oai:ipsj.ixsq.nii.ac.jp:00233703 2025-01-19T10:01:02Z 1164:10193:11470:11538

制約付き組合せ最適化問題に対するイジングマシン実機とシミュレーテッドアニーリングのハイブリッド手法の提案 網野, あかね 服部, 智大 菊池, 脩太 田中, 宗 イジングマシンは組合せ最適化問題の解探索に対する有効な専用計算機として期待されており，組合せ最適化問題をイジングモデルまたはそれと等価な Quadratic Unconstrained Binary Optimization (QUBO) で定式化し，イジングモデルや QUBO の低エネルギー状態を探索する．イジングマシンのよく知られた課題は，決定変数の個数が増えるにつれてイジングマシンの性能が低下することである．そのため先行研究では，前処理として得られた解候補をもとにいくつかの変数を固定し，変数固定後の問題をイジングマシンで解くハイブリッドアルゴリズムが構築されている．しかし，これらのハイブリッドアルゴリズムは制約条件を考慮していない場合が多い．そこで本研究では，制約条件を含む組合せ最適化問題に適したハイブリッドアルゴリズムを提案する．制約条件を満たす状態間のみを遷移させるシミュレーテッドアニーリングをもとに解候補を作成し，制約条件に反しないように変数を固定する．変数固定後，イジングマシンを用いて解を求める．二次割当問題をベンチマークとしたシミュレーションにより，イジングマシン単体と比較して，高精度な解を探索できることが示された． technical report 情報処理学会 2024-03-21 application/pdf 研究報告量子ソフトウェア（QS） 29 2024-QS-11 1 7 2435-6492 AA12894105 https://ipsj.ixsq.nii.ac.jp/record/233703/files/IPSJ-QS24011029.pdf jpn