Was ist Simulated Annealing?
Simulated Annealing (deutsch: simulierte Abkühlung) ist eine Metaheuristik für schwere Optimierungsprobleme, entwickelt von Scott Kirkpatrick, Daniel Gelatt und Mario Vecchi (1983) sowie unabhängig von V. Černý (1985). Der Name kommt vom Glühen in der Metallurgie: Wird Metall langsam abgekühlt, ordnen sich die Atome zu einem energiearmen, regelmäßigen Kristallgitter an – bei zu schneller Abkühlung entstehen Fehler.
Wie funktioniert es?
Simulated Annealing startet mit einer beliebigen Lösung und wandert durch den Suchraum, indem es benachbarte Lösungen probiert. Entscheidend ist das Metropolis-Kriterium: Verschlechterungen werden nicht sofort verworfen, sondern mit Wahrscheinlichkeit
p = exp(-ΔE / T)akzeptiert. Dabei ist ΔE die Qualitätsverschlechterung und T die aktuelle Temperatur. Hohe Temperaturen erlauben viele „schlechte" Züge (Exploration), niedrige fast keine (Ausbeutung, Konvergenz gegen ein lokales Optimum). Die Temperatur sinkt nach einem Abkühlplan, üblich ist geometrische Kühlung
T = T₀ · α^t mit α ≈ 0,9–0,99Stärken und Grenzen
Der Algorithmus ist einfach zu implementieren, robust und braucht kein Gedächtnis. Er eignet sich für viele NP-vollständige Probleme wie das Handelsreisendenproblem, VLSI-Layout, Job-Shop-Scheduling oder maschinelles Lernen (Modell-Pruning, Training). Beweisbar global optimal ist er nur bei einem logarithmischen Abkühlplan, der in der Praxis zu langsam ist – deshalb bleibt er eine Heuristik ohne Optimum-Garantie.
Abgrenzung
Simulated Annealing ist eine Einzel-Lösungs-Suche mit Zufallsakzeptanz: Der Genetische Algorithmus arbeitet populationbasiert, die Tabu-Suche nutzt deterministisches Gedächtnis statt Zufall, und einfaches Hill-Climbing akzeptiert grundsätzlich keine Verschlechterungen. Damit ist Simulated Annealing oft die beste Wahl, wenn der Suchraum viele lokale Optima hat und man schnell eine sehr gute Lösung braucht.