Lokale Suche und simulierte Abkühlung: ein Handlungsreisender durch die tschechischen Regionalhauptstädte

Das Optimierungsproblem, das Problem des Handlungsreisenden, der Bergsteigeralgorithmus mit der 2-opt-Nachbarschaft, lokale Minima und Neustarts, simulierte Abkühlung, Temperatur und Abkühlungsplan — auf einer Route durch dreizehn Regionalhauptstädte mit bekanntem Optimum.

13 Minuten Matěj Žalmánek 2026-10-15

Serie KI-Grundlagen Teil 26 von 52

1. Landkarte der künstlichen Intelligenz: was was ist und wie alles zusammenpasst
2. Eine kurze Geschichte der künstlichen Intelligenz: von Turing bis zu Sprachmodellen
3. Daten, Modell, Training, Inferenz: die Grundbegriffe an einem einzigen Beispiel
4. Mathematische Notation lesen: Symbole, Indizes, Summen und Quantoren
5. Mengen und Relationen: der Baukasten, aus dem Definitionen in der KI bestehen
6. Funktionen und Abbildungen: warum jedes KI-Modell eine Funktion ist
7. Logik und Beweise: die Regeln, nach denen KI schließt
8. Graphen und Bäume: die Struktur, auf der Suche und neuronale Netze stehen
9. Lineare Algebra für maschinelles Lernen: Vektoren, Matrizen und warum KI vor allem multipliziert
10. Ableitungen, Gradient und Kettenregel: wie ein Modell herausfindet, in welche Richtung es lernen soll
11. Gradientenabstieg: wie ein Modell lernt
12. Was ist Wahrscheinlichkeit: vom Würfelwurf zu den Kolmogorow-Axiomen
13. Bedingte Wahrscheinlichkeit und der Satz von Bayes: wie du deine Einschätzung änderst, wenn du etwas Neues erfährst
14. Zufallsvariable und Verteilungsfunktion: eine Funktion, die alles über eine Verteilung verrät
15. Dichtefunktion und Wahrscheinlichkeitsfunktion: warum eine stetige Zufallsvariable in einem Punkt die Wahrscheinlichkeit null hat
16. Erwartungswert, Varianz und Kovarianz: wo eine Verteilung liegt, wie breit sie ist und was womit zusammenhängt
17. Überblick über Wahrscheinlichkeitsverteilungen: Bernoulli-, Binomial-, Poisson-, Gleich-, Normal- und Exponentialverteilung
18. Gesetz der großen Zahlen und zentraler Grenzwertsatz: Warum sich Durchschnitte so vorhersagbar verhalten
19. Statistik und Parameterschätzung: Maximum Likelihood, MAP und Konfidenzintervalle
20. Informationstheorie: Entropie, Kreuzentropie und KL-Divergenz — woher Verlustfunktionen kommen
21. Zustandsraumsuche: BFS, DFS, UCS und A* mit Animationen
22. Spiele und Gegner: Minimax, Alpha-Beta-Suche und Monte Carlo Tree Search
23. Constraint Satisfaction: Backtracking, Constraint-Propagierung und AC-3 an Sudoku und einer Karte tschechischer Regionen
24. Logik und wissensbasierte Systeme: Vorwärts- und Rückwärtsverkettung, Resolution und Expertensysteme
25. Planung: STRIPS, die Blockwelt, Heuristiken aus Relaxierung und Planung in KI-Agenten
26. Lokale Suche und simulierte Abkühlung: ein Handlungsreisender durch die tschechischen Regionalhauptstädte
27. Genetische Algorithmen: Population, Kreuzung, Mutation und Selektion am Rucksack für die Wanderung
28. Evolutionsstrategien und genetische Programmierung: von der 1/5-Erfolgsregel zum Keplerschen Gesetz
29. Ameisenkolonieoptimierung: wie eine Pheromonspur einen kurzen Weg findet
30. Partikelschwarmoptimierung: Trägheit, eigene Erfahrung und die Erfahrung des Schwarms
31. Neuroevolution: Evolution der Gewichte und der Gestalt neuronaler Netze und der Algorithmus NEAT
32. Fuzzy-Mengen und Zugehörigkeitsfunktionen: wie man „etwas warm“ aufschreibt
33. Fuzzy-Logik und Wahrscheinlichkeit: warum „etwas warm“ nicht „wahrscheinlich warm“ bedeutet
34. Fuzzy-Logik: t-Normen, Implikationen und WENN–DANN-Regeln
35. Fuzzy-Regelung: Mamdani und Sugeno vom Ventilator bis zum Pendel auf dem Wagen
36. Fuzzy-Clustering: der Algorithmus fuzzy c-means und Punkte zwischen den Clustern
37. Neuro-Fuzzy-Systeme (ANFIS): Fuzzy-Regeln, die aus Daten lernen
38. Markow-Ketten: Übergangsmatrix, stationäre Verteilung und PageRank
39. Hidden-Markov-Modelle: der Viterbi-Algorithmus und das unehrliche Kasino
40. Bayessche Netze: warum das Gras nass ist und was das für den Rasensprenger bedeutet
41. Der Kalman-Filter: wie man aus ungenauen Messungen schätzt, wo ein Auto ist und wie schnell es fährt
42. Arten des maschinellen Lernens: überwacht, unüberwacht, halbüberwacht und mehr
43. Prompts, Kontext und RAG: wie man einem Modell die richtigen Informationen gibt
44. Variational Autoencoder (VAE): neue Bilder aus einem stetigen latenten Raum
45. Generative Adversarial Networks (GAN): der Fälscher gegen den Detektiv
46. Diffusionsmodelle: wie aus reinem Rauschen ein Bild wird
47. Markow-Entscheidungsprozesse: Zustände, Aktionen, Belohnungen und Bellman-Gleichungen
48. Q-Learning und DQN: den Wert von Aktionen lernen, von der Tabelle bis zum neuronalen Netz
49. Policy Gradient und PPO: die Strategie direkt lernen
50. Wie ein KI-Agent funktioniert: ein Sprachmodell in einer Schleife mit Werkzeugen
51. Programmieren mit KI-Agenten: Auftrag, Tests und Kontrolle
52. Bewertung und Sicherheit von KI-Systemen: wie man misst und wie man überwacht

