Monte-Carlo-Simulation

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen
Die Artikel Monte-Carlo-Algorithmus und Monte-Carlo-Simulation überschneiden sich thematisch. Hilf mit, die Artikel besser voneinander abzugrenzen oder zusammenzuführen (→ Anleitung). Beteilige dich dazu an der betreffenden Redundanzdiskussion. Bitte entferne diesen Baustein erst nach vollständiger Abarbeitung der Redundanz und vergiss nicht, den betreffenden Eintrag auf der Redundanzdiskussionsseite mit {{Erledigt|1=~~~~}} zu markieren. Siehe-auch-Löscher (Diskussion) 12:42, 27. Jul. 2020 (CEST)


Die Kreiszahl Pi wird mit der Monte-Carlo-Methode angenähert bestimmt durch das Vierfache der Wahrscheinlichkeit, mit der ein innerhalb des Quadrats zufällig gewählter Punkt in den Kreis fällt. Aufgrund des Gesetzes der großen Zahlen sinkt mit steigender Anzahl von Experimenten die Varianz des Ergebnisses.

Monte-Carlo-Simulation oder Monte-Carlo-Studie, auch MC-Simulation, ist ein Verfahren aus der Stochastik, bei dem eine sehr große Zahl gleichartiger Zufallsexperimente die Basis darstellt. Es wird dabei versucht, analytisch nicht oder nur aufwendig lösbare Probleme mit Hilfe der Wahrscheinlichkeitstheorie numerisch zu lösen. Als Grundlage ist vor allem das Gesetz der großen Zahlen zu sehen. Die Zufallsexperimente können entweder – etwa durch Würfeln – real durchgeführt werden oder in Computerberechnungen mittels Monte-Carlo-Algorithmen. Bei Letzteren werden zur Simulation von zufälligen Ereignissen, scheinbar zufällige Zahlen berechnet, die auch als Pseudozufallszahlen bezeichnet werden.

Zu den Pionieren der Monte-Carlo-Methode in den 1940er Jahren gehören Stanislaw Ulam, Nicholas Metropolis und John von Neumann. Als grundlegende Veröffentlichung gilt eine Arbeit von Metropolis, Edward Teller, Augusta H. Teller, Marshall Rosenbluth und Arianna W. Rosenbluth von 1953.

Geschichte[Bearbeiten | Quelltext bearbeiten]

Das 1733 von Georges-Louis Leclerc de Buffon vor der Pariser Akademie der Wissenschaften vorgestellte Nadelproblem[1], das mit Hilfe des Zufalls die nährungsweise Bestimmung der Kreiszahl Pi ermöglicht, war eine der ersten Anwendungen einer Monte-Carlo-Simulation. (→Probabilistische Bestimmung der Zahl Pi)

Enrico Fermi hatte in den 1930er Jahren die eigene Ideen zu Monte-Carlo-Simulationen mittels elektronischer Rechenmaschinen. Ausgeführt wurden diese 1946 von Stanislaw Ulam und dem von ihm deshalb kontaktierten John von Neumann.[2] Dies geschah zur Zeit des 2. Weltkriegs während der Arbeit an einem damals geheimen Projekt am Los Alamos Scientific Laboratory, für das ein Codename nötig war. Es ging im Rahmen der Entwicklung der ersten Atombombe um die Neutronendiffusion in nuklearen Materialien.[3] Auch die mathematische Methode der Simulation musste geheim gehalten werden. Der Name Monte-Carlo wurde von Nicholas Metropolis geprägt und hängt wie folgt mit der Methode zusammen: Stan Ulam hatte einen Onkel, der sich zum Spielen immer Geld von Verwandten geliehen hatte, denn „er musste nach Monte Carlo gehen“.[4] Dies ist natürlich eine Anspielung auf die Spielbank Monte-Carlo im gleichnamigen Stadtteil des Stadtstaates Monaco.[5][6][7]

Als grundlegende Veröffentlichung gilt eine Arbeit von Nicholas Metropolis, Marshall N. Rosenbluth und dessen Ehefrau Arianna W. Rosenbluth, Edward Teller und dessen Ehefrau Augusta H. Teller, veröffentlicht 1953 im Journal of Chemical Physics.[8] Ziel war die Berechnung der Zustandsgleichung eines zweidimensionalen Systems starrer Kugeln als Modelle einer Flüssigkeit. Simuliert wurde mit 224 Teilchen und periodischen Randbedingungen. Jede Simulation bestand aus bis zu 48 Zyklen, in denen jeweils jedes Teilchen einen Bewegungsschritt ausführte. Ein Zyklus benötigte drei Minuten auf dem MANIAC I Computer des Los Alamos National Laboratory. Verwendet wurde eine Sampling-Methode mit Wichtung über den Boltzmannfaktor, das Herzstück des MC-Verfahrens im Metropolis-Algorithmus, wobei die Idee nach Marshall Rosenbluth von Teller gekommen sein soll.[9][10] Nach Rosenbluth leisteten er und seine Frau die Hauptarbeit für den Artikel (Metropolis hätte hauptsächlich Computerzeit zur Verfügung gestellt) und sie waren die einzigen der Autoren, die das Verfahren in anschließenden Publikationen weiterverfolgten,[11][12] sie wandten sich aber selbst ebenfalls bald darauf anderen Forschungsthemen (Plasmaphysik) zu.

