Was ist Simulated Annealing?

Simulated Annealing ist ein probabilistisches Optimierungsverfahren, das vom langsamen Abkühlen von Metallen inspiriert ist. Es sucht eine kostengünstige Lösung durch zufällige Änderungen, akzeptiert dabei stets Verbesserungen, aber auch schlechtere Zustände mit einer temperaturabhängigen Wahrscheinlichkeit, was es erlaubt, lokale Minima zu überwinden.

Warum akzeptiert es schlechtere Lösungen?

Das Akzeptieren schlechterer Züge mit Wahrscheinlichkeit e^(−ΔE/T) erlaubt der Suche, aus lokalen Minima herauszuklettern. Bei hoher Temperatur wird fast jeder Zug akzeptiert, sodass breit erkundet wird; mit sinkender Temperatur wird die Suche gieriger und setzt sich in einem guten Becken fest.

Was ist das Metropolis-Akzeptanzkriterium?

Wenn ein vorgeschlagener Zug die Kosten senkt, wird er immer akzeptiert. Erhöht er die Kosten um ΔE, wird er mit Wahrscheinlichkeit exp(−ΔE/T) akzeptiert, wobei T die aktuelle Temperatur ist. Diese Regel stammt aus dem Metropolis-Hastings-Algorithmus der statistischen Mechanik.

Was ist ein Abkühlungsschema?

Ein Abkühlungsschema legt fest, wie die Temperatur im Laufe der Zeit sinkt. Diese Simulation verwendet ein geometrisches Schema, T ← α·T mit α knapp unter 1 (der Abkühlrate). Langsameres Abkühlen erkundet mehr und findet meist kürzere Touren, braucht aber länger.

Was ist das Problem des Handlungsreisenden?

Das Problem des Handlungsreisenden fragt nach der kürzesten Rundreise, die jede Stadt genau einmal besucht und zum Ausgangspunkt zurückkehrt. Es ist NP-schwer, sodass exaktes Lösen für viele Städte unpraktikabel ist; Simulated Annealing findet schnell kurze, nahezu optimale Touren.

Was sind 2-opt- und Tausch-Züge?

Ein 2-opt-Zug kehrt ein Segment der Tour um und entkreuzt zwei Kanten. Ein Tausch-Zug vertauscht die Positionen zweier Städte. Beide erzeugen eine benachbarte Tour, deren Länge innerhalb der Akzeptanzregel mit der aktuellen verglichen wird.

Was sagt mir die Akzeptanzrate?

Die Akzeptanzrate ist der Anteil der vorgeschlagenen Züge, die zuletzt akzeptiert wurden. Sie beginnt hoch, solange die Temperatur hoch ist, und sinkt gegen null, während das Schema abkühlt und die Suche gieriger wird.

Findet Simulated Annealing die optimale Tour?

Nicht garantiert. Bei unendlich langsamer Abkühlung konvergiert es theoretisch zu einem globalen Optimum, in der Praxis liefert es aber eine hochwertige, nahezu optimale Lösung. Neustarts oder langsameres Abkühlen verbessern das Ergebnis.

Wie beeinflusst die Abkühlrate das Ergebnis?

Eine Abkühlrate nahe 1 (z. B. 0,999) kühlt langsam ab, erkundet länger und liefert meist kürzere Touren. Eine kleinere Rate (z. B. 0,99) kühlt schnell ab, konvergiert rasch, bleibt aber eher in einem lokalen Minimum stecken.

Wo wird Simulated Annealing in der Praxis eingesetzt?

Es wird beim VLSI-Chip-Layout, bei Terminplanung, Fahrzeugrouting, Bildrekonstruktion, dem Training neuronaler Netze und vielen anderen kombinatorischen Problemen eingesetzt, bei denen der Suchraum groß und von lokalen Minima durchsetzt ist.

Startseite▸Algorithmen & KI▸Simulated Annealing — Lokale Minima überwinden

🌡️ Simulated Annealing — Lokale Minima überwinden

Löse eine Rundreise des Handlungsreisenden mit Simulated Annealing: akzeptiere schlechtere Züge mit Wahrscheinlichkeit e^(−ΔE/T), während die Temperatur sinkt, um lokale Minima zu überwinden und schließlich eine kurze Route zu finden.

Algorithmen & KI3DMittel60 FPS

Über Simulated Annealing

