共同利用

制約付き最適化問題に向けたアニーリングマシンの活用


種別 一般研究_短期研究員
研究計画題目 制約付き最適化問題に向けたアニーリングマシンの活用
研究代表者 奥山 拓哉(株式会社日立製作所・研究員)
研究実施期間 平成30年8月26日(日)~ 平成30年8月31日(金)
研究分野のキーワード 組合せ最適化,アニーリングマシン
目的と期待される成果 量子アニーリング装置や半導体回路を活用した装置など近年,イジングモデルに特化した様々なアニーリングマシンが提案されている。これらの計算機は最適化問題を解くことに特化したもので,機械学習や人工知能への応用が期待されている。
多くの最適化問題は制約を持つため,制約を満たさない場合は目的関数値を増加させるペナルティー関数を付加するというペナルティー法を用いて,制約なし最適化問題に再定式化する。ペナルティー関数の大きさを表す係数を一般にペナルティー係数と呼ぶ。この係数をある値以上に定めると,目的関数最小の状態が実行可能解となる。そのため,目的関数最小の状態が必ず求まるならばペナルティー係数を大きく設定すれば良い。しかし,アニーリングはマルコフ連鎖モンテカルロ法に基づく確率的アルゴリズムであり,この状態が必ずしも求まるとは限らない。またペナルティー係数を大きくすると,状態間の遷移確率が小さくなるため,目的関数最小の状態への収束が困難となる。
ペナルティー法は汎用性があるものの,上記の理由からアニーリングで良質な解を得るためには,ペナルティー係数を適切に決定する必要がある。上記の課題を解決するため,本研究ではペナルティー係数の決定法を検討する。また,提案法に基づいた性能比較を実施する。この方法ではSDP緩和による最適化問題の緩和が有効と考えられるため,半正定値計画問題を専門にするIMI/脇准教授と本研究を進める。
組織委員(研究集会)
参加者(短期共同利用)
奥山 拓哉(株式会社日立製作所・研究員)
脇 隼人(九州大学 マス・フォア・インダストリ研究所・准教授)