Metropolisalgorithmus
aus Wikipedia, der freien Enzyklopädie
Der Metropolisalgorithmus ist ein stochastisches Optimierungsverfahren zum Finden eines globalen Minimums einer Wertelandschaft. Das Verfahren ist dabei dem Bergsteigeralgorithmus (hill climbing) ähnlich, akzeptiert es aber manchmal, in eine andere Richtung zu gehen statt nur in die Richtung eines Optimums.
Der Wertebereich der Fitness-Funktion 
wird als Energie interpretiert, die es zu minimieren gilt. Es sei die Zahl T als Temperatur des Metropolis-Algorithmus definiert.
Der Unterschied zum Bergsteigeralgorithmus sieht wie folgt aus: Befindet man sich aktuell an einem Ort x und hat man einen Nachbarn y als nächsten Kandidat für den aktuellen Ort, so wird wie folgt verfahren:
- Man berechne die Energie-Differenz
. - Ist ΔE < 0,
- so wird y als neuer aktueller Ort akzeptiert.
- Andernfalls wird y als neuer aktueller Ort nur dann akzeptiert, wenn eine gerade ermittelte Zufallszahl zwischen 0 und 1 kleiner als
ist. Anders ausgedrückt, y wird mit Wahrscheinlichkeit p als neuer aktueller Ort akzeptiert.
Man sieht, dass kleine Hügel zu überwinden, bevor weiter in Richtung Tal gegangen wird, kein größeres Problem ist, da der Anstieg in Richtung Hügel klein ist, die Akzeptanz-Wahrscheinlichkeit also relativ groß.
Untersuchungen haben ergeben, dass es sinnvoll ist, mit einer hohen Temperatur zu beginnen (damit möglichst ein großes Gebiet der Wertelandschaft besucht wird) und dann die Temperatur langsam abzusenken (damit man mit immer höherer Wahrscheinlichkeit sich einem Minimum nähert). Ein solcher Metropolis-Algorithmus mit von der (Simulations-)Zeit abhängiger Temperatur heißt simulierte Abkühlung (simulated annealing). Für bestimmte Formen der simulierten Abkühlung konnte bewiesen werden, dass sie das globale Minimum einer Wertelandschaft finden.
Überraschenderweise gibt es viele Probleme, die bei optimaler Temperatur mit simulierter Abkühlung nicht effizienter gelöst werden können als mit dem Metropolisalgorithmus. Wegener hat für ein einfach zu beschreibendes Problem gezeigt, dass, unabhängig von der Temperatur, die simulierter Abkühlung effizienter ist als der Metropolisalgorithmus.
[Bearbeiten] Siehe auch
[Bearbeiten] Literatur
N. Metropolis, A. Rosenbluth, M. Rosenbluth, A. Teller und E. Teller: Equation of State Calculations by Fast Computing Machines. In: Journal of Chemical Physics. 21, 1953, S. 1087-1092.
Ingo Wegener: Simulated Annealing Beats Metropolis in Combinatorial Optimization. In: Lecture Notes in Computer Science. 3580, Springer, Berlin/Heidelberg 2005, S. 589-601, ISBN 978-3-540-27580-0 (doi:10.1007/11523468).
