Simulated Annealing

aus Wikipedia, der freien Enzyklopädie
(Weitergeleitet von Simulated annealing)
Wechseln zu: Navigation, Suche

Simulated Annealing (simulierte Abkühlung) ist ein heuristisches Approximationsverfahren. Es wird zum Auffinden einer Näherungslösung von Optimierungsproblemen eingesetzt, die durch ihre hohe Komplexität das vollständige Ausprobieren aller Möglichkeiten und 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 und ein besseres finden. Es werden ungünstigere Zwischenlösungen akzeptiert, um ein besseres lokales Optimum zu erhalten.

Der Algorithmus wird beispielsweise beim Floorplanning im Laufe eines Chipentwurfs oder für die Standort- und Routenplanung verwendet.[1]

Motivation[Bearbeiten | Quelltext bearbeiten]

Der Algorithmus des Simulated Annealing ist anhand physikalischer Überlegungen motiviert.[2] 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 anzutreffen, gegeben durch die Wahrscheinlichkeitsverteilung

wobei die Boltzmann-Konstante und die Temperatur ist. Die Energie des energetisch günstigsten Zustandes sei . Die obige Proportionalität bleibt bestehen bei Multiplikation mit einem von unabhängigen Faktor:

Da der energetisch günstigste Zustand ist, gilt . Weiterhin ist und . Somit ist der Exponent negativ, und mit abnehmender Temperatur wird sein Betrag größer, wodurch die Wahrscheinlichkeit sinkt, einen angeregten Energiezustand mit mindestens 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[Bearbeiten | Quelltext bearbeiten]

Gegeben sei der Lösungsraum , eine Fitnessfunktion , die jeder Lösung in einen Wert zuweist, und ein Abbruchkriterium.

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

Außerdem wird ein Umgebungsbegriff (siehe Potenzmenge) benötigt, um zu gegebenem eine benachbarte Lösung zu erzeugen.

Algorithmus[Bearbeiten | Quelltext bearbeiten]

  1. Initialisierung: Wähle eine Startlösung und setze . Wähle eine streng monoton gegen Null fallende Folge von positiven Temperaturwerten () und eine Folge , deren Glieder angeben, wie viele Schritte eine Temperatur beibehalten wird. Setze und .
  2. lokale Veränderung: Wähle zu einen Nachbarn zufällig aus
  3. Selektion:
    • wenn , setze
    • anderenfalls setze nur mit Wahrscheinlichkeit .
  4. Bisher beste Lösung aktualisieren:
    • wenn , setze
  5. Inkrementiere:
    • wenn , setze
    • anderenfalls setze und
  6. Abbruch oder weiter: wenn die Abbruchbedingung nicht erfüllt ist, gehe zu Schritt 2.

Erläuterungen[Bearbeiten | Quelltext bearbeiten]

Die Wahrscheinlichkeit , dass ein schlechteres akzeptiert wird, ist wegen für geringere Verschlechterungen größer und, weil 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 und wird als Bit-Vektor betrachtet. Ein Nachbar von 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 von Zeitpunkten definiert, über die sich nicht mehr geändert hat.

Graphische Verdeutlichung[Bearbeiten | Quelltext bearbeiten]

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

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.

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[Bearbeiten | Quelltext bearbeiten]

Literatur[Bearbeiten | Quelltext bearbeiten]

  • 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[Bearbeiten | Quelltext bearbeiten]

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  1. Bogatzki, A.: Fabrikplanung: Verfahren zur Optimierung von Maschinenaufstellung. Diss. Universität Wuppertal (1998). Roderer 1998. ISBN 978-3-89073-234-3
  2. 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.
  3. Google TechTalk Vortrag Eine kurze, aber sehr verständliche Erklärung zum Thema findet man ab Minute 35.