Loading AI tools
ウィキペディアから
局所探索法(きょくしょたんさくほう、英: local search)や逐次改善法(ちくじかいぜんほう、英: iterative improvement)や近傍探索法(きんぼうたんさくほう)は、探索アルゴリズムの一種である。
局所探索法とは近似アルゴリズムの中でも最も単純なアルゴリズムの枠組みの一つである。広義には後述する手法の枠組みを持つアルゴリズムの総称として使われており、狭義には山登り法の意味で使われている。今日のメタヒューリスティクスの多くの手法がこの枠組みを使用している。
「局所探索法」という言葉は主に探索アルゴリズムに対しての言葉であり、数値解析の分野に於いては「反復法」という言葉が用いられる。両者の違いとしては反復法は対象となる関数の連続性や1階微分方程式などが解っていることが前提の場合が多く、また求める解も最適解を要求されることが多いのに対し、局所探索法では離散的な関数や関数の内容自体が不明なときでも出来る限り良質な近似解を求めるということを主な目的としたものが多い。
このアルゴリズムは以下の枠組みで実装される。
実装にあたって定義するパラメータは以下の通りである。
一般に近傍の定義は現在の解とのハミング距離が近いものや、探索状態をグラフで表したときに現在の解に近い状態などが用いられる。
終了条件は繰り返しの回数を設定するか、解の入れ換えが起こらなくなったら終了するなどがある。
近傍解を選ぶ条件と近傍解と現在の解を入れ換える条件はさまざまなものが提案され、いくつかの方法は独立のアルゴリズムとして認知されている。
中には遺伝的アルゴリズムを含める者もいるが、この手法は近傍の定義が曖昧なので厳密には誤用(交叉した個体をもとの個体の近傍とすることに関して異論が多いため)。
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.