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

◎金原一歩・片山謙吾・岡野傑士・西原典孝（岡山理大）

最大クリーク問題（maximum clique problem，MCP）に対して，反復局所探索（Iterated local search，ILS）にk-opt局所探索法（k-opt local search，KLS）を導入した反復k-opt局所探索法(IKLS)は良好な解を算出することが可能である．しかしながら，良質な解を算出する前に，局所解に陥り探索が停滞することがある．その問題を解消するために多様化戦略を導入した反復局所探索法（提案IKLS）を提案する．従来IKLSとの性能比較実験を通して，多様化戦略を導入した提案IKLSの有効性を示す．