Simulated Annealing verständlich erklärt

Wer eine Lieferroute Schritt für Schritt verkürzt und jede Änderung ablehnt, die sie länger macht, bleibt irgendwann in einer Mulde stecken: Keine einzelne Änderung hilft mehr, obwohl eine kürzere Route existiert. Ein Verfahren namens Simulated Annealing lässt anfangs auch Verlängerungen zu und wird dann immer strenger. Diese Seite erklärt zuerst ohne Formeln, warum das hilft und wann nicht, und danach für Fachleute mit Modell, Formeln, Messwerten und Grenzen.

Zuletzt aktualisiert: 28. Oktober 2026

Ein Wort unbekannt? Das Begriffsverzeichnis erklärt es in wenigen Sätzen.

Der Wanderer im Nebel

Stellen Sie sich einen Wanderer vor, der im dichten Nebel den tiefsten Punkt eines Hügellands sucht, etwa den See im tiefsten Tal. Er sieht nur wenige Schritte weit. Seine Regel lautet: Ich gehe nur dorthin, wo es abwärts geht. So läuft er in die nächste Mulde und bleibt dort stehen, denn ringsum geht es nur noch bergauf. Ob hinter dem nächsten Hügel ein tieferes Tal liegt, kann er im Nebel nicht sehen. Eine solche Mulde, aus der kein einzelner Schritt mehr nach unten führt, heißt bei Fachleuten lokales Optimum: besser als alle unmittelbaren Nachbarn, aber nicht unbedingt das Beste überhaupt.

Mit einer Lieferroute geschieht dasselbe. Ein Lieferwagen fährt ab dem Depot mehrere Kunden an, gesucht ist die kürzeste Reihenfolge. Das einfachste Verfahren heißt Hill Climbing. Es probiert kleine Änderungen aus, etwa ein Stück der Route in umgekehrter Reihenfolge zu fahren, und behält eine Änderung nur, wenn die Route dadurch kürzer wird. Übertragen auf das Bild heißt das: Jede mögliche Route ist ein Ort im Gelände, und ihre Länge ist die Höhe. Das Verfahren geht also immer bergab. Irgendwann bringt keine einzelne Änderung mehr etwas. Die Route steckt dann in einer Mulde, obwohl es eine kürzere gibt.

Warum passiert das?

Dieser Abstieg kennt nur den nächsten Schritt. Um aus der Mulde zu kommen, müsste die Route erst länger werden, also den Hügelrücken überqueren, bevor sie auf der anderen Seite wieder kürzer wird. Das schließt die Regel des Abstiegs aus. Welche Mulde erreicht wird, hängt von der Startroute ab: Von einem Start aus führt der Weg meist in die nächstgelegene Mulde.

Eine Abhilfe sind Neustarts: Man beginnt den Abstieg mehrmals von neuen Zufallsrouten und behält das beste Ergebnis. Jeder Neustart kostet einen vollständigen neuen Abstieg.

Was hilft: erst erlauben, dann verbieten

Das Verfahren Simulated Annealing (englisch für „simuliertes Abkühlen“) ändert genau eine Regel. Der Name kommt vom Abkühlen von Metall: Ist es heiß, bewegen sich die Teilchen frei; kühlt man es langsam ab, finden sie eine stabile Anordnung. Das Verfahren führt dafür einen Wert mit, die Temperatur. Bei jedem Vorschlag einer Änderung gilt: Wird die Route kürzer, wird die Änderung angenommen. Wird sie länger, wird gewürfelt. Die Chance, dass die Verlängerung trotzdem gilt, ist umso größer, je kleiner die Verlängerung und je höher die Temperatur ist. Im Bild: Der Wanderer darf auch bergauf gehen, wenn die Steigung klein und es noch „heiß“ ist.

Zu Beginn ist die Temperatur hoch, und die Route darf Hügelrücken überqueren. Dann sinkt die Temperatur nach einem festen Plan, dem Abkühlplan, und das Verfahren wird immer wählerischer, bis am Ende praktisch nur noch Verbesserungen gelten. Es sucht also zuerst grob nach einem vielversprechenden Tal und feilt danach in einem Tal an den Einzelheiten. Gemerkt wird die beste Route, die unterwegs vorkam. In den Beispielaufgaben der Demo ist die gefundene Route bei gleichem Rechenaufwand kürzer als das Ergebnis eines einzelnen Abstiegs und auch kürzer als das beste Ergebnis mehrerer Neustarts.

