WikiDer > Simuliertes Glühen

Simuliertes Glühen (SA) ist ein generisches, probabilistisches heuristischOptimierungsalgorithmus verwendet, um eine Annäherung an die globales Optimum von einem gegebenen Funktion in einem großen Suchraum finden. Es wurde 1983 unabhängig von S. Kirkpatrick, C. D. Gelatt und M. P. Vecchi und 1985 von V. Cerny erfunden.

Der Name und die Inspiration stammen von einem englischen Begriff, 'annealing' (glühen), innerhalb der Metallbearbeitung. Es ist eine Technik, bei der Metall auf kontrollierte Weise erhitzt und dann abgekühlt wird, um die Größe der Kristalle im Material zu erhöhen und dadurch die Anzahl der Defekte zu reduzieren.

Hintergrundbilder

Simuliertes Glühen ist a Optimierungsalgorithmus von dem Kombinatorik. Es ist eine Verbesserung der Familie der lokalen Suchalgorithmen, basierend auf dem Annealing-Prozess, der innerhalb der Metallurgie.

Kombinatorik und lokale Suche

Das Kombinatorik ist ein Unterfeld von Mathematik Dabei geht es um die Lösung bestimmter Klassen von Problemen, den sogenannten kombinatorische Optimierungsprobleme.

Ein kombinatorisches Optimierungsproblem ist ein Problem, die beste Kombination von einigen zu finden Variablen oder variable Werte. Ein solches Problem wird auf einem sogenannten Zustandsraum -- ein Beispiel dafür ist der Probleme mit dem Handelsreisenden, wobei der Zustandsraum aus allen möglichen Kombinationen von Städten besteht, so dass diese Kombinationen einen Pfad bilden.

Jedes Element des Zustandsraums hat ein sogenanntes Anerkennung. Diese Bewertungen geben an, was die Lösung "wert" oder "kostet"; Die Bewertungen ermöglichen einen qualitativen Vergleich von Lösungen. Kurz gesagt, ein kombinatorisches Optimierungsproblem besteht darin, die Lösung mit dem höchsten Wert aus dem Zustandsraum zu finden (wir nennen dies a Maximierungsproblem) oder die niedrigsten Kosten (Minimierungsproblem).

Ein kombinatorisches Optimierungsproblem wie oben beschrieben wird in der Mathematik manchmal als Tupel bezeichnet

${Anzeigestil (S,f)}$

Mit ${Anzeigestil S}$ der Zustandsraum (Zustandsraum) und ${displaystyle f:Sightarrow mathbb {R} }$ eine Funktion, die die Bewertung für jede Lösung angibt. Kombinatorische Optimierungsprobleme für ein gegebenes Tupel suchen nach ${displaystyle i_{opt}in S}$ mit ${displaystyle forall _{iin S}:f(i_{opt})leq f(i)}$ (bei Minimierung, bei Maximierung umgekehrt). Dieses ${displaystyle i_{opt}}$ heißt übrigens eins (es, wenn es nur eines gibt) globales Optimum von dem Problem.

Es gibt zwei Arten von Algorithmen, die ein solches Problem lösen:

Genaue Algorithmen

Diese Algorithmen finden garantiert ein globales Optimum.

Näherungsalgorithmen oder heuristische Algorithmen

Diese Algorithmen durchsuchen den Zustandsraum intelligent ab einem bestimmten Anfangszustand. Sie finden immer eine Lösung, aber nicht unbedingt das globale Optimum.

Der Nutzen des heuristischen Ansatzes bei solchen Problemen besteht darin, dass nicht für jedes Problem ein exakter Algorithmus bekannt ist, der das Problem in angemessener Zeit löst. Es ist möglich, für jedes Problem eine exakte Lösung zu finden, aber manchmal dauert das unglaublich lange (siehe auch Komplexitätstheorie). In diesen Fällen bieten Approximationsalgorithmen oft eine praktikable Alternative, mit der Gefahr, dass nicht die beste Lösung gefunden wird.

Eine sehr bekannte Familie heuristischer Algorithmen ist die Familie der Lokale Suchalgorithmen. Diese Algorithmen sind beliebt, weil sie vernünftige Ergebnisse liefern und allgemein anwendbar sind – sie konzentrieren sich nicht auf ein bestimmtes Problem.

