Simulated Annealing ist eine Metaheuristik (ein generisches Optimierungsverfahren) zur näherungsweisen Lösung komplexer Optimierungsprobleme. Ausgehend von einer beliebigen Lösung als anfängliche aktuelle Lösung werden in einem iterativen Suchprozess zufallsbasiert modifizierte Lösungskandidaten erzeugt und mit einer abnehmenden Wahrscheinlichkeit gegebenenfalls auch bei Zielfunktionswertverschlechterungen als neue aktuelle Lösung akzeptiert.
Grundkonzept
Metaheuristiken basieren auf einer Modellierung von Optimierungsproblemen durch Lösungsräume, die alle denkbaren Lösungen für die betrachtete Problemstellung umfassen. Es ist eine möglichst gute zulässige Lösung zu ermitteln, wobei Lösungen durch eine zu optimierende Zielfunktion bewertet werden.
Die Metaheuristik Simulated Annealing wurde in Anlehnung an die Abkühlung geschmolzener Metalle zu Feststoffen konzipiert. Bei einer ausreichend langsamen Abkühlung tendieren Metallstrukturen zu einem Gleichgewicht mit minimaler Energie. Die im Verlauf des thermodynamischen Prozesses zugeführte Energie ermöglicht ein Ausbrechen aus energetisch ungünstigen Strukturen. Für diskrete Optimierungsprobleme entsprechen den Stoffzuständen Lösungen aus dem Lösungsraum, den Energieinhalten Zielfunktionswerte und ein Temperaturparameterwert beeinflusst die Wahrscheinlichkeit für das Akzeptieren von Verschlechterungen [Cerny 1985, Kirkpatrick, Gelatt Jr., Vecchi 1983].
Ausgehend von einer Startlösung werden in einem iterativen Suchprozess durch zufallsbasierte Modifikationen der aktuellen Lösung Lösungskandidaten erzeugt. Lösungskandidaten werden bei einer Zielfunktionswertverbesserung immer bzw. teilweise auch bei einer Zielfunktionswertverschlechterung (gemäß einem probabilistischen Akzeptanzkriterium) als neue aktuelle Lösung akzeptiert, wodurch lokale Optima überwunden werden können. Die entsprechende Wahrscheinlichkeit berechnet sich durch eine Exponentialfunktion mit der negativen Zielfunktionswertverschlechterung dividiert durch einen Temperaturparameterwert als Exponenten. Diese Wahrscheinlichkeit sinkt mit dem Ausmaß der Zielfunktionswertverschlechterung sowie im Allgemeinen im Verfahrensablauf (bei einem sukzessiv abgesenkten Temperaturparameterwert).
Die Ausgestaltung von Simulated Annealing umfasst neben der problemspezifischen Lösungsraumstruktur insbesondere die Festlegung und Anpassung des Temperaturparameterwerts. Häufig wird ein geometrisches Abkühlungsschema verwendet, bei dem der Temperaturparameterwert im Verfahrensablauf regelmäßig mit einer Zahl kleiner Eins multipliziert wird. Dabei ist auch der initiale Temperaturwert und der Abbruch des Verfahrens festzulegen (beispielsweise gemäß [Johnson et al. 1989]).
Literatur
Cerny, V.: Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm. Journal of Optimization Theory and Applications 45 (1985), S. 41-51.
Johnson, D.S.; Aragon, C.R.; McGeoch, L.A.; Schevon, C.: Optimization by simulated annealing: An experimental evaluation; part i, graph partitioning. In: Operations Research 37 (1989), S. 865-892.
Kirkpatrick, S.; Gelatt Jr., C.D.;Vecchi, M.P.: Optimization by simulated annealing. In: Science 220 (1983), S. 671-680
