実イジング計算機による制約付きスロット配置問題の解法

• Item type: SIG Technical Reports(1)
• 公開日: 2019-03-10
• タイトル: 実イジング計算機による制約付きスロット配置問題の解法
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 計算手法
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 早稲田大学大学院基幹理工学研究科情報理工・情報通信専攻
• 著者所属: 早稲田大学基幹理工学部情報通信学科
• 著者所属: 早稲田大学グリーン・コンピューティング・システム研究機構／科学技術振興機構さきがけ
• 著者所属: 早稲田大学大学院基幹理工学研究科情報理工・情報通信専攻
• 著者名: 金丸, 翔; 川村, 一志; 田中, 宗; 戸川, 望
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: イジング計算機は組合せ最適化問題を物理システムにマッピングすることで，組合せ最適化問題の準最適解を高速に得ることができるとして注目されている．スロット配置問題は論理ブロックの最適配置や最適配送決定において重要な役割を果たす組合せ最適化問題である．本研究では，スロット配置問題に制約条件を付加した問題をイジング計算機によって効率よく解法する手法を提案する．イジング計算機でこの問題を解法するため，この問題をイジングモデルで表現する．まず，スロット配置問題をイジングモデルの状態空間で表現する際に満足すべき制約条件が満たされているとき，イジングモデルのエネルギーが最小となる制約項を導入する．この制約をスロット配置制約と呼ぶ．また，今回は付加する制約条件として，特定の部品が一定の距離以内に置かれなければならない，というものを考える．この制約を違反したときにエネルギーが大きくなる付加制約項を導入する．この制約を付加制約と呼ぶ．更に，配置された部品間の配線数とマンハッタン距離の加重和である目的関数項をイジングモデルで表現する．また，イジング計算機によって得られた解に対し，解釈処理なるアイデアを導入することで，スロット配置制約を満たさない解が得られたとしても，スロット配置制約を満たす解に解釈し直す手法を提案する．デジタルアニーラを利用し，単純な SA 手法とデジタルアニーラで比較した結果，制約付きスロット配置問題において，SA と同程度の精度の準最適解を得るのに必要なデジタルアニーラの時間が最大で約 1/50 に圧縮することができた．
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA12149313
• 書誌情報: 研究報告組込みシステム（EMB）; 巻 2019-EMB-50, 号 52, p. 1-6, 発行日 2019-03-10
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-868X
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会