Lokale Suchalgorithmen beginnen bei einem gegebenen Zustand i aus dem Zustandsraum ${Anzeigestil S}$ und dann schau dir die "Nachbarstaaten" von i an. Die Nachbarstaaten von i sind die Staaten, die irgendwie "nahe an i" sind - im Fall des Problems des Handlungsreisenden, zum Beispiel bei einer bestimmten Route, die Routen, die Sie finden können, indem Sie dieser ersten Route folgen, nur um zwei zu verbinden connect Städtepaare umgekehrt. Lokale Suchalgorithmen betrachten diesen Nachbarraum und wählen die Lösung mit der besten Bewertung. Das wird die nächste Situation sein. Dann suchen sie wieder nach dem nächst besseren Zustand und so weiter und so weiter, bis es im lokalen Nachbarraum keinen besseren Zustand mehr gibt. Das ist ein lokales Optimum und möglicherweise auch das globale Optimum.

Das Problem mit lokalen Suchalgorithmen besteht darin, dass ihre Funktionsweise im Wesentlichen darauf hinausläuft, mit verbundenen Augen durch eine hügelige Landschaft zu gehen, in der Sie sich nur einen Schritt unter der Kante Ihrer Augenbinde umsehen können. Startet man am oberen Rand eines tiefen Tals und nimmt immer die Stufe, die am schnellsten abwärts geht, erreicht man am Ende der Fahrt den tiefsten Punkt. Aber in einer komplexeren Landschaft können Sie sich am Ende Ihres Spaziergangs auch in einer winzigen Grube auf einem hohen Berg wiederfinden – lokales Minimum, aber sicherlich nicht das am besten zugängliche.

Aus diesem Grund gibt es viele Arten von lokalen Suchalgorithmen. Jeder hat seine eigene Strategie, durch die Landschaft zu gehen und vielleicht auch eine Strategie, einen guten Ausgangspunkt zu wählen. Simulated Annealing ist ein Beispiel für einen solchen Algorithmus, der versucht, das Ergebnis durch eine bessere Strategie für die Wahl des nächsten Schritts zu verbessern. Im Gegensatz zu dem, was oben beschrieben wurde, macht Simulated Annealing nicht immer den Schritt nach unten - manchmal geht Simulated Annealing auch nach oben, um zu sehen, ob es weiter unten ein tieferes Tal gibt.

Glühen

Simulated Annealing basiert auf dem Glühprozess der Metallurgie.

Das Glühen wird in der Metallurgie angewendet, um Metall Objekt so, dass keine Risse oder Fehler im Material vorhanden sind, d. h., dass die Moleküle des Metalls passen perfekt in einen Rahmen ohne Löcher im Rahmen.

Dazu wird das Objekt in ein Heizbad getaucht und genau auf Schmelztemperatur gebracht. Anschließend wird das Objekt in genau kontrollierten Schritten sehr langsam abgekühlt. Dies hat zur Folge, dass das Energieniveau aller Moleküle im Objekt während der Abkühlung annähernd gleich bleibt – thermisches Gleichgewicht. Durch die Aufrechterhaltung dieses Gleichgewichts während des Abkühlens gibt es nirgendwo im Objekt eine "Energiespitze", einen Fleck mit Molekülen, die eine höhere Energie haben als die umgebenden Moleküle und sich daher relativ zum Gitter zusätzlich bewegen. Durch das Abkühlen des Objekts im thermischen Gleichgewicht erreichen alle Moleküle gleichzeitig (ungefähr) ihr niedrigstes Energieniveau und man erhält ein Objekt, bei dem alle Moleküle ordentlich an ihrem Platz im Gitter "ausgeruht" sind.

runden 1953 wurde der erste Computersimulationen des Glühens entwickelt. In diesem Fall von Monte-Carlo-Techniken verwendet, um das Verhalten von Molekülen im erhitzten Objekt zu bestimmen. Die angewandte Analyse des Problems führte zum Metropolis-Algorithmus zur Simulation des Glühprozesses.

Der Metropolis-Algorithmus betrachtet Zustände, die aus den Positionen von Molekülen relativ zum Gitter bestehen. Jeder Zustand wird mit der Gesamtenergie dieses Zustands bewertet. Der Algorithmus läuft, bis das System einen Zustand erreicht hat, in dem keine Verbesserung möglich ist, den Zustand mit der niedrigsten Energie.

