ヒルクライミング

数値解析において、ヒルクライミング法は局所探索法の一種である数学的最適化手法です。

これは、問題に対する任意の解決策から始めて、その解決策に段階的な変更を加えることで、より良い解決策を見つけようとする反復アルゴリズムです。変更によってより良い解決策が生まれたら、新しい解決策にさらに段階的な変更を加え、これ以上の改善が見つからなくなるまでこれを繰り返します。

たとえば、山登り法は巡回セールスマン問題に適用できます。すべての都市を訪問する初期ソリューションを見つけるのは簡単ですが、最適ソリューションと比較すると非常に劣る可能性があります。アルゴリズムはそのようなソリューションから開始し、2 つの都市を訪問する順序を切り替えるなど、小さな改善を加えます。最終的には、はるかに短いルートが得られる可能性が高くなります。

ヒルクライミング法は、凸問題に対して最適解を見つけます。他の問題に対しては、局所最適解（隣接する構成では改善できない解）のみを見つけます。局所最適解は、必ずしもすべての可能な解（探索空間） の中で最善の解（大域最適解）とは限りません。

山登り法で凸問題を解くアルゴリズムの例としては、線形計画法の単体アルゴリズムや二分探索法などがある。^{[1] : 253}

局所最適解に陥らないようにするために、リスタート（つまり、繰り返し局所探索）を使用したり、反復（反復局所探索など）やメモリ（反応探索最適化やタブー探索など）に基づくより複雑なスキーム、あるいはメモリなしの確率的修正（シミュレーテッドアニーリングなど）を使用したりすることができます。

このアルゴリズムは比較的単純なため、最適化アルゴリズムの中では第一選択肢として人気があります。人工知能では、開始ノードから目標状態に到達するために広く使用されています。関連するアルゴリズムでは、次のノードと開始ノードに異なる選択肢が使用されます。シミュレーテッド アニーリングやタブー探索などのより高度なアルゴリズムの方がよい結果が得られる場合もありますが、状況によってはヒル クライミングでも同様に機能します。ヒル クライミングは、リアルタイム システムなど、検索に使用できる時間が限られている場合に、少数の増分で通常は良好な解 (最適解または近似値) に収束する限り、他のアルゴリズムよりもよい結果を得られることがよくあります。対極的には、バブル ソートはヒル クライミング アルゴリズム (隣接する要素を交換するたびに無秩序な要素のペアの数が減少) と見なすことができますが、このアプローチは、必要な交換回数が 2 乗で増加するため、N がそれほど大きくない場合でも効率的とは言えません。

ヒルクライミングはいつでも実行できるアルゴリズムです。終了する前であればいつでも中断されても、有効なソリューションを返すことができます。

ヒル クライミングは、連続値および/または離散値のベクトルであるターゲット関数 を最大化 (または最小化) しようとします。各反復で、ヒル クライミングは の 1 つの要素を調整し、変更によって の値が改善されるかどうかを判断します。(これは、ヒルの勾配に従って各反復でのすべての値を調整する勾配降下法とは異なることに注意してください。) ヒル クライミングでは、改善する変更はすべて受け入れられ、 の値を改善する変更が見つからなくなるまでプロセスが続行されます。その後、は「局所的に最適」であると言われます。 ${\displaystyle f(\mathbf {x} )}$${\displaystyle \mathbf {x} }$${\displaystyle \mathbf {x} }$${\displaystyle f(\mathbf {x} )}$${\displaystyle \mathbf {x} }$${\displaystyle f(\mathbf {x} )}$${\displaystyle f(\mathbf {x} )}$${\displaystyle \mathbf {x} }$

離散ベクトル空間では、 の各可能な値はグラフの頂点として視覚化できます。山登り法はグラフを頂点から頂点へとたどり、常に の値を局所的に増加 (または減少) させ、極大値(または極小値)に達するまで続けます。 ${\displaystyle \mathbf {x} }$${\displaystyle f(\mathbf {x} )}$${\displaystyle x_{m}}$

単純な山登り法では、最初の近いノードが選択されますが、最急登り法では、すべての後続ノードが比較され、解に最も近いものが選択されます。どちらの形式も、近いノードがない場合には失敗します。これは、探索空間に解ではない局所的最大値がある場合に発生する可能性があります。最急登り法は、最良優先探索に似ており、現在のパスの1つだけではなく、すべての可能な拡張を試みます。^[2]

確率的ヒルクライミングでは、移動方法を決定する前にすべての隣接ノードを調べるわけではありません。 むしろ、隣接ノードをランダムに選択し、その隣接ノードの改善量に基づいて、その隣接ノードに移動する、または別の隣接ノードを調べるかどうかを決定します。

座標降下法では、各反復で現在のポイントの 1 つの座標方向に沿って直線検索が行われます。座標降下法の一部のバージョンでは、各反復で異なる座標方向がランダムに選択されます。

