山登り法とは

山登り法とは、いまの答えを少しずつ良い方向へ修正しながら、より良い解を探していく単純な最適化の手法です。坂を一歩ずつ登るように改善を積み重ねていくことから、この名で呼ばれています。考え方がやさしく計算も軽いため、AIの探索や最適化を学ぶときの入り口としても知られる方法です。

少しずつ改善して頂上を目指す

やり方はとてもシンプルです。まず適当な答えから始め、そこから少しだけ変えてみて、前より良くなれば採用、悪くなれば元に戻す。これを「もう改善できない」というところまで繰り返すだけ。地図全体を見渡さず、足元の傾きだけを頼りに高いほうへ進むイメージです。手数が少なく速いのが持ち味で、配送ルートや各種の設定値を「そこそこ良いところ」までさっと調整したい場面に向いています。

「小さな丘の頂上」で止まる弱点

ただし山登り法には、よく知られた弱点があります。それは小さな丘の頂上にたどり着くと、そこで止まってしまうこと。本当はもっと高い山が別の場所にあっても、目の前の傾きしか見ていないため気づけません。この「部分的な頂上」を局所最適と呼びます。対策として、出発点をいろいろ変えて何度も登り直すといった工夫が使われます。ちなみに、ニューラルネットの学習でおなじみの「勾配降下法」も、山を登るか下るかが逆なだけで、根っこは同じ発想。だから同じように局所解の悩みを抱えるのです。

山登り法に関するよくある質問

山登り法はどんなときに使われますか？

配送ルートの組み方や、機器・プログラムの設定値の調整など、「完璧でなくても、そこそこ良い答えを素早く出したい」場面で使われます。単純で計算が軽いぶん、手早く結果が得られるのが利点です。

山登り法は、すべての答えを試す方法と何が違いますか？

すべての選択肢を試す総当たりは確実ですが、選択肢が多いと膨大な時間がかかります。山登り法は近くの改善だけを見て進むため速い反面、最高の答えを必ず見つける保証はありません。速さと確実さのどちらを取るかの違いです。