Damit ist die Sache jedoch nicht erledigt. Der Metropolis-Algorithmus erfasst eine besondere Eigenschaft des Annealing-Prozesses: Nicht jeder Zustandsübergang beim Abkühlen reduziert die Gesamtenergie. Manchmal "tanzt" ein Molekül (oder mehr) noch im Gitter, damit der nächste Zustand keine niedrigere Energie hat als der vorherige. Um dies zu erfassen, haben sich die Macher von Metropolis die folgende Zustandsübergangsregel ausgedacht:

1. Bei einem gegebenen Anfangszustand wählen wir einen Zustand aus den möglichen Nachbarzuständen aus.
2. Wenn der Wert des ausgewählten Zustands niedriger ist als der Wert des aktuellen Zustands, akzeptieren wir dies.
3. Ist der Wert des gewählten Zustands höher als der Wert des aktuellen Zustands, akzeptieren wir ihn mit einer gewissen Wahrscheinlichkeit oder lehnen ihn mit der entsprechenden komplementären Wahrscheinlichkeit ab.
4. Wenn der ausgewählte Status akzeptiert wird, wechseln Sie in diesen Status und beginnen Sie von vorne.
5. Wenn der ausgewählte Status nicht akzeptiert wird, dann
   1. Wenn wir noch nicht den gesamten Nachbarraum gesehen haben, versuchen Sie es mit einem anderen Nachbarstaat.
   2. Wenn uns die Nachbarstaaten ausgehen, hören Sie auf.

Sie haben den Teil über die Akzeptanz und Ablehnung des Übergangs von Zustand i zu Zustand j in folgendem Ausdruck festgehalten:

