山登りアルゴリズム
1. 序章
このチュートリアルでは、最も単純で最もよく知られている最適化アルゴリズムの1つである山登り法の特性を学習します。
2. いくつかの定義
アルゴリズムの分析に取り組む前に、アルゴリズムを正しく組み立てるのに役立ついくつかの定義を作成しておくと便利です。
数理最適化問題。 これは、独立変数または入力の値が与えられた場合に、いくつかの実関数の最大値または最小値を特定することを解決する問題です。
ヒューリスティック検索。 これは、決定論的研究に対する概念の対抗策であり、問題または入力の独立変数の関数で予測される量をリンクするモデルがある場合に使用できます。
モデルがない場合、ヒューリスティック検索では問題のグローバル最適が見つからない可能性があり、最適ではないソリューションが提供されます。 ただし、制約は、妥当な時間（多項式）で結果を達成することです。
ローカル検索。 これは、ヒューリスティック検索がどのように機能するかに関連しています。 それは、いくつかの基準を最大化するものを特定して、特定の数の候補を提案します。 地域の研究には、地域の変化を適用することによる問題の解決策の空間での動きが含まれます。 事前設定された停止条件に達するか、それ以上の改善が見つからない場合、アルゴリズムは終了します。
凸最適化。 これは、ローカル調査によるヒューリスティック手法が適している数学関数のタイプを指します。 これらは、目的関数（必ずしもすべての点で連続している必要はありません）が凸である問題に適用されます。つまり、関数の任意の2点をセグメントで結合し、関数のグラフの下にないような関数があります。
次の表は、これらの概念をまとめたものです。
山登り法はヒューリスティックな検索方法であり、最適化問題に適応し、ローカル検索を使用して最適なを特定します。 凸問題の場合、それは大域的最適に到達することができますが、他のタイプの問題の場合、それは一般に局所的最適を生成します。
3. アルゴリズム
続けて、簡単にするために、最大化問題を検討します。
このような問題に対して、山登り法は、現在の状態に小さな変更を加えることによって、ターゲット関数のより大きな値を継続的に生成します（ローカル検索）。 新しい状態が目的関数の値の増加を想定している場合、それは受け入れられ、次のステップの現在の状態になります。
山登り法は基本的に、生成およびテストアルゴリズムの変形であり、次の図に示しています。
アルゴリズムの主な機能は次のとおりです。
- 貪欲なアプローチを採用する：それは、解の空間を通る動きが常に目的関数を最大化するという意味で発生することを意味します。
- 後戻りはありません。 現在の状態でのみ動作します。 ある状態に至った研究の過去の歴史は無関係です。
- メカニズムを生成してテストします。 次の現在の状態を決定できます。
- 増分変更。 現在の状態は、小さな増分変更によって改善されます。
4. 山登り法の制限
山登り法には多くの制限があります。 それらを説明するために、いわゆる状態空間図を使用します。これは、検索中に到達できる問題の解の空間を、目的関数の値と関連付けます。
この図から、現在の状態が「極大」とラベル付けされた状態に対応している場合、バックトラックなしの山登りアルゴリズムではそれ以上の改善が得られないことが明らかです。 収束の問題を引き起こす可能性のある他の領域があります。
次の収差を解決するには、古典的な山登り法にいくつかの変更を加える必要があります。
- 問題のある領域をバイパスするために、大きなジャンプを許可します。
- 調査の各ステップで、現在の状態の変化を複数の方向で同時に調査します。
- 調査した状態のリストを保持し、それらの不要な状態にタグを付けて、バックトラックを導入します。 この場合、過去の歴史の状態の1つに戻ります。
- モーメント項を使用します。 これにより、目的関数の値に修正が加えられ、問題のあるソリューションや見込みのないソリューションにペナルティを課すことができます。
4.1. 高原またはフラットローカルマキシマム
現在の状態に近いポイントは、目的関数と同じ値になります。 これは極大値の一種です。 この場合、解空間で発生する可能性のある動きのほとんどが目的関数値の低下につながるため、検索が妨げられます。
4.2. 海嶺
これは極大値の一種です。 この場合、解空間で発生する可能性のある動きのほとんどが目的関数値の低下につながるため、検索が妨げられます。
4.3. ショルダー
これは、エッジの1つがより高い目的関数値につながるタイプのプラトーです。
このタイプの収差の難しさは、アルゴリズムが目的関数の値の勾配を識別できないため、方向を選択できないことです。
この問題は、現在の状態から大きくジャンプすることで解決されます。
5. クラシックな山登り法の進化
山登り法には2つの主要な進化があり、前のセクションの問題を完全にまたは部分的に解決することができます。 まず、最も急な山登り法または山登り法について話しましょう。 現在の状態に近い一連のソリューションを調べ、それらから最適なソリューションを選択します。
この手法の変形は、確率的山登り法です。 単一の潜在的なソリューションをランダムに選択します。 改善の程度に基づいて、アルゴリズムはそれが新しい現在の状態になるかどうかを決定します。 この方法論は、計算の各ステップで候補解を選択する際に使用される基準に応じて、さまざまな方法で拒否できます。
6. 焼き鈍し法
通常、シミュレーテッドアニーリングは山登り法の一種とは見なされません。 このチュートリアルでは、これを確率的山登り法の特に高度な進化と見なします。
この考慮事項の理由は、両方のアルゴリズムが基本的な動作モードを共有しているという事実にあります。 特に、彼らは単一の解決策、現在の状態から始まる状態の空間での動きを実現します。 実際、目的関数の改善を想定した解が見つかると、新しい現在の状態が変更されます。
前のセクションの異常を回避するために、アルゴリズムが現在のソリューションから遠く離れた領域に「ジャンプ」し、問題のある領域をバイパスできるようにする必要があります。これにより、アプリケーションを一般的な問題に拡張できます。 最も急な山登り法または確率的な山登り法の違いは、これらのジャンプが発生する基準です。
6.1. 閉じ込めを回避するための物理的なアナロジー
シミュレーテッドアニーリングのベースには、物理的なアナロジーがあります。それは、固体のアニーリングです。 与えられたエネルギーを持つ粒子の割合は温度に依存し、ボルツマン分布に従って統計的に分布します。
ここで、は粒子の総数であり、はボルツマン定数です。
6.2. メトロポリス基準
シミュレーテッドアニーリングのアイデアは、同様の統計法則に従ってソリューション空間でジャンプできるようにすることです。 特に、最大化問題の場合：
- 目的関数の値を使用して、初期状態である現在の状態から開始します。
- たとえば、初期温度を定義します。
- すでに隣接する状態の間に新しい候補状態をランダムに生成します。 新しい状態の目的関数が大きい場合、ソリューションを新しい現在の状態として受け入れ、ソリューション空間を通過する動きを実現します。
- が小さい場合、範囲内の乱数が生成され、その値がメトロポリス基準よりも小さい場合、ソリューションを新しい現在の状態として受け入れます。
- 状態変化が発生すると、温度が下がります。 通常、それはのような法則に従います。
- たとえば、温度が事前設定値に達すると実行が終了します。
温度が下がると、目的関数値が小さい新しい状態が受け入れられる可能性が低くなります。 これにより、計算の初期段階では確率が高く、最終段階では確率が低い、現在の領域以外の領域の探索が可能になります。
私たちのチュートリアルJavaでの巡回セールスマン問題は、シミュレーテッドアニーリングアルゴリズムのJavaでの実装をカバーしています。
7. 結論
このチュートリアルでは、山登り法について見てきました。 これは非常に単純なヒューリスティック手法であり、凸問題などの特定のタイプの最適化問題に適しています。 シンプルですが、多くの産業分野で使用されており、マーケティング、ロボット工学、ジョブスケジューリング問題などのさまざまな分野の問題を解決します。
山登り法の進化により、古典的な山登り法の範囲内にない問題に対しても、アプリケーションを一般化することが可能になります。 特に、シミュレーテッドアニーリングはマルチモーダル問題を解決することもでき、場合によっては遺伝的アルゴリズムなどのより高度なアルゴリズムよりも優れています。
