Benutzer:Doc z/Metropolis

Der Metropolisalgorithmus ist eine Monte-Carlo Methode zur Erzeugung von Zuständen eines Systems entsprechend der Boltzmann-Verteilung.

Algorithmus

Der Metropolisalgorithmus wurde 1953 von Nicholas Metropolis et. al. publiziert. Er wird dazu genutzt, eine Markow-Kette und damit die Zustände eines Systems, entsprechend der Boltzmann-Verteilung zu erzeugen. Dabei hängt der neue Zustand des Systems $x^{i+1}$ nur vom voherigen Zustand $x^{i}$ ab.

Im folgenden wird der Algorithmus für den Fall beschrieben, dass dass System von einem mehrdimensionalen Ort $x$ abhängt. $x$ sei kontinuierlich und der aktuelle Ort nach $i$ Iterationen wird mit $x^{i}$ bezeichnet. Der Metropolisalgorithmus ergibt sich dann durch Wiederholung der folgenden Schritte:

1. Ein neuer Ort $y=x^{i}+(2r-1)\,\delta$ wird ausgewählt, wobei $r$ eine Zufallszahl zwischen 0 und 1 und $\delta$ ein fest gewählter Abstand ist. Dies bedeutet, dass ein neuer Ort zufällig in einer festen Umgebung gewählt wird. Dabei müssen die verschiedenen Komponenten für die verschiedenen räumlichen Dimensionen nicht notwendigerweise gleich sein.
2. Die Energie-Differenz $\Delta E=E\left(y\right)-E\left(x^{i}\right)$ wird berechnet und die neue Konfiguration mit der Wahrscheinlichkeit $p_{A}=\min \left(1,\exp \left(-{\frac {\Delta E}{kT}}\right)\right)$ akzeptiert. Dabei beschreibt $T$ die Temperatur des Systems und $k$ stellt die Boltzmannkonstante dar. Dies bedeutet:
   • Ist $\Delta E\leq 0\,$, so wird $y$ als neuer aktueller Ort akzeptiert.
   • Ist $\Delta E>0\,$, so wird $y$ wird mit Wahrscheinlichkeit $p_{A}$ als neuer aktueller Ort akzeptiert. Dazu wird eine gerade ermittelte Zufallszahl zwischen 0 und 1 mit $p_{A}$ verglichen und $y$ nur dann akzeptiert falls die Zufallszahl keiner als $p_{A}$ ist.

Falls der Zustand nicht akzeptiert wird, so bleibt der Wert von $x$ erhalten: $x^{i+1}=x^{i}$.

FÜr mehere Teilchen.... diskrete Positionen... Korrelation... Akzeptanz

Verallgemeinerung

W.K. Hastings generalisierte 1970 das Verfahren. Der Metropolis-Hastings-Algorithmus kann Zustände für eine beliebige Wahrscheinlichkeitverteilung $W(x)$ erzeugen. Voraussetzung ist lediglich, dass die Dichte an jedem Ort $x$ berechnet werden kann. Der Algorithmus benutzt eine Vorschlagsdichte $P(y;x^{i})$, die vom derzeitigen Ort $x^{i}$ und möglichem nächsten Ort $y$ abhängt. Ein Vorschlag $y$ wird anhand der Vorschlagsdichte zufällig erzeugt und mit der Wahrscheinlichkeit $p_{A}=\min \left(1,{\frac {W(y)P(x^{i}|y)}{W(x)P(y|x^{i})}}\right)$ akzeptiert.

Für eine Vorschlagsdichte, die in einem festen Intervall um den aktuellen Ort konstant und sonst null ist sowie einer Boltzmann-Verteilung als Wahrscheinlichkeitsverteilung ergibt sich hieraus der Metropolisalgorithmus.

Anwendungen

Monte-Carlo-Simulation

Für die Monte-Carlo-Simulation werden Konfigurationen mittels des Metropolisalgorithmus erzeugt und Mittelwerte/Erwartungswerte physikalisch relevanter Größen, wie beispielsweise dem Druck oder Dichte, berechnet:

$\left\langle A\right\rangle =Z^{-1}\int [\mathrm {d} x]e^{-\beta E(x)}\,A(x)$ mit $\ \ Z=\int [\mathrm {d} x]e^{-\beta E(x)}$ und $\ \ \beta =(kT)^{-1}$

Von diesen Iterationsschritten werden so viele ausgeführt, bis das System sich weit genug dem thermischen Gleichgewicht genähert hat, d. h. wenn die Wahrscheinlichkeit der einzelnen Konfigurationen der Boltzmann-Verteilung entspricht. Befindet sich das System im Gleichgewicht, so entspricht $W(x)$ der Boltzmann-Verteilung. Da der Metropolisalgorithmus die Konfigurationen mit der Wahrscheinlichkeit $W(x)={\frac {1}{Z}}e^{-\beta E(x)}$ erzeugt, muss nun lediglich über jeden Messwert, bzw. Messwerte in konstantem Abstand, gemittelt werden.

, d.h. es findet eine ... (importance sampling) statt. In numerischen Simulationen werden die Konfigurationen so erzeugt, dass die Verteilung ... entspricht. Für den Erwartungswert einer Größe $A$ gilt dann $\left\langle A\right\rangle =\lim _{N\to \infty }{\frac {1}{N}}\sum _{i=1}^{N}A(x^{i})$

Kanonischer Zustand, d.h. konstante Temperatur ... Hamilton-Funktion bzw. Wirkung Korrelation

In der Originalarbeit von Nicholas Metropolis et. al. wurde der Algorithmus für die Monte-Carlo-Simulation des zweidimensionalen Harte-Scheiben-Modells verwendet. Der Algorithmus wurde später für eine Vielzahl unterschiedlichster Monte-Carlo-Simulationen in Bereichen wie der Thermodynamik bzw. Statistischen Physik, Festkörperphysik, Quantenelektrodynamik oder Quantenchromodynamik eingesetzt. Er ist leicht zu implementieren, jedoch nicht der effektiveste Algorithmus. Alternativ können andere lokale oder nicht-lokale Verfahren Verwendung finden.

Optimierungsverfahren

Der Metropolisalgorithmus kann auch als stochastisches Optimierungsverfahren zum Finden eines globalen Minimums einer Wertelandschaft verwendet werden. Hierzu wird mit einer hohen Temperatur begonnen, damit möglichst ein großes Gebiet der Wertelandschaft besucht wird. Anschließend wird die Temperatur langsam abgesenkt und sich so mit immer höherer Wahrscheinlichkeit einem Minimum genähert. Ein solcher Metropolisalgorithmus 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.

Das Verfahren ähnelt dem Bergsteigeralgorithmus (hill climbing), akzeptiert jedoch im Gegensatz zu diesem auch Schritte weg vom nächsten Minimum, so dass frühzeitige Konvergenz zu lokalen Minima vermieden wird. Der Metropolisalgorithmus überwindet so kleine Hügel, bevor weiter in Richtung Tal gegangen wird, da der Anstieg in Richtung Hügel klein ist und somit die Akzeptanz-Wahrscheinlichkeit relativ groß ist.

Siehe auch

• Gibbs sampling

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. Band 21, 1953, S. 1087–1092 (doi:10.1063/1.1699114). 

• W.K. Hastings: Monte Carlo Sampling Methods Using Markov Chains and Their Applications. In: Biometrika. Band 57, 1970, S. 97–109.