トップ > 数理計画用語集 > 局所探索

数理計画用語集

局所探索

読み:きょくしょたんさく
英名:Local Search
別名:局所探索法,LS,反復改善法,山登り法
関連近似解法近傍近傍探索局所的最適解タブーサーチ

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

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

[参考]
広中平祐,現代数理科学事典,大阪書籍,1991
相吉英太郎(編),安田恵一郎(編),メタヒューリスティクスと応用,電気学会,2007