Die Einstellung entscheidet

Das funktioniert nur, wenn die Temperatur zur Aufgabe passt. Zwei Einstellungen sind wichtig: die Anfangstemperatur (wie großzügig das Verfahren beginnt) und die Endtemperatur (wie streng es endet). Ist es von Anfang an zu kalt, wird in der Demo eine Verlängerung so gut wie nie angenommen, und das Verfahren verhält sich wie der einfache Abstieg. Ist es am Ende noch zu heiß, wandert die Route weiter umher und kommt nicht zur Ruhe. Die Route, bei der das Verfahren zuletzt steht, ist dann schlecht. Deshalb merkt es sich die kürzeste Route, die unterwegs vorkam, und gibt diese zurück. Die Demo zeigt beide Fälle.

Drei weitere Grenzen: Bei knappem Rechenaufwand ist Simulated Annealing in der Demo nicht besser als ein einzelner Abstieg. Bei Aufgaben mit mehr Kunden braucht es in der Demo mehr Rechenaufwand, damit die Abkühlung genug Zeit hat. Und das Verfahren würfelt: Zwei Läufe mit derselben Einstellung können verschiedene Routen liefern, ein einzelner Lauf sagt also wenig über die Güte des Verfahrens.

Wie ernst ist das Modell zu nehmen?

Die Demo ist ein stark vereinfachtes Modell. Die Kundenorte sind zufällig erzeugt, die Entfernungen sind Luftlinie, es gibt ein einziges Fahrzeug ohne Ladekapazität und ohne Zeitfenster. Die Demo zeigt, wie das Verfahren arbeitet und wo es Grenzen hat, nicht wie ein bestimmter Betrieb planen sollte. Der Vorsprung vor dem Abstieg ist außerdem nicht sicher. Der einfache Abstieg der Demo probiert nach jedem Schritt alle denkbaren Änderungen durch. Ein schlauerer Abstieg prüft nur Änderungen zwischen benachbarten Kunden und überspringt Stellen, an denen zuletzt nichts half. Mit Neustarts war er in der Demo bei der Standardeinstellung besser als Simulated Annealing und bei größerem Rechenaufwand gleichauf.

Was Sie mitnehmen: Wirbt ein Planungsprogramm mit Abkühlen oder Simulated Annealing, lohnt sich die Frage, wie Anfangs- und Endtemperatur gewählt wurden, ob diese Einstellung an Aufgaben Ihrer Größe geprüft wurde und wie das Ergebnis bei gleicher Rechenzeit gegen einen einfachen Abstieg mit Neustarts abschneidet. Im Betrieb erkennen Sie das Verfahren daran, dass dieselbe Aufgabe bei jedem Lauf eine andere Route liefern kann; in der Demo schwankten die Ergebnisse von Lauf zu Lauf merklich. Schauen Sie sich deshalb mehrere Läufe an. Die Antworten sagen nur etwas, solange der Vergleich bei gleichem Rechenaufwand und für Aufgaben wie Ihre gemacht wurde.

Hinweis: Alle Demos rechnen mit synthetischen oder frei verfügbaren Beispieldaten und laufen auf einem externen Anbieter (Datenschutz). Bitte geben Sie darin keine vertraulichen oder personenbezogenen Daten ein. Die Ergebnisse gelten für die jeweilige Demo-Instanz und lassen sich nicht ungeprüft auf reale Fälle übertragen; für darauf gestützte Entscheidungen übernehme ich keine Gewähr.

Modell und Annahmen

Dieser Teil ist eigenständig lesbar. Er fasst die formale Beschreibung der Demo zusammen; die vollständige Fassung steht im Expander „📐 Mathematische Formulierung“ der Demo.

