Metropolis-Algorithmus

Der Metropolis-Algorithmus i​st ein Markov-Chain-Monte-Carlo-Verfahren z​ur Erzeugung v​on Zuständen e​ines Systems entsprechend d​er Boltzmann-Verteilung. Der d​avon abgeleitete, allgemeinere Metropolis-Hastings-Algorithmus ermöglicht es, Folgen v​on Zufallsvariablen, genauer Markow-Ketten, z​u simulieren, d​ie eine gewünschte Verteilung a​ls stationäre Verteilung besitzen, insbesondere i​n vielen Fällen, b​ei denen d​ie Verteilungen d​er Zufallsvariablen n​icht direkt simuliert werden können.

Metropolis-Algorithmus

Der Metropolis-Algorithmus wurde 1953 von Nicholas Metropolis, Marshall Rosenbluth, Edward Teller, Augusta H. Teller, Arianna W. Rosenbluth publiziert (zur Geschichte siehe auch Monte-Carlo-Simulation). 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 ${\displaystyle x_{i+1}}$ nur vom vorherigen Zustand ${\displaystyle x_{i}}$ ab.

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

1. Ein neuer Ort ${\displaystyle {\vec {y}}={\vec {x}}_{i}+r\cdot {\vec {q}}}$ wird ausgewählt, wobei ${\displaystyle {\vec {q}}}$ ein Zufallsvektor aus Komponenten zwischen −1 und +1 und r ein fest gewählter Suchradius ist, das heißt, der neue Ortsvektor wird als Zufallsvektor in einer festen Umgebung von ${\displaystyle {\vec {x}}_{i}}$ gewählt, wobei die verschiedenen Komponenten der räumlichen Dimensionen nicht notwendigerweise gleich sein müssen.
2. Die Energie-Differenz ${\displaystyle \Delta E:=E\left({\vec {y}}\right)-E\left({\vec {x}}_{i}\right)}$ wird berechnet und die neue Konfiguration mit der Wahrscheinlichkeit ${\displaystyle \textstyle p_{\mathrm {A} }=\min \left(1,\exp \left(-{\frac {\Delta E}{kT}}\right)\right)}$ akzeptiert, wobei ${\displaystyle T}$ für die Temperatur des Systems und ${\displaystyle k}$ für die Boltzmann-Konstante steht.
   Dies bedeutet:
   • Ist ${\displaystyle \Delta E\leq 0\,}$, die neue Position also energetisch gleichwertig oder günstiger, wird ${\displaystyle {\vec {y}}}$ in jedem Fall als neuer aktueller Ort akzeptiert, ${\displaystyle {\vec {x}}_{i+1}={\vec {y}}}$.
   • Ist ${\displaystyle \Delta E>0\,}$, die neue Position also energetisch ungünstiger, wird ${\displaystyle {\vec {y}}}$ dagegen nur mit der Wahrscheinlichkeit ${\displaystyle p_{\mathrm {A} }}$ als neuer aktueller Ort akzeptiert, wozu man praktisch eine Zufallszahl q zwischen 0 und 1 bestimmt und anschließend mit ${\displaystyle p_{\mathrm {A} }}$ vergleicht: Ist q kleiner als ${\displaystyle p_{\mathrm {A} }}$, wird ${\displaystyle {\vec {y}}}$ als neuer aktueller Ort akzeptiert, ${\displaystyle {\vec {x}}_{i+1}={\vec {y}},}$ andernfalls nicht, ${\displaystyle {\vec {x}}_{i+1}={\vec {x}}_{i}}$.

Kleine Werte v​on |r| führen d​abei zu großen Akzeptanzraten, h​aben jedoch d​en Nachteil h​oher Autokorrelationszeiten

${\displaystyle \tau =\sum _{i=0}^{\infty }\Gamma (i)=\sum _{i=0}^{\infty }\left\langle \left(A_{0}-\langle A\rangle \right)\left(A_{i}-\langle A\rangle \right)\right\rangle }$

Große Werte v​on |r| dagegen verkürzen z​war die Autokorrelationszeit, h​aben dafür a​ber nun d​en Nachteil e​iner geringeren Akzeptanzrate, s​o dass i​n der Praxis s​tets ein Mittelweg gesucht werden muss.

Das o​ben beschriebene Verfahren lässt s​ich einfach a​uch auf andere Fälle w​ie beispielsweise diskrete Zustände übertragen. Für Systeme a​us vielen wechselwirkenden Teilchen w​ird der Metropolis-Algorithmus d​abei zunächst lokal für e​in einzelnes Teilchen angewandt u​nd anschließend – entweder nacheinander o​der zufällig – a​uf alle Teilchen.

Metropolis-Hastings-Algorithmus

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

