Das stochastische Bergsteigen ist im Allgemeinen schlechter als das steilste Bergsteigen , aber in welchen Fällen ist das erstere besser?
Die steilsten Bergsteigeralgorithmen eignen sich gut für die konvexe Optimierung. Probleme in der realen Welt sind jedoch typischerweise nicht konvexe Optimierungstypen: Es gibt mehrere Peaks. In solchen Fällen ist die Wahrscheinlichkeit hoch, dass dieser Algorithmus bei einer zufälligen Lösung einen der lokalen Peaks anstelle des globalen Peaks erreicht. Verbesserungen wie simuliertes Tempern verbessern dieses Problem, indem sie dem Algorithmus ermöglichen, sich von einem lokalen Peak zu entfernen, und dadurch die Wahrscheinlichkeit erhöhen, dass er den globalen Peak findet.
Für ein einfaches Problem mit nur einem Gipfel ist das steilste Bergsteigen natürlich immer besser. Es kann auch ein vorzeitiges Stoppen verwendet werden, wenn ein globaler Peak gefunden wird. Im Vergleich dazu würde ein simulierter Annealing-Algorithmus tatsächlich von einem globalen Peak wegspringen, zurückkehren und wieder wegspringen. Dies würde sich wiederholen, bis es ausreichend abgekühlt ist oder eine bestimmte voreingestellte Anzahl von Iterationen abgeschlossen ist.
Probleme in der realen Welt betreffen verrauschte und fehlende Daten. Ein stochastischer Bergsteigeransatz ist zwar langsamer, aber für diese Probleme robuster, und die Optimierungsroutine hat im Vergleich zum steilsten Bergsteigeralgorithmus eine höhere Wahrscheinlichkeit, den globalen Gipfel zu erreichen.
Epilog: Dies ist eine gute Frage, die beim Entwerfen einer Lösung oder bei der Auswahl zwischen verschiedenen Algorithmen eine anhaltende Frage aufwirft: den Kompromiss zwischen Leistung und Rechenkosten. Wie Sie vielleicht vermutet haben, lautet die Antwort immer: Sie hängt von den Prioritäten Ihres Algorithmus ab. Wenn es Teil eines Online-Lernsystems ist, das mit einem Datenstapel arbeitet, gibt es eine starke Zeitbeschränkung, aber eine schwache Leistungsbeschränkung (die nächsten Datenstapel korrigieren fehlerhafte Verzerrungen, die durch den ersten Datenstapel verursacht werden). Wenn es sich dagegen um eine Offline-Lernaufgabe mit den gesamten verfügbaren Daten handelt, ist die Leistung die Hauptbeschränkung, und die stochastischen Ansätze sind ratsam.
Beginnen wir zunächst mit einigen Definitionen.
Bergsteigen ist ein Suchalgorithmus, der einfach eine Schleife durchläuft und sich kontinuierlich in Richtung steigenden Wertes bewegt, dh bergauf. Die Schleife endet, wenn sie einen Spitzenwert erreicht und kein Nachbar einen höheren Wert hat.
Das stochastische Bergsteigen , eine Variante des Bergsteigens, wählt aus den Steigungen einen Zufall aus. Die Auswahlwahrscheinlichkeit kann mit der Steilheit der Bergaufbewegung variieren. Zwei bekannte Methoden sind:
Bergsteigen erster Wahl: Generiert zufällig Nachfolger, bis eine generiert wird, die besser als der aktuelle Zustand ist. * Wird als gut angesehen, wenn der Staat viele Nachfolger hat (wie Tausende oder Millionen).
Bergsteigen nach dem Zufallsprinzip:Arbeitet an der Philosophie "Wenn Sie keinen Erfolg haben, versuchen Sie es erneut".
Nun zu Ihrer Antwort. Stochastisches Bergsteigen kann in vielen Fällen sogar eine bessere Leistung bringen . Betrachten Sie den folgenden Fall. Das Bild zeigt die Zustandsraumlandschaft. Das im Bild gezeigte Beispiel stammt aus dem Buch Künstliche Intelligenz: Ein moderner Ansatz .
Angenommen, Sie befinden sich an dem Punkt, der vom aktuellen Status angezeigt wird. Wenn Sie einen einfachen Bergsteigeralgorithmus implementieren, erreichen Sie das lokale Maximum und der Algorithmus wird beendet. Obwohl es einen Zustand mit einem optimaleren Zielfunktionswert gibt, erreicht der Algorithmus diesen nicht, da er an einem lokalen Maximum hängen geblieben ist. Der Algorithmus kann auch bei flachen lokalen Maxima hängen bleiben .
Das zufällige Neustarten des Bergsteigens führt eine Reihe von Suchvorgängen zum Bergsteigen aus zufällig generierten Anfangszuständen durch, bis ein Zielzustand gefunden wird.
Der Erfolg des Bergsteigens hängt von der Form der State-Space-Landschaft ab. Falls es nur wenige lokale Maxima gibt, flache Hochebenen; Ein zufälliger Neustart des Bergaufstiegs wird sehr schnell eine gute Lösung finden. Die meisten realen Probleme haben eine sehr raue Zustandsraumlandschaft, so dass sie nicht für die Verwendung des Bergsteigeralgorithmus oder einer seiner Varianten geeignet sind.
HINWEIS: Der Hill Climb-Algorithmus kann auch verwendet werden, um den Minimalwert und nicht nur die Maximalwerte zu ermitteln. Ich habe in meiner Antwort den Begriff Maximum verwendet. Wenn Sie nach Mindestwerten suchen, werden alle Dinge umgekehrt, einschließlich des Diagramms.
Ich bin auch neu in diesen Konzepten, aber so wie ich es verstanden habe, würde stochastisches Bergsteigen in Fällen, in denen Rechenzeit kostbar ist (einschließlich der Berechnung der Fitnessfunktion), eine bessere Leistung erbringen, aber es ist nicht wirklich notwendig, das Beste zu erreichen mögliche Lösung. Es wäre in Ordnung, auch nur ein lokales Optimum zu erreichen. Roboter, die in einem Schwarm arbeiten, wären ein Beispiel, wo dies verwendet werden könnte.
Der einzige Unterschied, den ich beim steilsten Bergsteigen sehe, ist die Tatsache, dass nicht nur die Nachbarknoten, sondern auch die Nachfolger der Nachbarn durchsucht werden, ähnlich wie bei einem Schachalgorithmus nach vielen weiteren Zügen gesucht wird, bevor der beste Zug ausgewählt wird.
quelle
quelle