Der ganze Lehrplan der Serie 52 von 83 Themen fertig

Ein Schmied, der eine feste Klinge will, lässt das glühende Metall nicht schlagartig erkalten — er kühlt es langsam ab. So haben die Atome Zeit, eine regelmäßige Anordnung mit der niedrigsten Energie zu finden. Würde er das Metall auf einen Schlag abschrecken, erstarrten die Atome dort, wo sie gerade waren, und die Klinge wäre spröde. 1983 bemerkten Physiker, dass genau das auch Algorithmen plagt, die die beste Lösung suchen: Wenn sie immer nur „bergab“ gehen, erstarren sie in der ersten Mulde. So entstand die simulierte Abkühlung — und mit ihr eine der nützlichsten Ideen der Optimierung.

Mit diesem Teil beginnt das Modul über von der Natur inspirierte Algorithmen. Er knüpft an den Teil Zustandsraumsuche an, in dem der Bergsteigeralgorithmus und die simulierte Abkühlung zum ersten Mal auftauchten.

1. Das Optimierungsproblem

Definition — Optimierungsproblem und Nachbarschaft

Gegeben ist eine Menge zulässiger Lösungen S und eine Zielfunktion f : S → ℝ. Gesucht ist s* = argmin_{s ∈ S} f(s) — die Lösung mit dem kleinsten Wert (bei der Maximierung umgekehrt).

Eine Nachbarschaft ist eine Abbildung N : S → 2^S, die jeder Lösung die Menge der „benachbarten“ Lösungen zuordnet, die aus ihr durch eine kleine Änderung entstehen. Eine Lösung s ist ein lokales Minimum, wenn f(s) ≤ f(s′) für alle s′ ∈ N(s) gilt, und ein globales Minimum, wenn das für alle s′ ∈ S gilt.

2. Das Problem des Handlungsreisenden

Ein Handlungsreisender soll alle dreizehn Regionalhauptstädte Tschechiens besuchen, jede genau einmal, und dorthin zurückkehren, wo er losgefahren ist. Auf welcher Route legt er die kürzeste Strecke zurück? Die Entfernungen messen wir in Luftlinie.

