Simulated Annealing (SA)


(Contents)(Previous)(Next)

Aus der Physik weiss man, dass bei der Abkühlung von Flüssigkeiten Kristalle unterschiedlicher Grösse entstehen können. Dabei sinkt mit der Temperatur T die Gesamtenergie E. Je nach Kristallisation werden sehr unterschiedliche lokale Minima der Energie erreicht. Bei schneller Abkühlung erreicht das System üblicherweise rasch ein lokales Minimum mit relativ hohem Energiewert, während bei genügend langsamer Abkühlung das globale Energieminimum erreicht werden kann. Wichtig ist dabei die Wahrscheinlichkeitsverteilung

width="76",

wobei k die Bolzmann'sche Konstante ist.

Simulated Annealing ahmt diese physikalischen Prozesse auf ganz primitive Weise nach. Prinzipiell wird dabei nach Minima Funktion f(r) gesucht und die oben erwähnte Wahrscheinlichkeitsverteilung in den Suchalgorithmus eingebaut.

Zunächst werden in der Initialisierungsphase ein Ort raktuell im Suchraum, eine maximale Schrittweite saktuell und eine Temperatur Taktuell bestimmt. Dabei wird raktuell normalerweise rein zufällig gesetzt, während saktuell der Grösse des Suchraums angepasst wird. Das Setzen von Taktuell braucht etwas Erfahrung.

Während eines Optimierungsschrittes wird mittels Zufallsgenerator ein neuer Punkt rneu in der Umgebung von raktuell erzeugt, wobei der Abstand dieser zwei Punkte kleiner als saktuell sein sollte. Bei einer streng zielgerichteten Suche würde man den neuen Punkt nur dann akzeptieren (d.h. raktuell=rneu setzen), wenn f(rneu)<f(raktuell) gilt. Beim Simulated Annealing akzeptiert man den neuen Punkt hingegen auch wenn diese Ungleichung nicht erfüllt ist, allerdings nur mit der Wahrscheinlichkeit p=exp(-(f(rneu)-f(raktuell))/T). (N.B. die Boltzmann'sche Konstante k ist masssystemabhängig und kann hier eins gesetzt werden.) Dadurch wird die Möglichkeit geschaffen, dass die Suche ein lokales Minimum wieder verlässt. Als nächstes müssen die maximale Schrittweite saktuell und die Temperatur Taktuell angepasst werden. Beide Grössen werden tendenziell vermindert, was bedeutet, dass sich die Suche auf eine kleinere Umgebung des aktuellen Punktes konzentriert und die Suche zielgerichteter wird. Ein geeignetes Szenario für die Anpassung von saktuell und Taktuell zu finden erfordert allerdings einige Erfahrung. Dabei kann man es dem Benutzer überlassen, Schrittweiten- und Temperaturfunktionen zu definieren, welche während der Suche aufgerufen werden und so auf dessen Erfahrung abstellen. Ein geübter Benutzer erhält damit die Möglichkeit, seine Erfahrung einzubringen. Wenig erfahrene Benutzer bevorzugen sicher vordefinierte Schrittweiten- und Temperaturfunktionen. Dabei ist allerdings zu beachten, dass die Effizienz und Zuverlässigkeit von Simulated Annealing sehr darunter leiden können, da Schrittweiten- und Temperaturfunktionen, welche bei manchen Optimierungsaufgaben sehr erfolgreich sind bei andern Optimierungsaufgaben versagen.

Übungsaufgabe: Während des Suchprozesses gewinnt das Optimierungsverfahren einige „Erfahrung" über die zu betrachtete Funktion f(r). Wie lässt sich diese Erfahrung nutzen um Schrittweite und Temperatur während der Suche anzupassen?

Übungsaufgabe: Überlege, welche Probleme beim Simulated Annealing auftreten, wenn f(r) im zweidimensionalen Fall die Form eines langgestreckten Tales hat. Wie lassen sich die Probleme beheben?

Übungsaufgabe: Versuche Simulated Annealing mit der Simplex Methode zu kombinieren.

Simulated Annealing macht klar, dass die Wahrscheinlichkeit ein globales Minimum zu finden durch Einbau von Zufallsgrössen erhöht werden kann, wobei allerdings gleichzeitig die Rechenzeit erhöht und die Zielgerichtetheit der Suche reduziert wird. Zuverlässigere Algorithmen sind also tendenziell rechenintensiver. Dies heiss allerdings nicht, dass es unmöglich ist, Algorithmen zu finden, welche zuverlässiger und gleichzeitig effizienter als Simulated Annealing sind. Prinzipiell leidet Simulated Annealing sicher unter der Tatsache, dass jeweils nur die Information in den zwei Punkten raktuell und rneu verwendet wird. Da moderne Computer über viel Speicher verfügen, ist dies nicht sehr sinnvoll. Die im folgenden beschriebenen Verfahren sind speicherintensiver, was allerdings in diesem Zusammenhang als vorteilhaft betrachtet werden muss.


(Contents)(Previous)(Next)