最大クリーク問題に対する反復局所探索法における多様化戦略の導入

摘要

組合せ最適化問題に対する代表的な局所探索法として，巡回セールスマン問題やグラフ分割問題に対するLin とKernighan による解法がよく知られている．これは，一般に，可変深度探索法，または（可変）k-opt局所探索法(k-opt local search, KLS) などと呼ばれ，単純な近傍操作を連鎖的に適用することで得られる解集合を改めて大きな近傍として捉える，局所探索の一般化のアイデアである．我々の研究グループでは，最大クリーク問題(maximum clique problem, MCP)，2 次割当問題等の困難な問題に対してKLS やその変形アルゴリズムを示し，メタ戦略への導入によって，良好な結果が得られることを確認しつつある.