• Modell: kürzeste Rundtour über \(N = n+1\) Knoten (Depot und \(n\) Stopps) mit euklidischen Entfernungen \(d_{ij}\), ein Fahrzeug, keine Kapazitäten oder Zeitfenster; Stopps gleichverteilt oder in fünf Gruppen. Kennzahl ist der Abstand zur 1-Baum-Schranke \(w\) in Prozent, \(100 \cdot (L - w)/w\). Bei gleichverteilten 60 Stopps liegt die Schranke im Mittel 0,5 % unter dem Optimum.
• Verfahren: eine Kette, je Vorschlag ein zufälliger Nachbar (2-opt, Or-opt, Tausch oder eine Mischung), \(\Delta\) in \(O(1)\) aus wenigen Kanten. Ein Vorschlag ist ein bewerteter Nachbar, so zählt auch das Hill Climbing seine Bewertungen; das macht das Budget vergleichbar. Die Temperatur steht in Vielfachen der mittleren Kantenlänge einer guten Tour (Schranke geteilt durch die Knotenzahl) und sinkt in Stufen. Gemerkt wird die beste besuchte Tour.
• Vergleichsverfahren: ein einzelner Abstieg und Hill Climbing mit Neustarts: Abstiege aus zufälligen Startlösungen, bis die bewerteten Nachbarn das Budget erreichen (der erste läuft immer zu Ende). Im Hauptvergleich bewertet der Abstieg nach jedem Zug alle Nachbarn neu (voller Rescan, keine Nachbarschaftslisten, keine Don't-Look-Bits).
• Annahmeregeln: vier wählbare Regeln: Metropolis (mit Zufallszahl), Threshold Accepting, Great Deluge und Late Acceptance Hill Climbing (die drei letzten deterministisch).
• Instanzen: fünf feste Instanzen (Zufalls-Seeds 100000–100004) mit je drei Ketten, für Streuung und Optimum-Vergleich weitere Läufe, wie in den Zeilen genannt.

Die Formeln

Ein Vorschlag \(\pi \to \pi'\) mit der Längenänderung \(\Delta = L(\pi') - L(\pi)\) wird mit der Metropolis-Wahrscheinlichkeit angenommen. Für \(\Delta \le 0\) ist sie eins, für eine Verlängerung sinkt sie mit \(\Delta\) und steigt mit \(T\):

\[\min\{1, e^{-\Delta/T}\}\]

Ist der Vorschlag symmetrisch (2-opt, Or-opt und Tausch mit gleichverteilter Wahl der Kanten), ist bei festem \(T\) die Boltzmann-Verteilung die stationäre Verteilung der Kette (Detailed Balance). Für \(T \to 0\) konzentriert sie sich auf die kürzesten Touren, für \(T \to \infty\) ist sie gleichverteilt:

\[p_T(\pi) \propto e^{-L(\pi)/T}\]

Der Abkühlplan teilt die Temperatur in \(K\) Stufen \(k = 0, \dots, K-1\) mit gleichbleibendem Kontrollwert. Geometrisch, mit Anfangs- und Endtemperatur \(T_0\) und \(T_{\text{end}}\):

\[T_k = T_0 (T_{\text{end}}/T_0)^{k/(K-1)}\]

Daneben gibt es einen linearen Plan, \(T_k = T_0 + (T_{\text{end}} - T_0)\, k/(K-1)\), und den logarithmischen Plan, für den nach Hajek die Konvergenz in Wahrscheinlichkeit gegen ein globales Optimum gilt, wenn \(c\) mindestens die größte Tiefe eines lokalen Minimums ist, allerdings erst in unendlicher Zeit:

\[T_k = T_0 \ln 2 / \ln(k+2)\]

