Simulierte Abkühlung

Die simulierte Abkühlung (englisch simulated annealing, auch simuliertes Tempern oder simulierte Vergütung genannt) ist ein heuristisches Approximationsverfahren. Sie wird zum Auffinden einer Näherungslösung von Optimierungsproblemen eingesetzt, die durch ihre hohe Komplexität das vollständige Ausprobieren aller Möglichkeiten und mathematische Optimierungsverfahren ausschließen.

Grundidee ist die Nachbildung eines Abkühlungsprozesses, wie er etwa beim Glühen in der Metallurgie stattfindet: Nach dem Erhitzen eines Metalls sorgt die langsame Abkühlung dafür, dass die Atome ausreichend Zeit haben, sich zu ordnen und stabile Kristalle zu bilden. Dadurch wird ein energiearmer Zustand nahe am Optimum erreicht. Übertragen auf das Optimierungsverfahren entspricht die Temperatur einer Wahrscheinlichkeit, mit der sich ein Zwischenergebnis der Optimierung auch verschlechtern darf. Wie viele andere Lokale-Suche-Algorithmen kann das Verfahren dadurch ein lokales Optimum wieder verlassen, um ein besseres zu finden. Vom Metropolis-Algorithmus in Monte-Carlo-Simulationen unterscheidet sich das Verfahren durch das Absenken der Temperatur im Verlauf der Iteration.

Der Algorithmus wird beispielsweise beim Floorplanning im Laufe eines Chipentwurfs oder für die Standort- und Routenplanung verwendet.

In den 1990er Jahren wurden Quantenversionen der simulierten Abkühlung (mit Tunnelung zwischen den Minima) eingeführt.

1. ↑ Raúl Rojas: Theorie der neuronalen Netze: eine systematische Einführung (= Springer-Lehrbuch). 4., korrigierter Nachdr Auflage. Springer, Berlin Heidelberg 1996, ISBN 978-3-540-56353-2. Fehler in Vorlage:Literatur – *** Parameterproblem: Dateiformat/Größe/Abruf nur bei externem Link
2. ↑ Bogatzki, A.: Fabrikplanung: Verfahren zur Optimierung von Maschinenaufstellung. Diss. Universität Wuppertal (1998). Roderer 1998. ISBN 978-3-89073-234-3
3. ↑ T. Kadowaki, H. Nishimori, Quantum annealing in the transverse Ising model, Phys. Rev. E, Band 58, 1998, S. 5355
4. ↑ A. B. Finilla, M. A. Gomez, C. Sebenik, J. D. Doll, Quantum annealing: A new method for minimizing multidimensional functions, Chem. Phys. Lett., Band 219, 1994, S. 343