Simulated Annealing (SA) ist eine probabilistische Metaheuristik, die 1983 von Kirkpatrick, Gelatt und Vecchi eingeführt wurde, inspiriert vom physikalischen Prozess des kontrollierten Abkühlens in der Metallurgie: Langsames Abkühlen eines geschmolzenen Materials erlaubt es Atomen, sich in energiearme Kristallgitter einzufinden, während schnelles Abschrecken sie in energiereichen amorphen Zuständen einschließt. In der Optimierung startet SA bei einer hohen „Temperatur" T und akzeptiert schlechtere Lösungen mit Wahrscheinlichkeit e^−ΔE/T (das Metropolis-Kriterium), was ein Entkommen aus lokalen Minima erlaubt; mit sinkendem T verhält sich der Algorithmus zunehmend wie Bergsteigen (Hill-Climbing) und konvergiert. SA kann nahezu optimale Lösungen für NP-schwere Probleme wie das Problem des Handlungsreisenden (TSP) finden, bei denen eine erschöpfende Suche unmöglich ist.

Diese Simulation wendet SA auf das TSP mit einer zufälligen Menge von Städten an: Beobachte, wie sich die Route beim Abkühlen der Temperatur verbessert, verfolge akzeptierte schlechtere Züge, die orange hervorgehoben sind, und vergleiche die endgültige Tourlänge mit dem gierigen Nächster-Nachbar-Verfahren. Einstellbare Parameter sind Starttemperatur, Abkühlrate und Städteanzahl, sodass du den Kompromiss zwischen Qualität und Laufzeit direkt erkunden kannst.

Häufig gestellte Fragen

Warum akzeptiert Simulated Annealing schlechtere Lösungen?

Das Akzeptieren schlechterer Lösungen mit Wahrscheinlichkeit e^−ΔE/T erlaubt dem Algorithmus, lokale Minima zu verlassen — Konfigurationen, bei denen jede kleine Änderung die Lösung verschlechtert, die aber nicht global optimal sind. Bei hoher Temperatur T werden fast alle schlechteren Züge akzeptiert (der Algorithmus erkundet breit); mit sinkendem T werden weniger schlechtere Züge akzeptiert und der Algorithmus konzentriert sich auf Ausbeutung. Diese Balance zwischen Erkundung und Ausbeutung ist der Kernmechanismus, der SA vom einfachen Hill-Climbing unterscheidet.

Welches Abkühlungsschema liefert die besten Ergebnisse?

Logarithmisches Abkühlen (T(t) = T₀/ln(1+t)) ist theoretisch garantiert, das globale Optimum für t→∞ zu finden, ist aber unpraktisch langsam. In der Praxis ist geometrisches Abkühlen T(t+1) = α·T(t) mit α ∈ [0,95; 0,999] Standard: Es kühlt schnell genug ab, um praktikabel zu sein, aber langsam genug, um ein Entkommen aus lokalen Minima zu ermöglichen. Das optimale α und die anfängliche T₀ hängen vom Problem ab; T₀ wird oft so gewählt, dass anfänglich 80 % der schlechteren Züge akzeptiert werden, was eine gründliche frühe Erkundung sicherstellt.

Wie wird Simulated Annealing auf das Problem des Handlungsreisenden angewendet?

Der TSP-Zustand ist eine Tour (Permutation von Städten); die Nachbarschaft wird durch 2-opt-Tausche (Umkehren eines Tour-Segments) oder 3-opt-Züge (Neuverbindung von drei Tour-Segmenten) definiert. Die Energie E ist die gesamte Tourlänge. Jede Iteration schlägt einen zufälligen Nachbarn vor: Ist er kürzer, wird er akzeptiert; ist er um ΔL länger, wird er mit Wahrscheinlichkeit e^−ΔL/T akzeptiert. Nach Millionen von Iterationen mit sinkendem T findet SA typischerweise Touren innerhalb von 1–3 % des Optimums für Hunderte von Städten.

Ist Simulated Annealing garantiert, das globale Optimum zu finden?

Bei logarithmischem Abkühlen (T(t) = c/ln(t+2)) konvergiert SA mit Wahrscheinlichkeit 1 in unendlicher Zeit zum globalen Optimum — ein Ergebnis von Hajek (1988). In der Praxis garantieren endliche Läufe mit geometrischem Abkühlen kein globales Optimum. Für das TSP mit n Städten ist das globale Optimum NP-schwer zu berechnen, aber SA mit guten 2-opt- oder Lin-Kernighan-Zügen findet für n ≤ 1000 Städte konsistent Lösungen innerhalb weniger Prozent des Optimums in Sekunden.

Was ist das Metropolis-Kriterium und woher stammt es?

