Simuliertes Abkühlen

Simuliertes Abkühlen, eingeführt von Kirkpatrick Gelatt und Vecchi (1983) und unabhängig davon von Cerny (1985), ist eine Einzel-Lösungs-Metaheuristik, die das langsame Abkühlen von Metallen zu niederenergetischen Kristallstrukturen nachbildet. Der Algorithmus startet bei einer hohen Anfangstemperatur T0 und bewertet jede Nachbarschaftsbewegung über Δ = f(neu) − f(aktuell): verbessernde Schritte (Δ < 0) werden stets akzeptiert, verschlechternde (Δ > 0) mit der Metropolis-Wahrscheinlichkeit P = exp(−Δ / T). Die Akzeptanz verschlechternder Schritte ist das definierende Merkmal, das den Ausbruch aus lokalen Optima ermöglicht. Die Temperatur sinkt gemäss einem Abkühlplan: geometrisch T_k+1 = αT_k mit α ∈ [0.85, 0.99], logarithmisch (Geman und Geman 1984, theoretisch konvergent aber langsam) oder adaptiv. Kühlplan, Anfangstemperatur (Faustregel: initiale Akzeptanzrate etwa 80 Prozent), Anzahl Versuche pro Temperatur und Abbruchkriterium sind die kritischen Parameter. Gegenüber genetischen Algorithmen hält das Verfahren nur eine Lösung, benötigt keine Population und minimalen Speicher. Anwendungen: VLSI-Platzierung, Tourenplanung, Scheduling, Layoutplanung. Bei kombinatorischen Problemen konkurriert es eng mit Tabu Search. Literatur: Aarts und Korst (1989), Henderson Jacobson Johnson (2003).