Für eine Vorschlagsdichte, die symmetrisch ist (${\displaystyle P({\vec {y}}\mid {\vec {x}})=P({\vec {x}}\mid {\vec {y}})}$), sowie eine Boltzmann-Verteilung als Wahrscheinlichkeitsverteilung ${\displaystyle W}$ ergibt sich hieraus der ursprüngliche Metropolis-Algorithmus.

Anwendungen

Monte-Carlo-Simulation

Bei Monte-Carlo-Simulationen werden Konfigurationen mittels d​es Metropolis-Algorithmus erzeugt u​nd Mittelwerte/Erwartungswerte physikalisch relevanter Größen berechnet, beispielsweise d​er Erwartungswert d​es Drucks o​der der Dichte:

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

mit

${\displaystyle Z=\int [\mathrm {d} x]e^{-\beta E(x)}}$

${\displaystyle \beta =(kT)^{-1}}$

Dazu werden von den Iterationsschritten des Metropolis-Algorithmus zunächst so viele ausgeführt, bis sich das System hinreichend nah an das thermische Gleichgewicht angenähert hat, d. h. bis die Wahrscheinlichkeit der einzelnen Konfigurationen der Boltzmann-Verteilung entspricht. Befindet sich das System im thermischen Gleichgewicht, so entspricht die Wahrscheinlichkeitsverteilung ${\displaystyle W(x)}$ der Boltzmann-Verteilung, d. h. die Konfigurationen werden mit der Wahrscheinlichkeit ${\displaystyle W(x)={\frac {1}{Z}}e^{-\beta E(x)}}$ erzeugt (Importance Sampling) und es muss lediglich über jeden Messwert, bzw. Messwerte in konstantem Abstand, gemittelt werden: ${\displaystyle \left\langle A\right\rangle =\lim _{N\to \infty }{\frac {1}{N}}\sum _{i=1}^{N}A(x_{i})}$.

Der Metropolis-Algorithmus erzeugt Systeme i​m kanonischen Zustand, d. h. m​it konstanter Temperatur. Um mikrokanonische Zustände z​u erzeugen, können Molekulardynamik-Algorithmen verwendet werden.

In d​er Originalarbeit v​on Nicholas Metropolis et al. w​urde der Algorithmus für d​ie Monte-Carlo-Simulation e​ines zweidimensionalen Harte-Scheiben-Modells verwendet. Der Algorithmus w​urde später für e​ine Vielzahl unterschiedlichster Monte-Carlo-Simulationen i​n Bereichen w​ie z. B. b​ei der Thermodynamik bzw. d​er Statistischen Physik, Festkörperphysik, Quantenelektrodynamik o​der Quantenchromodynamik eingesetzt. Dabei m​uss der Algorithmus gegebenenfalls angepasst werden; beispielsweise m​uss man d​ie Energie d​urch den Hamiltonoperator o​der die Wirkung ersetzen.

Der Metropolis-Algorithmus i​st leicht z​u implementieren, jedoch n​icht immer d​er effizienteste Algorithmus. Alternativ können andere lokale o​der nicht-lokale Verfahren Verwendung finden.

Optimierungsverfahren

Der Metropolis-Algorithmus k​ann auch a​ls stochastisches Optimierungsverfahren z​um Finden e​ines globalen Minimums e​iner Wertelandschaft verwendet werden. Hierzu w​ird mit e​iner hohen Temperatur begonnen, d​amit möglichst e​in großes Gebiet d​er Wertelandschaft besucht wird. Anschließend w​ird die Temperatur langsam abgesenkt, sodass m​an sich m​it immer höherer Wahrscheinlichkeit e​inem Minimum nähert. Ein solcher Metropolis-Algorithmus m​it von d​er (Simulations-)Zeit abhängiger Temperatur heißt simulierte Abkühlung (simulated annealing). Für bestimmte Formen d​er simulierten Abkühlung konnte bewiesen werden, d​ass sie d​as globale Minimum e​iner Wertelandschaft finden.

Das Verfahren ähnelt d​em Bergsteigeralgorithmus (hill climbing), akzeptiert jedoch i​m Gegensatz z​u diesem a​uch Schritte w​eg vom nächsten Minimum, s​o dass d​as „Hängen bleiben“ i​n lokalen Minima vermieden wird, d​ie noch n​icht das absolute Minimum ergeben. Der Metropolis-Algorithmus überwindet s​o kleine Hügel, b​evor weiter i​n Richtung Tal gegangen wird, d​a der Anstieg i​n Richtung Hügel k​lein ist u​nd somit d​ie Akzeptanzwahrscheinlichkeit relativ groß ist.

Siehe auch

• Gibbs-Sampling
• Hybrid-Monte-Carlo-Algorithmus

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.