Don’t Look Bit による変形可変深度探索法の高速化

摘要

組合せ最適化問題に対する反復局所探索法やmemeticrnアルゴリズムなどのメタ戦略アルゴリズムでは，局所rn探索法を繰り返し適用することで良好な解の探索を行rnう．一般的にそのようなメタ戦略では，局所探索法rnが占める処理時間の割合は多いため，局所探索法の処理rn時間を減少させることでメタ戦略の効率の向上が見込まrnれる．代表的な組合せ最適化問題である2 次割当問題rn(Quadratic Assignment Problem, QAP) に対する2-opt 局所rn探索法(2-opt Local Search, 2LS) の高速化のアイデアとしrnて， Don’t Look Bit (DLB) が知られている．DLB は改rn善の見込みが薄い近傍の探索を行わないことで高速化すrnる技法である．また，2LS より巧妙に大きな近傍を探索rnする可変深度探索法(variable depth search, VDS) が知らrnれている．