山登り法

山登り法とは

山登り法（hill climbing）は、探索アルゴリズムの一種で、評価関数の極値（最大値または最小値）を探索するために用いられます。特に局所探索法の代表的な手法として知られており、その単純さから広く利用されています。

概要

山登り法は、現在の解の近傍にある解の中で最も評価の高い解を選択し、現在の解よりもその近傍解の評価が高い場合に、現在の解をその近傍解に置き換えるというプロセスを繰り返します。このプロセスは、より良い解が見つからなくなるまで、つまり極値に到達するまで続けられます。山登り法は、探索対象を現在の解のみに限定しているため、最良優先探索のように過去の解を管理する必要がなく、アルゴリズムが非常に単純です。そのため、しばしば局所探索法と同一視されることがあります。

最小値・最大値の探索

山登り法は極値を探索するアルゴリズムであるため、評価関数の大域的な最小値や最大値を探索する際には、必ずしも最適な手法とは限りません。なぜなら、山登り法は局所的な最適解に陥りやすく、大域的な最適解を見逃してしまう可能性があるからです。しかし、実装が容易であるため、最小値や最大値の探索にも用いられることがあります。

乱択アルゴリズム

山登り法を用いて最小値や最大値を探索する際には、ランダムに初期値を複数選び、それぞれの初期値から山登り法を実行するという方法が用いられます。探索が終了し、それぞれの初期値に対応する極値が見つかった後、それらの極値の中から最小値または最大値を選びます。この方法は、乱択アルゴリズムの一種と見なすことができます。この方法の有効性は、評価関数が持つ特性に大きく依存します。もし最小値や最大値にたどり着ける初期値の割合が高いのであれば、十分な数の初期値を用意することで、最小値や最大値にたどり着ける確率を高めることができます。しかし、最小値や最大値にたどり着ける初期値の割合が非常に小さい場合、この方法で最小値や最大値を見つけ出すことは困難になります。初期値を選ぶ際には、完全にランダムではなく、メッシュ状に均等間隔で選ぶという方法も有効です。

擬似コード

以下に山登り法の擬似コードを示します。この擬似コードは、評価関数 EVAL(node) の極大値を探索するものです。


EVAL(node) : node の評価値を返す関数
NEIGHBORS(node) : node の近傍の集合を返す関数
bestNode : 探索した中での最良解

function 山登り法(startNode)
bestNode = startNode
bestEval = EVAL(bestNode)
無限ループ
nextNode = NULL
nextEval = 負の無限大
for each (x in NEIGHBORS(currentNode))
if (nextEval < EVAL(x))
nextEval = EVAL(x)
nextNode = x
if (nextEval <= bestEval)
return bestNode
bestNode = nextNode


この擬似コードでは、まず開始ノードを最良ノードとし、その評価値を最良評価値とします。その後、無限ループの中で、現在のノードの近傍ノードを評価し、より良い評価値を持つノードがあれば、それを次のノードとします。もし、近傍ノードの中に現在のノードよりも良い評価値を持つノードがなければ、現在の最良ノードを返して探索を終了します。

関連項目

• - 局所探索法
• - 最良優先探索

もう一度検索