Definition — Problem des Handlungsreisenden (TSP)

Gegeben sind n Städte und Entfernungen d(i, j). Eine Lösung ist eine zyklische Permutation π der Städte; ihre Länge ist f(π) = ∑_k=1ⁿ d(π_k, π_k+1), wobei π_n+1 = π₁.

Es gibt (n − 1)! / 2 verschiedene Rundreisen (unabhängig davon, wo und in welcher Richtung sie beginnen). Die Entscheidungsversion des Problems ist NP-vollständig.

Anzahl der Rundreisen = n! / (n · 2) = (n − 1)! / 2

n!

alle Reihenfolgen, in denen sich n Städte aufschreiben lassen — so viele Permutationen gibt es; jede Rundreise ist darunter aber mehrfach gezählt

n

eine Rundreise hat keinen Anfang: Praha → Brno → … → Praha ist dieselbe Route wie Brno → … → Praha → Brno. Jede Rundreise kann in jeder der n Städte beginnen, daher n-mal weniger

2

die Entfernung hin ist dieselbe wie zurück, also ist eine rückwärts gefahrene Rundreise dieselbe Route mit derselben Länge

Beispiel — die Luftlinie von Praha nach Brno

Die Städte sind durch geografische Breite φ und Länge λ in Grad gegeben. Auf dem Gebiet Tschechiens genügt eine ebene Näherungsprojektion: Ein Breitengrad misst 110,57 km, ein Längengrad 111,32 · cos φ₀ km, wobei φ₀ = 49,8° die Mitte des Landes ist (die Meridiane laufen zum Pol hin zusammen). Dann gilt

d(i, j) = √( (71,85 · Δλ)² + (110,57 · Δφ)² ).

Praha (50,08° n. Br., 14,42° ö. L.), Brno (49,20°, 16,61°)

Δλ = 2,19° → 71,85 · 2,19 = 157,35 km nach Osten

Δφ = −0,88° → 110,57 · 0,88 = 97,30 km nach Süden

d = √(157,35² + 97,30²) = √(24 759 + 9 467) = √34 226 ≈ 185,0 km

Der Fehler gegenüber der exakten Rechnung auf der Kugel liegt bei solchen Entfernungen bei etwa 1 %; für den Vergleich von Routen spielt das keine Rolle.

Dreizehn Städte sind noch wenig genug, um das Optimum exakt zu berechnen — mit der dynamischen Programmierung nach Held und Karp über Teilmengen der Städte, die 2ⁿ · n² Schritte statt (n − 1)! braucht. Die kürzeste Rundreise misst 1 060,4 km. Dadurch sehen wir bei jedem weiteren Algorithmus genau, wie nah er dem Optimum gekommen ist:

Algorithmus — dynamische Programmierung nach Held und Karp (1962)

Nummerieren wir die Städte 0, …, n − 1 und beginnen in Stadt 0. Für jede Menge von Städten M ∋ 0 und jede Stadt j ∈ M sei D(M, j) die Länge des kürzesten Weges, der in 0 startet, genau die Städte aus M durchläuft und in j endet. Dann gilt

D({0}, 0) = 0,   D(M, j) = min_{k ∈ M ∖ {j}} [ D(M ∖ {j}, k) + d(k, j) ],

und die Länge der optimalen Rundreise ist min_{j ≠ 0} [ D(alle Städte, j) + d(j, 0) ]. Es gibt höchstens 2ⁿ · n Werte D, und jeder ist das Minimum von höchstens n Zahlen.

n = 13:   2¹³ · 13² = 8 192 · 169 = 1 384 448 Schritte

alle Reihenfolgen ab einem festen Start durchgehen: 12! = 479 001 600 — etwa 346-mal mehr

3. Bergsteigeralgorithmus und die 2-opt-Nachbarschaft

Definition — der 2-opt-Zug

Ein 2-opt-Zug entfernt aus der Rundreise zwei nicht benachbarte Kanten (a, b) und (e, f) und ersetzt sie durch die Kanten (a, e) und (b, f) — kehrt also die Reihenfolge der Städte zwischen b und e um. Die Länge ändert sich um Δ = d(a, e) + d(b, f) − d(a, b) − d(e, f). Die Nachbarschaft einer Route durch n Städte hat (n − 1)(n − 2) / 2 Züge.

