Mathematik > Arbeitsgruppen > Stochastische Optimierung > Forschung > Simulated Annealing

Simulated Annealing

Simulated Annealig ist eine stochastische Suchmethode zur näherungsweisen Lösung schwieriger Optimierungprobleme. Ein typisches Beispiel ist die Aufgabe, eine Reihenfolge für verschiedene Bearbeitungsschritte einer Produktion zu finden, so dass die Aufträge möglichst schnell, ohne sich gegenseitig an den Maschinen zu blockieren, durchgeführt werden können. Bezeichnet man die Menge aller möglichen Reihenfolgen mit S, so ist ein x* aus S zu finden mit minimaler Ausführungszeit c(x*). Stellt man sich die Kostenfunktion c: S -> R als eine Landschaft vor, in der hohe Werte c(x) einen erhöhten Punkt an der Stelle x bedeuten, so ist es also das Ziel, ein möglichst tiefes Tal zu finden.

Ausgehend von einem zufälligen Startpunkt x0 untersucht Simulated Annealing zufällig gewählte Lösungen y in der Nachbarschaft der aktuellen Lösung x. Ist y besser als x, d.h. gilt c(y)<c(x), so wird y als neue Lösung übernommen. In der Kostenlandschaft wird der abwärtsführende Weg von x nach y genommen. Gilt dagegen c(y)>c(x), führt der Weg von x nach y also bergauf, so wird y trotzdem als neue Lösung akzeptiert – allerdings nur mit einer gewissen Wahrscheinlichkeit, der sogenannten Akzeptanzwahrscheinlichkeit. Durch diese Fähigkeit, Verschlechterungen zu akzeptieren, kann das Verfahren lokale Täler verlassen und zum globalen Minimum vorstoßen, wie auf der Abbildung angedeutet ist.

Als Akzeptanzwahrscheinlichkeit für einen Kandidaten y bei gegenwärtiger Lösung x wird meist exp(-(c(y)-c(x))/tn) gewählt. Dabei ist tn die sogenannte Temperatur, die mit wachsender Schrittzahl n gegen 0 geht. Kleinere Verschlechterungen D=c(y)-c(x)>0 werden also eher akzeptiert als größere, auch mit wachsendem n, also fallender Temperatur, werden Verschlechterungen seltener akzeptiert. Wird eine Lösung y nicht akzeptiert, so wird ein neuer Kandidat y' aus der Nachbarschaft zufällig ausgewählt.

Das Verfahren ist angelehnt an ein physikalisches Modell für Abkühlungsvorgänge ('annealing') bei geschmolzenen Metallen, bei denen abhängig von der Temperaturführung das Material besonders günstige Strukturen beim Erstarren aufbauen kann. Bei anfangs hohen Temperaturen werden viele Verschlechterungen akzeptiert, der Prozess bewegt sich in der Regel schnell vom Ausgangspunkt weg, auf Dauer wird die Schwelle zur Akzeptanz von Verschlechterungen höher, der Prozess kommt zur Ruhe.

Die Folge der besuchten Lösungen bildet eine inhomogene Markoffkette und es können Bedingungen für die Konvergenz gegen eine optimale Lösung angegeben werden. In der Clausthaler Arbeitsgruppe sind Erweiterungen untersucht worden, bei denen die Temperatur in Abhängigkeit vom bisherigen Prozessverlauf auch wieder erhöht werden kann. Es konnte gezeigt werden, dass entgegen der z.T. in der Literatur verbreiteten Auffassung, Simulated Annealing z.B. beim sogenannten Job Shop Scheduling Problem nicht zu konvergieren braucht (vgl. Myths and Counterexamples in Mathematical Programming, http://glossary.computing.society.informs.org/myths/CurrentVersion/myths.pdf).

Literatur

  • M. Kolonko und M. T. Tran : Convergence of Simulated Annealing with Feedback Temperature Schedules. Prob. in the Engineering and Informational Sciences, 11,279-304, 1997.(Corrected Version) [ps]

  • M. Kolonko : Some New Results on Simulated Annealing Applied to the Job Shop Scheduling Problem. European J. of Operational Research, 113,123-136, 1999. [pdf]

 

Sitemap  Datenschutz  Kontakt  Impressum
© TU Clausthal 2017