Das Metropolis-Kriterium e^−ΔE/T stammt aus der statistischen Mechanik: Im kanonischen Ensemble bei Temperatur T ist die Wahrscheinlichkeit, dass ein System einen Energiezustand E einnimmt, proportional zu e^−E/kT (die Boltzmann-Verteilung). Das Akzeptanzverhältnis e^−ΔE/T für einen Zug, der die Energie um ΔE erhöht, stellt sicher, dass die Markow-Kette bei festem T zur Boltzmann-Verteilung konvergiert — eine Eigenschaft, die garantiert, dass SA bei niedrigen Temperaturen am häufigsten energiearme (gute) Lösungen besucht.

Wie schneidet Simulated Annealing im Vergleich zu genetischen Algorithmen ab?

Beide sind populationsinspirierte Metaheuristiken für NP-schwere Optimierung. SA hält eine einzelne aktuelle Lösung und nutzt Temperatur zur Steuerung der Vielfalt; genetische Algorithmen halten eine Population von Lösungen und nutzen Crossover und Mutation. SA ist einfacher zu implementieren und einzustellen; genetische Algorithmen können Lösungsstrukturen durch Crossover ausnutzen. In der Praxis übertrifft SA oft einfache genetische Algorithmen beim TSP für moderate Städteanzahlen, während genetische Algorithmen (besonders mit lokaler Suche — „memetische Algorithmen") besser auf sehr große Instanzen skalieren.

Was ist Reheat und wann sollte es verwendet werden?

Reheating erhöht T periodisch wieder auf einen höheren Wert, wenn der Algorithmus über viele Iterationen anscheinend in einem lokalen Minimum feststeckt. Dies kann SA helfen, tiefe lokale Becken zu verlassen, die geometrisches Abkühlen allein nicht überwinden kann. Reheating verkompliziert jedoch die Konvergenzanalyse und kann Rechenzeit verschwenden. Adaptive Abkühlungsschemata, die Akzeptanzraten überwachen und T dynamisch anpassen (z. B. eine Ziel-Akzeptanzrate von 20 % beibehalten), sind oft prinzipiellere Alternativen.

Welche realen Probleme nutzen Simulated Annealing?

SA wird beim VLSI-Chip-Layout eingesetzt (Platzierung von Schaltkreiselementen zur Minimierung der Leitungslänge — IBM nutzte es für den Chip, aus dem der ursprüngliche Mac wurde), bei der Proteinfaltung (Minimierung der freien Energie), bei der Terminplanung (Prüfungsplanung, Flugpersonal-Einsatzplanung), beim Design von Telekommunikationsnetzen und bei der Bildrekonstruktion in der Tomografie. Moderne SA-Implementierungen werden oft mit lokalen Suchheuristiken hybridisiert, um die Lösungsqualität innerhalb desselben CPU-Budgets drastisch zu verbessern.

Wie wählt man die Anfangstemperatur T₀?

Eine gängige Heuristik: Nimm eine Stichprobe zufälliger Züge, berechne den durchschnittlichen Energieanstieg ΔE̅ für diejenigen, die die Lösung verschlechtern, und setze dann T₀ = −ΔE̅ / ln(χ₀), wobei χ₀ die gewünschte anfängliche Akzeptanzwahrscheinlichkeit ist (typischerweise 0,8). Dies stellt sicher, dass der Algorithmus „heiß" genug startet, um 80 % der schlechteren Züge zu akzeptieren, was eine breite anfängliche Erkundung garantiert. Alternativ kann T₀ auf die Standardabweichung der Zielfunktionswerte über zufällige Lösungen gesetzt werden, skaliert mit einer Konstante.

Was ist der Unterschied zwischen Simulated Annealing und Basin-Hopping?

Basin-Hopping (Wales und Doye, 1997) kombiniert zufällige Störungsschritte mit lokaler Minimierung: Jeder SA-„Schritt" führt einen vollständigen Gradientenabstieg zum nächsten lokalen Minimum durch, bevor das Metropolis-Kriterium angewendet wird. Dies verwandelt die Energielandschaft in eine vereinfachte „Becken"-Landschaft (flach innerhalb jedes Beckens, unstetig an Beckengrenzen), die für SA viel leichter zu navigieren ist. Basin-Hopping ist in der Computerchemie Standard, um Protein- und Clusterstrukturen zu finden.

⚙ Unter der Haube

simulated annealingOptimierungMetropolisTSPCanvas 2D

3D · Three.js / WebGL-Renderer · 60 FPS Ziel · läuft vollständig clientseitig, keine Installation nötig