Δ = d(a, e) + d(b, f) − (d(a, b) + d(e, f))

Δ

um wie viel die Rundreise länger wird; ein negatives Δ bedeutet eine Verkürzung. Nach dem Vorzeichen entscheiden sowohl der Bergsteigeralgorithmus als auch die simulierte Abkühlung, deshalb brauchen wir es billig

d(a, e) + d(b, f)

zwei neue Kanten, mit denen wir die aufgeschnittenen Enden wieder verbinden — sie werden addiert, weil die Route um sie länger wird

d(a, b) + d(e, f)

die zwei Kanten, die wir durchgeschnitten haben — sie werden abgezogen, weil sie aus der Route verschwinden. Den Abschnitt zwischen b und e fahren wir nur rückwärts, und die Entfernungen sind symmetrisch, also ändert sich seine Länge nicht und er fehlt in der Formel

Algorithmus — Bergsteigeralgorithmus (steilster Abstieg)

Beginne mit einer zufälligen Lösung s. Wiederhole: Finde s′ ∈ N(s) mit dem kleinsten f(s′); ist f(s′) < f(s), gehe zu s′, sonst höre auf — s ist ein lokales Minimum.

def delta(c, i, j):                    # 2-opt-Zug: c[i..j] umkehren
    a, b = c[i - 1], c[i]
    e, f = c[j], c[(j + 1) % len(c)]
    return d(a, e) + d(b, f) - d(a, b) - d(e, f)

def horolezec(c):
    n = len(c)
    while True:
        tahy = [(i, j) for i in range(1, n - 1) for j in range(i + 1, n)]
        i, j = min(tahy, key=lambda t: delta(c, *t))   # steilster Abstieg
        if delta(c, i, j) >= 0:                        # nichts verkürzt die Route
            return c                                    # lokales Minimum
        c = c[:i] + c[i:j + 1][::-1] + c[j + 1:]

Die erste Stadt lassen wir an ihrem Platz (i ≥ 1) — eine Rundreise hat keinen Anfang, also brächte das nichts Neues. Für n = 13 ergeben die Paare 1 ≤ i < j ≤ 12 genau 12 · 11 / 2 = 66 Züge.

Von einer zufälligen, 2 402 km langen Rundreise kommt der Bergsteigeralgorithmus in 8 Schritten auf 1 065,8 km — und bleibt dort stehen. Bis zum Optimum fehlen nur 5 km, aber kein einzelner 2-opt-Zug verkürzt die Route noch. Der Bergsteiger steckt in einem lokalen Minimum und weiß es nicht:

4. Wo der Bergsteigeralgorithmus hängen bleibt

Von hundert zufälligen Starts endete der Bergsteigeralgorithmus 61-mal im Optimum. In den übrigen 39 Fällen blieb er woanders hängen, im schlimmsten Fall bei 1 162,6 km — hundert Kilometer daneben. Es gibt drei Fallen:

• Lokales Minimum — eine Mulde, aus der jeder Schritt bergauf führt.
• Plateau — alle Nachbarn sind gleich gut, sodass der Bergsteiger nicht weiß, wohin er gehen soll.
• Grat — eine gute Richtung gibt es, aber sie verläuft entlang keines einzelnen Zuges; man erreicht sie nur über schlechtere Lösungen.

Beispiel — warum der Bergsteigeralgorithmus aus 1 065,8 km nicht herauskommt

Der Bergsteigeralgorithmus endete beim ersten Start auf der Rundreise Zlín → Ostrava → Olomouc → Pardubice → Hradec Králové → Liberec → Ústí nad Labem → Karlovy Vary → Plzeň → Praha → České Budějovice → Jihlava → Brno → Zlín. Wir berechnen Δ für alle 66 2-opt-Züge: Einer davon (alles außer der ersten Stadt umkehren) ergibt dieselbe Rundreise in umgekehrter Richtung und Δ = 0, alle anderen verlängern die Route. Der günstigste davon kehrt das Paar Pardubice – Hradec Králové um:

a = Olomouc, b = Pardubice, e = Hradec Králové, f = Liberec

Δ = d(a, e) + d(b, f) − d(a, b) − d(e, f)

  = 122,9 + 95,9 − 116,8 − 83,0 = +19,0 km

