www.wikidata.de-de.nina.az

Simulated Annealing simulierte s Abkühlung Ausglühen ist ein heuristisches Approximationsverfahren Es wird zum Auffinden

Simulated Annealing

Simulated Annealing (simulierte/-s Abkühlung/Ausglühen) 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.

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. Wie viele andere Lokale-Suche-Algorithmen kann das Verfahren dadurch ein lokales Optimum wieder verlassen, um ein besseres zu finden. Vom Metropolis-Algorithmus 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.

Es gibt auch Quantenversionen von Annealing (mit Tunnelung zwischen den Minima), eingeführt in den 1990er Jahren.

Motivation Bearbeiten

Der Algorithmus des Simulated Annealing ist durch physikalische Überlegungen motiviert. 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

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

  1. Initialisierung:
    • wähle eine Startlösung
    • setze
    • wähle eine monoton gegen Null fallende Folge von positiven Temperaturwerten
    • Setze
  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:
    • setze
  6. Abbruch oder weiter:
    • wenn die Abbruchbedingung nicht erfüllt ist, gehe zu Schritt 2.

Erläuterungen Bearbeiten

Die Wahrscheinlichkeit , dass durch ein schlechteres ersetzt wird, ist umso kleiner, je größer die Verschlechterung ist. Weil eine monoton fallende Folge ist, nimmt die Wahrscheinlichkeit außerdem während eines Programmlaufs immer mehr ab. Das Verfahren verhält sich mit abnehmendem mehr und mehr wie ein Bergsteigeralgorithmus.

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 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 von Zeitpunkten definiert, über die sich nicht mehr geändert hat.

Graphische Verdeutlichung Bearbeiten

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

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

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

Literatur 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

