局所探索法

出典: フリー百科事典『ウィキペディア（Wikipedia）』

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

[編集] 概要

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

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

[編集] アルゴリズムの枠組み

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

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

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

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

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

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

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

[編集] 関連手法

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

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