Was ist der Unterschied zwischen stochastischem Bergsteigen und simuliertem Tempern?

Question

Ich lese über die lokale Suche: Bergsteigen und seine Arten und simuliertes Tempern

Eine der Bergsteigerversionen ist das "stochastische Bergsteigen" mit der folgenden Definition:

Das stochastische Bergsteigen prüft nicht alle Nachbarn, bevor es sich bewegt. Vielmehr wählt dieser Suchalgorithmus zufällig einen Nachbarknoten aus und entscheidet, ob er als aktueller Zustand ausgewählt oder ein anderer Zustand untersucht wird

Einige Quellen erwähnten, dass es verwendet werden kann, um lokale Optima zu vermeiden.

Dann las ich über simuliertes Tempern und seine Definition:

Bei jeder Iteration wird eine zufällige Bewegung ausgewählt. Wenn es die Situation verbessert, wird der Zug akzeptiert, andernfalls wird er mit einer Wahrscheinlichkeit von weniger als 1 akzeptiert

Was ist der Hauptunterschied zwischen den beiden Ansätzen? Wählt der Stochastiker nur einen zufälligen (bergauf) Nachfolger? Wenn es nur wählt (bergauf Nachfolger), wie vermeidet es dann lokale Optima?

Answer 1

Das Buch von Russell und Norvig (3. Auflage) beschreibt diese beiden Algorithmen (Abschnitt 4.1.1., S. 122). Dieses Buch ist die Referenz, die Sie im Allgemeinen verwenden sollten, wenn Sie Suchalgorithmen in künstlicher Intelligenz studieren. Ich bin mit simuliertem Tempern (SA) vertraut, da ich es in der Vergangenheit implementiert habe, um ein kombinatorisches Problem zu lösen, aber ich bin mit stochastischem Bergsteigen (SHC) nicht sehr vertraut. Lassen Sie mich daher die Teile des Buches zitieren, die SHC beschreiben .

Das stochastische Bergsteigen wählt zufällig aus den Steigungen aus; Die Auswahlwahrscheinlichkeit kann mit der Steilheit der Steigung variieren. Dies konvergiert normalerweise langsamer als der steilste Aufstieg, aber in einigen staatlichen Landschaften findet es bessere Lösungen.

Daher wählt SHC nach dem Zufallsprinzip eine "Bergaufbewegung", dh eine Bewegung, die die Zielfunktion verbessert (wenn Sie beispielsweise versuchen, das Problem des Handlungsreisenden zu lösen , kann eine "Bergaufbewegung" eine Änderung des aktuellen Hamilton-Zyklus sein , eine Lösung, so dass der neue halmitonische Zyklus kürzere Kosten hat) unter den Bergaufbewegungen (also unter einigen Bewegungen, die das Ziel verbessern).

Beim simulierten Tempern führen Sie eine Bewegung aus. Wenn dieser Schritt zu einer besseren Lösung führt, behalten Sie immer die bessere Lösung. Wenn dies zu einer schlechteren Lösung führt, akzeptieren Sie diese schlechtere Lösung mit einer bestimmten Wahrscheinlichkeit. Es gibt andere Details, wie Sie die schlechtere Lösung akzeptieren (die Sie in Russell und Norvigs Buch finden), aber dies sollte bereits klarstellen, dass SA sich von SHC unterscheidet: SA kann schlechtere Lösungen akzeptieren, um lokalen Minima zu entkommen. während SHC nur Steigungen akzeptiert.