Simulierte Abkühlung

Die simulierte Abkühlung ({{#invoke:Vorlage:lang|full|CODE=en|SCRIPTING=Latn|SERVICE=englisch}}, auch simuliertes Tempern oder simulierte Vergütung<ref>{{#invoke:Vorlage:Literatur|f}}</ref> genannt) ist ein heuristisches Approximationsverfahren. Sie 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.

Grundidee ist die Nachbildung eines Abkühlungsprozesses, wie er etwa beim Glühen in der Metallurgie stattfindet: 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. Wie viele andere Lokale-Suche-Algorithmen kann das Verfahren dadurch ein lokales Optimum wieder verlassen, um ein besseres zu finden. Vom Metropolis-Algorithmus in Monte-Carlo-Simulationen unterscheidet sich das Verfahren durch das Absenken der Temperatur im Verlauf der Iteration.

Der Algorithmus wird beispielsweise beim Floorplanning im Laufe eines Chipentwurfs oder für die Standort- und Routenplanung verwendet.<ref>Bogatzki, A.: Fabrikplanung: Verfahren zur Optimierung von Maschinenaufstellung. Diss. Universität Wuppertal (1998). Roderer 1998. ISBN 978-3-89073-234-3</ref>

In den 1990er Jahren wurden Quantenversionen der simulierten Abkühlung (mit Tunnelung zwischen den Minima) eingeführt.<ref>T. Kadowaki, H. Nishimori, Quantum annealing in the transverse Ising model, Phys. Rev. E, Band 58, 1998, S. 5355</ref><ref>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</ref>

Motivation

Der Algorithmus der simulierten Abkühlung ist durch physikalische Überlegungen motiviert.<ref>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.</ref> 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>\ge E_j</math> anzutreffen, gegeben durch die Wahrscheinlichkeitsverteilung

<math>p(E_j) \propto \exp \left( -\frac{E_j}{k_\mathrm B T} \right),</math>

wobei <math>k_\mathrm B</math> die Boltzmann-Konstante und <math>T</math> die Temperatur ist. Die Energie des energetisch günstigsten Zustandes sei <math>E_0</math>. Die obige Proportionalität bleibt bestehen bei Multiplikation mit einem von <math>E_j</math> unabhängigen Faktor:

<math>p(E_j) \propto \exp \left(- \frac{(E_j-E_0)}{k_\mathrm B T} \right) </math>

Da <math>E_0</math> der energetisch günstigste Zustand ist, gilt <math>E_j-E_0 \ge 0</math>. Weiterhin ist <math>k_\mathrm B>0</math> und <math>T > 0</math>. Somit ist der Exponent negativ, und mit abnehmender Temperatur wird sein Betrag größer, wodurch die Wahrscheinlichkeit sinkt, einen angeregten Energiezustand mit mindestens <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.

Problemstellung

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

Gesucht ist eine approximative Lösung des globalen Minimums von <math>f</math> über <math>D</math>, also ein <math>x \in D</math> mit möglichst kleinem Wert <math>f(x)</math>. Sollte ein <math>x</math> mit möglichst großem Wert gesucht sein (Maximierungsproblem), kann man dies durch Negieren von <math>f</math> einfach auf den vorigen Fall zurückführen.

Außerdem wird ein Umgebungsbegriff <math>U \colon D \rightarrow \mathcal P(D)</math> benötigt (wobei <math>\mathcal P(D)</math> die Potenzmenge von <math>D</math> bezeichnet), um zu gegebenem <math>x \in D</math> eine benachbarte Lösung <math>y \in U(x)</math> zu erzeugen.

Algorithmus

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

Erläuterungen

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

Wie ein Nachbar <math>y \in U(x)</math> 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 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 <math>t</math> von Zeitpunkten definiert, über die <math>x_\mathrm{approx}</math> sich nicht mehr geändert hat.

Graphische Verdeutlichung

Datei:SimAnnealingLandschaft.png

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

Die Idee des simulierten Abkühlens kann man sich graphisch verdeutlichen.<ref>Google TechTalk Vortrag Eine kurze, aber sehr verständliche Erklärung zum Thema findet man ab Minute 35.</ref>

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.

Datei:Hill Climbing with Simulated Annealing.gif

Simulierte Abkühlung 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

{{#invoke:Vorlage:Literatur|f}}

Weblinks

<templatestyles src="Webarchiv/styles.css" />{{#if:20150313202204

      | {{#ifeq: 20150313202204 | *
    | Vorlage:Webarchiv/Wartung/Stern{{#if: Interaktives JavaScript zur Demonstration | {{#invoke:WLink|getEscapedTitle|Interaktives JavaScript zur Demonstration}} | {{#invoke:Webarchiv|getdomain|http://www.heatonresearch.com/fun/tsp/anneal}} }} (Archivversionen)
    | {{#iferror: {{#time: j. F Y|20150313202204}}
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/DatumDer Wert des Parameters {{#if: wayback | wayback | Datum }} muss ein gültiger Zeitstempel der Form YYYYMMDDHHMMSS sein!
         | {{#if: Interaktives JavaScript zur Demonstration | {{#invoke:WLink|getEscapedTitle|Interaktives JavaScript zur Demonstration}} | {{#invoke:Webarchiv|getdomain|http://www.heatonresearch.com/fun/tsp/anneal}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer }} vom {{#time: j. F Y|20150313202204}} im Internet Archive{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
      }}
  }}
      | {{#if:
          | {{#iferror: {{#time: j. F Y|{{{webciteID}}}}}
    | {{#switch: {{#invoke:Str|len|{{{webciteID}}}}}
       | 16= {{#if: Interaktives JavaScript zur Demonstration | {{#invoke:WLink|getEscapedTitle|Interaktives JavaScript zur Demonstration}} | {{#invoke:Webarchiv|getdomain|http://www.heatonresearch.com/fun/tsp/anneal}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer }} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{{webciteID}}}|1|10}}/86400}} }} days}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
       | 9 = {{#if: Interaktives JavaScript zur Demonstration | {{#invoke:WLink|getEscapedTitle|Interaktives JavaScript zur Demonstration}} | {{#invoke:Webarchiv|getdomain|http://www.heatonresearch.com/fun/tsp/anneal}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer}} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{#invoke:Expr|base62|{{{webciteID}}}}}|1|10}}/86400}} }} days}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
       | #default= Der Wert des Parameters {{#if: webciteID | webciteID | ID }} muss entweder ein Zeitstempel der Form YYYYMMDDHHMMSS oder ein Schüsselwert mit 9 Zeichen oder eine 16-stellige Zahl sein!Vorlage:Webarchiv/Wartung/webcitation{{#if:  || }}
      }}
    | c|{{{webciteID}}}}} {{#if: Interaktives JavaScript zur Demonstration | {{#invoke:WLink|getEscapedTitle|Interaktives JavaScript zur Demonstration}} | {{#invoke:Webarchiv|getdomain|http://www.heatonresearch.com/fun/tsp/anneal}} }} (Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer}} vom {{#time: j. F Y|{{{webciteID}}}}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
  }}
          | {{#if: 
              | Vorlage:Webarchiv/Today
              | {{#if:
                      | Vorlage:Webarchiv/Generisch
                      | {{#if: Interaktives JavaScript zur Demonstration | {{#invoke:WLink|getEscapedTitle|Interaktives JavaScript zur Demonstration}} | {{#invoke:Webarchiv|getdomain|http://www.heatonresearch.com/fun/tsp/anneal}} }}  
                 }}}}}}}}{{#if:
    | Vorlage:Webarchiv/archiv-bot
  }}{{#invoke:TemplatePar|check
     |all      = url=
     |opt      = text= wayback= webciteID= archive-is= archive-today= archiv-url= archiv-datum= ()= archiv-bot= format= original=
     |cat      = Wikipedia:Vorlagenfehler/Vorlage:Webarchiv
     |errNS    = 0
     |template = Vorlage:Webarchiv
     |format   = *
     |preview  = 1
  }}{{#ifexpr: {{#if:20150313202204|1|0}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}} <> 1
    | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Genau einer der Parameter 'wayback', 'webciteID', 'archive-today', 'archive-is' oder 'archiv-url' muss angegeben werden.|1}}
  }}{{#if: 
    | {{#switch: {{#invoke:Webarchiv|getdomain|{{{archiv-url}}}}}
        | web.archive.org = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von Internet Archive erkannt, bitte Parameter 'wayback' benutzen.|1}} 
        | webcitation.org = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von WebCite erkannt, bitte Parameter 'webciteID' benutzen.|1}} 
        | archive.today |archive.is |archive.ph |archive.fo |archive.li |archive.md |archive.vn = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von archive.today erkannt, bitte Parameter 'archive-today' benutzen.|1}}
      }}{{#if: 
         | {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|Vorlage:FormatDate/Wartung/Error}}
             | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Wert des Parameter 'archiv-datum' ist ungültig oder hat ein ungültiges Format.|1}}
          |  }} 
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Pflichtparameter 'archiv-datum' wurde nicht angegeben.|1}}
      }}
    | {{#if: 
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Parameter 'archiv-datum' ist nur in Verbindung mit 'archiv-url' angebbar.|1}}
      }}
  }}{{#if:{{#invoke:URLutil|isHostPathResource|http://www.heatonresearch.com/fun/tsp/anneal}}
    || {{#if:  || }} URL/Pfad ungültig.
  }}{{#if: Interaktives JavaScript zur Demonstration
    | {{#if: {{#invoke:WLink|isBracketedLink|Interaktives JavaScript zur Demonstration}}
        | {{#if:  || }} Linktext ungültig.
      }}
    | {{#if:  || }}Vorlage:Webarchiv/Wartung/Linktext_fehlt Linktext fehlt.
  }}{{#switch: 
    |addlarchives|addlpages= {{#if:  || }}{{#if: 1 |Vorlage:Webarchiv/Wartung/Parameter}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: enWP-Wert im Parameter 'format'.|1}}
  }}{{#ifeq: {{#invoke:Str|find|http://www.heatonresearch.com/fun/tsp/anneal%7Carchiv}} |-1
    || {{#ifeq: {{#invoke:Str|find|{{#invoke:Str|cropleft|http://www.heatonresearch.com/fun/tsp/anneal%7C4}}%7Chttp}} |-1
         || {{#switch: {{#invoke:Webarchiv|getdomain|http://www.heatonresearch.com/fun/tsp/anneal }}
              | abendblatt.de | daserste.ndr.de | inarchive.com | webcitation.org = 
              | #default = {{#if:  || }}{{#if: 1 |Vorlage:Webarchiv/Wartung/URL}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Archiv-URL im Parameter 'url' anstatt URL der Originalquelle. Entferne den vor der Original-URL stehenden Mementobestandteil und setze den Archivierungszeitstempel in den Parameter 'wayback', 'webciteID', 'archive.today' oder 'archive-is' ein, sofern nicht bereits befüllt.|1}}
            }} 
       }}
  }}

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