1-hot制約付き問題に対する1-hot変数選択法を用いた部分QUBOアニーリング手法

• Item type: SIG Technical Reports(1)
• 公開日: 2024-11-05
• タイトル: 1-hot制約付き問題に対する1-hot変数選択法を用いた部分QUBOアニーリング手法
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 早稲田大学大学院基幹理工学研究科情報理工・情報通信専攻
• 著者所属: 早稲田大学大学院基幹理工学研究科情報理工・情報通信専攻
• 著者所属: 早稲田大学大学院基幹理工学研究科情報理工・情報通信専攻
• 著者所属: 早稲田大学大学院基幹理工学研究科情報理工・情報通信専攻
• 著者名: 野口, 竜弥; 深田, 佳佑; 鮑, 思雅; 戸川, 望
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: イジングマシンは組合せ最適化問題を効率的に求解するための新しい非ノイマン型コンピュータとして注目されており，問題を Quadratic Unconstrained Binary Optimization (QUBO) モデルにマッピングして基底状態解を探索することができる．しかし，イジングマシンには入力可能な QUBO モデルのサイズに制約があり，大規模な問題を直接解くことが難しい．そこで，QUBO モデルを分割し，分割した部分 QUBO をイジングマシンで繰り返し求解するアプローチが研究されているが，良い解を高速に得るには効率的な分割手法が鍵となる．そこで本研究では，実行可能解において値が 1 の二値変数の個数が一定となる 1-hot 制約に焦点を当て，問題の制約条件を考慮した新たな QUBO 分割手法を提案する．1-hot 制約を有する組合せ最適化問題では，実行可能解において値が 1 となる二値変数の個数が一定であるため，アニーリングにおいてより良いエネルギー値へと更新するには，値が 1 の二値変数数を陽に考慮することが重要である．1-hot 制約付き問題を効率的に解決するために，値が 1 の二値変数を優先的に選択する 1-hot 変数選択法を提案し，従来の偏差選択法やランダム選択法と組み合わせた新しい部分 QUBO アニーリング手法を提案する．1-hot 制約を持つ複数日旅程最適化問題に提案手法を適用し，イジングマシンを用いて結果を評価し，既存手法との比較を行う．評価実験の結果，従来の部分 QUBO アニーリング手法よりもエネルギーの低い解を少ない繰り返し回数で得ることができた．
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11451459
• 書誌情報: 研究報告システムとLSIの設計技術（SLDM）; 巻 2024-SLDM-207, 号 55, p. 1-6, 発行日 2024-11-05
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8639
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会