山登り法とは、現在の状態から最も評価が高くなる隣接した状態へ移動することを繰り返し、より良い解を探す基本的な探索アルゴリズムです。霧の中で最も傾斜の高い方向へ一歩ずつ登るように動作し、シンプルで計算コストが低い一方、途中の低い山頂である局所最適解に陥りやすい特性を持ちます。
山登り法とは
山登り法は、解の候補を少しずつ変化させて評価値を改善していく「局所探索法」の代表的なアルゴリズムです。一言で言えば、現在地から見渡して一番高い方向へ一歩ずつ進むことで、最適化問題の解を求める手法です。
詳しく解説
山登り法は、初期状態からスタートし、近傍にある複数の候補の中から最も評価値が良い状態を選択して移動する処理を繰り返します。これ以上評価が良くならない地点に達した時点で探索を終了します。構造が極めてシンプルで実装が容易であり、メモリ消費量も少ないため、古典的なAIの探索やゲーム木の評価、初期的なパラメータ調整などに広く利用されてきました。しかし、全体の最高地点（大域的最適解）ではなく、周囲より一時的に高いだけの「局所最適解」や、傾斜が存在しない平坦な領域（プラトー）に遭遇すると、それ以上進めなくなる弱点があります。
具体例・使われ方
具体的なイメージとしては、濃い霧に包まれた山で頂上を目指す状況が挙げられます。登山者は周囲の足元しか見えないため、最も上り坂になっている方向へ一歩ずつ進みます。実際の応用例としては、巡回セールスマン問題において近傍の経路を入れ替えて距離を短縮する試みや、ゲームAIにおける盤面の静的評価値改善、スケジューリング問題における割り当て調整などがあります。
似た用語との違い
確率的に悪い手も受け入れる「焼きなまし法」や集団で多様な解を同時に探す「遺伝的アルゴリズム」とは異なり、山登り法は常に良くなる方向しか選ばない決定論的な貪欲手法です。また、数学的な微分値を用いてパラメータを更新する「勾配降下法」と発想は似ていますが、山登り法は離散的な状態空間や微分不可能な問題にも適用できる点で異なります。
注意点
山登り法の最大の限界は、局所最適解からの脱出ができない点です。そのため、初期値の選び方によって得られる結果が大きく変動します。この問題を緩和するために、異なる初期値から何度もやり直すランダムリスタート山登り法や、一時的に確率的な後退を許容する手法と組み合わせて使われることが一般的です。