Handbuch: 7.3.1. Simuliertes Annealing

Wenn eine Legierung von verschiedenen Metallen angefertigt wird, werden diese Metalle alle über den Schmelzpunkt erhitzt, durchmischt und dann wieder abgekühlt – alles nach einem sorgfältig getakteten Zeitplan. Erlaubt man dem System, sich allzu schnell abzukühlen oder waren die Metalle anfangs nicht ausreichend zusammengeschmolzen, so kann es sein, dass sich vereinzelte Schwachstellen im System herausbilden und die Legierung unbrauchbar wird, weil sie dann zu brüchig ist oder andere Mängel aufweist. Simuliertes Annealing ist ein Optimierungsalgorithmus, der auf demselben Prinzip basiert. Der Vorgang beginnt bei einem willkürlichen Punkt. Dann wird dieser verändert, und es ergibt sich ein benachbarter Punkt. Der neue Punkt wird mit dem alten Punkt verglichen. Stellt er sich als besser heraus, wird er beibehalten. Ist er schlechter, behalten wir ihn trotzdem bei, gemäß einer gewissen Wahrscheinlichkeit, die von einem "Temperatur"-Parameter abhängig ist. Bei sinkender Temperatur sinkt die Wahrscheinlichkeit, eine Veränderung zum Schlechteren zu akzeptieren, so dass schwierige, ansteigende Veränderungen immer seltener akzeptiert werden. Am Ende ist die Lösung so gut, dass weitere Verbesserung kaum noch möglich sind und auch Veränderungen zum Schlechten nur noch selten vorkommen bzw. akzeptiert werden, weil die Temperatur sehr niedrig ist, mit der Folge, dass die Methode konvergiert und so zum Abschluss kommt. Das genaue Ausbuchstabieren der Temperaturwerte und anderer Parameter nennen wir den Abkühlungsplan (cooling schedule). In der Literatur werden viele Abkühlungspläne vorgeschlagen, aber diese wirken sich nur auf Einzelheiten aus, nicht jedoch auf die Gesamtphilosophie der Methode.

Wir können dabei sogleich einige verlockende Eigenschaften erkennen: (1) Es müssen jeweils nur zwei Lösungen abgespeichert werden, (2) wir müssen jeweils nur diese beiden miteinander vergleichen, (3) wir können zeitweilige Verschlechterungen der Lösung in Kauf nehmen, (4) je mehr Zeit wir dem Algorithmus geben, umso besser wird die Lösung werden, und schließlich: (5) Diese Methode ist sehr allgemein und kann auf praktisch jedes Problem angewandt werden, weil sie vom eigentlichen Problem gar nichts verstehen muss. Der einzige Punkt, an dem das (zu lösende) Problem diese Methode betrifft, ist dort, wo der Punkt verschoben wird und beide Punkte miteinander verglichen werden.