Die drei anderen Annahmeregeln der Demo (Threshold Accepting: \(\Delta \le T_k\); Great Deluge: \(L(\pi') \le B_k\) mit sinkendem Wasserspiegel \(B_k\); Late Acceptance: Vergleich mit einem Ringpuffer vergangener Tourlängen) stehen im Expander der Demo. Nur Metropolis hat die Boltzmann-Verteilung als Grundlage, die anderen sind deterministische Faustregeln.

Befunde

Alle Zahlen stammen aus der README der Demo (und stehen in deren Tests). Wenn nichts anderes steht, gilt der Standardfall: 60 gleichverteilte Stopps, 2-opt, geometrisch von 0,5 auf 0,1 mittlere Kantenlängen, 200 Tausend Vorschläge, 100 Stufen, zufällige Startlösung; Mittel über 5 feste Instanzen (Zufalls-Seeds 100000–100004) mit je 3 Zufalls-Seeds der Kette. Der Abstand ist der Prozentsatz über der 1-Baum-Schranke, Hill Climbing hat dasselbe Bewertungsbudget.

Frage	Befund
Schlägt Simulated Annealing den Abstieg bei gleichem Budget?	Ja, im Standardfall: beste Tour 1,4 % (letzte Tour 1,8 %) gegen 7,9 % für einen Hill-Climbing-Abstieg und 4,9 % für Hill Climbing mit Neustarts (3,2 Abstiege). Angenommen werden 1,2 % der Vorschläge, knapp die Hälfte davon Verschlechterungen (0,56 % aller Vorschläge).
Wie hängt das vom Budget ab?	Beste Tour bei 10 / 25 / 50 / 100 / 200 Tausend / 0,5 / 1 / 2 Millionen Vorschlägen 8,0 / 4,1 / 2,6 / 2,6 / 1,4 / 1,0 / 0,7 / 0,5 %; Hill Climbing mit Neustarts 7,9 / 7,9 / 7,9 / 7,9 / 4,9 / 2,9 / 2,5 / 1,9 %. Bei 10 Tausend Vorschlägen ist Simulated Annealing nicht besser als ein Abstieg (8,0 gegen 7,9 %; ein Abstieg braucht 74 Tausend Bewertungen). Mit 2-opt + Or-opt bei 1 Million Vorschlägen sind beide fast gleichauf (0,7 % gegen 1,0 %).
Gilt das auch für einen billigeren Abstieg?	Nein. Mit Kandidatenliste + Don't-Look-Bits (nur 2-opt) braucht ein Abstieg nur noch rund 650 statt 74 000 Bewertungen. Hill Climbing mit Neustarts erreicht dann bei gleichem Budget 0,8 % bei 200 Tausend Vorschlägen (besser als Simulated Annealing mit 1,4 %) und 0,7 % bei 1 Million (gleichauf).
Wie eng ist das Temperaturfenster?	Endtemperatur kritisch: 0,005 / 0,02 / 0,05 / 0,1 / 0,2 / 0,5 Einheiten ergeben beste Tour 3,1 / 2,3 / 1,75 / 1,4 / 1,4 / 9,5 %, letzte Tour 3,1 / 2,4 / 2,0 / 1,8 / 3,7 / 27,2 %. Anfangstemperatur weit: 0,1 / 0,25 / 0,5 / 1 / 2 / 4 ergeben 3,8 / 2,1 / 1,4 / 1,2 / 1,7 / 1,8 %, mit angenommenen Vorschlägen von 0,3 / 0,6 / 1,2 / 3,0 / 7,6 / 15,2 %. Einheit ist die mittlere Kantenlänge einer guten Tour, bei 60 Stopps etwa 10 km.
Was passiert bei zu kalter oder zu heißer Einstellung?	Zu kalt (T0 = 0,05, T_end = 0,02): 7,1 %, wie ein Abstieg (7,9 %); nur 0,04 % der Vorschläge sind angenommene Verschlechterungen. Zu heiß (T0 = 1, T_end = 0,5): beste Tour 15,1 %, letzte Tour 26,7 %.
Welcher Abkühlplan?	Geometrisch 1,4 %, linear 1,3 %: gleichwertig. Der logarithmische Plan (Hajek, in unendlicher Zeit optimal) liegt bei 3,4 %, weil er im endlichen Budget zu langsam abkühlt.
Ersetzt die Temperatur eine gute Nachbarschaft?	Nein. Beste Tour: Tausch 22,6 %, 2-opt 1,4 %, Or-opt 5,7 %, 2-opt + Or-opt 1,2 % (Hill Climbing: 54,5 / 7,9 / 10,4 / 3,7 %). Tausch bleibt schlecht, aber 2-opt allein reicht: die Kombination ändert kaum etwas, beim Hill Climbing halbiert sie die Lücke.
Wie viele Stufen, welche Startlösung?	1 / 3 / 10 / 30 / 100 / 300 / 1000 Stufen: 8,9 / 2,2 / 1,1 / 1,7 / 1,4 / 1,3 / 1,6 %. Eine Stufe (konstante Temperatur) ist Unsinn (letzte Tour 28,4 %); ab drei Stufen ändert sich nichts Sicheres mehr. Startlösung zufällig 1,4 %, Nächster Nachbar 2,0 % (Hill Climbing: 7,9 / 7,3 %).
Was passiert bei größeren Instanzen?	Beste Tour bei 10 / 20 / 40 / 60 / 100 / 150 / 200 Stopps mit 200 Tausend Vorschlägen: 0,0 / 0,05 / 0,9 / 1,4 / 3,8 / 6,3 / 7,7 % (Abstieg 1,7 / 1,9 / 7,7 / 7,9 / 9,1 / 9,1 / 9,5 %). Mit 5 000 Vorschlägen je Stopp: 0,05 / 0,9 / 1,4 / 2,0 / 3,8 / 4,1 %. Das nötige Budget wächst stärker als linear; bei 200 Stopps und 1 Million Vorschlägen 4,1 % gegen 9,5 %.
Wie stark streuen die Läufe?	20 Ketten auf der Standardinstanz: 1,5 ± 1,0 % (0,1 bis 5,1 %), 85 % höchstens 2 % über der Schranke. 20 Hill-Climbing-Abstiege aus denselben Startlösungen: 5,0 ± 2,4 % (0,8 bis 11,5 %), 5 % höchstens 2 % darüber.
Wie wirkt die Annahmeregel?	Bei 200 Tausend Vorschlägen: Metropolis 1,4 %, Late Acceptance Hill Climbing 2,2 % (L=500), Threshold Accepting 2,7 % und Great Deluge 3,2 %, alle vier vor Hill Climbing mit Neustarts (4,9 %). Late Acceptance kippt bei zu großem L: L=500 2,2 %, L=700 15,4 %, L=1000 44,2 %, L=3000 147 %.
Wie nah am echten Optimum?	Bei 1 Million Vorschlägen liegt die Kette auf den fünf Instanzen im Mittel unter 0,8 % über dem echten Optimum (CP-SAT); die beste von 15 Ketten mit 200 Tausend Vorschlägen liegt nur 0,08 % über der Schranke.

Grenzen

• Temperatur und Instanz: Der Temperaturbereich muss zur Instanz passen. Die Einheit nimmt die Kantenlänge ab, nicht die Struktur. Nur die Endtemperatur ist eng, die Anfangstemperatur weit.
• Budget: Das nötige Budget wächst stärker als linear mit der Zahl der Stopps; bei knappem Budget ist ein Abstieg gleichwertig.
• Vergleich mit dem Abstieg: Der Vorsprung gilt nur gegen den Abstieg mit vollem Rescan. Mit Kandidatenliste + Don't-Look-Bits (nur 2-opt) dreht sich das Bild bei 200 Tausend Vorschlägen um und ist bei 1 Million gleichauf.
• Gedächtnis: Die Kette vergisst; die letzte Tour liegt im Mittel hinter der besten (1,8 gegen 1,4 %). Gemerkt wird die beste Tour, genutzt wird sie nicht.
• Garantie: Die Theorie (logarithmischer Plan) trägt nur für unendliche Zeit. Im endlichen Budget ist er schlechter als der geometrische Plan.
• Ein Lauf: Die Ketten streuen; ein einzelner Vergleich mit dem Hill Climbing kann kippen. Das Urteil der Demo vergleicht einen Lauf.
• Synthetische Instanzen: euklidisch, gleichverteilt oder in fünf Gruppen, ein Fahrzeug, keine Kapazitäten oder Zeitfenster. Die Zahlen gelten für dieses Szenario und diese Regler.
• Rechenzeit: Je Vorschlag kostet die Python-Schleife ein Mehrfaches einer Bewertung im vektorisierten Abstieg; belegt ist nur die Größenordnung, sie hängt vom Rechner und der Python-Version ab.
• Nicht enthalten: Verfahren mit Störung, Gedächtnis oder mehreren Temperaturen gleichzeitig; sie behandelt die Themenseite zu diesen Verfahren.

Quellen

• Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983): Optimization by simulated annealing. Science 220(4598), 671–680.
• Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N., Teller, A. H., & Teller, E. (1953): Equation of state calculations by fast computing machines. Journal of Chemical Physics 21(6), 1087–1092.
• Hajek, B. (1988): Cooling schedules for optimal annealing. Mathematics of Operations Research 13(2), 311–329.
• Dueck, G., & Scheuer, T. (1990): Threshold Accepting. Dueck, G. (1993): Great Deluge. Burke, E. K., & Bykov, Y. (2012/2017): Late Acceptance Hill Climbing. Namen und Jahre wie in der README der Demo.
• Quelltext, Messreihen und Tests der Demo: github.com/sebastian-hanisch/simulated-annealing-demo.

Die genannten Arbeiten wurden für diese Seite nicht nachgeschlagen. Hajek, Dueck und Scheuer, Dueck sowie Burke und Bykov stehen mit Name und Jahr in der README der Demo; die Angaben zu Kirkpatrick et al. (1983), Metropolis et al. (1953) und die Zeitschriftenangaben stammen aus dem Gedächtnis des Autors und sind nicht gegen die Originale geprüft. Das Bild vom Wanderer im Nebel und die Herkunft des Namens aus dem Abkühlen von Metall sind eigene Veranschaulichungen bzw. Standardwissen und stehen nicht in der README.