2024-03-29T11:31:05Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:001952442023-04-27T10:00:04Z01164:02822:09758:09759
実イジング計算機による制約付きスロット配置問題の解法jpn計算手法http://id.nii.ac.jp/1001/00195155/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=195244&item_no=1&attribute_id=1&file_no=1Copyright (c) 2019 by the Information Processing Society of Japan早稲田大学大学院基幹理工学研究科情報理工・情報通信専攻早稲田大学基幹理工学部情報通信学科早稲田大学グリーン・コンピューティング・システム研究機構/科学技術振興機構さきがけ早稲田大学大学院基幹理工学研究科情報理工・情報通信専攻金丸, 翔川村, 一志田中, 宗戸川, 望イジング計算機は組合せ最適化問題を物理システムにマッピングすることで,組合せ最適化問題の準最適解を高速に得ることができるとして注目されている.スロット配置問題は論理ブロックの最適配置や最適配送決定において重要な役割を果たす組合せ最適化問題である.本研究では,スロット配置問題に制約条件を付加した問題をイジング計算機によって効率よく解法する手法を提案する.イジング計算機でこの問題を解法するため,この問題をイジングモデルで表現する.まず,スロット配置問題をイジングモデルの状態空間で表現する際に満足すべき制約条件が満たされているとき,イジングモデルのエネルギーが最小となる制約項を導入する.この制約をスロット配置制約と呼ぶ.また,今回は付加する制約条件として,特定の部品が一定の距離以内に置かれなければならない,というものを考える.この制約を違反したときにエネルギーが大きくなる付加制約項を導入する.この制約を付加制約と呼ぶ.更に,配置された部品間の配線数とマンハッタン距離の加重和である目的関数項をイジングモデルで表現する.また,イジング計算機によって得られた解に対し,解釈処理なるアイデアを導入することで,スロット配置制約を満たさない解が得られたとしても,スロット配置制約を満たす解に解釈し直す手法を提案する.デジタルアニーラを利用し,単純な SA 手法とデジタルアニーラで比較した結果,制約付きスロット配置問題において,SA と同程度の精度の準最適解を得るのに必要なデジタルアニーラの時間が最大で約 1/50 に圧縮することができた.AA12149313研究報告組込みシステム(EMB)2019-EMB-5052162019-03-102188-868x2019-03-06