Jeder einzelne Zug verlängert die Route also um mindestens 19,0 km — dabei ist das Optimum um bloße 5,4 km kürzer. Der Weg dorthin führt über schlechtere Rundreisen, und die nimmt der Bergsteigeralgorithmus nie an.

Das einfachste Gegenmittel sind zufällige Neustarts: den Bergsteiger erneut von einer anderen Stelle loslaufen lassen und das beste Ergebnis behalten. Gelingt ein Start mit der Wahrscheinlichkeit 0,61, dann gelingt von fünf Starts mindestens einer mit der Wahrscheinlichkeit 1 − 0,39⁵ ≈ 99 %. Bei einem kleinen Problem reicht das. Bei einem großen gibt es Millionen von Mulden, und man bräuchte viel zu viele Neustarts.

P_r = 1 − (1 − p)^r

P_r

die Wahrscheinlichkeit, dass mindestens einer von r Starts das Optimum findet — wir berechnen sie über das Gegenereignis, weil „mindestens einer“ viele Formen hat, „kein einziger“ dagegen nur eine

1 − p

die Wahrscheinlichkeit, dass ein Start scheitert (bei uns 0,39 aus hundert Versuchen)

r

die Anzahl der Starts im Exponenten: Die Starts sind unabhängig (jeder hat einen anderen Zufalls-Seed), also multiplizieren sich die Wahrscheinlichkeiten des Scheiterns

5. Simulierte Abkühlung

Algorithmus — simulierte Abkühlung

Beginne mit einer zufälligen Lösung s und der Anfangstemperatur T₀. In jeder Iteration:

1. wähle einen zufälligen Nachbarn s′ ∈ N(s) und berechne Δ = f(s′) − f(s);
2. ist Δ ≤ 0, gehe zu s′; sonst gehe mit der Wahrscheinlichkeit e^−Δ/T dorthin (Metropolis-Kriterium);
3. senke die Temperatur nach dem Abkühlungsplan, zum Beispiel T ← α · T mit 0 < α < 1.

Gib die beste Lösung zurück, die du unterwegs gesehen hast.

P(annehmen) = min(1, e^{−Δ / T})

P(annehmen)

mit welcher Wahrscheinlichkeit wir zum vorgeschlagenen Nachbarn wechseln; im Programm ziehen wir u gleichverteilt aus [0, 1) und nehmen den Zug an, wenn u < P

min(1, …)

bei einer Verbesserung (Δ ≤ 0) ist die Exponentialfunktion ≥ 1, und eine Wahrscheinlichkeit darf 1 nicht überschreiten — ein besserer Schritt wird also immer angenommen, genau wie beim Bergsteigeralgorithmus

Δ

um wie viel der Nachbar schlechter ist, in km. Es steht mit negativem Vorzeichen im Exponenten, also multipliziert jeder weitere Kilometer Verschlechterung die Chance mit derselben Zahl kleiner als 1 — große Verschlechterungen sind exponentiell seltener als kleine

T

die Temperatur, in denselben Einheiten wie Δ (km). Sie teilt Δ und legt damit den Maßstab fest: Eine Verschlechterung um T km kommt bei jeder Temperatur mit der Wahrscheinlichkeit 1/e ≈ 0,37 durch. Ein hohes T macht große Verschlechterungen „klein“, T → 0 verbietet alle

Die Regel für die Annahme eines schlechteren Schritts stammt aus der Physik: 1953 benutzten sie Nicholas Metropolis und seine Kollegen, um Atome im thermischen Gleichgewicht zu simulieren, wo die Wahrscheinlichkeit eines Zustands mit der Energie E proportional zu e^−E/kT ist. Für die Optimierung passten sie 1983 unabhängig voneinander Kirkpatrick, Gelatt und Vecchi von IBM an — und zwei Jahre später, ebenfalls unabhängig, der slowakische Physiker Vladimír Černý, und zwar gerade am Problem des Handlungsreisenden.

import math, random

