局所探索法は、現在の解の近傍を評価し、より優れた解へ逐次移動することで最適化を図るアルゴリズム手法です。初期解から出発して局所的な改善を繰り返すため、大規模で複雑な問題に対しても高速に実行可能な解を見つけられます。しかし、全体で最も優れた大域的最適解ではなく局所最適解に陥る可能性がある点に注意が必要です。
局所探索法とは
局所探索法とは、現在の状態から「すぐ近くの解（近傍）」を評価し、より良い方向へ少しずつ移動しながら最適な答えを探す最適化アルゴリズム手法です。
詳しく解説
局所探索法は、組み合わせ最適化問題や数理計画問題などで広く用いられる基本的な探索手法です。解空間全体を網羅的に探索するのが困難な大規模な問題に対して、まず何らかの初期解を設定し、その周辺にある解（近傍解）を比較評価します。現在の解より評価が高い近傍解が見つかればその解に移動し、これをより良い解が得られなくなるまで繰り返します。計算コストを抑えつつ実用的な近似解を短時間で得られるため、人工知能やデータ分析の各種パラメータ調整や問題解決プロセスにおいて重要な位置を占めています。
具体例・使われ方
局所探索法の具体的な利用例として、巡回セールスマン問題のような配送ルートの最適化があげられます。都市の訪問順序を少しだけ入れ替えた近傍ルートを作成・評価し、移動距離が短くなる改善を繰り返します。また、機械学習モデルのハイパーパラメータ調整や、スケジュール最適化問題、ニューラルネットワークの初期重み探索の補助など、幅広い領域で活用されています。
似た用語との違い
局所探索法と混同されやすい概念に大域探索があります。大域探索は解空間全体を視野に入れて最も優れた解を目指すのに対し、局所探索法は現在の解の周辺のみを探索します。また、単純に常に良い方向へ移動する山登り法は局所探索法の代表的な一形態ですが、確率的に悪化する移動を許容して局所最適解からの脱出を図る焼きなまし法や、生物の進化を模した遺伝的アルゴリズムといったメタヒューリスティクス手法も、局所探索の要素を拡張・応用した技術として区別されます。
注意点
局所探索法の最大の限界は、スタート地点となる初期解の質に結果が大きく依存し、全体で真に最も優れた大域的最適解ではなく局所最適解に囚われて停止してしまうリスクがある点です。この欠点を補うために、複数の初期解から探索を開始する手法の併用や、一時的に評価が悪化する解への移動を認める工夫が必要です。