制約付き組合せ最適化問題に対するイジングマシン実機とシミュレーテッドアニーリングのハイブリッド手法の提案

• Item type: SIG Technical Reports(1)
• 公開日: 2024-03-21
• タイトル: 制約付き組合せ最適化問題に対するイジングマシン実機とシミュレーテッドアニーリングのハイブリッド手法の提案
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 慶應義塾大学大学院理工学研究科基礎理工学専攻
• 著者所属: 慶應義塾大学大学院理工学研究科基礎理工学専攻
• 著者所属: 慶應義塾大学大学院理工学研究科基礎理工学専攻
• 著者所属: 慶應義塾大学大学院理工学研究科基礎理工学専攻／慶應義塾大学理工学部物理情報工学科／慶應義塾大学ヒト生物学―微生物叢―量子計算研究センター(WPI-Bio2Q)／早稲田大学グリーン・コンピューティング・システム研究機構／東京工業大学国際先駆研究機構
• 著者所属(英): en
• 著者所属(英): Graduate School of Science and Technology, Keio University
• 著者所属(英): en
• 著者所属(英): Graduate School of Science and Technology, Keio University
• 著者所属(英): en
• 著者所属(英): Graduate School of Science and Technology, Keio University
• 著者所属(英): en
• 著者所属(英): Graduate School of Science and Technology, Keio University / Department of Applied Physics and Physico-Informatics, Keio University / Human Biology-Microbiome-Quantum Research Center (WPI-Bio2Q), Keio University / Green Computing System Research Organization, Waseda University / International Research Frontiers Initiative, Tokyo Institute of Technology
• 著者名: 網野, あかね; 服部, 智大; 菊池, 脩太; 田中, 宗
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: イジングマシンは組合せ最適化問題の解探索に対する有効な専用計算機として期待されており，組合せ最適化問題をイジングモデルまたはそれと等価な Quadratic Unconstrained Binary Optimization (QUBO) で定式化し，イジングモデルや QUBO の低エネルギー状態を探索する．イジングマシンのよく知られた課題は，決定変数の個数が増えるにつれてイジングマシンの性能が低下することである．そのため先行研究では，前処理として得られた解候補をもとにいくつかの変数を固定し，変数固定後の問題をイジングマシンで解くハイブリッドアルゴリズムが構築されている．しかし，これらのハイブリッドアルゴリズムは制約条件を考慮していない場合が多い．そこで本研究では，制約条件を含む組合せ最適化問題に適したハイブリッドアルゴリズムを提案する．制約条件を満たす状態間のみを遷移させるシミュレーテッドアニーリングをもとに解候補を作成し，制約条件に反しないように変数を固定する．変数固定後，イジングマシンを用いて解を求める．二次割当問題をベンチマークとしたシミュレーションにより，イジングマシン単体と比較して，高精度な解を探索できることが示された．
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA12894105
• 書誌情報: 研究報告量子ソフトウェア（QS）; 巻 2024-QS-11, 号 29, p. 1-7, 発行日 2024-03-21
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2435-6492
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会