def zihani(c, T0=200, Tk=0.5, K=10_000):
    alfa = (Tk / T0) ** (1 / K)          # geometrische Abkühlung
    T, delka = T0, delka_okruhu(c)
    nej, nej_delka = c, delka
    for k in range(K):
        i, j = sorted(random.randint(1, len(c) - 1) for _ in range(2))
        if i != j:                          # i = j: kein Zug
            D = delta(c, i, j)
            if D <= 0 or random.random() < math.exp(-D / T):
                c = c[:i] + c[i:j + 1][::-1] + c[j + 1:]
                delka += D
                if delka < nej_delka:
                    nej, nej_delka = c, delka
        T *= alfa
    return nej

Wie das in Wirklichkeit aussieht: die ersten sechs Iterationen unseres Laufs und sechs Iterationen aus seiner Mitte. p ist die Annahmewahrscheinlichkeit min(1, e^−Δ/T), u die gezogene Zahl; ein verschlechternder Zug kommt durch, wenn u < p.

Am Anfang, bei T ≈ 200, kommt sogar ein Zug durch, der die Route um 146,6 km verlängert — die Chance ist 0,48, und gezogen wurde u = 0,14. In der Mitte des Laufs ist T = 10, und die Route liegt schon im Optimum; Züge, die sie um 70 und mehr Kilometer verlängern würden, haben eine Chance unter einem Promille und werden alle abgelehnt. Manchmal treffen beide Zufallszahlen dieselbe Stelle (i = j), und die Iteration schlägt nichts vor — im ganzen Lauf geschah das 824-mal.

Satz — Boltzmann-Verteilung (heutige Formulierung)

Halten wir die Temperatur T fest und schlagen Nachbarn symmetrisch vor (der Nachbar s′ wird von s aus mit derselben Wahrscheinlichkeit vorgeschlagen wie s von s′ aus — bei 2-opt gilt das, weil derselbe Zug (i, j) auch zurückführt), dann ist der Metropolis-Prozess eine Markow-Kette, deren stationäre Verteilung gegeben ist durch

π_T(s) = e^−f(s)/T / Z(T)

π_T(s)

wie oft wir uns nach langem Umherirren bei der Temperatur T in der Lösung s befinden

e^−f(s)/T

das Gewicht einer Lösung: je kürzer die Route f(s), desto größer. Es ist genau das Gewicht, das das Metropolis-Kriterium ausbalanciert — das Verhältnis der Gewichte zweier Nachbarn ist e^−Δ/T

Z(T)

die Summe der Gewichte über alle Lösungen; wir teilen durch sie, damit sich die Wahrscheinlichkeiten zu 1 addieren

Beweis (Bedingung des detaillierten Gleichgewichts): Für Nachbarn mit f(s′) = f(s) + Δ, Δ > 0, ist der Fluss von s nach s′ proportional zu π(s) · e^−Δ/T und der Fluss zurück zu π(s′) · 1. Für π = π_T sind beide Ausdrücke gleich e^−f(s′)/T / Z, die Flüsse gleichen sich aus, und die Verteilung ändert sich nicht mehr.

Optimum (1 060,4 km) gegen die Falle des Bergsteigeralgorithmus (1 065,8 km): Verhältnis der Häufigkeiten e^5,38/T

T = 100: 1,06   T = 10: 1,71   T = 1: 217   T = 0,5: 47 089

6. Temperatur und Abkühlungsplan

Welche Chance hat ein Schritt, der die Route um 20 km verlängert? Das hängt von der Temperatur ab:

Bei 200 kommt fast jeder verschlechternde Schritt durch, bei 0,5 keiner — dann verhält sich die simulierte Abkühlung wie der Bergsteigeralgorithmus. Der Abkühlungsplan bestimmt, wie lange der Algorithmus „umherirrt“ und wie lange er „absteigt“. Der günstigste Ausweg aus der Falle des Bergsteigeralgorithmus (+19,0 km, siehe oben) käme bei T = 50 mit der Wahrscheinlichkeit 0,68 durch, bei T = 10 mit 0,15 und bei T = 2 praktisch nie.

T_k = T₀ · α^k,   α = (T_K / T₀)^1/K

T_k

die Temperatur in der k-ten Iteration — sie bestimmt, wie große Verschlechterungen in diesem Moment noch angenommen werden

T₀

die Anfangstemperatur; man wählt sie so, dass am Anfang die meisten Verschlechterungen durchkommen — bei uns 200 km, mehr als ein typischer 2-opt-Zug auf einer zufälligen Route

