Simulierte Abkühlung

Die simulierte Abkühlung (Englisch simulated annealing) ist ein heuristisches Optimierungsverfahren des Operations Research. Das Verfahren wird für Optimierungsprobleme eingesetzt, die durch ihre hohe Komplexität das vollständige Ausprobieren aller Möglichkeiten und einfache mathematische Verfahren ausschließen. Benutzt wird dieses Verfahren zum Beispiel beim Floorplanning im Laufe eines Chipentwurfs.

Grundidee ist die Nachbildung eines Abkühlungsprozesses, etwa beim Glühen in der Werkstoffkunde. Nach Erhitzen eines Metalls sorgt die langsame Abkühlung dafür, dass die Moleküle ausreichend Zeit haben, sich zu ordnen und stabile Kristalle zu bilden. Dadurch wird ein energiearmer Zustand, nahe am Optimum erreicht.

Übertragen auf das Optimierungsverfahren entspricht die Temperatur einer Akzeptanzschwelle unterhalb derer sich ein Zwischenergebnis der Optimierung auch verschlechtern darf. Der Metropolisalgorithmus ist die Grundlage der simulierten Abkühlung. Im Gegensatz zum Bergsteigeralgorithmus (hill climbing) kann das Verfahren ein lokales Optimum wieder verlassen und ein besseres finden.

Algorithmus

Problemstellung

Gegeben sei der Wertebereich $D$ und die Fitness-Funktion $f:D\rightarrow \mathbb {R}$ .

Gesucht ist ein globales Minimum von $f$ über $D$ , d.h. ein $x\in D$ für das gilt, $f(x)\leq f(y)$ für alle $y\in D$ .

Initialisierung

Wähle Temperatur $T$ und Kühlungskonstante $\alpha <1$ . Startzeit $t:=0$ .

Lokale Veränderung

Wähle einen Nachbarn $y\in D$ von $x$ .

Selection

Gilt $f(y)\leq f(x)$ , setze $x:=y$ .
Gilt $f(y)>f(x)\,$ , setze $x:=y$ mit Wahrscheinlichkeit $\exp \left(-{\frac {f\left(y\right)-f\left(x\right)}{\alpha ^{t}\cdot T}}\right)$ .

Abbruch oder Weiter

Ist die Abbruchbedingung nicht erfüllt, beginne im nächsten Zeittakt $t:=t+1$ wieder mit einer lokalen Veränderung.

Erläuterungen

Wie ein Nachbarn gewählt wird, hängt von dem vorliegenden Problem ab. In der Informatik ist häufig der Wertebereich $D=\{0,1\}^{n}$ und $x=(x_{1},x_{2},\ldots ,x_{n})$ wird als Bit–Vektor betrachtet. Ein Nachbar $y$ von $x$ kann z.B. durch das flippen (invertieren) eines oder mehrerer Bits gewählt werden (siehe Wegener 2005).

Es sind verschiedene Abbruchbedingungen denkbar. Zum Beispiel wird nur eine maximale Anzahl von Durchläufen erlaubt, eine ausreichende Fitness definiert oder eine Untergrenze für die Abkühlung festgelegt.

Siehe

Schwellenakzeptanz (threshold Accepting)

Deterministic Annealing

Sintflutalgorithmus

Weblinks

Literatur

Ingo Wegener: Simulated Annealing Beats Metropolis in Combinatorial Optimization. In: Lecture Notes in Computer Science. Band 3580. Springer, Berlin/Heidelberg 2005, ISBN 978-3-540-27580-0, S. 589–601 (doi:10.1007/11523468 – Für ein einfach zu beschreibendes Problem gezeigt wird, dass, unabhängig von der Temperatur, die simulierter Abkühlung effizienter ist als der Metropolisalgorithmus.).