Mathematik[Bearbeiten | Quelltext bearbeiten]

Mathematisch ist das System ein wahrscheinlichkeitsgewichteter Weg im Phasenraum (allgemein Zustandsraum). Monte-Carlo-Simulationen sind besonders geeignet, um statistische Mittelwerte einer Größe ,

oder hochdimensionale Integrale (Monte-Carlo-Integration) wie

zu berechnen. soll in diesem Zusammenhang ein normiertes statistisches Gewicht (etwa ein Boltzmanngewicht) sein. ist der Wert der Größe im Zustand . Die Summation bzw. Integration verläuft hier über einen Raum , also der Phasenraum der Teilchen im System.

Häufig ist der Raum so groß, dass die Summation nicht vollständig durchgeführt werden kann. Stattdessen erzeugt man nun eine Markow-Kette von Zuständen in , deren Häufigkeit wie das vorgegebene Gewicht verteilt ist. Bereiche des Raumes mit hohem Gewicht sollen also häufiger in der Markow-Kette vertreten sein als Bereiche mit niedrigem Gewicht. Man spricht hier von Importance Sampling. Gelingt dies, so lassen sich die Erwartungswerte einfach als arithmetisches Mittel der Größe zu diesen Zuständen der Markow-Kette berechnen, also als

Dieser Zusammenhang basiert auf dem Gesetz der großen Zahlen. Je nach physikalischem System kann es schwierig sein, diese Markow-Kette zu erzeugen. Insbesondere ist sicherzustellen, dass die Markow-Kette tatsächlich den gesamten Raum bedeckt und nicht nur einen Teil des Raumes abtastet. Man sagt: der Algorithmus muss ergodisch sein.

Anwendungen[Bearbeiten | Quelltext bearbeiten]

Anwendungen der Monte-Carlo-Simulation sind beispielsweise:

  • als Alternative zur analytischen Lösung von Problemen rein mathematischer Herkunft,
    • die Approximation der Zahl Pi mit Hilfe des Buffonschen Nadelproblems oder durch die zufällige „Beregnung“ eines Quadrats auf dem Einheitskreis mit Zufallspunkten (hier ist der Anteil der Punkte, die im Einheitskreis liegen, etwa π/4).
    • in Verallgemeinerung die Berechnung des Integrals einer Funktion über dem Intervall [0;1] (Flächeninhalt) und dann auch höherdimensionaler Integrale (Volumen).
  • Verteilungseigenschaften von Zufallsvariablen unbekannten Verteilungstyps,
  • die Nachbildung von komplexen Prozessen, die nicht direkt analysiert werden können,
    • Produktionsprozesse in einem Fertigungsunternehmen, um Engpässe und Opportunitäten in der Produktion aufzudecken
    • Wetter und Klima der Erde.
    • Rekonstruktionsverfahren in der Nuklearmedizin.
    • Risikoaggregation zur Bestimmung des Gesamtrisikoumfangs eines Unternehmens im Risikomanagement[13]
    • Ableitung von Bewertungen in der Wertermittlung, z. B. bei der Unternehmensbewertung oder Immobilienwirtschaft[14][15]. Bereisung komplexe Finanzkontrakte wie „exotische“ Optionen, bei denen keine analytische Formel für die Bewertung eines Finanzproduktes bekannt ist.
    • räumliche Verteilung des energieabhängigen Neutronenflusses in einem heterogenen Medium, etwa im Blanket eines Kernfusionsreaktors.
    • Wege eines einzelnen Regentropfens simulieren, der mit zufällig verteilten anderen Tropfen kollidiert. Nach der Simulation mehrerer konkreter Tropfen sind Aussagen über die durchschnittliche Tropfengröße möglich oder auch zu Temperatur und Tröpfchendichte, bei denen Schnee oder Hagel entstehen.
    • Verteilung der Kugeln auf die Fächer beim Galtonbrett.

Mit der Monte-Carlo-Methode können Probleme mit statistischem Verhalten simuliert werden. Diese Methode hat deshalb besonders in der Physik wichtige Anwendungen gefunden, und zwei Bücher des Autors Kurt Binder gehören zu den meistzitierten Veröffentlichungen in dieser Wissenschaftssparte.