ランダム リスタート ヒル クライミングは、ヒル クライミング アルゴリズムの上に構築されたメタ アルゴリズムです。ショットガン ヒル クライミングとも呼ばれます。ランダムな初期条件でヒル クライミングを繰り返し実行します。最良の結果が保持されます。つまり、ヒル クライミングを新たに実行した結果が保存されている状態よりも良い結果になった場合は、保存されている状態が置き換えられます。 ${\displaystyle x_{0}}$${\displaystyle x_{m}}$${\displaystyle x_{m}}$

ランダムリスタートヒルクライミングは、多くの場合、驚くほど効果的なアルゴリズムです。初期条件から慎重に最適化するよりも、CPU 時間を費やして空間を探索する方がよい場合が多いことが判明しました。^{[独自の研究? ]}

ヒルクライミングは必ずしも大域的最大値を見つけるわけではなく、局所的最大値に収束する可能性があります。この問題は、ヒューリスティックが凸の場合に発生しません。ただし、多くの関数は凸ではないため、ヒルクライミングでは大域的最大値に到達できないことがよくあります。確率的ヒルクライミング、ランダムウォーク、シミュレーテッドアニーリングなどの他の局所探索アルゴリズムは、この問題を克服しようとします。

尾根は、連続空間で最適化を行うヒルクライマーにとって難しい問題です。ヒルクライマーはベクトルの要素を一度に 1 つだけ調整するため、各ステップは軸に沿った方向に移動します。ターゲット関数が軸に沿っていない方向に上昇する狭い尾根 (または、目標が最小化である場合は、軸に沿っていない方向に下降する狭い路地) を作成する場合、ヒルクライマーはジグザグに尾根を登る (または路地を下る) ことしかできません。尾根 (または路地) の側面が非常に急勾配の場合、ヒルクライマーはジグザグに進み、より良い位置に向かって非常に小さなステップを踏まざるを得ない場合があります。そのため、尾根を登る (または路地を下る) のに不合理な時間がかかる場合があります。

対照的に、勾配降下法は尾根や路地が上昇または下降するあらゆる方向に移動できます。したがって、ターゲット関数が微分可能な場合は、勾配降下法または共役勾配法が山登り法よりも一般的に好まれます。ただし、山登り法にはターゲット関数が微分可能である必要がないという利点があるため、ターゲット関数が複雑な場合は山登り法が好まれる場合があります。

ヒルクライミングで時々発生するもう 1 つの問題は、プラトーの問題です。プラトーは、検索空間が平坦な場合、または、マシンが値を表すために使用する精度により、ターゲット関数によって返される値が近くの領域で返される値と区別できないほど平坦な場合に発生します。このような場合、ヒルクライマーはどの方向に進むべきかを判断できず、改善につながらない方向に迷い込む可能性があります。

擬似コード
アルゴリズム離散空間ヒルクライミングは
    現在のノード:=開始ノード
    ループする
        L := 近隣ノード(現在のノード)
        次の評価:= −INF
        次のノード:= NULL
        L内のすべてのxに対して、 EVAL(x) > nextEvalであれ
            ば
                次のノード:= x
                次の評価:=EVAL(x)
        nextEval ≤ EVAL(currentNode)の場合
            // より良い隣接ノードが存在しないため、現在のノードを返します
            現在のノードを返す
        現在のノード := 次のノード

アルゴリズム連続空間ヒルクライミングは
    currentPoint := initialPoint // ゼロ振幅ベクトルは共通です
    stepSize := initialStepSizes // すべて1のベクトルは共通です
    acceleration := someAcceleration // 1.2 のような値が一般的です
    候補[0] := −加速度
    候補[1] := −1 / 加速度
    候補[2] := 1 / 加速度
    候補[3] := 加速度
    ベストスコア := EVAL(現在のポイント)
    ループする
        前のスコア:=ベストスコア
        currentPointの各要素iに対して
            前のポイント:=現在のポイント[i]
            ベストステップ:= 0
            j が 0 から 3 の場合、       4 つの候補場所をそれぞれ試します。
                ステップ := ステップサイズ[i] × 候補[j]
                現在のポイント[i] := 前のポイント + ステップ
                スコア := EVAL(現在のポイント)
                スコア > bestScoreの場合
                    ベストスコア := スコア
                    ベストステップ := ステップ
            bestStepが0の場合
                現在のポイント[i] := 前のポイント
                stepSize[i] := stepSize[i] / 加速度
            それ以外
                現在のポイント[i] := 前のポイント + ベストステップ
                stepSize[i] := bestStep // 加速
        if (bestScore − beforeScore) < epsilon then 
            return currentPoint

遺伝的アルゴリズムとランダム最適化の対比。

• 勾配降下法
• 貪欲アルゴリズム
• タトネマン
• 平均シフト
• A*検索アルゴリズム

• ラッセル、スチュアート J. ;ノーヴィグ、ピーター(2003)、人工知能: 現代的アプローチ (第 2 版)、アッパー サドル リバー、ニュージャージー: プレンティス ホール、pp. 111–114、ISBN 0-13-790395-2

• ラスリー、ジョージ（2018）。検索メタヒューリスティックスによる古典暗号の暗号解読の方法論（PDF）。カッセル大学出版局。ISBN 978-3-7376-0459-8。

• ウィキブックスのヒルクライミング