Was sind die Einschränkungen des Bergsteigeralgorithmus und wie können sie überwunden werden?

Was sind die Einschränkungen des Hill Climbing-Algorithmus ? Wie können wir diese Einschränkungen überwinden?

Wie @nbro bereits gesagt hat, ist Hill Climbing eine Familie lokaler Suchalgorithmen . Als Sie in der Frage Hill Climbing sagten, habe ich angenommen, dass Sie über das Standard-Hill Climbing sprechen. Die Standardversion des Bergsteigens weist einige Einschränkungen auf und bleibt häufig im folgenden Szenario hängen:

• Lokale Maxima: Der Hill-Climbing-Algorithmus erreicht in der Nähe einen lokalen Maximalwert, wird zum Gipfel gezogen und bleibt dort stecken, ohne einen anderen Ort zu haben .
• Grate: Dies sind Sequenzen lokaler Maxima , die es dem Algorithmus erschweren, zu navigieren.
• Hochebenen: Dies ist eine flache State-Space-Region . Da es nicht bergauf geht, geht der Algorithmus häufig auf dem Plateau verloren.
  

Um diese Probleme zu lösen, wurden viele Varianten von Bergsteigeralgorithmen entwickelt. Diese werden am häufigsten verwendet:

• Stochastic Hill Climbing wählt zufällig aus den Steigungen aus. Die Auswahlwahrscheinlichkeit variiert mit der Steilheit der Steigung.
• First-Choice Climbing implementiert das oben genannte, indem zufällig Nachfolger generiert werden, bis ein besserer gefunden wird.
• Zufällige Neustart-Bergsteigersuche von zufällig generierten Anfangsbewegungen bis zum Erreichen des Zielzustands.

Der Erfolg von Bergsteigeralgorithmen hängt von der Architektur der Zustandsraumlandschaft ab. Immer wenn es nur wenige Maxima und Plateaus gibt, funktionieren die Varianten der Suchalgorithmen für Bergsteiger sehr gut. In der realen Welt gibt es jedoch Probleme mit einer Landschaft, die eher wie eine weit verstreute Familie kahlköpfiger Stachelschweine auf einem flachen Boden aussieht, wobei Miniaturstachelschweine an der Spitze jeder Stachelschweinnadel leben (wie im 4. Kapitel des Buches Künstliche Intelligenz beschrieben: A. Moderner Ansatz). NP-harte Probleme haben normalerweise eine exponentielle Anzahl lokaler Maxima, an denen sie hängen bleiben müssen.
Gegebene Algorithmen wurden entwickelt, um diese Art von Problemen zu überwinden:

• Stimuliertes Tempern
• Lokale Strahlensuche
• Genetische Algorythmen

Nachschlagewerk - Künstliche Intelligenz: Ein moderner Ansatz

Bergsteigen ist kein Algorithmus, sondern eine Familie von "lokalen Such" -Algorithmen. Spezifische Algorithmen, die in die Kategorie der "Bergsteiger" -Algorithmen fallen, sind 2-opt, 3-opt, 2,5-opt, 4-opt oder allgemein jeder N-opt. Weitere Informationen zu einigen dieser lokalen Suchalgorithmen (angewendet auf den TSP) finden Sie in Kapitel 3 des Dokuments " Das Problem des Handlungsreisenden: Eine Fallstudie zur lokalen Optimierung " (von David S. Johnson und Lyle A. McGeoch).

Was einen Algorithmus in dieser Kategorie von dem anderen unterscheidet, ist die "Nachbarschaftsfunktion", die sie verwenden (in einfachen Worten, die Art und Weise, wie sie benachbarte Lösungen zu einer bestimmten Lösung finden). Beachten Sie, dass dies in der Praxis nicht immer der Fall ist: Oft haben diese Algorithmen mehrere unterschiedliche Implementierungen.

Die offensichtlichste Einschränkung von Bergsteigeralgorithmen liegt in ihrer Natur, dh sie sind lokale Suchalgorithmen. Daher finden sie normalerweise nur lokale Maxima (oder Minima). Wenn also einer dieser Algorithmen bereits zu einem lokalen Minimum (oder Maximum) konvergiert hat und es in der Lösung oder im Suchraum nahe dieser gefundenen Lösung eine bessere Lösung gibt, kann keiner dieser Algorithmen dies finden bessere Lösung. Sie werden im Grunde gefangen sein.

Lokale Suchalgorithmen werden normalerweise nicht alleine verwendet. Sie werden als Unterroutinen anderer meta-heuristischer Algorithmen verwendet, wie z. B. simuliertes Tempern, iterierte lokale Suche oder in einem der Ameisenkolonie-Algorithmen. Um ihre Einschränkungen zu überwinden, verwenden wir sie normalerweise nicht alleine, sondern in Verbindung mit anderen Algorithmen, die probabilistisch sind und globale Minima oder Maxima finden können (z. B. einen der Ameisenkolonie-Algorithmen).