Heutige Supercomputer (HPC) basieren auf massivem Multiprocessing mit vielen tausend Einzelprozessoren, die parallel arbeiten. Diese Gegebenheiten lassen sich besonders gut mit solchen probabilistischen Lösungsverfahren ausnutzen.[16] Supercomputer und MC Methoden werden u. a. für die Simulation der alternden Nuklearwaffen (siehe auch Stockpile stewardship) der USA benutzt.[17][18][19][20]

Beispiele[Bearbeiten | Quelltext bearbeiten]

Illustration zur Monte-Carlo-Bestimmung von Pi.

Probabilistische Bestimmung der Zahl Pi[Bearbeiten | Quelltext bearbeiten]

Man wählt hierzu zufällige Punkte aus und überprüft (durch Anwendung des Satzes von Pythagoras), ob diese innerhalb des Einheitskreises liegen:

.

Über das Verhältnis der Anzahl der Punkte innerhalb und außerhalb des Kreises kann dann folgendermaßen bestimmt werden:

Numerische Integration[Bearbeiten | Quelltext bearbeiten]

Numerische Integration mit Monte Carlo: Die Stützstellen werden zufällig gleichverteilt auf dem Integrationsintervall gewählt. Neue Stützstellen sind dunkelblau, die alten hellblau eingezeichnet. Der Wert des Integrals nähert sich 3,32 an.

Das obige Beispiel zur Bestimmung von Pi bildet praktisch das Flächenintegral einer Viertelkreisfläche. Entsprechend kann man das Flächenintegral allgemeiner, auch höherdimensionaler Funktionen nach dieser Methode berechnen. Soll das Integral

einer Funktion berechnet werden, dann wählt man unabhängige im Intervall gleichverteilte Punkte und approximiert durch

Im allgemeineren Fall von höherdimensionalen Funktionen ist das Vorgehen ähnlich. Sei eine beliebige -dimensionale Menge und eine integrierbare Funktion. Um den Wert

näherungsweise zu berechnen, wählt man zufällig in der Menge gleichverteilte Punkte für . Dann approximiert

den Wert in Abhängigkeit von beliebig genau. Um wie oben vorgestellt Pi zu berechnen, muss man und als charakteristische Funktion des Einheitskreises wählen. Hier ist gerade die Fläche des Einheitskreises.

In der Praxis werden Monte-Carlo Verfahren vor allem für die Berechnung hochdimensionaler Integrale verwendet. Hier sind klassische Integrationsalgorithmen stark vom Fluch der Dimensionalität betroffen und nicht mehr anwendbar. Allerdings sind speziell hochdimensionale Integranden meist stark lokalisiert[21]. In diesen Fällen erlauben insbesondere MCMC-Verfahren die Erzeugung von Stichproben mit einer Verteilung die eine effiziente Berechnung solcher hochdimensionaler Integrale erlaubt.

Miller-Rabin-Primzahltest[Bearbeiten | Quelltext bearbeiten]

Ein Beispiel für einen Monte-Carlo-Simulation ist der Miller-Rabin-Test, bei dem probabilistisch bestimmt wird, ob eine natürliche Zahl prim ist oder nicht. Die Ausgabe des Tests lautet entweder „sicher zusammengesetzt“ oder „wahrscheinlich prim“. Die Wahrscheinlichkeit, dass eine zusammengesetzte Zahl als „wahrscheinlich prim“ klassifiziert wird, liegt pro Durchgang unter 25 % und kann durch mehrfache Ausführung weiter gesenkt werden. Der Miller-Rabin-Test liefert keine Aussage über die Faktoren einer zusammengesetzten Zahl, ist also kein Faktorisierungsverfahren.

Programmpakete[Bearbeiten | Quelltext bearbeiten]

  • MCNP, der Monte-Carlo N-Particle Transport Code, ist ein prototypisches, weltweit verbreitetes reaktorphysikalisches Programm, das sehr häufig angewendet wird, auch in der Kerntechnik und der Kernfusionstechnik.[22] Die aktuelle Version ist MCNP6.2. Auf der MCNP-Webseite[23] sind Handbücher und Release Notes als Internetdokumente zu finden, zum Beispiel der Band I des MCNP-Handbuchs Overview and Theory.[24]
  • PYTHIA ist ein Simulationsprogramm für die Teilchenphysik und simuliert Kollisionen und dabei entstehende Teilchen.
  • SHERPA ist ein Simulationsprogramm für die Hochenergie-Teilchenphysik. Entstanden an der TU Dresden, wird es inzwischen von einer international verteilten Arbeitsgruppe um Frank Krauss entwickelt.
  • SPICE ist ein Simulationsprogramm für analoge, digitale und gemischte elektronische Schaltungen. Mit der Monte-Carlo-Simulation ist es möglich, die Auswirkungen der Streuung der Bauteilewerte innerhalb der angegebenen Toleranz zu berechnen.

