Simulated Annealing

Dieses Verfahren ist ebenfalls an ein natürliches Phänomen angelehnt: der Abkühlung eines erhitzten Stoffes. Von einem zufällig gewählten Punkt im Suchraum aus wird ein mehr oder weniger zufällig gewählter nächster Punkt evaluiert. Der Suchfokus wird unter 2 Bedingungen auf diesen neuen Punkt gerichtet:

• immer wenn der neue Punkt besser ist als der alte oder
• mit der Wahrscheinlichkeit $p(t)$, wenn der neue Punkt schlechter ist als der alte.

Die Funktion $p(t)$ ist hierbei eine von der Zeit $t$ abhängige Funktion, welche für t=0 nahe 1 beginnt und für wachsende t gegen 0 strebt. Diese monoton fallende Funktion simuliert somit den Abkühlungsprozess, bei dem im heissen Zustand Atome große Sprünge oder Drehungen vollziehen und bei der Abkühlung diese Sprünge und Drehungen nur noch erfolgen, wenn dadurch die Energie eines Systems verringert wird.

Simulated Annealing stellt in gewissem Sinne einen modifizierten Hillclimber dar, dem eine Zufallsakzeptanz für schlechtere Punkte eingebaut ist, um aus lokalen Optima wieder herauszufinden. Die Methoden zur Überführung des anfangs rein explorativen Verfahrens in ein exploitatives und das richtige Mischungsverhältnis ist immer noch Gegenstand zahlreicher Untersuchungen [9].