山登り法【hill climbing】ヒルクライム法

概要

この名称は、山の斜面を登る際、常に足元より標高の高い方向へ一歩ずつ進めばいずれ頂上に到達するという発想に由来する。評価値の高さを山の高さに見立て、より高い場所を目指して移動を続ける様子がアルゴリズムの動作と重なることから、こう呼ばれるようになった。

具体的な手順としては、まず初期解を一つ決める。次に、その解を少し変化させた近傍解をいくつか生成し、評価関数を用いて現在の解と比較する。近傍解の中に現在の解より優れたものがあれば、その中で最も評価の高い解へと移動し、同じ操作を繰り返す。

近傍解の作り方は問題によって異なり、巡回セールスマン問題では訪問順序の一部を入れ替え、機械学習ではパラメータを僅かに増減させるといった方法が取られる。評価関数も移動距離の短さや誤差の小ささなど問題ごとに異なり、評価値が高いほど優れた解である場合も、その逆もある。周囲に現在より良い近傍解が存在しなくなった時点で探索は終了し、そのときの解が最終的な結果となる。

山登り法は現在地から見て局所的に評価値が改善する方向にしか移動しないため、真の頂上に達する前に途中の小さな丘の頂上で「これ以上高い場所がない」と判断し、探索を打ち切ってしまう場合がある。このような解を「局所最適解」（local optimum）という。また、平坦な領域では進む方向を決めにくく、複数の頂上が存在する探索空間では初期解によって得られる結果が変わることもある。

こうした弱点を補う目的で、初期解を変えて複数回探索を行う方法や、評価値が一時的に下がる方向への移動も一定の確率で許容する方法、複数の探索点を並行して扱う方法などの派生手法が考案されている。組み合わせ最適化の分野では、チェスや将棋の次の一手を決めるプログラム、配送ルートを決定する処理など、様々な最適化問題の基礎理論として古くから利用されてきた手法である。