imported>Biggerj1 |
imported>Doc z |
| Zeile 1: |
Zeile 1: |
| Der '''Metropolis-Algorithmus''' ist ein [[MCMC|Markov-Chain-Monte-Carlo-Verfahren]] zur Erzeugung von Zuständen eines Systems entsprechend der [[Boltzmann-Statistik|Boltzmann-Verteilung]]. Der davon abgeleitete, allgemeinere '''Metropolis-Hastings-Algorithmus''' ermöglicht es, Folgen von [[Zufallsvariable]]n, genauer [[Markow-Kette]]n, zu simulieren, die eine gewünschte Verteilung als [[Stationäre Verteilung|stationäre Verteilung]] besitzen, insbesondere in vielen Fällen, bei denen die Verteilungen der Zufallsvariablen nicht direkt simuliert werden können.
| | #WEITERLEITUNG [[Metropolis-Algorithmus]] |
| | |
| == Metropolisalgorithmus ==
| |
| 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 <math>x_{i+1}</math> nur vom vorherigen Zustand <math>x_i</math> ab.
| |
| | |
| Im Folgenden wird der [[Algorithmus]] für den Fall beschrieben, dass das System von einem mehrdimensionalen Ort <math>\vec x</math> abhängt. <math>\vec x</math> sei kontinuierlich und der aktuelle Ort nach <math>i</math> Iterationen wird mit <math>\vec x_i</math> bezeichnet. Der Metropolisalgorithmus ergibt sich dann durch Wiederholung der folgenden Schritte:
| |
| # Ein neuer Ort <math>\vec y = \vec x_i + r\cdot \vec q</math> wird ausgewählt, wobei <math>\vec q</math> 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 <math>\vec x_i</math> gewählt, wobei die verschiedenen Komponenten der räumlichen Dimensionen nicht notwendigerweise gleich sein müssen. | |
| # Die Energie-Differenz <math>\Delta E := E \left( \vec y \right) - E \left( \vec x_i \right)</math> wird berechnet und die neue Konfiguration mit der [[Wahrscheinlichkeit]] <math>\textstyle p_{\mathrm{A}} = \min \left ( 1, \exp \left( -\frac {\Delta E} {kT} \right) \right)</math> akzeptiert, wobei <math>T</math> für die ''Temperatur'' des Systems und <math>k</math> für die [[Boltzmannkonstante]] steht.<br/>Dies bedeutet:
| |
| #* Ist <math>\Delta E \le 0\,</math>, die neue Position also energetisch gleichwertig oder günstiger, wird <math>\vec y</math> in jedem Fall als neuer aktueller Ort akzeptiert, <math>\vec x_{i+1}=\vec y</math>.
| |
| #* Ist <math>\Delta E > 0\,</math>, die neue Position also energetisch ungünstiger, wird <math>\vec y</math> dagegen nur mit der Wahrscheinlichkeit <math>p_{\mathrm{A}}</math> als neuer aktueller Ort akzeptiert, wozu man praktisch eine [[Zufallszahl]] ''q'' zwischen 0 und 1 bestimmt und anschließend mit <math>p_{\mathrm{A}}</math> vergleicht: Ist ''q'' kleiner als <math>p_{\mathrm{A}}</math>, wird <math>\vec y</math> als neuer aktueller Ort akzeptiert, <math>\vec x_{i+1}=\vec y,</math> andernfalls nicht, <math>\vec x_{i+1}=\vec x_i</math>.
| |
| | |
| Kleine Werte von |''r''| führen dabei zu großen Akzeptanzraten, haben jedoch den Nachteil hoher [[Autokorrelation|Autokorrelationszeiten]]
| |
| | |
| :<math>\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</math>
| |
| | |
| Große Werte von |''r''| dagegen verkürzen zwar die Autokorrelationszeit, haben dafür aber nun den Nachteil einer geringeren Akzeptanzrate, so dass in der Praxis stets ein Mittelweg gesucht werden muss.
| |
| | |
| Das oben beschriebene Verfahren lässt sich einfach auch auf andere Fälle wie beispielsweise diskrete Zustände übertragen. Für Systeme aus vielen wechselwirkenden Teilchen wird der Metropolisalgorithmus dabei zunächst ''lokal'' für ein einzelnes Teilchen angewandt und anschließend - entweder nacheinander oder zufällig - auf alle Teilchen.
| |
| | |
| == Metropolis-Hastings-Algorithmus ==
| |
| W. Keith Hastings generalisierte 1970 das Verfahren. Der Metropolis-Hastings-Algorithmus kann Zustände für eine beliebige Wahrscheinlichkeitsverteilung <math>W(\vec x)</math> erzeugen. Voraussetzung ist lediglich, dass die Dichte an jedem Ort <math>\vec x</math> berechnet werden kann. Der Algorithmus benutzt eine ''Vorschlagsdichte'' <math>P(\vec y\mid \vec x)</math>, die vom derzeitigen Ort <math>\vec x</math> und möglichem nächsten Ort <math>\vec y</math> abhängt. Beim Metropolis-Hastings-Algorithmus wird ein Vorschlag <math>\vec y</math> anhand der Vorschlagsdichte zufällig erzeugt und mit der Wahrscheinlichkeit <math> 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) </math> akzeptiert.
| |
| | |
| Für eine Vorschlagsdichte, die symmetrisch ist (<math>P(\vec y\mid \vec x)=P(\vec x\mid \vec y)</math>), sowie eine Boltzmann-Verteilung als Wahrscheinlichkeitsverteilung <math> W</math> ergibt sich hieraus der ursprüngliche Metropolisalgorithmus.
| |
| | |
| == Anwendungen ==
| |
| === Monte-Carlo-Simulation ===
| |
| Bei [[Monte-Carlo-Simulation]]en werden Konfigurationen mittels des Metropolisalgorithmus erzeugt und Mittelwerte/Erwartungswerte physikalisch relevanter Größen berechnet, beispielsweise der Erwartungswert des Drucks oder der Dichte:
| |
| | |
| :<math> \left\langle A \right\rangle = Z^{-1} \int [\mathrm{d} x] e^{-\beta E(x)} \, A(x) </math>
| |
| mit
| |
| :<math>Z = \int [\mathrm{d} x] e^{-\beta E(x)}</math>
| |
| :<math>\beta = (k T)^{-1}</math>
| |
| | |
| Dazu werden von den Iterationsschritten des Metropolisalgorithmus zunächst so viele ausgeführt, bis sich das System hinreichend nah an das [[Thermisches Gleichgewicht|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 <math>W(x)</math> der Boltzmann-Verteilung, d. h. die Konfigurationen werden mit der Wahrscheinlichkeit <math>W(x) = \frac{1}{Z} e^{- \beta E(x)}</math> erzeugt (''[[Importance Sampling]]'') und es muss lediglich über jeden Messwert, bzw. Messwerte in konstantem Abstand, gemittelt werden: <math> \left\langle A \right\rangle = \lim_{N \to \infty } \frac{1}{N} \sum_{i=1}^N A(x_i) </math>.
| |
| | |
| Der Metropolisalgorithmus erzeugt Systeme im [[Kanonischer Zustand|kanonischen Zustand]], d. h. mit konstanter Temperatur. Um [[Mikrokanonisches Ensemble|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 eines zweidimensionalen Harte-Scheiben-Modells verwendet. Der Algorithmus wurde später für eine Vielzahl unterschiedlichster Monte-Carlo-Simulationen in Bereichen wie z. B. bei der [[Thermodynamik]] bzw. der [[Statistische Physik|Statistischen Physik]], [[Festkörperphysik]], [[Quantenelektrodynamik]] oder [[Quantenchromodynamik]] eingesetzt. Dabei muss der Algorithmus gegebenenfalls angepasst werden; beispielsweise muss man die Energie durch den [[Hamiltonoperator]] oder die [[Wirkung (Physik)|Wirkung]] ersetzen.
| |
| | |
| Der Metropolisalgorithmus ist leicht zu implementieren, jedoch nicht immer der effizienteste Algorithmus. Alternativ können andere lokale oder nicht-lokale Verfahren Verwendung finden.
| |
| | |
| === Optimierungsverfahren ===
| |
| Der Metropolisalgorithmus kann auch als stochastisches [[Optimierungsverfahren]] zum Finden eines [[Globales Minimum|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, sodass man sich mit immer höherer Wahrscheinlichkeit einem [[Extremwert|Minimum]] nä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 das „Hängen bleiben“ in lokalen Minima vermieden wird, die noch nicht das absolute Minimum ergeben. 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 Akzeptanzwahrscheinlichkeit relativ groß ist.
| |
| | |
| == Siehe auch ==
| |
| * [[Gibbs-Sampling]]
| |
| * [[Hybrid-Monte-Carlo-Algorithmus]]
| |
| | |
| == Literatur ==
| |
| | |
| * {{Literatur
| |
| |Autor = [[Nicholas Metropolis|N. Metropolis]], A. Rosenbluth, [[Marshall Rosenbluth|M. Rosenbluth]], A. Teller und [[Edward Teller|E. Teller]]
| |
| |Titel = Equation of State Calculations by Fast Computing Machines
| |
| |Sammelwerk = Journal of Chemical Physics
| |
| |Band = 21
| |
| |Jahr = 1953
| |
| |Seiten = 1087-1092
| |
| |DOI = 10.1063/1.1699114
| |
| }}
| |
| * {{Literatur
| |
| |Autor = W.K. Hastings
| |
| |Titel = Monte Carlo Sampling Methods Using Markov Chains and Their Applications
| |
| |Sammelwerk = Biometrika
| |
| |Band = 57
| |
| |Jahr = 1970
| |
| |Seiten = 97-109
| |
| }}
| |
| | |
| | |
| [[Kategorie:Computerphysik]]
| |
| [[Kategorie:Theoretische Chemie]]
| |
| [[Kategorie:Optimierungsalgorithmus]]
| |