Simulated Annealing: Der Optimierungsalgorithmus aus der Stahlbranche
Aus dem großen Zoo der Optimierungsalgorithmen hat mich seit dem Studium einer besonders interessiert: Simulated Annealing, auf Deutsch entspricht simuliertes Glühen der Bedeutung am ehesten. Dass der Algorithmus so spannend ist, hat zwei Gründe: Zunächst steckt er etwa hinter der Software, welche die Platzierung von Komponenten auf FPGAs und Chips optimiert und hat damit für mich praktische Relevanz. Der zweite Grund ist, dass seine Funktionsweise ziemlich mysteriös ist, wenn man den Algorithmus nur kurz, etwa in einer Vorlesung, streift.
Der Name sagt absolut nichts über die genaue Funktion, lediglich, dass sie dem sogenannten Glühen(öffnet im neuen Fenster) nachempfunden ist. So heißt ein Verfahren, mit dem durch Erhitzen und anschließendes langsames, kontrolliertes Abkühlen Spannungen und Kristallgitterdefekte in einem Material verringert werden. Durch das Erhitzen steigt die Beweglichkeit der Atome im Material, beim Optimierungsverfahren hingegen die Beweglichkeit im Lösungsraum. Was das bedeutet, wie es umgesetzt ist und warum das Glühen sowohl bei Metall als auch bei Optimierungsproblemen Erfahrung braucht, klären wir in diesem Artikel.