局所探索法

【きょくしょたんさくほう (local search)】

最適化問題の実行可能解や近似解$x$に対して, その近傍の解集合$N(x)$を定義する. 何らかの順序で(あるいはランダムに)$N(x)$内の解を探索してゆき, $x$よりも良い解が見つかれば$x$の更新を行い, 再びその$x$に対して$N(x)$を生成し, 同様の手続きを更新が行われるかぎり繰り返す. 局所探索の結果得られる解は局所最適ではあるが, 大域最適であるとは限らないため, メタヒューリスティクス等の様々な手法が取り入れられる.