統計量推定に基づく組合せ最適化手法の最大充足可能性問題への適用

カテゴリ: 部門大会

論文No: GS5-5

グループ名: 【C】平成25年電気学会電子・情報・システム部門大会講演論文集

発行日: 2013/09/04

タイトル(英語): A Combinatorial Optimization Method Based on the Estimation of the Statistics and Its Application to the Maximum Satisfiability Problem

著者名: 重弘 裕二(大阪工業大学),増田 達也(大阪工業大学)

著者名(英語): Yuji Shigehiro(Osaka Institute of Technology),Tatsuya Masuda(Osaka Institute of Technology)

キーワード: 組合せ最適化|確率分布|最大充足可能性問題最大充足可能性問題|combinatorial optimization|probability distribution|maximum satisfiability problem

要約(日本語): 著者らはこれまで、大規模な組合せ最適化問題に対して効率良く解探索を行う方法について、特に単位近傍操作の反復からなる近傍操作を用いて探索を行う方法について考察している。具体的には、単位近傍操作の反復回数の異なる多数の近傍操作を用意し、その中で最も良い操作を選んで解に適用する。最も良い操作を選ぶために、近傍操作により得られる解の評価値の分布を推定する。評価値の分布を推定するために、近傍操作により得られる解の評価値が従うであろう分布の形状を仮定し、探索の過程において近傍操作を適用する際に解の評価値等の情報を収集するものとし、それらから統計量を推定するための式を導出する。本稿では、提案する手法を最大充足可能性問題に適用し、局所探索法と比較することにより、手法の正当性を評価する。さらに遺伝的アルゴリズムを実装し、交叉や突然変異といった遺伝的操作と比較することにより、手法の有効性を評価する。

PDFファイルサイズ: 6,077 Kバイト