Siehe auch[Bearbeiten | Quelltext bearbeiten]

Literatur[Bearbeiten | Quelltext bearbeiten]

Weblinks[Bearbeiten | Quelltext bearbeiten]

Commons: Monte-Carlo-Simulation – Sammlung von Bildern, Videos und Audiodateien

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  1. Isaac Todhunter: History of the Mathematical Theory of Probability, 1865, S. 203
  2. Christophe Andrieu, Nando de Freitas, Arnaud Doucet, Michael I. Jordan: An Introduction to MCMC for Machine Learning (PDF, 1,0 MB), In: Machine Learning 2003, Vol. 50, Band 1–2, S. 5–43.
  3. Lecture Notes in Structural Reliability - Engineering Risk Analysis Group; Technische Universität München
  4. N Metropolis: BEGINNING of the MONTE CARLO METHOD. Hrsg.: Los Alamos Science Special Issue. 1987, S. 125–130 (fas.org [PDF]).
  5. Douglas Hubbard: How to Measure Anything: Finding the Value of Intangibles in Business. John Wiley & Sons, 2007, S. 46.
  6. Charles Grinstead, J. Laurie Snell: Introduction to Probability. American Mathematical Society, 1997, S. 10–11.
  7. H. L. Anderson: Metropolis, Monte Carlo and the MANIAC. (PDF, 829 kB) Los Alamos Science, Nr. 14, 1986, S. 96–108, 1986.
  8. N. Metropolis, A. W. Rosenbluth, M. N. Rosenbluth, A. H. Teller, E. Teller: Equation of State Calculations by Fast Computing Machines. In: The Journal of Chemical Physics. Volume 21, Number 6, Juni 1953, S. 1087–1092, doi:10.1063/1.1699114.
  9. M. Rosenbluth: Genesis of the Monte Carlo Algorithm for Statistical Mechanics, AIP Conference Proceedings, Band 690, 2003, S. 22–30, Konferenz am LANL anlässlich des 50. Jahrestags der Veröffentlichung der Arbeit von 1953
  10. J. E. Gubernatis: "Marshall Rosenbluth and the Metropolis Algorithm, Physics of Plasmas, Band 12, 2005, S. 057303.
  11. M. Rosenbluth, A. Rosenbluth: Further Results on Monte Carlo Equations of State, The Journal of Chemical Physics, Band 22, 1954, S. 881–884
  12. M. Rosenbluth, A. Rosenbluth: Monte Carlo Calculation of the Average Extension of Molecular Chains, The Journal of Chemical Physics, Band 23, 1955, S. 356–359
  13. Gleißner; W.: Risikoanalyse, Risikoquantifizierung und Risikoaggregation, in: WiSt, 9/2017, S. 4–11
  14. S. Jayraman: A Review of Monte Carlo Methods in Real Estate. 2. Mai 2013, abgerufen am 20. Mai 2017 (englisch, und Quellen darin).
  15. Klaus Bernhard Gablenz: Monte Carlo hilft bei Unsicherheiten. In: Immobilienzeitung. Ausgabe 29, 26. Juli 2007, S. 6 (svgablenz.de [PDF]).
  16. Prof. A. Bachem in Interview, c't 12/2010, S. 18: So lassen sich probabilistische Lösungsverfahren zumeist weitaus besser parallelisieren als die heute üblichen deterministischen.
  17. MERCURY. Abgerufen am 13. August 2019.
  18. 2014 Jul 10: Trinity supercomputer to support nuclear stockpile simulations -. Abgerufen am 13. August 2019 (englisch).
  19. Nicole Hemsoth: NNSA Stockpile of Nuclear Security Supercomputers Continues Evolution. 16. Juli 2015, abgerufen am 13. August 2019 (amerikanisches Englisch).
  20. Stockpile Stewardship Program. Abgerufen am 13. August 2019.
  21. David MacKay: Kapitel 4.4 Typicality & Kapitel 29.1. In: Information Theory, Inference and Learning Algorithms. Cambridge University Press, 2003, ISBN 978-0-521-64298-9.
  22. Im der bibliografischen Datenbank WorldCat sind über 10000 Arbeiten verzeichnet, die dem Programm MCNP selbst oder Anwendungen des Programms gewidmet sind
  23. A General Monte Carlo N-Particle (MCNP) Transport Code: Monte Carlo Methods, Codes, & Applications Group. Abgerufen am 19. Juni 2018.
  24. X-5 Monte Carlo Team: MCNP — A General Monte Carlo N-Particle Transport Code, Version 5: Volume I: Overview and Theory. Abgerufen am 19. Juni 2018.