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

1. 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.
2. Auswahl eines Nachbarpunktes
   Ein Punkt in der Nähe des vorherigen Wertes wird zufällig ausgewählt.
3. 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.
4. Abkühlen
   Die Temperatur wird dann entsprechend der in Schritt 1 festgelegten Verlaufskurve aktualisiert.
5. 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.