2D-Visualisierung der Verfahren Simulated Annealing, Toleranzschwellen-Algorithmus und Sintflut-Algorithmus

 

Beschreibung der Algorithmen

Der Ursprung aller drei Algorithmen liegt in der Übertragung eines Verfahrens aus der Werkstoffphysik auf die Optimierungstheorie. Seit den 50er Jahren wird in der Forschung zur Herstellung von besonders reinen Kristallstrukturen das Verfahren der langsamen Abkühlung von Schmelzen angewandt. Metalle bilden Kristallstrukturen, was heißt, daß die Atome sich iner einer regelmäßigen Struktur zueinander gruppieren. Eine Energiebilanz dieser Kristalle ist umso günstiger, je reiner sie sind. Je weniger Fehler in dieser Anordnung vorhanden sind, desto mehr entspricht die Eigenschaft des Materials der theoretischen Eigenschaft des Metalls. In der Natur kommen solche reinen Kristalle praktisch nicht vor: beim schnellen Abkühlen einer Schmelze bleiben Atome auf sogenannten Fehlstellen sitzen und stören dadurch die Struktur des Kristalls. Wie eine solche Fehlstelle zu verstehen ist zeigt das folgende Bild:

b1.gif (1870 Byte) siehe folgenden Text

Wird die Schmelze unter Zufuhr von Wärme sehr langsam abgekühlt, so erlaubt es die zugeführte kinetische Energie den Atomen das zu überwinden, und so den energetisch günstigeren Platz einzunehmen. Dadurch ist der Kristall der indealen Struktur um einen Schritt nährer und erhält eine günstigere Energiebilanz. Die zugeführte Energie muß sehr genau dosiert werden, um einerseits den beschriebenen Effekt zu erhalten, andererseits aber das Erstarren zu verhindern. Dieser Prozeß hängt hauptsächlich von der Erfahrung des Ausführenden ab; er muß die Temperatur, die Abkühlgeschwindigkeit, usw. für das jeweilige Metall herausfinden. (-> entspricht einem heuristischen Verfahren).
Die Verbindung zwischen diesem physikalischen Verfahren und der Optimierungstheorie wurde von drei Wissenschaftler 1983 in den IBM-Laboratorien von Yorktown Heights gefunden.

c't 1/94:
Ein Atom ist von seinem idealen Gitterplatz durch eine Barriere getrennt. Der ideale Gitterplatz stellt für das Atom gleichzeitig das globale Energieminimum G dar, es ist jedoch im lokalen Minimum L gefangen.
Die Wahrscheinlichkeit P(De), mit der das Atom die Barriere überwindet beträgt: P(E)=exp(-DE/k¥T))
T ist dabei die Temperatur und k die Boltzman-Konstante. Sie stellt den Zusammenhang zwischen der Temperatur eines Körpers und der kinetischen Energie der Atome, die ihn aufbauen, her. Mit zunehmender Temperatur und damit wachsender kinetischen Energie des Atoms steigt auch die Wahrscheinlichkeit P(E).

Bei einem iterativen Algorithmus wird z.B. beim Vertreterproblem nur die Variante akzeptiert, die zu einer Verringerung des Gesamtweges führt. Dies führt im Regelfall dazu, daß das Verfahren in einem lokalen Minimum steckenbleibt, da im Einzelfall immer zugunsten einer lokal günstigeren Variante entschieden wird, ohne das globale Minimum im Auge zu behalten. Dieses Verhalten entspricht dem Verhalten der Kristallstruktur eines zu schnell erstarrenden Metalles, wo einzelne Atome eben auch in energetisch schlechteren Zuständen verbleiben, weil ihnen die kinetische Energie fehlt, sich aus diesem Zustand wieder zu befreien (der Weg würde über einen ungünstigeren Energiezustand führen was bei einem iterativen Verfahren die Optimierungsvorschrift nicht erlaubt).Das Problem der Wissenschaftler lag nun darin, die Temperatur (beim Abkühlen der Schmelze) in das iterative Verfahren mitaufzunehmen.
Ein ähnliches Problem wurde schon in den fünfziger Jahren durch eine andere Gruppe von Wissenschaftler gelöst, um eine Computersimulation von physikalischen Systemen zu erzeugen.

c't 1/94:
Der Metropolis-Algorithmus, eine der Monte-Carlo-Methoden, beschreibt atomare Systeme im thermischen Gleichgewicht mit einem Wärmebad der Temperatur. In einer Anordnung von Atomen werden Veränderungen akzeptiert, wenn diese die Gesamtenergie verringern. Mit einer gewissen Wahrscheinlichkeit werden auch schlechtere Konfigurationen angenommen; die Wahrscheinlichkeit dafür beträgt: P(E)=exp(-DE/k¥T), wobei DE der Temperaturunterschied, T die Temperatur und k die Bolzmann-Konstante ist. In der Praxis wird dies dadurch bewerkstelligt, daß man eine Zufallszahl zwischen 0 und 1 bestimmt. Ist sie kleiner als P(DE), wird auch die energetisch schlechtere Konfiguration als der neue Systemzustand übernommen.

Die oben genannte Formel musste nun nur noch an das reale Problem angepasst werden, wodurch der Simulated Annealing Algorithmus entstanden war.
Beim Problem des Handlungsreisenden wird z.B. die maximal mögliche Entfernung gleich der Temperatur gesetzt und eine Wahrscheinlichkeitsvariable erzeugt, die sich in dem gleichen Bereich bewegt.
Die beiden anderen Algorithmen wurden als Verbesserung, bzw. Variation des Simulated Annealing weiterentwickelt.

1 Simulated Annealing

