山登り法

近傍の中で最も良い解へ移り続け、改善が無くなったら止める。 hill climbing。局所探索のうち、 改善する手だけを受け入れる最も素朴な形。

最小化で書くと、$f(x^{\prime })<f(x)$ となる $x^{\prime }\in 𝒩(x)$ があれば移る、 無ければ停止。

止まる場所#

改善する手が無い場所で止まる。それは次のいずれか。

• 局所最適解 — 周りより良い。目的の一つ
• 平坦地 (plateau) — 周りと同じ値が続く。どちらへ進むべきか分からない
• 尾根 (ridge) — 斜めに進めば改善するが、軸方向の 1 手では改善しない

後ろ 2 つは近傍の設計が原因で、近傍を広げるか、 斜め方向を含む手を用意すると解消することがある。

変種#

変種	工夫
確率的山登り	改善する手の中から確率的に選ぶ。決定的な偏りを避ける
ランダム再開	止まったら別の初期解からやり直す
最急上昇	近傍を全部調べて最良へ移る（＝最良改善）

ランダム再開を十分繰り返せば、原理的には大域最適解に到達する確率が 1 に近づくが、効率は良くない。より賢く抜け出すのが 焼きなまし法。

参考文献#

• Stuart Russell, Peter Norvig. Artificial Intelligence: A Modern Approach, 4th ed., Chapter 4. Pearson, 2020. https://aima.cs.berkeley.edu/
• Holger H. Hoos, Thomas Stützle. Stochastic Local Search: Foundations and Applications. Morgan Kaufmann, 2004. https://doi.org/10.1016/B978-1-55860-872-6.X5016-1