Information Technology Reference
In-Depth Information
8.5 Simuliertes Ausglühen
Die im vorangehenden Abschnitt angesprochenen Schwierigkeiten beimEinsatz von
Hopfield-Netzen zur Lösung von Optimierungsproblemen beruhen imwesentlichen
darauf, dass das Verfahren in einem lokalen Minimum der Energiefunktion hängen-
bleiben kann. Dieses Problem tritt auch bei anderenOptimierungsmethoden auf und
so liegt es nahe, Lösungsideen, die für andere Optimierungsmethoden entwickelt
wurden, auf Hopfield-Netze zu übertragen. Eine solche Idee ist das sogenannte
si-
mulierte Ausglühen
.
Die Grundidee des simulierten Ausglühens (simulated annealing) [Metropolis
u. a. 1953, Kirkpatrick u. a. 1983] besteht darin, mit einer zufällig erzeugten Kandi-
datenlösung des Optimierungsproblems zu beginnen und diese zu bewerten. Die
jeweils aktuelle Kandidatenlösung wird dann modifiziert und erneut bewertet. Ist
die neue Lösung besser als die alte, so wird sie angenommen und ersetzt die alte
Lösung. Ist sie dagegen schlechter, so wird sie nur mit einer bestimmten Wahrschein-
lichkeit angenommen, die davon abhängt, umwieviel schlechter die neue Lösung ist.
Außerdemwird diese Wahrscheinlichkeit im Laufe der Zeit gesenkt, so dass schließ-
lich nur noch Kandidatenlösungen übernommen werden, die besser sind. Oft wird
außerdem die beste bisher gefundene Lösung mitgeführt.
Der Grund für die Übernahme einer schlechteren Kandidatenlösung ist, dass
das Vorgehen sonst einem Gradientenabstieg sehr ähnlich wäre. Der einzige Unter-
schied bestünde darin, dass die Abstiegsrichtung nicht berechnet, sondern durch
Versuch und Irrtum bestimmt wird. Wie wir aber in Kapitel 5 gesehen haben, kann
ein Gradientenabstieg leicht in einem lokalen Minimum hängenbleiben (siehe Abbil-
dung 5.23 auf Seite 69). Indem bisweilen auch schlechtere Lösungen akzeptiert wer-
den, kann dieses unerwünschte Verhalten zumindest teilweise verhindert werden.
Anschaulich gesprochen können „Barrieren“ (Gebiete des Suchraums mit geringe-
rer Lösungsgüte) überwunden werden, die lokale Minima vom globalen Minimum
trennen. Später, wenn die Wahrscheinlichkeit für die Übernahme schlechterer Lösun-
gen gesenkt wurde, wird die Zielfunktion dagegen lokal optimiert.
Der Name „simuliertes Ausglühen“ für dieses Verfahren stammt daher, dass es
sehr ähnlich ist zu der physikalischen Minimierung der Gitterenergie der Atome,
wenn ein erhitztes Stück Metall sehr langsam abgekühlt wird. Dieser Prozess wird
gewöhnlich „Ausglühen“ genannt und dient dazu, ein Metall weicher zu machen,
Spannungen und Gitterbaufehler abzubauen, um es leichter bearbeiten zu können.
Physikalisch gesehen verhindert die thermische Energie der Atome, dass sie eine
Konfiguration annehmen, die nur ein lokales Minimum der Gitterenergie ist. Sie
„springen“ aus dieser Konfiguration wieder heraus. Je „tiefer“ das (lokale) Energie-
minimum jedoch ist, umso schwerer ist es für die Atome, die Konfiguration wieder
zu verlassen. Folglich ist es wahrscheinlich, dass sie schließlich eine Konfiguration
sehr geringer Energie annehmen, dessen Optimum im Falle des Metalles eine mono-
kristalline Struktur ist.
Es ist allerdings klar, dass nicht garantiert werden kann, dass das globale Mini-
mum der Gitterenergie erreicht wird. Besonders, wenn das Metallstück nicht lange
genug erhitzt wird, ist es wahrscheinlich, dass die Atome eine Konfiguration einneh-
men, die nur ein lokales Minimum der Energiefunktion ist (im Falle eines Metalls
eine polykristalline Struktur). Es ist daher wichtig, dass die Temperatur langsam
