山登り: 基礎と応用

By Fouad Sabry

ヒル クライミングとは

ヒル クライミングは、数値解析で使用される数学的最適化の手法です。 これは、ローカル検索として知られる技術ファミリーのメンバーです。 これは、問題に対する任意の解決策から開始し、その後、より良い解決策につながるかどうかを確認するために、最初の解決策に段階的に変更を加えることで、より良い答えを発見しようとする反復アルゴリズムです。 変更の結果、より良いソリューションが得られた場合は、さらに改善が見られなくなるまで、新しいソリューションに対してさらに段階的な調整が行われ、これが繰り返されます。

方法 メリット

(I) 次のトピックに関する洞察と検証:

第 1 章: ヒルクライミング

第 2 章: 勾配降下

第 3 章: 貪欲アルゴリズム

第 4 章: 平均シフト

第 5 章: A* 検索アルゴリズム

第 6 章: 数学的最適化

第 7 章: ローカル検索 (最適化)

第 8 章: 反復法

第 9 章: 巡回セールスマン問題

第 10 章: 局所最適

(II) ヒル クライミングに関する一般のよくある質問に答える。

(III) 多くの分野でのヒル クライミングの使用例の実例。

(IV) 17 の付録で、各業界の 266 の新興テクノロジーを簡潔に説明し、ヒル クライミング テクノロジーを 360 度完全に理解できます。

この本の対象者

専門家、学部生、大学院生、愛好家、趣味人、あらゆる種類のヒルクライムについて基礎的な知識や情報を超えて学びたい人。

 

• Language: 日本語
• Publisher: 10億人の知識があります [Japanese]
• Release date: Jul 1, 2023

Book preview

第8章:山登り

ヒルクライミングは、数値解析で使用される数学的最適化の方法です。これは、ローカル検索として知られる手法のファミリーのメンバーです。これは、問題に対する任意の解決策から始まり、それがより良い解決策につながるかどうかを確認するために、最初の解決策に段階的な変更を加えることによって、より良い答えを見つけようとする反復的な方法です。変更によってより良いソリューションが得られる場合は、新しいソリューションに対して別の増分調整が行われ、識別できる改善点がなくなるまで続きます。

たとえば、巡回セールスマンの問題は、山登りの解決策に役立ちます。すべての都市を訪問する初期の解決策はかなり簡単に見つけることができますが、理想的なオプションと比較して特に優れている可能性はほとんどありません。アルゴリズムは、このようなソリューションから始まり、2 つの都市が訪問される順序を再配置するなど、一連の段階的な改善を実行します。結局、はるかに短いパスが得られる可能性があります。

山登りは、凸でない問題に対する局所的な最適点のみを特定します。凸問題の場合、可能な限り最良の解(隣接する構成では改善できない解)が見つかります。 それらは、考えられるすべての選択肢(グローバル最適)(探索空間)の中から常に最適な答えを構成するとは限りません。

山登りによって凸問題を解くアルゴリズムの例としては、線形計画法やバイナリ探索のためのシンプレックスアルゴリズムが挙げられる。: 253 ローカル最適に陥らないようにするには、再起動(つまり、

同じ領域内で繰り返される検索)、または反復(反復ローカル検索など)、または回想(リアクティブ検索最適化やタブー検索など)、あるいは記憶のない確率的変更(シミュレートされたアニーリングなど)に基づいて構築されたさらに複雑な計画。

アルゴリズムの複雑さは中程度であるため、最初の最適化の試行で使用するための実行可能なオプションとして選択されることがよくあります。人工知能では、最初のノードから目的の宛先状態に進む目的で広く使用されています。同様のアルゴリズムでは、最初のノードと後続のノードの両方にさまざまな代替手段が採用されています。シミュレーテッドアニーリングやタブー検索などのより複雑なアルゴリズムは、多くの場合、優れた結果を提供する可能性がありますが、山登りは状況によっては依然として非常に役立ちます。リアルタイムシステムを扱う場合など、検索の実行に使用できる時間が限られている場合、山登りは、少数の増分が通常適切なソリューションに収束する限り、他のアルゴリズムよりも優れた結果を生成することがよくあります。これは、増分の数が最小限に抑えられている場合です(最適解または近似)。一方、バブルソートは山登りアルゴリズム(近くのすべての要素交換が無秩序な要素ペアの数を減らす)として解釈される可能性がありますが、必要な交換の数が二次的に増加するため、この戦略は小さなNに対してもリモートで効率的ではありません。

ヒルクライミングはいつでもアルゴリズムであり、完了する前に任意の時点で停止しても正解が得られる可能性があります。

山登りは、ターゲット関数を最大化(または最小化)しようとします f(\mathbf {x} ) が、 \mathbf {x} は連続値および/または離散値のベクトルです。

サイクル中の毎回、山登りはの単一の要素を調整 \mathbf {x} し、その変更によっての値が向上するかどうかを判断します f(\mathbf {x} ) 。