Beim Simulated Annealing benötigt man zunächst eine Kosten- oder Qualitätsfunktion, die die Qualität eines durchgeführten Schrittes bewertet. Dies kann zum Beispiel eine Wegstrecke, Kapitalkosten oder auch Materialkosten sein. Man erzeugt eine zufällige Ausgangskonfiguration und untersucht dann benachbarten Lösungen auf die oben genannte Kostenfunktion hin. Ob die neue Konfiguration als Ausgangspunkt für einen neuen Suchlauf akzeptiert wird hängt von der Qualität der Konfiguration und einem Kontrollparameter ab. Der Kontrollparameter ist z.B. ein abnehmender Wert zwischen 1 und 0, der in Verbindung mit einer Zufallszahl zwischen 0 und 1 entscheidet, ob ein neuer, eigentlich ungünstigere Zustand akzeptiert werden kann oder ob er abgelehnt wird.

So werden am Anfang des Verfahren noch fast wahllos die neuen Konfigurationen akzeptiert, da die Wahrscheinlichkeit, mit der eine schlechtere Variante akzeptiert wird, noch sehr hoch ist. Mit abnehmender Wahrscheinlichkeit nimmt dann auch die Bereitschaft ab, eine schlechtere Konfiguration zu akzeptieren. Geht diese Wahrscheinlichkeit langsam gegen 0, so werden nur noch kleinere Variationen zugelassen, analog zu der Metallschmelze, die immer zähflüssiger wird und sich die Sprünge zu ungünstigeren energetischen Zuständen immer mehr reduzieren. Je geringer die Wahrscheinlichkeit ist, daß ein schlechterer Zustand akzeptiert wird, desto starrer wird die Suche.

Damit der Algorithmus immer wieder einen Ausweg aus lokalen Minima findet, muß die Abkühlung, das heißt das Sinken der Wahrscheinlichkeit, entsprechend langsam stattfinden.
Setzt man die Wahrscheinlichkeit von Anfang an auf 0, so hat man das einfache Optimierungsverfahren ohne Simulated Annealing. Der Algorithmus steckt dann im ersten lokalen Minimum welches er findet fest. Beim Vertreterproblem heißt das, daß am Anfang fast alle Touren durchgespielt werden, im Verlauf des Verfahrens sich aber für die weiteren Entfernungssprünge eine feste Lösung herauskristallisiert und zum Ende zu nur noch die Strecken mit kleineren Variationen optimiert werden (Länderrouten -> Städterouten -> innerstädtische Routen).

Das folgende Struktogramm zeigt die allgemeine Lösung nach dem Simulated Annealing-Verfahren.

b2.gif (12824 Byte)



2 Toleranzschwellen-Algorithmus

Die Plazierung einer großen Anzahl von Bauelementen auf kleinsten integrierten Schaltungen stellt eine ähnliche Aufgabenstellung dar wie z.B. das Problem des Handlungsreisenden. Daher wurde bei IBM auf diesem Gebiet weitergeforscht, um andere geeignete Lösungsverfahren für solche Probleme zu finden.
Die beiden Wissenschaftler Dueck und Scheuer ( IBM-Forschungszentrum Heidelberg) veröffentlichten 1990 eine Variante des Simulated Annealing-Verfahrens, bei dem der Algorithmus weiter verbessert wurde.

Beim Simulated Annealing wird eine ungünstige Konfiguration mit einer gewissen Wahrscheinlichkeit, und eine bessere Konfiguration immer akzeptiert. Beim neuen Toleranzschwellen-Verfahren (Treshholding Accept) wird jede Konfiguration akzeptiert, bei der die Änderung unterhalb eines Schwellenwertes liegt. Das heißt bei einem Maximierungsproblem, daß eine akzeptierte Konfiguration besser sein muss als die alte, oder maximal bis zu einem bestimmten Wert unter der Qualität der alten Lösung liegen darf.
Die Abfrage ob die neue Lösung besser ist als die alte entfällt, da z.B. bei einer Maximierung die Differenz zwischen der Qualitätsfunktion einer besseren Konfiguration und der Qualitätsfunktion der alten Konfiguration immer unter der Toleranzschwelle liegen muß:

    T=Schwellenwert (negativ)
    Q(neu) - Q(alt) = Differenz

    Ist Q(neu) besser als Q(alt) dann ist die Differenz immer positiv, d.h. die bessere Konfiguration wird immer automatisch akzeptiert.

Die beiden IBM-Wissenschaftler haben in groß angelegten Versuchsreihen herausgefunden, daß das Toleranzschwellen-Verfahren meist bessere Lösungen errechnet als Simulated Annealing und dafür sogar weniger Zeit benötigt.

b3.gif (11063 Byte)



3 Sintflut-Algorithmus

Beim Toleranzschwellen-Verfahren und beim Simulated Annealing ist die Steuerung der Temperaturverringerung nicht unproblematisch. Wie bei allen heuristischen Verfahren muss hier erst ein Verfahren gefunden werden, welches möglichst optimale Lösungen hervorbringt (man kann die Temperatur schnell oder langsam sinken lassen, linear, progressiv oder degressiv, usw..).

Um diese Notwendigkeit zu umgehen hat Dueck ( IBM) 1993 eine weitere Vereinfachung der vorangehenden Verfahren veröffentlicht. Der einzige Parameter der zu berücksichtigen ist, ist der ,,Regen". Das Verfahren mit dem kuriosen Namen ,,Sinfflut"-Algorithrnus akzeptiert alle Konfigurationen die über einem bestimmten Wasserstand liegen. Dieser neue Algorithmus ist einfacher, benötigt aber laut Dueck doppelt solange, um zum Ergebnis zu kommen wie das Toleranzschwellen-Verfahren.

b4.gif (10403 Byte)


Autor: Richard Motzer

Tips und Anregungen an: emiel@informatik.fh-augsburg.de
Stand: 21.03.2003