α

der Abkühlungskoeffizient knapp unter 1; wir berechnen ihn aus der Zieltemperatur T_K und der Anzahl der Iterationen K, damit der Lauf genau dort endet, wo wir wollen

k

die Nummer der Iteration im Exponenten: Jede Iteration multipliziert die Temperatur mit derselben Zahl, also sinkt die Temperatur in gleich vielen Iterationen immer um dasselbe Verhältnis — von 200 auf 100 dauert es genauso lange wie von 1 auf 0,5

Satz — Konvergenz der simulierten Abkühlung

Sinkt die Temperatur langsam genug, nämlich logarithmisch: T_k = c / ln(k + 1) mit einer ausreichend großen Konstante c, dann strebt die Wahrscheinlichkeit, dass die simulierte Abkühlung im globalen Minimum endet, mit der Anzahl der Iterationen gegen eins (Hajek, 1988).

„Ausreichend groß“ heißt genau c ≥ d*, wobei d* die Tiefe des tiefsten lokalen Minimums ist, das nicht global ist: um wie viel ein Weg aus ihm mindestens ansteigen muss, bevor er zu einer besseren Lösung gelangt.

würde c = 20 km reichen, hätten wir die Temperatur 0,5 erst bei ln(k + 1) = 20 / 0,5 = 40,

also nach k ≈ e⁴⁰ ≈ 2,4 · 10¹⁷ Iterationen — rund milliardenmal mehr, als es Rundreisen überhaupt gibt (239 500 800)

7. Simulierte Abkühlung für die Regionalhauptstädte

Lassen wir die simulierte Abkühlung auf dasselbe Problem los: 10 000 Iterationen, die Temperatur sinkt geometrisch von 200 auf 0,5. Die Karte zeigt, wie die Route am Anfang und nach 1 000, 3 000, 5 000 und 10 000 Iterationen aussah:

Nach tausend Iterationen ist die Route immer noch chaotisch (1 985 km) — bei hoher Temperatur nimmt die simulierte Abkühlung fast alles an. Nach dreitausend hat sie schon Gestalt (1 159 km), und nach fünftausend liegt sie im Optimum, 1 060,4 km. Von den 1 498 angenommenen Zügen waren 695 verschlechternd; der Bergsteigeralgorithmus hätte keinen einzigen davon gemacht. Das Diagramm zeigt, wie die Routenlänge auf und ab springt, bis die Temperatur sinkt:

Der Übergang vom Umherirren zum Abstieg zeigt sich auch an der Zahl der angenommenen Züge in den einzelnen Tausenderblöcken der Iterationen: 597, 411, 232, 104, 35, 35, 26, 21, 26, 11. Im ersten Tausend, wenn T zwischen 200 und 110 liegt, wird mehr als die Hälfte der Vorschläge angenommen. Ab dem fünften Tausend (T unter 20) nur noch Dutzende; verschlechternd waren davon 37, darunter 26 winzige, unter 3 km.

Und das ist kein Glück eines einzelnen Laufs: Von hundert Läufen mit verschiedenen Seeds endeten 98 im Optimum und die übrigen zwei knapp 3 km daneben. Gegenüber 61 % beim Bergsteigeralgorithmus mit einem einzigen Start ist das ein großer Unterschied.

8. Wann sich die simulierte Abkühlung lohnt

Fairerweise muss man sagen: Die simulierte Abkühlung machte 10 000 Iterationen, der Bergsteigeralgorithmus mit einem Start nur etwa sechshundert Auswertungen. Bei einem kleinen Problem hätte der Bergsteigeralgorithmus mit Neustarts zum selben Preis genauso gut abgeschnitten. Der Unterschied zeigt sich bei einem größeren Problem. Nehmen wir 60 zufällig verteilte Städte und geben beiden Algorithmen dasselbe Budget — 200 000 ausgewertete 2-opt-Züge:

Der Bergsteigeralgorithmus passte nur zweimal ins Budget: Bei 60 Städten hat die Nachbarschaft 1 711 Züge, und der steilste Abstieg prüft sie in jedem Schritt alle. Die simulierte Abkühlung probiert jeweils einen zufälligen Zug und verteilt dasselbe Budget auf die Erkundung der ganzen Landschaft. Jeder ihrer drei Läufe endete besser als der Bergsteigeralgorithmus.