(これは、丘の勾配に応じて各反復ですべての値を調整する勾配降下アプローチと同じではないことに注意してください \mathbf {x} 。山登りでは、改善する変更はすべて f(\mathbf {x} ) 受け入れられ、の値は f(\mathbf {x} ) 。

次に \mathbf {x} 、「局所最適」と呼ばれます。

離散ベクトル空間では、 の可能な各値は、 \mathbf {x} グラフの頂点として視覚化され得る。

グラフは、丘が登るにつれて頂点から頂点へとたどられ、ローカル最大値(または f(\mathbf {x} ) ローカル最小値)に達するまで、常にローカルに増加(または減少)します x_{m} 。

単純な山登りでは、丘の頂上に最も近いノードが選択されますが、最も急な登り坂では、すべての後続ノードが比較され、解に最も類似したものが選択されます。両方のバリアントは、探索空間に解ではない局所最大値が含まれ、より近いノードがない場合には無効です。これは、検索空間に極大値がある場合に発生する可能性があります。最も急な登りのテクニックは、ベストファースト検索アルゴリズムに類似した一種の山登りであり、1つではなく現在のルートのすべての潜在的な延長を検索します。

確率的山登りの進め方を決定する際に、隣人は考慮されません。代わりに、ランダムにネイバーを選択し、そのネイバーの進行状況に応じて、そのネイバーに移動するか、別のネイバーを調査するかを決定します。

各反復で、座標降下アルゴリズムは、現在位置から始まる 1 つの座標方向に沿ってライン検索を実行します。座標降下アルゴリズムのいくつかの実装では、各反復の次の座標方向をランダムに選択します。

山登りアルゴリズムは、ランダム再開山登りメタアルゴリズムの基礎であり、その上に構築されています。

ショットガンを使った山登りは別名です。

山登りは、毎回ランダムな初期条件で反復的に行われます x_{0} 。

最高のものが x_{m} 維持されます:山登りの新しい実行が保存された状態よりも優れたものを生成する場合 x_{m} 、それは以前に保存された状態の代わりになります。

多くの状況で、ランダムリスタート山登りとして知られるテクニックは非常に成功していることが証明されています。多くの場合、初期状態から慎重に最適化するよりも、CPU 時間を領域の探索に費やす方が有益であることが示されています。

山登りは必ずしも地球極大値の発見につながるとは限りません。むしろ、それは局所極大値の発見につながる可能性があります。ヒューリスティックが凸状の場合、この問題は発生しません。ただし、多くの機能が凸状ではないため、山登りは必ずしもグローバルな最大値に達することに成功するとは限りません。確率的山登り、ランダムウォーク、シミュレーテッドアニーリングなどの他のタイプのローカル検索アルゴリズムも、この問題を解決しようとします。

連続した広がりでパフォーマンスを最大化するヒルクライマーは、尾根に遭遇すると難しいジレンマを抱えます。ヒルクライマーはベクトル内の要素を一度に1つだけ変更するため、実行する各ステップは軸に沿った方向に移動します。ターゲット関数が軸と整列しない方向に登る狭い尾根を作成する場合、または目標が最小化である場合、ターゲット関数が軸と整列しない方向に下降する狭い路地を作成する場合、ヒルクライマーが尾根を登る(または路地を下る)唯一の方法はジグザグです。尾根(または路地)の側面が特に急な場合、ヒルクライマーは尾根(または路地)のより良い位置に向かってジグザグに動くため、ほとんど歩かざるを得ないかもしれません。この結果、尾根を登る(または路地を下る)のに不当に長い時間がかかる場合があります。

一方、勾配降下技術は、尾根または路地が上昇しているか下降しているかに関係なく、どちらの方向にも進むことができます。したがって、目標関数を微分できる場合、ほとんどの場合、山登りよりも勾配降下法または共役勾配法が選択されます。ただし、山登りには、目標関数を微分可能にする必要がないという利点があります。したがって、ヒルクライマーは、ターゲット機能の区別が難しい場合に選択される可能性があります。

山登りはまた、ある時点で高原に到達するという追加の課題を提供するかもしれません。検索空間が平坦な場合、または十分に平坦な場合、ターゲット関数によって返される値は、マシンがその値を表すために使用する精度のために、隣接する領域に返される値と区別がつかなくなります。これは、プラトーに遭遇したときです。このような状況では、ヒルクライマーはどちらの方向に踏むべきかを理解できず、決して前進につながらないルートに進む可能性があります。

擬似コード

アルゴリズム 離散スペースヒルクライミング は

現在のノード := 開始ノード

ループ do

L := ネイバー(現在のノード)

nextEval := −INF

次のノード := NULL

L のすべての x に対して

EVAL(x) > nextEval の場合、

次のノード := x

nextEval := EVAL(x)

次の 評価≤ EVAL(現在のノード) の場合、

より良いネイバーが存在しないため、現在のノードを返します

リターン カレントノード

現在のノード := 次のノード

アルゴリズム 連続スペースヒルクライミング は

currentPoint := initialPoint // 大きさゼロのベクトルは一般的です

ステップサイズ := initialStepSizes // すべての1のベクトルが共通です

加速度 := いくつかの加速度 //