局所探索法

OR事典

局所探索法

読み方：きょくしょたんさくほう
【英】：local search

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

「OR事典」の他の用語

近似・知能・感覚的手法：

多スタート局所探索  定性推論  導出原理  局所探索法  支配関係に基づくラフ集合  最大カット問題  欲張り法

ウィキペディア

局所探索法

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/12/10 07:58 UTC 版)

局所探索法（きょくしょたんさくほう、英: local search）や逐次改善法（ちくじかいぜんほう、英: iterative improvement）や近傍探索法（きんぼうたんさくほう）は、探索アルゴリズムの一種である。

概要

局所探索法とは近似アルゴリズムの中でも最も単純なアルゴリズムの枠組みの一つである。広義には後述する手法の枠組みを持つアルゴリズムの総称として使われており、狭義には山登り法の意味で使われている。今日のメタヒューリスティクスの多くの手法がこの枠組みを使用している。

「局所探索法」という言葉は主に探索アルゴリズムに対しての言葉であり、数値解析の分野に於いては「反復法」という言葉が用いられる。両者の違いとしては反復法は対象となる関数の連続性や1階微分方程式などが解っていることが前提の場合が多く、また求める解も最適解を要求されることが多いのに対し、局所探索法では離散的な関数や関数の内容自体が不明なときでも出来る限り良質な近似解を求めるということを主な目的としたものが多い。

アルゴリズムの枠組み

このアルゴリズムは以下の枠組みで実装される。

1. 解を一つランダムに生成する。
2. 現在の解の近傍の内一つをある条件で選び近傍解とする。
3. 定義した条件を満たすなら、近傍解を現在の解と入れ換える。
4. 終了条件を満たすまで 2. 以下を繰り返す。

実装にあたって定義するパラメータは以下の通りである。

• 近傍の定義
• 近傍解を選ぶ条件
• 近傍解と現在の解を入れ換える条件
• 終了条件

一般に近傍の定義は現在の解とのハミング距離が近いものや、探索状態をグラフで表したときに現在の解に近い状態などが用いられる。

終了条件は繰り返しの回数を設定するか、解の入れ換えが起こらなくなったら終了するなどがある。

近傍解を選ぶ条件と近傍解と現在の解を入れ換える条件はさまざまなものが提案され、いくつかの方法は独立のアルゴリズムとして認知されている。

局所探索法の一覧

• 山登り法 - 全ての近傍の内で最も成績の良いものを近傍解に選び、現在の解より近傍解の成績が良ければ入れ換える方法、局所探索法の代名詞的存在である。
• 焼きなまし法 - 近傍の内一つをランダムで選び、ある遷移確率（主にメトロポリス法）で入れ換えを行う手法。
• タブーサーチ - 近傍を複数（全てではない）探索しその中で最も良い解を選び、必ず入れ換える方法、ただし入れ換えられた解はしばらくの間、再度入れ換える事ができない。

中には遺伝的アルゴリズムを含める者もいるが、この手法は近傍の定義が曖昧なので厳密には誤用（交叉した個体をもとの個体の近傍とすることに関して異論が多いため）。