Simulierte Abkühlung

Grundidee und Bedeutung

Die simulierte Abkühlung (englisch simulated annealing, auch simuliertes Tempern oder simulierte Vergütung) ist ein heuristisches Approximationsverfahren. Sie sucht Näherungslösungen für Optimierungsprobleme, bei denen wegen ihrer hohen Komplexität weder alle Möglichkeiten vollständig ausprobiert noch gewöhnliche mathematische Optimierungsverfahren sinnvoll eingesetzt werden können.

Vorbild ist das Glühen in der Metallurgie: Ein erhitztes Metall wird langsam abgekühlt, sodass seine Atome Zeit haben, sich zu ordnen und stabile Kristalle zu bilden. Dadurch entsteht ein energiearmer Zustand nahe am Optimum. Im Algorithmus entspricht die „Temperatur“ der Bereitschaft, vorübergehend auch eine schlechtere Lösung anzunehmen. So kann die Suche ein lokales Optimum verlassen und möglicherweise ein besseres, globales Optimum erreichen. Im Unterschied zum Metropolis-Algorithmus wird die Temperatur im Verlauf der Iterationen abgesenkt.

Anwendungen sind beispielsweise das Floorplanning beim Chipentwurf sowie die Standort- und Routenplanung. In den 1990er Jahren wurden außerdem Quantenversionen mit Tunnelung zwischen den Minima eingeführt.

Physikalische Motivation

Die physikalische Grundlage liefert die Boltzmann-Statistik. Gesucht wird der energetisch günstigste Zustand eines Systems. Die Wahrscheinlichkeit, einen Mikrozustand mit Energie mindestens E_j anzutreffen, ist proportional zu

p(E_j) ∝ exp(−E_j/(k_B T)),

wobei k_B die Boltzmann-Konstante und T die Temperatur ist. Bezeichnet E_0 die Energie des günstigsten Zustands, kann die Verteilung auch geschrieben werden als

p(E_j) ∝ exp(−(E_j−E_0)/(k_B T)).

Da E_0 der energetisch günstigste Zustand ist, gilt E_j−E_0 ≥ 0. Außerdem sind k_B > 0 und T > 0. Der Exponent ist deshalb negativ. Wenn die Temperatur sinkt, wird sein Betrag größer; damit nimmt die Wahrscheinlichkeit ab, einen angeregten Zustand mit mindestens der Energie E_j anzutreffen. Wird ein System langsam abgekühlt, befindet es sich daher mit immer größerer Wahrscheinlichkeit im energetisch günstigsten Zustand. Diese Entwicklung bildet der Optimierungsalgorithmus nach.

Mathematische Problemstellung

Gegeben sind:

• ein Lösungsraum D, • eine Fitnessfunktion f: D → ℝ, die jeder Lösung einen Wert zuordnet, • ein Abbruchkriterium, • ein Umgebungsbegriff U: D → ℘(D), wobei ℘(D) die Potenzmenge von D ist.

Gesucht wird eine approximative Lösung des globalen Minimums von f über D, also ein x ∈ D mit möglichst kleinem Wert f(x). Ein Maximierungsproblem lässt sich darauf zurückführen, indem man f negiert.

Die Umgebung U(x) beschreibt die Lösungen, die als Nachbarn einer aktuellen Lösung x gelten. Aus ihr wird während der Suche eine benachbarte Lösung y ∈ U(x) erzeugt. Wie diese Nachbarschaft festgelegt wird, hängt vom jeweiligen Optimierungsproblem ab.

Ablauf des Algorithmus

Zu Beginn wählt man eine Startlösung x ∈ D und speichert sie zugleich als bisher beste Lösung x_approx. Außerdem wird eine Folge positiver Temperaturen (T_t)_{t∈ℕ} gewählt, die monoton gegen null fällt; der Iterationszähler wird auf t = 0 gesetzt.

In jeder Iteration läuft die Suche so ab:

• Aus der Umgebung U(x) wird zufällig ein Nachbar y ausgewählt. • Ist f(y) ≤ f(x), wird y immer als neue aktuelle Lösung übernommen. • Ist y schlechter, wird es nur mit der Wahrscheinlichkeit exp(−(f(y)−f(x))/T_t) übernommen. • Falls die dadurch erreichte aktuelle Lösung besser als die bisher beste ist, also f(x) < f(x_approx) gilt, wird x_approx = x gesetzt. • Danach wird t um 1 erhöht. Solange das Abbruchkriterium nicht erfüllt ist, beginnt die nächste Iteration.

Am Ende enthält x_approx die beste während des Programmlaufs gefundene Lösung.

Temperatur, Nachbarschaft und Abbruch

Die Wahrscheinlichkeit, eine Verschlechterung zu akzeptieren, wird kleiner, wenn die Differenz f(y)−f(x) größer ist. Sie nimmt auch im Laufe der Suche ab, weil die Temperaturfolge T_t monoton fällt. Bei hoher Temperatur sind daher größere zufällige Abweichungen möglich; bei niedriger Temperatur verhält sich das Verfahren zunehmend wie ein Bergsteigeralgorithmus, der vor allem Verbesserungen verfolgt.

Die Bildung eines Nachbarn richtet sich nach dem Problem. Häufig gilt in der Informatik D = {0,1}^n, und eine Lösung x = (x_1,x_2,…,x_n) wird als Bit-Vektor dargestellt. Ein Nachbar kann dann erzeugt werden, indem man ein Bit oder wenige Bits flippt, also ihre Werte invertiert.

Als Abbruchbedingungen kommen unter anderem eine maximale Zahl von Durchläufen, das Erreichen einer ausreichenden Fitness, eine Untergrenze für die Temperatur oder eine festgelegte Zahl t von Zeitpunkten infrage, während der sich x_approx nicht mehr geändert hat.

Anschauliches Landschaftsmodell

Das Verfahren lässt sich als Suche nach dem tiefsten Punkt einer zweidimensionalen Landschaft mit vielen unterschiedlich tiefen Dellen vorstellen. Eine einfache lokale Suche ähnelt einer Kugel, die stets bergab rollt: Sie erreicht das nächste lokale Minimum und bleibt dort liegen, obwohl eine andere Delle tiefer sein kann.

Bei der simulierten Abkühlung erhält die Kugel wiederholt Stöße, die mit fortschreitender Abkühlung schwächer werden. Ein Stoß soll stark genug sein, um sie aus einer flachen Delle, also einem lokalen Minimum, zu befreien. Gegen Ende soll er jedoch nicht mehr ausreichen, um das globale Minimum zu verlassen.

Bei einer Maximumsuche wirken die Bewegungen entsprechend in einer Landschaft mit vielen Gipfeln. Die bei hoher Temperatur starke Rauschbewegung ermöglicht es, lokale Maxima schnell wieder zu verlassen. Durch die sinkende Temperatur wird das globale Maximum schließlich nicht mehr verlassen. Deshalb kann simulierte Abkühlung bessere Ergebnisse liefern als ein einfacher Bergsteigeralgorithmus.