DAA - Hill Climbing Algorithmus

Die in den vorherigen Kapiteln beschriebenen Algorithmen werden systematisch ausgeführt. Um das Ziel zu erreichen, müssen ein oder mehrere zuvor untersuchte Pfade zur Lösung gespeichert werden, um die optimale Lösung zu finden.

Für viele Probleme ist der Weg zum Ziel irrelevant. Zum Beispiel müssen wir uns beim N-Queens-Problem nicht um die endgültige Konfiguration der Königinnen sowie um die Reihenfolge kümmern, in der die Königinnen hinzugefügt werden.

Berg steigen

Hill Climbing ist eine Technik zur Lösung bestimmter Optimierungsprobleme. Bei dieser Technik beginnen wir mit einer suboptimalen Lösung und die Lösung wird wiederholt verbessert, bis einige Bedingungen maximiert sind.

Die Idee, mit einer suboptimalen Lösung zu beginnen, wird mit dem Starten vom Fuß des Hügels aus verglichen. Das Verbessern der Lösung wird mit dem Gehen auf dem Hügel verglichen, und schließlich wird das Maximieren einiger Bedingungen mit dem Erreichen der Spitze des Hügels verglichen.

Daher kann die Bergsteigertechnik als die folgenden Phasen betrachtet werden:

• Konstruieren einer suboptimalen Lösung unter Berücksichtigung der Einschränkungen des Problems
• Schritt für Schritt die Lösung verbessern
• Verbesserung der Lösung, bis keine Verbesserung mehr möglich ist

Die Hill Climbing-Technik wird hauptsächlich zur Lösung rechenintensiver Probleme verwendet. Es wird nur der aktuelle Zustand und der unmittelbare zukünftige Zustand betrachtet. Daher ist diese Technik speichereffizient, da sie keinen Suchbaum verwaltet.

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

Iterative Verbesserung

Bei der iterativen Verbesserungsmethode wird die optimale Lösung erreicht, indem bei jeder Iteration Fortschritte in Richtung einer optimalen Lösung erzielt werden. Diese Technik kann jedoch auf lokale Maxima stoßen. In dieser Situation gibt es keinen nahe gelegenen Staat für eine bessere Lösung.

Dieses Problem kann durch verschiedene Methoden vermieden werden. Eine dieser Methoden ist das simulierte Tempern.

Zufälliger Neustart

Dies ist eine weitere Methode zur Lösung des Problems lokaler Optima. Diese Technik führt eine Reihe von Suchen durch. Jedes Mal beginnt es mit einem zufällig generierten Ausgangszustand. Daher können Optima oder nahezu optimale Lösungen erhalten werden, wenn die Lösungen der durchgeführten Suchen verglichen werden.

Probleme der Bergsteigertechnik

Lokale Maxima

Wenn die Heuristik nicht konvex ist, kann Hill Climbing zu lokalen Maxima anstelle von globalen Maxima konvergieren.

Grate und Gassen

Wenn die Zielfunktion einen schmalen Grat erzeugt, kann der Kletterer den Grat nur im Zick-Zack-Verfahren besteigen oder die Gasse hinuntersteigen. In diesem Szenario muss der Kletterer sehr kleine Schritte unternehmen, die mehr Zeit benötigen, um das Ziel zu erreichen.

Plateau

Ein Plateau tritt auf, wenn der Suchraum flach oder ausreichend flach ist, so dass der von der Zielfunktion zurückgegebene Wert aufgrund der von der Maschine zur Darstellung ihres Werts verwendeten Genauigkeit nicht von dem für benachbarte Regionen zurückgegebenen Wert zu unterscheiden ist.

Komplexität der Bergsteigertechnik

Diese Technik leidet nicht unter weltraumbezogenen Problemen, da sie nur den aktuellen Status betrachtet. Zuvor erkundete Pfade werden nicht gespeichert.

Für die meisten Probleme bei der Random-Restart-Hill-Climbing-Technik kann eine optimale Lösung in Polynomzeit erreicht werden. Bei NP-Complete-Problemen kann die Rechenzeit jedoch basierend auf der Anzahl der lokalen Maxima exponentiell sein.

Anwendungen der Bergsteigertechnik

Die Hill Climbing-Technik kann verwendet werden, um viele Probleme zu lösen, bei denen der aktuelle Status eine genaue Bewertungsfunktion ermöglicht, z. B. Netzwerkfluss, Problem des Handlungsreisenden, 8-Queens-Problem, Entwurf integrierter Schaltkreise usw.

Hill Climbing wird auch in induktiven Lernmethoden eingesetzt. Diese Technik wird in der Robotik zur Koordination zwischen mehreren Robotern in einem Team verwendet. Es gibt viele andere Probleme, bei denen diese Technik verwendet wird.

Beispiel

Diese Technik kann angewendet werden, um das Problem des Handlungsreisenden zu lösen. Zunächst wird eine erste Lösung festgelegt, die alle Städte genau einmal besucht. Daher ist diese anfängliche Lösung in den meisten Fällen nicht optimal. Auch diese Lösung kann sehr schlecht sein. Der Hill Climbing-Algorithmus beginnt mit einer solchen anfänglichen Lösung und verbessert sie iterativ. Schließlich wird wahrscheinlich eine viel kürzere Route erhalten.