確率的山登り法とシミュレーテッドアニーリングの違いは何ですか？
私はローカル検索について読んでいます：山登り法とそのタイプ、およびシミュレーテッドアニーリング
山登り法のバージョンの1つは「確率的山登り法」であり、次の定義があります。
確率的な山登り法は、移動する前にすべての隣人を調べません。むしろ、この検索アルゴリズムは1つの隣接ノードをランダムに選択し、それを現在の状態として選択するか、別の状態を調べるかを決定します。
一部の情報源は、局所最適点を回避するために使用できると述べています。
それから私はシミュレーテッドアニーリングとその定義について読んでいました：
すべての反復で、ランダムな動きが選択されます。それが状況を改善する場合、移動は受け入れられます、そうでない場合、それは1未満の確率で受け入れられます
では、2つのアプローチの主な違いは何ですか？確率論はランダムな（上り坂の）後継者のみを選択しますか？（上り坂の後継者）のみを選択した場合、どのようにして局所最適点を回避しますか？
回答
Russell and Norvigの本（第3版）では、これら2つのアルゴリズム（セクション4.1.1。、p。122）について説明しています。この本は、人工知能の検索アルゴリズムを研究するときに一般的に使用する必要のあるリファレンスです。過去に組み合わせ問題を解決するためにシミュレーテッドアニーリング（SA）を実装したことを考えると、シミュレーテッドアニーリング（SA）には精通していますが、確率的山登り法（SHC）にはあまり精通していないため、SHCについて説明している本の部分を引用します。 。
確率的な山登り法は、上り坂の動きの中からランダムに選択します。選択の確率は、上り坂の動きの急勾配によって異なります。これは通常、最も急な上昇よりもゆっくりと収束しますが、一部の州の風景では、より良い解決策が見つかります。
したがって、SHCはランダムに1つの「上り坂の動き」、つまり目的関数を改善する動きを選択します（たとえば、巡回セールスマン問題を解決しようとしている場合、「上り坂の動き」は現在のハミルトン閉路への変更である可能性があります、解決策。これにより、新しいハルミトニアンサイクルのコストが短くなります）、上り坂の動きの間で（つまり、目的を改善する一連の動きの中で）。
でシミュレーテッドアニーリング、あなたはいくつかの移動を実行します。その動きがより良い解決策につながる場合、あなたは常により良い解決策を維持します。それがより悪い解決策につながる場合、あなたは特定の確率でそのより悪い解決策を受け入れます。より悪い解決策を受け入れる方法（ラッセルとノーヴィグの本にあります）など、他の詳細もありますが、これはSAがSHCとは異なることをすでに明確にしているはずです：SAは極小値から逃れるためにより悪い解決策を受け入れることができます、 SHCは上り坂の動きのみを受け入れます。