- Der Bergsteigeralgorithmus ist ein lokaler Suchalgorithmus, der sich kontinuierlich in Richtung zunehmender Höhe/Wert bewegt, um den Gipfel des Berges oder die beste Lösung für das Problem zu finden. Es endet, wenn es einen Spitzenwert erreicht, bei dem kein Nachbar einen höheren Wert hat.
- Der Hill-Climbing-Algorithmus ist eine Technik, die zur Optimierung mathematischer Probleme verwendet wird. Eines der vieldiskutierten Beispiele für Hill-Climbing-Algorithmen ist das Problem des Handlungsreisenden, bei dem wir die vom Verkäufer zurückgelegte Strecke minimieren müssen.
- Sie wird auch als gierige lokale Suche bezeichnet, da sie nur auf den guten unmittelbaren Nachbarstaat und nicht darüber hinaus schaut.
- Ein Knoten eines Hill-Climbing-Algorithmus besteht aus zwei Komponenten: Zustand und Wert.
- Hill Climbing wird meist verwendet, wenn eine gute Heuristik verfügbar ist.
- Bei diesem Algorithmus müssen wir den Suchbaum oder das Suchdiagramm nicht verwalten und verwalten, da es nur einen einzelnen aktuellen Status beibehält.
Merkmale des Bergsteigens:
Im Folgenden sind einige Hauptmerkmale des Hill Climbing-Algorithmus aufgeführt:
Zustandsraumdiagramm für Bergsteigen:
Die Zustandsraumlandschaft ist eine grafische Darstellung des Hill-Climbing-Algorithmus, die einen Graphen zwischen verschiedenen Zuständen des Algorithmus und der Zielfunktion/-kosten zeigt.
Auf der Y-Achse haben wir die Funktion verwendet, die eine Zielfunktion oder eine Kostenfunktion sein kann, und auf der X-Achse den Zustandsraum. Wenn die Funktion auf der Y-Achse Kosten ist, besteht das Ziel der Suche darin, das globale Minimum und das lokale Minimum zu finden. Wenn die Funktion der Y-Achse eine Zielfunktion ist, besteht das Ziel der Suche darin, das globale Maximum und das lokale Maximum zu finden.
Verschiedene Regionen in der Zustandsraumlandschaft:
Lokales Maximum: Das lokale Maximum ist ein Zustand, der besser ist als seine Nachbarstaaten, aber es gibt auch einen anderen Zustand, der höher ist als dieser.
Globales Maximum: Das globale Maximum ist der bestmögliche Zustand der Zustandsraumlandschaft. Es hat den höchsten Wert der Zielfunktion.
Jahr der Erfindung des Computers
Aktuellen Zustand: Es handelt sich um einen Zustand in einem Landschaftsdiagramm, in dem sich derzeit ein Agent befindet.
Flaches lokales Maximum: Es handelt sich um einen flachen Raum in der Landschaft, in dem alle Nachbarstaaten aktueller Staaten den gleichen Wert haben.
Schulter: Es handelt sich um eine Hochebene mit einem ansteigenden Rand.
Arten von Bergsteigeralgorithmen:
- Einfaches Bergsteigen:
- Bergsteigen mit dem steilsten Aufstieg:
- Stochastisches Bergsteigen:
1. Einfaches Bergsteigen:
Einfaches Bergsteigen ist die einfachste Möglichkeit, einen Bergsteiger-Algorithmus zu implementieren. Es wertet jeweils nur den Status des Nachbarknotens aus und wählt den ersten aus, der die aktuellen Kosten optimiert, und legt ihn als aktuellen Status fest . Es wird nur überprüft, ob es sich um einen Nachfolgestatus handelt. Wenn ein besserer als der aktuelle Status festgestellt wird, wird der andere Status in denselben Status verschoben. Dieser Algorithmus weist die folgenden Funktionen auf:
- Weniger zeitaufwändig
- Weniger optimale Lösung und die Lösung ist nicht garantiert
Algorithmus für einfaches Bergsteigen:
- Wenn es sich um den Zielzustand handelt, geben Sie Erfolg zurück und beenden Sie den Vorgang.
- Andernfalls wird der neue Status als aktueller Status zugewiesen, wenn er besser als der aktuelle Status ist.
- Andernfalls, wenn nicht besser als der aktuelle Zustand, kehren Sie zu Schritt 2 zurück.
2. Bergsteigen mit steilstem Anstieg:
Der steilste Aufstiegsalgorithmus ist eine Variation des einfachen Bergsteigeralgorithmus. Dieser Algorithmus untersucht alle Nachbarknoten des aktuellen Zustands und wählt einen Nachbarknoten aus, der dem Zielzustand am nächsten liegt. Dieser Algorithmus benötigt mehr Zeit, da er nach mehreren Nachbarn sucht
Algorithmus für das Bergsteigen mit dem steilsten Aufstieg:
- Sei SUCC ein Zustand, in dem jeder Nachfolger des aktuellen Zustands besser ist als dieser.
- Für jeden Operator, der für den aktuellen Status gilt:
- Wenden Sie den neuen Operator an und generieren Sie einen neuen Status.
- Bewerten Sie den neuen Zustand.
- Wenn es sich um den Zielzustand handelt, geben Sie ihn zurück und beenden Sie ihn. Vergleichen Sie ihn andernfalls mit dem SUCC.
- Wenn es besser als SUCC ist, legen Sie den neuen Status auf SUCC fest.
- Wenn der SUCC besser ist als der aktuelle Status, setzen Sie den aktuellen Status auf SUCC.
3. Stochastisches Bergsteigen:
Stochastisches Bergsteigen prüft vor der Bewegung nicht alle seine Nachbarn. Vielmehr wählt dieser Suchalgorithmus zufällig einen Nachbarknoten aus und entscheidet, ob er diesen als aktuellen Zustand wählt oder einen anderen Zustand untersucht.
Probleme im Bergsteigeralgorithmus:
1. Lokales Maximum: Ein lokales Maximum ist ein Spitzenzustand in der Landschaft, der besser ist als jeder seiner Nachbarzustände, aber es gibt auch einen anderen Zustand, der höher als das lokale Maximum ist.
Singleton-Designmuster Java
Lösung: Die Backtracking-Technik kann eine Lösung des lokalen Maximums in der Zustandsraumlandschaft sein. Erstellen Sie eine Liste des vielversprechenden Pfads, damit der Algorithmus den Suchraum zurückverfolgen und auch andere Pfade erkunden kann.
2. Plateau: Ein Plateau ist der flache Bereich des Suchraums, in dem alle Nachbarstaaten des aktuellen Staates denselben Wert enthalten, da dieser Algorithmus keine beste Bewegungsrichtung findet. Eine Bergsteiger-Suche könnte im Plateau-Bereich verloren gehen.
Lösung: Die Lösung für das Plateau besteht darin, bei der Suche große oder sehr kleine Schritte zu unternehmen, um das Problem zu lösen. Wählen Sie zufällig einen Zustand aus, der weit vom aktuellen Zustand entfernt ist, sodass der Algorithmus möglicherweise einen Nicht-Plateau-Bereich finden kann.
3. Grate: Ein Grat ist eine Sonderform des lokalen Maximums. Es verfügt über eine Fläche, die höher liegt als die umliegenden Gebiete, weist aber selbst eine Neigung auf und kann nicht in einer einzigen Bewegung erreicht werden.
Lösung: Durch den Einsatz einer bidirektionalen Suche oder durch Bewegung in verschiedene Richtungen können wir dieses Problem verbessern.
Simuliertes Tempern:
Ein Hill-Climbing-Algorithmus, der sich niemals in Richtung eines niedrigeren Werts bewegt, ist garantiert unvollständig, da er bei einem lokalen Maximum hängen bleiben kann. Und wenn der Algorithmus eine Zufallswanderung anwendet, indem er einen Nachfolger verschiebt, ist er möglicherweise zwar vollständig, aber nicht effizient. Simuliertes Tempern ist ein Algorithmus, der sowohl Effizienz als auch Vollständigkeit liefert.
In mechanischer Hinsicht Glühen ist ein Prozess, bei dem ein Metall oder Glas auf eine hohe Temperatur gehärtet und dann allmählich abgekühlt wird, sodass das Metall einen kristallinen Zustand mit niedriger Energie erreichen kann. Der gleiche Prozess wird beim Simulated Annealing verwendet, bei dem der Algorithmus eine zufällige Bewegung auswählt, anstatt die beste Bewegung auszuwählen. Wenn die zufällige Bewegung den Zustand verbessert, folgt sie demselben Weg. Andernfalls folgt der Algorithmus dem Pfad, der eine Wahrscheinlichkeit von weniger als 1 hat, oder er bewegt sich bergab und wählt einen anderen Pfad.