局所探索#
読み: きょくしょたんさく
英名: Local Search
別名: 局所探索法,LS,反復改善法,山登り法
狭義では,「適当な初期解から出発し,解の近傍にそれより良い解があれば置き換える, という操作を繰り返し実行して,解の更新が行われなくなったとき終了する」というアルゴリズムを指す. このとき得られた解(局所的最適解)は,初期解や近傍の定義に大きく依存する. 非常に単純なアルゴリズムであるため,多くの近似解法で用いられる.
広義では,上記のアルゴリズムを組み込んだ近似解法全般を指す. タブーサーチ,焼きなまし法,遺伝的アルゴリズムなどが代表的である.
関連
参考文献
[1]
広中平祐, editor. 現代数理科学事典. 大阪書籍, 1991.
[2]
相吉英太郎 and 安田恵一郎, editors. メタヒューリスティクスと応用. 電気学会, 2007.