Metropolis-Sampling

Metropolis-Sampling

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

Inhaltsverzeichnis

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 xi + 1 nur vom vorherigen Zustand xi ab.

Im folgenden wird der Algorithmus für den Fall beschrieben, dass das System von einem mehrdimensionalen Ort x abhängt. x sei kontinuierlich und der aktuelle Ort nach i Iterationen wird mit xi 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 δ ein fest gewählter Abstand ist. Dies bedeutet, dass ein neuer Ort zufällig in einer festen Umgebung gewählt wird, wobei die verschiedenen Komponenten der räumlichen Dimensionen nicht notwendigerweise gleich sein müssen.
  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_{\mathrm{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 \le 0\,, so wird y als neuer aktueller Ort akzeptiert.
    • Ist \Delta E > 0\,, so wird y wird mit Wahrscheinlichkeit pA als neuer aktueller Ort akzeptiert. Dazu wird eine gerade ermittelte Zufallszahl zwischen 0 und 1 mit pA verglichen und y nur dann akzeptiert, falls die Zufallszahl kleiner als pA ist.

Falls der Zustand nicht akzeptiert wird, so bleibt der Wert von x erhalten: xi + 1 = xi.

Kleine | δ | führen zu großen Akzeptanzraten, haben jedoch den Nachteil hoher Autokorrelationszeiten. Die Autokorrelationszeit \tau = \sum_{i=0}^{\infty} \Gamma (i) wird mit Hilfe der Autokorrelationsfunktion \Gamma (i) = \left \langle \left ( A_0 - \langle A \rangle \right ) \left ( A_i - \langle A \rangle \right ) \right \rangle  bestimmt. Große | δ | haben wiederum den Nachteil einer geringen Akzeptanzrate, so dass in der Praxis ein Mittelweg gesucht wird.

Das oben beschriebene Verfahren lässt sich einfach auf andere Fälle, wie beispielsweise diskrete Zustände, übertragen. Für ein System aus vielen wechselwirkenden Teilchen wird der Metropolisalgorithmus lokal für ein einzelnes Teilchen angewandt und anschließend alle Teilchen - entweder nacheinander oder zufällig - durchlaufen.

Verallgemeinerung

W. Keith Hastings generalisierte 1970 das Verfahren. Der Metropolis-Hastings-Algorithmus kann Zustände für eine beliebige Wahrscheinlichkeitsverteilung W(x) erzeugen. Voraussetzung ist lediglich, dass die Dichte an jedem Ort x berechnet werden kann. Der Algorithmus benutzt eine Vorschlagsdichte P(y;xi), die vom derzeitigen Ort xi und möglichem nächsten Ort y abhängt. Beim Metropolis-Hastings-Algorithmus wird ein Vorschlag y anhand der Vorschlagsdichte zufällig erzeugt und mit der Wahrscheinlichkeit  p_{\mathrm{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

Bei Monte-Carlo-Simulationen 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 = (k T)^{-1}

Dazu werden von den Iterationsschritten des Metropolisalgorithmus zunächst so viele ausgeführt, bis sich das System dem thermischen Gleichgewicht genähert hat, d.h. die Wahrscheinlichkeit der einzelnen Konfigurationen der Boltzmann-Verteilung entspricht. Befindet sich das System im thermischen Gleichgewicht, so entspricht die Wahrscheinlichkeitsverteilung W(x) der Boltzmann-Verteilung, d.h. die Konfigurationen werden mit der Wahrscheinlichkeit 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:  \left\langle A \right\rangle = \lim_{N \to \infty }  \frac{1}{N} \sum_{i=1}^N   A(x_i) .

Der Metropolisalgorithmus erzeugt Systeme im kanonischen Zustand, d.h. mit konstanter Temperatur. Um mikrokanonische Zustände zu erzeugen, können Molekulardynamik-Algorithmen verwendet werden.

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 z.B. der Thermodynamik bzw. Statistischen Physik, Festkörperphysik, Quantenelektrodynamik oder Quantenchromodynamik eingesetzt. Dabei muss der Algorithmus gegebenenfalls angepasst werden, wie die Energie durch den Hamiltonoperator oder die Wirkung ersetzt werden. Der Metropolisalgorithmus 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

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 (doi:10.1063/1.1699114). 
  • W.K. Hastings: Monte Carlo Sampling Methods Using Markov Chains and Their Applications. In: Biometrika. 57, 1970, S. 97-109. 

Wikimedia Foundation.

Игры ⚽ Нужно сделать НИР?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Metropolis (Sister Machine Gun album) — Metropolis Studio album by Sister Machine Gun Released July 15, 1997 Genre …   Wikipedia

  • Metropolis–Hastings algorithm — The Proposal distribution Q proposes the next point that the random walk might move to. In mathematics and physics, the Metropolis–Hastings algorithm is a Markov chain Monte Carlo method for obtaining a sequence of random samples from a… …   Wikipedia

  • Metropolis-Algorithmus — Der Metropolisalgorithmus ist eine Monte Carlo Methode zur Erzeugung von Zuständen eines Systems entsprechend der Boltzmann Verteilung. Inhaltsverzeichnis 1 Algorithmus 1.1 Verallgemeinerung 2 Anwendungen 2.1 Monte Carlo Simulation …   Deutsch Wikipedia

  • Metropolis-Verfahren — Der Metropolisalgorithmus ist eine Monte Carlo Methode zur Erzeugung von Zuständen eines Systems entsprechend der Boltzmann Verteilung. Inhaltsverzeichnis 1 Algorithmus 1.1 Verallgemeinerung 2 Anwendungen 2.1 Monte Carlo Simulation …   Deutsch Wikipedia

  • Multiple-try Metropolis — In Markov chain Monte Carlo, the Metropolis–Hastings algorithm (MH) can be used to sample from a probability distribution which is difficult to sample from directly. However, the MH algorithm requires the user to supply a proposal distribution,… …   Wikipedia

  • Gibbs sampling — In statistics and in statistical physics, Gibbs sampling or a Gibbs sampler is an algorithm to generate a sequence of samples from the joint probability distribution of two or more random variables. The purpose of such a sequence is to… …   Wikipedia

  • Rejection sampling — In mathematics, rejection sampling is a technique used to generate observations from a distribution. It is also commonly called the acceptance rejection method or accept reject algorithm .It generates sampling values from an arbitrary probability …   Wikipedia

  • Nicholas Metropolis — Nicholas Constantine Metropolis Born June 11, 1915(1915 06 11) Chicago …   Wikipedia

  • Umbrella sampling — is a technique in computational physics and chemistry, used to improve sampling of a system (or different systems) where ergodicity is hindered by the form of the system s energy landscape. It was first suggested by Torrie and Valleau in 1977… …   Wikipedia

  • Gibbs-Sampling — ist ein Algorithmus, um eine Folge von Stichproben der gemeinsamen Wahrscheinlichkeitsverteilung zweier oder mehrerer Zufallsvariablen zu erzeugen. Das Ziel ist es dabei, die unbekannte gemeinsame Verteilung zu approximieren. Der Algorithmus ist… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”