Simulated Annealing
Intuition des Simulated Annealing
Unter Simulated Annealing versteht man einen Optimierungsalgorithmus, der der Thermodynamik entlehnt ist. Beim Abkühlen eines Metalls bewegen sich die Atome aufgrund der hohen Temperatur zunächst schnell und schließlich mit dem Sinken der Temperatur immer langsamer. Dabei organisieren sie sich in einer stabilen Struktur, die einen nahezu optimalen energiearmen Zustand darstellt. Auch bei Fittingalgorithmen wird ein optimaler Zustand gesucht – das Minimum der Fehlerfunktion. Der Algorithmus durchläuft also verschiedene Positionen auf der Fehleroberfläche, wobei die Temperatur ein Maß dafür ist, mit welcher Wahrscheinlichkeit eine Verschlechterung akzeptiert wird.
Ablauf des Algorithmus
- Festlegung eines Startpunktes und des Temperaturverlaufes
Zunächst wird eine Stelle der Fehleroberfläche zufällig ausgewählt, um die Optimierung von dort zu beginnen. Es muss außerdem festgelegt werden, bei welcher Temperatur gestartet wird und wie sie sich mit jedem Schritt verändert. Dazu kann beispielsweise eine Exponentialfunktion verwendet werden. - Auswahl eines Nachbarpunktes
Ein Punkt in der Nähe des vorherigen Wertes wird zufällig ausgewählt. - Entscheidung, ob der Nachbarpunkt akzeptiert wird
Wenn der gewählte Punkt einen geringeren Fehlerwert als der vorherige hat, wird er als neuer Punkt akzeptiert. Wenn der Punkt schlechter ist, wird zufällig bestimmt, ob er akzeptiert wird. Die Wahrscheinlichkeit des Akzeptierens ist dabei umso höher, je höher die Temperatur ist. - Abkühlen
Die Temperatur wird dann entsprechend der in Schritt 1 festgelegten Verlaufskurve aktualisiert. - Wiederholung der Schritte 2 bis 5, solange keine vollständige Abkühlung erfolgt ist
Vor- und Nachteile des Simulated Annealing
Im Gegensatz zum Gradient Descent ist das Simulated Annealing weniger anfällig für lokale Minima, da kein deterministisches Voranschreiten in Richtung des steilsten Abstiegs erfolgt. Stattdessen können auch schlechtere Werte vorläufig akzeptiert werden.
Zu Schwierigkeiten kann es kommen, wenn die Parameter des Algorithmus nicht optimal gewählt werden. Zum Beispiel können eine zu geringe Anfangstemperatur oder ein zu schnelles Abkühlen dafür sorgen, dass lokale Minima nicht mehr verlassen werden. Außerdem kann ein einmal gefundenes Optimum wieder verloren gehen, wenn der Algorithmus später nicht mehr dorthin zurückkehrt, da kein Beibehalten der besten Lösung vorgesehen ist.
kkk Das Verhalten des Simulated-Annealing-Verfahrens kann in der R-Shiny-App "Fitting" beobachtet und untersucht werden.