局所探索

局所探索#

  • 読み: きょくしょたんさく

  • 英名: Local Search

  • 別名: 局所探索法,LS,反復改善法,山登り法

狭義では,「適当な初期解から出発し,解の近傍にそれより良い解があれば置き換える, という操作を繰り返し実行して,解の更新が行われなくなったとき終了する」というアルゴリズムを指す. このとき得られた解(局所的最適解)は,初期解や近傍の定義に大きく依存する. 非常に単純なアルゴリズムであるため,多くの近似解法で用いられる.

広義では,上記のアルゴリズムを組み込んだ近似解法全般を指す. タブーサーチ,焼きなまし法,遺伝的アルゴリズムなどが代表的である.

関連

参考文献

[1]

広中平祐, editor. 現代数理科学事典. 大阪書籍, 1991.

[2]

相吉英太郎 and 安田恵一郎, editors. メタヒューリスティクスと応用. 電気学会, 2007.