9. Simulierte Abkühlung in der künstlichen Intelligenz und anderswo

• Chipentwurf und Zeitpläne. Das Platzieren von Bauteilen auf einem Chip war in den Achtzigerjahren einer der ersten großen Einsätze der simulierten Abkühlung; bis heute nutzt man sie für Zeitpläne, Fahrzeugrouten oder die Anordnung von Lagern.
• Training neuronaler Netze. Der stochastische Gradientenabstieg berechnet den Gradienten aus einem kleinen Datenbatch, und so ist jeder Schritt ein wenig zufällig — ähnlich wie die simulierte Abkühlung kann er aus einer flachen Mulde herausrutschen. Lernratenpläne, die die Lernrate allmählich senken, heißen sogar cosine annealing.
• Die Temperatur von Sprachmodellen. Wenn ein Sprachmodell das nächste Wort wählt, teilt es die Scores der Wörter durch eine Temperatur T und wandelt sie mit der Softmax-Funktion in Wahrscheinlichkeiten proportional zu e^z/T um — dieselbe Boltzmann-Formel. Eine hohe Temperatur bedeutet einfallsreicheren und riskanteren Text, eine niedrige vorsichtigeren und vorhersehbareren.
• Quantenannealing. Spezialisierte Computer (zum Beispiel von D-Wave) suchen das Energieminimum physikalisch und nutzen dabei Quanteneffekte. Ob und wann sie schneller sind als klassische Algorithmen, ist immer noch Gegenstand der Forschung.

Beispiel — Temperatur bei der Wahl des nächsten Wortes

Ein Modell gibt drei Kandidaten für das nächste Wort die Scores z = (2, 1, 0). Die Wahrscheinlichkeit des i-ten Wortes ist p_i = e^z_i/T / ∑_j e^z_j/T — die Boltzmann-Verteilung aus dem Abschnitt über die simulierte Abkühlung, nur mit der „Energie“ −z.

T = 1:   (e², e¹, e⁰) = (7,39; 2,72; 1), Summe 11,11 → 0,665; 0,245; 0,090

T = 0,5:   (e⁴, e², 1) = (54,6; 7,39; 1), Summe 62,99 → 0,867; 0,117; 0,016

T = 2:   (e¹, e^0,5, 1) = (2,72; 1,65; 1), Summe 5,37 → 0,506; 0,307; 0,186

Eine niedrigere Temperatur verschiebt die Wahrscheinlichkeit zum besten Kandidaten (bei T → 0 ist es immer er), eine höhere verteilt sie auch auf weniger wahrscheinliche Wörter — genau wie die simulierte Abkühlung bei hoher Temperatur auch schlechtere Routen annimmt.

10. Zusammenfassung

• Ein Optimierungsproblem sucht die Lösung mit dem besten Wert der Zielfunktion; die lokale Suche bewegt sich in der Nachbarschaft der aktuellen Lösung.
• Der Bergsteigeralgorithmus geht immer zum besseren Nachbarn und bleibt in einem lokalen Minimum hängen — bei den Regionalhauptstädten in 39 von 100 Starts. Zufällige Neustarts helfen bei kleinen Problemen.
• Die simulierte Abkühlung nimmt auch schlechtere Schritte an, mit der Wahrscheinlichkeit e^−Δ/T; mit sinkender Temperatur geht sie von der Erkundung zum Abstieg über.
• Bei den Regionalhauptstädten fand sie das Optimum in 98 von 100 Läufen; bei einem größeren Problem schlug sie den Bergsteigeralgorithmus mit demselben Budget.
• Dieselbe Boltzmann-Formel lebt in der Temperatur von Sprachmodellen weiter und die Idee des Abkühlens in den Lernratenplänen neuronaler Netze.

Willst du es selbst ausprobieren? Lass einen KI-Agenten die simulierte Abkühlung für deine eigene Route schreiben — etwa über die Orte, die du in den Ferien besuchen willst — und probiere aus, was zu schnelles Abkühlen anrichtet.

Siehst du das anders? Schreib an support@coden-app.com.