${displaystyle mathbb {P} _{T}(X_{i}=j)={ egin{cases}E_{j}leq E_{i}ightarrow 1/E_{i}$

Darin ist ${displaystyle X_{i}}$ ein stochastisch was für "der Nachfolger des Staates i" steht. Das heißt, das Obige lautet "die Wahrscheinlichkeit, dass der nachfolgende Zustand von i der Zustand j ist, ist ...". Darin ist ${displaystyle E_{n}}$ die Energie (oder Wertschätzung) des Zustands n, ${Anzeigestil T}$ die Temperatur des Objekts und ${displaystyle k_{B}}$ das Boltzmann-Konstante.

Diese Simulation demonstriert gut das Glühphänomen, dass das thermische Gleichgewicht bei jeder Temperatur durch die Boltzmann-Verteilung gekennzeichnet ist – dies ist eine statistische Verteilung, die die Wahrscheinlichkeit jedes möglichen Zustands bei einer gegebenen Temperatur T angibt. Die Wahrscheinlichkeit, dass ein Objekt bei der Temperatur T annimmt ein gegebener Zustand während des Glühens ist

${displaystyle mathbb {P} _{T}(X_{i}=j)={frac {e^{frac {-E_{i}}{k_{B}cdot T}}}{sum _{j}e ^{frac {-E_{j}}{k_{B}cdot T}}}}}$

Der Nenner in diesem Term heißt Partitionsfunktion und die Domäne dieser Funktion ist die Menge aller möglichen Zustände im System. Eine solche Funktion ist auch für die Analyse des Verhaltens des Simulated Annealing Algorithmus wichtig.

Simuliertes Glühen

Der Algorithmus

Daraus lässt sich der Simulated Annealing Algorithmus besonders leicht ableiten. Wie beim echten Glühen haben wir einen vorhandenen Zustand, eine Reihe möglicher Zustandsübergänge und eine Bewertung für jeden Übergang. Aus dem gegebenen Zustand wählen wir einen Nachbarzustand. Wenn es eine bessere Bewertung hat, werden wir es akzeptieren. Wenn nicht, akzeptieren wir es mit einer gewissen Wahrscheinlichkeit. Alles in allem lautet die Regel für die Annahme

${displaystyle mathbb {P} _{c}(accept(j))=left{{ egin{matrix}f(j)leq f(i)&1/f(i)$

Dabei ist c ein Regelparameter, der die Rolle der Temperatur übernimmt. Der gesamte Algorithmus führt die Auswahl von Nachbarn und den Übergang von Zuständen mehrmals durch. Mit jeder Iteration wird der Wert von c verringert. Wir werden sehen, dass der Algorithmus dadurch „lokaler“ wird, das heißt, der Algorithmus nimmt bei der Auswahl eines Nachbarn immer weniger große Bewertungsverschlechterungen in Kauf und tendiert daher mit der Zeit immer mehr dazu, bessere Bewertungen zu wählen.

Der gesamte Algorithmus für ein Problem ${Anzeigestil (S,f)}$ sieht aus wie das:

ProzessSimuliertes_Annealing(so,f)=|[varich,ja:Elementvonso;c:Real;k,l,l:Ganze Zahl;|ich:=<Elementvonso>;k,c,l:=0,Unendlichkeit,<angemessenUrsprünglicher Wert>;tunNICHT(Stoppkriterium)->l:=1;tunl<=l->ja:=<wähleneinElementvondasNachbarnvonichimso>;wennf(ja)<=f(ich)->ich:=ja[]f(ich)<f(ja)->wenne^((f(ich)-f(ja))/c)>zufällig[0,1)->ich:=jafifi;od;k:=k1;c:=<Berechnungneuec>;l:=<BerechnungneuelBieneneuec>;od]|

Beachten Sie den zusätzlichen Parameter L im obigen Code. Für jeden Wert des Steuerparameters c werden eine Reihe von Zustandsübergängen simuliert, wie dies beim realen Glühen bei einer bestimmten Temperatur geschieht. Beim Annealing wird damit simuliert, was in einem physikalischen Objekt passiert, nämlich dass sich die Moleküle beim Abkühlen von einer Temperatur zur nächsten in mehreren Stufen (Zuständen) auf ein niedrigeres Energieniveau vorarbeiten.

Indem wir dies beim Simulated Annealing getreu reproduzieren, erhöhen wir die Chance, das globale Optimum zu finden. Unterm Strich akzeptieren wir nicht blind eine Bedingung pro Kontrollparameter und fahren damit fort, sondern können uns zunächst umschauen, ob es eine bessere Option gibt. Manchmal akzeptieren wir sogar eine schlechtere Option als möglich und denken, dass wir am Ende besser herauskommen. Wir werden später sehen, dass wir – da c einen niedrigeren Wert bekommt – wahrscheinlich dem globalen Optimum näher kommen.

Vorerst bemerken wir jedoch genauer, was wir zuvor angesprochen haben: Der direkte Einfluss von c auf die Berechnung ist das Simulated Annealing, während es Zustandsübergänge ermöglicht, bei denen die Bewertung mit der Zeit immer schlechter wird. Das heißt, je niedriger der Wert von c ist (und wir gehen normalerweise davon aus, dass c monoton abnimmt), desto geringer ist die Wahrscheinlichkeit, dass ein Übergang in einen Zustand mit einem höheren Wert akzeptiert wird. Dies ist direkt aus dem Begriff ersichtlich

${displaystyle e^{frac {f(i)-f(j)}{c}}}$

Wenn c einen großen Wert hat (wie anfangs), ist der Wert dieses Termes ungefähr 1. Das bedeutet, dass ein Übergang in einen Zustand mit einem höheren (schlechteren) Wert (f(j) ist schließlich größer als f(i)) ist etwa 1. Wenn c kleiner wird, wird das Ergebnis mehr und mehr durch den Term bestimmt ${Anzeigestil f(i)-f(j)}$, die immer höchstens Null ist (wiederum: es handelt sich um den Übergang in einen Zustand mit höher Anerkennung). Je größer die Differenz, desto geringer der Wert des Begriffs (und damit die Akzeptanzwahrscheinlichkeit des Übergangs). Die Akzeptanzchance ist daher höher als die Differenz ${Anzeigestil f(i)-f(j)}$ ist kleiner.

Wahrscheinlichkeit, eine Lösung zu finden

Bei der Diskussion von True Annealing und dem Metropolis-Algorithmus haben wir festgestellt, dass das Objekt für jede Temperatur ein sogenanntes thermisches Gleichgewicht erreicht. Dieses Gleichgewicht war durch eine Verteilung von Wahrscheinlichkeiten über Zustände hinweg gekennzeichnet – für jeden Zustand gab es eine gewisse Wahrscheinlichkeit, dass das System diesen Zustand annehmen würde.

Simuliertes Annealing verhält sich genauso. Für jeden Wert des Parameters c wird eine Anzahl von Zustandsübergängen im Nachbarraum untersucht -- diese Zahl ist der Parameter L. Es ist nachweisbar, dass wenn L für jeden Wert von c groß genug ist, dann für jeden Wert von c a " Wärmebilanz". Das heißt, für jeden Wert von c und Zustand ${displaystyle iinS}$ zählt das

${displaystyle mathbb {P} _{c}(X=i) {hat {=}} {frac {e^{frac {-f(i)}{c}}}{sum _{jin S}e^{ frac {-f(j)}{c}}}}}}$

Der Grund für diese Ausgewogenheit ist, dass sie garantiert, dass der Simulated Annealing-Algorithmus asymptotisch nähert sich der Menge der global optimalen Zustände im Zustandsraum (wir nennen diese Menge ${displaystyle S_{opt}}$). Immerhin gibt es

${displaystyle { egin{matrix}&{ egin{matrix}lim /cdownarrow 0end{matrix}}{frac {e^{frac {-f(i)}{c}}}{sum _{jin S}e^{ frac {-f(j)}{c}}}/=&{{mbox{Bewertung des globalen Optimums einfügen}}}/&{ egin{matrix}lim /cdownarrow 0end{matrix}}{frac { e ^{frac {f_{opt}}{c}}}{e^{frac {f_{opt}}{c}}}}{frac {e^{frac {-f(i)}{c}} } {sum _{jin S}e^{frac {-f(j)}{c}}}}/=&/&{ egin{matrix}lim /cdownarrow 0end{matrix}}{frac {e^{frac { f_{opt}-f(i)}{c}}}{Summe _{jin S}e^{frac {f_{opt}-f(j)}{c}}}}/=&{{mbox { Diese Wahrscheinlichkeit setzt sich zusammen aus der Wahrscheinlichkeit, wenn Zustand i ein Optimum ist und wenn nicht;}}/&{mbox{ wir geben dies mit der Chi-Funktion an}}}/&{ egin{matrix}lim /cdownarrow 0end{matrix } }{frac {e^{frac {f_{opt}-f(i)}{c}}}{sum _{jin S}e^{frac {f_{opt}-f(j)}{c} } }}mathrm {X} _{(S_{opt})}(i) {frac {e^{frac {f_{opt}-f(i)}{c}}}{Summe _{jin S}e ^ {frac {f_{opt}-f(j)}{c}}}}mathrm {X} _{(Ssetminus S_{opt})}(i)/=&{{mbox{Wenn i kein Optimum ist, dann }}f_{opt}-f(i){mbox{ nicht 0;}}/&{mbox{benutze jetzt das }}{ egin{matrix}lim /xdownarrow 0end{matrix}}e^{frac {a}{x}}/&{mbox{ gleich 0 wenn a kleiner als 0 ist und 1 wenn a = 0 }}}/&{ egin{matrix}lim /cdownarrow 0end{matrix}}{frac {e^{frac {f_{opt}-f(i)}{c}}}{Summe _{jin S}e^{frac {f_{opt}-f(j)} {c}}}}mathrm {X} _{(S_{opt})}(i) 0/=&{{mbox{Die maßgeschneiderte Entwicklung von }}e^{x}{mbox{ ist }} 1 x { frac {x^{2}}{2!}} ldots /&{mbox{Nur der erste Term dieser Erweiterung ist nicht 0, weil }}f_{opt}-f(i)/&{mbox{ 0 ist, wenn i ist ein Optimum}}}/&{ egin{matrix}lim /cdownarrow 0end{matrix}}{frac {1}{sum _{jin S}e^{frac {f_{opt}-f(j)}{ c}}}}mathrm {X} _{(S_{opt})}(i)/=&{{mbox{Auf den Nenner im vorherigen Term können wir auch das Limit von vorhin anwenden.}} /&{mbox { Die Summe wird dann zur Summe von 1 für Optima und 0 für Nicht-Optimum;}}/&{mbox{ das ist die Anzahl der Optima in S}}}/&{frac {1}{|S_{ opt}| }}mathrm {X} _{(S_{opt})}(i)end{matrix}}}$

Das heißt, wenn c kleiner wird, nähern wir uns einer Verteilung, bei der die Wahrscheinlichkeit, das System in einem bestimmten Zustand zu finden, normal über die optimalen Zustände verteilt ist und für nicht optimale Zustände 0 beträgt. Mit abnehmendem c wird die Annäherung an das Optimum immer besser.

Oben haben wir die Χ-Funktion verwendet, um die Wahrscheinlichkeit zwischen optimalen und nicht optimalen Zuständen aus dem Zustandsraum zu teilen. Diese Funktion ist wie folgt definiert:

${displaystyle mathrm {X} :A imes {mathcal {P}}(A)ightarrow {0,1}}$

${displaystyle mathrm {X} _{(A')}(a)={{ egin{matrix}1&ain A'Teilmenge A/0&aot in A'Teilmenge Aend{matrix}}}$