Design-and-analysis-of-algorithms-hill-climbing
DAA-ヒルクライミングアルゴリズム
前の章で説明したアルゴリズムは体系的に実行されます。 目標を達成するには、最適なソリューションを見つけるために、以前に探索したソリューションへのパスを1つ以上保存する必要があります。
多くの問題では、目標への道は無関係です。 たとえば、Nクイーンの問題では、クイーンの最終的な構成や、クイーンが追加される順序を気にする必要はありません。
山登り
ヒルクライミングは、特定の最適化の問題を解決する手法です。 この手法では、次善のソリューションから開始し、ある条件が最大になるまでソリューションを繰り返し改善します。
最適ではない解決策から始めるという考えは、丘のふもとから始めることと比較され、解決策の改善は丘を登るのと比較され、最終的に何らかの条件を最大化することは丘の頂上に達することと比較されます。
したがって、山登り技術は、次の段階とみなすことができます-
- 問題の制約に従う準最適なソリューションの構築
- ソリューションを段階的に改善する
- 改善が不可能になるまでソリューションを改善する
ヒルクライミング技術は、主に計算が難しい問題を解決するために使用されます。 現在の状態とその直後の状態のみを調べます。 したがって、この手法は検索ツリーを維持しないため、メモリ効率が高くなります。
Algorithm: Hill Climbing
Evaluate the initial state.
Loop until a solution is found or there are no new operators left to be applied:
- Select and apply a new operator
- Evaluate the new state:
goal -→ quit
better than current state -→ new current state反復的な改善
反復改善法では、すべての反復で最適なソリューションに向かって前進することにより、最適なソリューションが達成されます。 ただし、この手法では極大値が発生する場合があります。 この状況では、より良い解決策のための近くの州はありません。
この問題はさまざまな方法で回避できます。 これらの方法の1つは、シミュレーテッドアニーリングです。
ランダム再起動
これは、局所最適の問題を解決する別の方法です。 この手法は、一連の検索を実行します。 毎回、ランダムに生成された初期状態から開始します。 したがって、実行された検索のソリューションを比較して、最適なソリューションまたはほぼ最適なソリューションを取得できます。
登山技術の問題
ローカルマキシマ
ヒューリスティックが凸でない場合、ヒルクライミングはグローバルな最大値ではなくローカルな最大値に収束する可能性があります。
尾根と路地
ターゲット関数が狭い尾根を作成する場合、登山者はジグザグで尾根を登るか、路地を下ることしかできません。 このシナリオでは、登山者は非常に小さなステップを踏む必要があり、目標を達成するためにより多くの時間を必要とします。
高原
探索空間がフラットであるか、またはターゲット関数によって返される値が近くの領域に対して返される値と区別できないほど十分に平坦である場合、プラトーが発生します。
登山技術の複雑さ
この手法は、現在の状態のみを調べるため、スペースに関連する問題の影響を受けません。 以前に探索されたパスは保存されません。
ランダムリスタートヒルクライミングテクニックのほとんどの問題では、多項式時間で最適なソリューションを実現できます。 ただし、NP完全問題の場合、計算時間は局所的な最大数に基づいて指数関数的になります。
ヒルクライミング技術の応用
ヒルクライミング技術は、ネットワークフロー、巡回セールスマン問題、8クイーン問題、集積回路設計など、現在の状態が正確な評価関数を可能にする多くの問題を解決するために使用できます。
ヒルクライミングは帰納的学習法でも使用されます。 この手法は、チーム内の複数のロボット間の調整のためにロボット工学で使用されます。 この手法が使用される他の多くの問題があります。
例
この手法は、巡回セールスマンの問題を解決するために適用できます。 最初に、すべての都市を一度だけ訪問する初期ソリューションが決定されます。 したがって、ほとんどの場合、この初期ソリューションは最適ではありません。 この解決策でさえ非常に貧弱な場合があります。 Hill Climbingアルゴリズムは、このような初期ソリューションから始まり、反復的な方法で改善を行います。 最終的には、はるかに短いルートが取得される可能性があります。
