Simulated Annealing

Simulated Annealing (simulierte/-s Abkühlung/Ausglühen) i​st ein heuristisches Approximationsverfahren. Es w​ird zum Auffinden e​iner Näherungslösung v​on Optimierungsproblemen eingesetzt, d​ie durch i​hre hohe Komplexität d​as vollständige Ausprobieren a​ller Möglichkeiten u​nd mathematische Optimierungsverfahren ausschließen.

Der Metropolisalgorithmus ist die Grundlage für das Verfahren der simulierten Abkühlung. Grundidee ist die Nachbildung eines Abkühlungsprozesses, etwa beim Glühen in der Metallurgie. Nach dem Erhitzen eines Metalls sorgt die langsame Abkühlung dafür, dass die Atome 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 Wahrscheinlichkeit, mit der sich ein Zwischenergebnis der Optimierung auch verschlechtern darf. Im Gegensatz zu einem Lokale-Suche-Algorithmus kann das Verfahren ein lokales Optimum wieder verlassen. Es werden ungünstigere Zwischenlösungen akzeptiert, weil dies die Chance bietet, ein besseres lokales Optimum zu finden.

Der Algorithmus w​ird beispielsweise b​eim Floorplanning i​m Laufe e​ines Chipentwurfs o​der für d​ie Standort- u​nd Routenplanung verwendet.[1]

Es g​ibt auch Quantenversionen v​on Annealing (mit Tunnelung zwischen d​en Minima), eingeführt i​n den 1990er Jahren.[2][3] Sie wurden i​n Hardware realisiert i​n adiabatischen Quantencomputern v​on D-Wave Systems.

Motivation

Der Algorithmus des Simulated Annealing ist durch physikalische Überlegungen motiviert.[4] Gesucht sei ein energetisch günstigster Zustand eines Systems, welches mithilfe der Boltzmann-Statistik beschrieben werden kann. Gemäß der Boltzmann-Statistik ist die Wahrscheinlichkeit, einen Mikrozustand mit Energie ${\displaystyle \geq E_{j}}$ anzutreffen, gegeben durch die Wahrscheinlichkeitsverteilung

${\displaystyle p(E_{j})\propto \exp \left(-{\frac {E_{j}}{k_{\mathrm {B} }T}}\right),}$

wobei ${\displaystyle k_{\mathrm {B} }}$ die Boltzmann-Konstante und ${\displaystyle T}$ die Temperatur ist. Die Energie des energetisch günstigsten Zustandes sei ${\displaystyle E_{0}}$. Die obige Proportionalität bleibt bestehen bei Multiplikation mit einem von ${\displaystyle E_{j}}$ unabhängigen Faktor:

${\displaystyle p(E_{j})\propto \exp \left(-{\frac {(E_{j}-E_{0})}{k_{\mathrm {B} }T}}\right)}$

Da ${\displaystyle E_{0}}$ der energetisch günstigste Zustand ist, gilt ${\displaystyle E_{j}-E_{0}\geq 0}$. Weiterhin ist ${\displaystyle k_{\mathrm {B} }>0}$ und ${\displaystyle T>0}$. Somit ist der Exponent negativ, und mit abnehmender Temperatur wird sein Betrag größer, wodurch die Wahrscheinlichkeit sinkt, einen angeregten Energiezustand mit mindestens ${\displaystyle E_{j}}$ zu finden. Senkt man somit die Temperatur des Systems langsam ab, so wird der energetisch günstigste Zustand mit immer größerer Wahrscheinlichkeit angetroffen.

Problemstellung

Gegeben sei der Lösungsraum ${\displaystyle D}$, eine Fitnessfunktion ${\displaystyle f\colon D\rightarrow \mathbb {R} }$, die jeder Lösung in ${\displaystyle D}$ einen Wert zuweist, und ein Abbruchkriterium.

Gesucht ist eine approximative Lösung des globalen Minimums von ${\displaystyle f}$ über ${\displaystyle D}$, also ein ${\displaystyle x\in D}$ mit möglichst kleinem Wert ${\displaystyle f(x)}$ (oder auch möglichst großem, was man durch Negieren von ${\displaystyle f}$ einfach auf den vorigen Fall zurückführen kann).

Außerdem wird ein Umgebungsbegriff ${\displaystyle U\colon D\rightarrow {\mathcal {P}}(D)}$ (siehe Potenzmenge) benötigt, um zu gegebenem ${\displaystyle x\in D}$ eine benachbarte Lösung ${\displaystyle y\in U(x)}$ zu erzeugen.

Algorithmus

1. Initialisierung:
   • wähle eine Startlösung ${\displaystyle x\in D}$
   • setze ${\displaystyle x_{\mathrm {approx} }=x}$
   • wähle eine monoton gegen Null fallende Folge von positiven Temperaturwerten ${\displaystyle (T_{t})_{t\in \mathbb {N} }}$
   • Setze ${\displaystyle t=0}$
2. lokale Veränderung:
   • wähle zu ${\displaystyle x}$ einen Nachbarn ${\displaystyle y\in U(x)}$ zufällig aus
3. Selektion:
   • wenn ${\displaystyle f(y)\leq f(x)}$, setze ${\displaystyle x=y}$
   • anderenfalls setze ${\displaystyle x=y}$ nur mit Wahrscheinlichkeit ${\displaystyle \exp \left(-{\frac {f\left(y\right)-f\left(x\right)}{T_{t}}}\right)}$.
