Simulated Annealing - LinkFang.de





Simulated Annealing


Simulated Annealing (simulierte Abkühlung) ist ein heuristisches Optimierungsverfahren. Das Verfahren wird zum Auffinden einer approximativen Lösung von Optimierungsproblemen 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 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. Der Metropolisalgorithmus ist die Grundlage der simulierten Abkühlung. Im Gegensatz zu einem Lokale-Suche-Algorithmus kann das Verfahren ein lokales Optimum wieder verlassen und ein besseres finden.

Motivation

Der Algorithmus des Simulated Annealing kann leicht anhand physikalischer Überlegungen motiviert werden.[1] 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 [math]E_j[/math] anzutreffen, gegeben durch die Wahrscheinlichkeitsverteilung

[math]p(E_j) \propto \exp \left( -\frac{E_j}{k_B T} \right),[/math]

wobei [math]k_B[/math] die Boltzmann-Konstante und [math]T[/math] die Temperatur ist. Die Energie des energetisch günstigsten Zustandes sei [math]E_0[/math], also kann man folgende Gleichung aufstellen:

[math]p(E_j) \propto \exp \left(- \frac{E_j}{k_B T} \right) \cdot \underbrace{\exp \left(-\frac{1}{k_B T}(E_0-E_0) \right)}_{=1} \propto \exp \left(- \frac{(E_j-E_0)}{k_B T} \right) [/math]

Da [math]E_0[/math] der energetisch günstigste Zustand ist, gilt [math]E_j-E_0\gt0[/math]. Da [math]k_B\gt0[/math] und [math]T\ge 0[/math], gilt somit, dass für kleiner werdende Temperaturen der absolute Betrag des Exponent größer wird. Unter Berücksichtigung des negativen Vorzeichens des Exponenten sinkt daher die Wahrscheinlichkeit für kleinere Temperaturen einen angeregten Energiezustand [math]E_j[/math] zu finden. Senkt man somit die Temperatur des Systems langsam ab, so wird der energetisch günstigste Zustand mit immer größerer Wahrscheinlichkeit angetroffen.

Algorithmus

Problemstellung

Gegeben sei der Wertebereich [math]D[/math], eine Fitness-Funktion [math]f \colon D \rightarrow \mathbb{R}[/math], ein Umgebungsbegriff [math]U(x)[/math] und ein Abbruchkriterium.

Gesucht ist eine approximative Lösung des globalen Minimums von [math]f[/math] über [math]D[/math].

Initialisierung

Wähle eine Startlösung [math]x \in D[/math]. Wähle eine monoton gegen Null fallende Temperaturfolge [math]T_t, t \in \N[/math] und eine Folge [math]N_i, i \in \N[/math], die angibt, wie viele Schritte eine Temperatur [math]T_t[/math] beibehalten wird. Startzeiten [math]t = 0[/math] und [math]i = 1[/math].

Lokale Veränderung

Falls [math]i \le N_t[/math]: Wähle einen Nachbarn [math]y \in D[/math] aus der Umgebung [math]U(x)[/math], sonst setze [math]i=1[/math] und [math]t=t+1[/math] und suche wieder einen Nachbarn.

Selektion

  • Gilt [math]f(y) \le f(x)[/math], setze [math]x = y[/math] und, falls [math]f(y) \le f(x_\text{approx})[/math], setze [math]x_\text{approx}=y[/math]
  • Gilt [math]f(y) \gt f(x)\,[/math], setze [math]x = y[/math] nur mit Wahrscheinlichkeit [math]\exp \left( -\frac{f \left( y \right) - f \left( x \right)}{T_t} \right)[/math].

Abbruch oder weiter

Wurde das [math]x[/math] nicht durch [math]y[/math] ersetzt, setze [math]i=i+1[/math] und beginne wieder mit einer lokalen Veränderung.

Sonst, falls die Abbruchbedingung zudem nicht erfüllt und damit die approximative Lösung [math]x_\text{approx}[/math] gefunden ist, beginne im nächsten Zeittakt [math]t = t + 1[/math] wieder mit einer lokalen Veränderung und setze [math]i = 1[/math].

Erläuterungen

Die Wahrscheinlichkeit [math]\exp \left( -\frac{f (y) - f (x)}{T_t} \right)[/math], dass ein schlechteres [math]y[/math] akzeptiert wird, ist wegen [math]f (y) - f(x)[/math] für geringere Verschlechterungen größer und, weil [math]T_t[/math] eine monoton fallende Folge ist, am Anfang des Verfahrens ebenfalls wahrscheinlicher.

Wie ein Nachbar gewählt werden sollte, hängt von dem vorliegenden Problem ab. In der Informatik ist häufig der Wertebereich [math]D = \{0,1\}^n[/math] und [math]x = (x_1, x_2, \dotsc, x_n)[/math] wird als Bit-Vektor betrachtet. Ein Nachbar [math]y[/math] von [math]x[/math] 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, eine Untergrenze für die Abkühlung festgelegt oder eine Anzahl [math]t[/math] von Zeitpunkten definiert, über die [math]x[/math] sich nicht mehr geändert hat.

Der Algorithmus wird beispielsweise für die Standort- und Routenplanung verwendet. Hier werden ungünstigere Zwischenlösungen akzeptiert, um ein besseres lokales Optimum zu erhalten.[2]

Graphische Verdeutlichung

Die Idee des simulierten Abkühlens kann man sich graphisch verdeutlichen. [3]

Angenommen, man sucht in einer zweidimensionalen Landschaft den (global) tiefsten Punkt. Die Landschaft selbst besteht aus vielen unterschiedlich tiefen Dellen. Die einfache Suchstrategie (suche den nächsten tiefsten Punkt) entspricht dem Verhalten einer Kugel, welche in dieser Landschaft ausgesetzt wird. Sie rollt zum nächsten lokalen Minimum und bleibt dort. Bei der simulierten Abkühlung wird der Kugel immer wieder ein Stoß versetzt, der mit zunehmender „Abkühlung“ schwächer wird. Dieser ist idealerweise stark genug, um die Kugel aus einer flachen Delle (lokales Minimum) zu entfernen, reicht aber nicht aus, um aus dem globalen Minimum zu fliehen.

Einzelnachweise

  1. JP Dr. A. Arnold, Universität Stuttgart, Institut für Computerphysik, Skript zur Vorlesung Physik auf dem Computer (PDF; 3,5 MB) S. 181 ff.
  2. Bogatzki, A.: Fabrikplanung: Verfahren zur Optimierung von Maschinenaufstellung. Diss. Universität Wuppertal (1998). Roderer 1998. ISBN 978-3-89073-234-3
  3. Google TechTalk Vortrag Eine kurze, aber sehr verständliche Erklärung zum Thema findet man ab Minute 35.

Siehe auch

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

Kategorien: Keine Kategorien vorhanden!

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Simulated Annealing (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.