逆自己畳込みアルゴリズムに基づく組合せ最適化手法の最大充足可能性問題への適用

カテゴリ: 部門大会

論文No: GS6-1

グループ名: 【C】2019年電気学会電子・情報・システム部門大会プログラム

発行日: 2019/08/28

タイトル(英語): A Combinatorial Optimization Method Based on the Inverse Self-Convolution Algorithm and Its Application to the Maximum Satisfiability Problem

著者名: 八木 祐介(大阪工業大学),重弘 裕二(大阪工業大学),山村 真由子(エヌ・ティ・ティ・データ・セキスイシステムズ)

著者名(英語): Yusuke Yagi|Yuji Shigehiro|Mayuko Yamamura

キーワード: 組合せ最適化|確率分布|逆自己畳み込み逆自己畳み込み|combinatorial optimization|probabilistic distribution|inverse self-convolution

要約(日本語): 著者らはこれまで，大規模な組合せ最適化問題に対して効率良く解探索を行う方法について，特に単位近傍操作の反復からなる近傍操作を用いて探索を行う方法について考察している。具体的には，単位近傍操作の反復回数の異なる多数の近傍操作を用意し，その中で最も良い操作を選んで解に適用する。最も良い操作を選ぶために，近傍操作により得られる解の評価値の分布を推定するが，そのために，探索の過程において近傍操作を適用する際に得られる解の評価値の情報を収集する。本稿では，自己畳込み，および逆自己畳込みを用いて，異なる反復回数の近傍操作に対する評価値の分布を推定し，その結果に基づいて近傍操作を選択する。また，提案する手法を最大充足可能性問題に適用し，有効性を評価する。

PDFファイルサイズ: 407 Kバイト