4. Bisher beste Lösung aktualisieren:
   • wenn ${\displaystyle f(x)<f(x_{\text{approx}})}$, setze ${\displaystyle x_{\text{approx}}=x}$
5. Inkrementiere:
   • setze ${\displaystyle t=t+1}$
6. Abbruch oder weiter:
   • wenn die Abbruchbedingung nicht erfüllt ist, gehe zu Schritt 2.

Erläuterungen

Die Wahrscheinlichkeit ${\displaystyle \exp \left(-{\frac {f(y)-f(x)}{T_{t}}}\right)}$, dass ${\displaystyle x}$ durch ein schlechteres ${\displaystyle y}$ ersetzt wird, ist umso kleiner, je größer die Verschlechterung ${\displaystyle f(y)-f(x)}$ ist. Weil ${\displaystyle T_{t}}$ eine monoton fallende Folge ist, nimmt die Wahrscheinlichkeit außerdem während eines Programmlaufs immer mehr ab. Das Verfahren verhält sich mit abnehmendem ${\displaystyle T_{t}}$ mehr und mehr wie ein Bergsteigeralgorithmus.

Wie ein Nachbar ${\displaystyle y\in U(x)}$ gewählt werden sollte, hängt von dem vorliegenden Problem ab. In der Informatik ist häufig der Wertebereich ${\displaystyle D=\{0,1\}^{n}}$ und ${\displaystyle x=(x_{1},x_{2},\dotsc ,x_{n})}$ wird als Bit-Vektor betrachtet. Ein Nachbar ${\displaystyle y}$ von ${\displaystyle x}$ kann dann z. B. durch das Flippen (Invertieren) von einem oder von wenigen Bits erzeugt werden (siehe Wegener 2005).

Es sind verschiedene Abbruchbedingungen denkbar. Zum Beispiel wird nur eine maximale Anzahl von Durchläufen erlaubt, eine ausreichende Fitness definiert, eine Untergrenze für die Abkühlung festgelegt oder eine Anzahl ${\displaystyle t}$ von Zeitpunkten definiert, über die ${\displaystyle x_{\mathrm {approx} }}$ sich nicht mehr geändert hat.

Graphische Verdeutlichung

Graphische Darstellung einer Landschaft, in der ein globales Minimum gefunden werden soll.

Die Idee d​es simulierten Abkühlens k​ann man s​ich graphisch verdeutlichen.[5]

Angenommen, m​an sucht i​n einer zweidimensionalen Landschaft d​en (global) tiefsten Punkt. Die Landschaft selbst besteht a​us vielen unterschiedlich tiefen Dellen. Die einfache Suchstrategie (suche d​en nächsten tiefsten Punkt) entspricht d​em Verhalten e​iner Kugel, welche i​n dieser Landschaft ausgesetzt wird. Sie r​ollt zum nächsten lokalen Minimum u​nd bleibt dort. Bei d​er simulierten Abkühlung w​ird der Kugel i​mmer wieder e​in Stoß versetzt, d​er mit zunehmender „Abkühlung“ schwächer wird. Dieser i​st idealerweise s​tark genug, u​m die Kugel a​us einer flachen Delle (lokales Minimum) z​u entfernen, reicht a​ber nicht aus, u​m aus d​em globalen Minimum z​u fliehen.

Simulated Annealing bei der Suche nach einem Maximum. Die zahlreichen lokalen Maxima werden durch die bei noch hoher „Temperatur“ starke Rausch-Bewegung der Temperatursimulation schnell wieder verlassen. Das globale Maximum wird aber zuverlässig gefunden, da der fallende „Temperatur“-Wert zum Ende nicht mehr ausreicht, es zu verlassen. Das erbringt bessere Resultate als ein einfacher Bergsteigeralgorithmus.

Siehe auch

• Schwellenakzeptanz (threshold accepting)
• Deterministic Annealing
• Stochastisches Tunneln
• Sintflutalgorithmus
• Metropolisalgorithmus

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 wird gezeigt, dass unabhängig von der Temperatur die simulierte Abkühlung effizienter ist als der Metropolisalgorithmus.).

Weblinks

• Interaktives JavaScript zur Demonstration (Memento vom 13. März 2015 im Internet Archive)
• Interaktive Demonstration zum Ausprobieren
• C#-Implementierung und Anwendung zur Minimierung und auf das Problem des Handelsreisenden
• Simulated Annealing in C++ Optimierungs-Bibliothek cppOpt cppOpt bzw. OptSimulatedAnnealing.h

Einzelnachweise

1. Bogatzki, A.: Fabrikplanung: Verfahren zur Optimierung von Maschinenaufstellung. Diss. Universität Wuppertal (1998). Roderer 1998. ISBN 978-3-89073-234-3
2. T. Kadowaki, H. Nishimori, Quantum annealing in the transverse Ising model, Phys. Rev. E, Band 58, 1998, S. 5355
3. A. B. Finilla, M. A. Gomez, C. Sebenik, J. D. Doll, Quantum annealing: A new method for minimizing multidimensional functions, Chem. Phys. Lett., Band 219, 1994, S. 343
4. JP Dr. A. Arnold, Universität Stuttgart, Institut für Computerphysik, Skript zur Vorlesung Physik auf dem Computer (PDF; 3,3 MB) S. 181 ff.
5. Google TechTalk Vortrag Eine kurze, aber sehr verständliche Erklärung zum Thema findet man ab Minute 35.