Einzelnachweise Bearbeiten

  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.
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Simulated Annealing simulierte s Abkuhlung Ausgluhen ist ein heuristisches Approximationsverfahren Es wird zum Auffinden einer Naherungslosung von Optimierungsproblemen eingesetzt die durch ihre hohe Komplexitat das vollstandige Ausprobieren aller Moglichkeiten und mathematische Optimierungsverfahren ausschliessen Grundidee ist die Nachbildung eines Abkuhlungsprozesses etwa beim Gluhen in der Metallurgie Nach dem Erhitzen eines Metalls sorgt die langsame Abkuhlung dafur dass die Atome ausreichend Zeit haben sich zu ordnen und stabile Kristalle zu bilden Dadurch wird ein energiearmer Zustand nahe am Optimum erreicht Ubertragen 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 unterscheidet sich das Verfahren durch das Absenken der Temperatur im Verlauf der Iteration Der Algorithmus wird beispielsweise beim Floorplanning im Laufe eines Chipentwurfs oder fur die Standort und Routenplanung verwendet 1 Es gibt auch Quantenversionen von Annealing mit Tunnelung zwischen den Minima eingefuhrt in den 1990er Jahren 2 3 Inhaltsverzeichnis 1 Motivation 2 Problemstellung 3 Algorithmus 3 1 Erlauterungen 3 2 Graphische Verdeutlichung 4 Siehe auch 5 Literatur 6 Weblinks 7 EinzelnachweiseMotivation BearbeitenDer Algorithmus des Simulated Annealing ist durch physikalische Uberlegungen motiviert 4 Gesucht sei ein energetisch gunstigster Zustand eines Systems welches mithilfe der Boltzmann Statistik beschrieben werden kann Gemass der Boltzmann Statistik ist die Wahrscheinlichkeit einen Mikrozustand mit Energie E j displaystyle geq E j nbsp anzutreffen gegeben durch die Wahrscheinlichkeitsverteilung p E j exp E j k B T displaystyle p E j propto exp left frac E j k mathrm B T right nbsp wobei k B displaystyle k mathrm B nbsp die Boltzmann Konstante und T displaystyle T nbsp die Temperatur ist Die Energie des energetisch gunstigsten Zustandes sei E 0 displaystyle E 0 nbsp Die obige Proportionalitat bleibt bestehen bei Multiplikation mit einem von E j displaystyle E j nbsp unabhangigen Faktor p E j exp E j E 0 k B T displaystyle p E j propto exp left frac E j E 0 k mathrm B T right nbsp Da E 0 displaystyle E 0 nbsp der energetisch gunstigste Zustand ist gilt E j E 0 0 displaystyle E j E 0 geq 0 nbsp Weiterhin ist k B gt 0 displaystyle k mathrm B gt 0 nbsp und T gt 0 displaystyle T gt 0 nbsp Somit ist der Exponent negativ und mit abnehmender Temperatur wird sein Betrag grosser wodurch die Wahrscheinlichkeit sinkt einen angeregten Energiezustand mit mindestens E j displaystyle E j nbsp zu finden Senkt man somit die Temperatur des Systems langsam ab so wird der energetisch gunstigste Zustand mit immer grosserer Wahrscheinlichkeit angetroffen Problemstellung BearbeitenGegeben sei der Losungsraum D displaystyle D nbsp eine Fitnessfunktion f D R displaystyle f colon D rightarrow mathbb R nbsp die jeder Losung in D displaystyle D nbsp einen Wert zuweist und ein Abbruchkriterium Gesucht ist eine approximative Losung des globalen Minimums von f displaystyle f nbsp uber D displaystyle D nbsp also ein x D displaystyle x in D nbsp mit moglichst kleinem Wert f x displaystyle f x nbsp oder auch moglichst grossem was man durch Negieren von f displaystyle f nbsp einfach auf den vorigen Fall zuruckfuhren kann Ausserdem wird ein Umgebungsbegriff U D P D displaystyle U colon D rightarrow mathcal P D nbsp siehe Potenzmenge benotigt um zu gegebenem x D displaystyle x in D nbsp eine benachbarte Losung y U x displaystyle y in U x nbsp zu erzeugen Algorithmus BearbeitenInitialisierung wahle eine Startlosung x D displaystyle x in D nbsp setze x a p p r o x x displaystyle x mathrm approx x nbsp wahle eine monoton gegen Null fallende Folge von positiven Temperaturwerten T t t N displaystyle T t t in mathbb N nbsp Setze t 0 displaystyle t 0 nbsp lokale Veranderung wahle zu x displaystyle x nbsp einen Nachbarn y U x displaystyle y in U x nbsp zufallig aus Selektion wenn f y f x displaystyle f y leq f x nbsp setze x y displaystyle x y nbsp anderenfalls setze x y displaystyle x y nbsp nur mit Wahrscheinlichkeit exp f y f x T t displaystyle exp left frac f left y right f left x right T t right nbsp Bisher beste Losung aktualisieren wenn f x lt f x approx displaystyle f x lt f x text approx nbsp setze x approx x displaystyle x text approx x nbsp Inkrementiere setze t t 1 displaystyle t t 1 nbsp Abbruch oder weiter wenn die Abbruchbedingung nicht erfullt ist gehe zu Schritt 2 Erlauterungen Bearbeiten Die Wahrscheinlichkeit exp f y f x T t displaystyle exp left frac f y f x T t right nbsp dass x displaystyle x nbsp durch ein schlechteres y displaystyle y nbsp ersetzt wird ist umso kleiner je grosser die Verschlechterung f y f x displaystyle f y f x nbsp ist Weil T t displaystyle T t nbsp eine monoton fallende Folge ist nimmt die Wahrscheinlichkeit ausserdem wahrend eines Programmlaufs immer mehr ab Das Verfahren verhalt sich mit abnehmendem T t displaystyle T t nbsp mehr und mehr wie ein Bergsteigeralgorithmus Wie ein Nachbar y U x displaystyle y in U x nbsp gewahlt werden sollte hangt von dem vorliegenden Problem ab In der Informatik ist haufig der Wertebereich D 0 1 n displaystyle D 0 1 n nbsp und x x 1 x 2 x n displaystyle x x 1 x 2 dotsc x n nbsp wird als Bit Vektor betrachtet Ein Nachbar y displaystyle y nbsp von x displaystyle x nbsp 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 Durchlaufen erlaubt eine ausreichende Fitness definiert eine Untergrenze fur die Abkuhlung festgelegt oder eine Anzahl t displaystyle t nbsp von Zeitpunkten definiert uber die x a p p r o x displaystyle x mathrm approx nbsp sich nicht mehr geandert hat Graphische Verdeutlichung Bearbeiten nbsp Graphische Darstellung einer Landschaft in der ein globales Minimum gefunden werden soll Die Idee des simulierten Abkuhlens kann man sich graphisch verdeutlichen 5 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 nachsten tiefsten Punkt entspricht dem Verhalten einer Kugel welche in dieser Landschaft ausgesetzt wird Sie rollt zum nachsten lokalen Minimum und bleibt dort Bei der simulierten Abkuhlung wird der Kugel immer wieder ein Stoss versetzt der mit zunehmender Abkuhlung schwacher 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 nbsp 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 zuverlassig gefunden da der fallende Temperatur Wert zum Ende nicht mehr ausreicht es zu verlassen Das erbringt bessere Resultate als ein einfacher Bergsteigeralgorithmus Siehe auch BearbeitenSchwellenakzeptanz threshold accepting Deterministic Annealing Stochastisches Tunneln Sintflutalgorithmus MetropolisalgorithmusLiteratur BearbeitenIngo 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 Fur ein einfach zu beschreibendes Problem wird gezeigt dass unabhangig von der Temperatur die simulierte Abkuhlung effizienter ist als der Metropolisalgorithmus Weblinks BearbeitenInteraktives JavaScript zur Demonstration Memento vom 13 Marz 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 hEinzelnachweise Bearbeiten Bogatzki A Fabrikplanung Verfahren zur Optimierung von Maschinenaufstellung Diss Universitat Wuppertal 1998 Roderer 1998 ISBN 978 3 89073 234 3 T Kadowaki H Nishimori Quantum annealing in the transverse Ising model Phys Rev E Band 58 1998 S 5355 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 JP Dr A Arnold Universitat Stuttgart Institut fur Computerphysik Skript zur Vorlesung Physik auf dem Computer PDF 3 3 MB S 181 ff Google TechTalk Vortrag Eine kurze aber sehr verstandliche Erklarung zum Thema findet man ab Minute 35 Abgerufen von https de wikipedia org w index php title Simulated Annealing amp oldid 230612373