A-015
大規模なバイナリー2次計画問題に対するMemetic algorithm

◎脇坂猛虎・外山　史・森　博志・東海林健二（宇都宮大）

バイナリー2次計画問題(BQP)は，NP困難な問題に含まれる組み合わせ最適化問題の1つであり，マシンスケジューリング問題やCAD問題に適用可能であるため，応用例が広い問題として知られている．
本研究では，OR-Libraryに存在する問題より大規模な問題を対象とする．大規模なBQPに対する従来手法としてIGKLSが提案されている．本研究では，IGKLSにMemetic Algorithmを組み合わせることにより，大規模なBQPに有効な手法を提案する．
提案手法では，IGKLSによる単点探索を行った後にMAによる多点探索に切り替えることで解空間の探索性能を高める．
実験では，10000変数の問題を用いて従来手法と比較し，提案手法の有効性を示す．