CA-005
即時移動戦略に基づくk-opt局所探索法

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

組合せ最適化問題に対する最も重要な基本的解法として局所探索法があげられる．局所探索法は近傍解集合から良好な近傍解への移動を繰り返す解改善法である．局所探索の一般化のアイデアである可変深度探索法(可変k-opt局所探索法)は単純な近傍操作を連鎖的に適用することで得られる解集合を改めて大きな近傍として捉える局所探索法である．
2次割当問題(QAP)に対する一般的な局所探索法である2-opt局所探索法では良好な近傍解へ移動する際，即時移動戦略と最良移動戦略の2種類の移動戦略が主流であり，QAPに対する従来のk-opt局所探索法は最良移動戦略に基づいて探索が行われる．
本研究ではQAPに対する即時移動戦略に基づくk-opt局所探索法を提案し，その有効性を示す．