Simulated Annealing

Allgemein

Die Heuristik Simulated Annealing ist eine Lokale Lösungsraumsuche, die auf der Idee der Abkühlung einer physischen Materie (statistische Thermodynamik) basiert.

Der Vorteil, den Simulated Annealing gegenüber eine normalen Lokalen Suche hat, ist, dass Simulated Annealing mit einer bestimmten Wahrscheinlichkeit eine schlechtere Lösung akzeptiert und somit lokale Optima überwindet um das global Optimum zu finden.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Idee

Ein anfänglich zufälliger Gang durch den Lösungsraum ändert sich allmählich zu einer Verbesserungsmethode, wenn es „kälter wird“.

Ablauf

Ziel: Die Optimierung der Zielfunktion F

1. Setzte Start- (Ts) und Zieltemperatur(Te) sowie die Abkühlungsfunktion C(x). Die aktuelle Temperatur T ist zunächst gleich der Starttemperatur (T = Ts).
2. Generiere eine zufällige Startlösung Si
3. Erzeuge mit Hilfe einer Nachbarschaftsrelation eine neue zufällige Lösung Si‘
4. Wenn die neue Lösung Si‘ besser ist als die alte Lösung Si, dann ersetzte Si mit Si‘ (Si = Si‘)
5. Wenn die neue Lösung Si‘ schlechter oder gleich gut mit der alten Lösung Si, dann berechne die Wahrscheinlichkeit p=e^(-( ΔE/t)) mit ΔE=F(Si‘)-F(Si)
6. Ist p größer als eine Zufallszahl R, welche im Bereich zwischen 0 und 1 liegt, dann ersetzt Si mit Si‘ (Si = Si‘) ansonsten verwerfe Si‘
7. Kühle Temperatur T ab. T=C(T)
8. Ist T höher als die Zieltemperatur Te, dann gehe zurück zu Schritt 3.
9. Sobald die Zieltemperatur erreicht ist, stoppt der Algorithmus und gibt Si als Lösung zurück.

Beispiel

Gegeben sein ein Transportproblem, mit der Zielfunktion F, welche die gefahrene Distanz bestimmt. Ziel ist es die Distanz, also F, zu minimieren.

Ts = 10, Te=0, C(x)=x-2 und T=Ts=10

Generiere zufällige Startlösung Si mit F(Si)= 200

T=10

Generiere neue Lösung Si‘ mit F(Si‘)=180

F(Si‘)<F(Si) (180<200) , also ersetzte Si (Si=Si‘)

Kühle ab. T=C(T)=10-2=8

Überprüfe, ob Zieltemperatur erreicht ist (8>0), also weiter.

T=8

Generiere neue Lösung Si‘ mit F(Si‘)=185

F(Si‘)>F(Si) (185>180), also berechne ΔE=185-180=5 und p=e^(-5/8)=0,53

Erzeuge zufällige Zahl R = 0,5

p>R (0.53>0,5), also ersetzte Si (Si=Si‘)

Kühle ab. T=8-2=6 >0 , also weiter

T=6

Generiere neue Lösung Si‘ mit F(Si‘)=170

F(Si‘)<F(Si) (170<185) , also ersetzte Si (Si=Si‘)

Kühle ab. T=C(T)=6-2=4 >0, also weiter.

T=4

Generiere neue Lösung Si‘ mit F(Si‘)=178

F(Si‘)>F(Si) (178>170), also berechne ΔE=178-170=8 und p=e^(-8/4)=0,14

Erzeuge zufällige Zahl R = 0,6

p<R (0.14<0,6), also verwerfe Si‘

Kühle ab. T=4-2=2 >0 , also weiter

T=2

Generiere neue Lösung Si‘ mit F(Si‘)=165

F(Si‘)<F(Si) (165<170) , also ersetzte Si (Si=Si‘)

Kühle ab. T=C(T)=2-2=0

Zieltemperatur ist erreicht. Also stoppt der Algorithmus und als Ergebnis erhalten wir die Lösung Si mit einer Distanz von 165.