Sind alle Simulationsmethoden eine Form von Monte Carlo?

35

Gibt es eine Simulationsmethode, die nicht Monte Carlo ist? Bei allen Simulationsmethoden werden Zufallszahlen in die Funktion eingesetzt, um einen Wertebereich für die Funktion zu finden. Sind also alle Simulationsmethoden im Wesentlichen Monte-Carlo-Methoden?

Sieger
quelle
2
Ich denke, "Stan" war nur Ulams Vorname, nicht der Nachname eines anderen.
Nick Cox
Stan ist in der Tat die Abkürzung für Stanislas . Aus diesem Grund wählte Andrew Gelman STAN für seine neue Simulationssprache.
Xi'an
Wäre bei einem kleinen, vielleicht grenzwertigen, kombinatorischen Problem eine erschöpfende Suche immer noch "Monte Carlo"?
Nick T
3
Ich erinnere mich an meine Vorlesung über randomisierte Algorithmen, dass Monte-Carlo-Methoden stochastische Ergebnisse mit bekannten Laufzeiten haben, im Gegensatz zu Las Vegas-Methoden, die stochastische Laufzeiten haben, aber korrekte Ergebnisse. Keine Referenz dafür außer einem fünf Jahre alten, handgeschriebenen Skript in meiner Schublade. Bearbeiten: Die Wikipedia-Seiten auf Monte Carlo und Las Vegas scheinen damit einverstanden zu sein.
Bayerj
Eine erschöpfende Suche wäre wahrscheinlich eine Brute-Force-Berechnung. Monte-Carlo-Methoden ziehen aus einem Probenraum. Diese Stichprobe ist normalerweise eine kleine Teilmenge des Ergebnisuniversums, wodurch die statistische Analyse nachvollziehbar wird.
Alex Reynolds

Antworten:

41

Es gibt Simulationen, die nicht Monte Carlo sind. Grundsätzlich verwenden alle Monte-Carlo-Methoden das (schwache) Gesetz der großen Zahlen: Der Mittelwert konvergiert zu seiner Erwartung.

Dann gibt es Quasi-Monte-Carlo-Methoden. Diese werden mit einem Kompromiss aus Zufallszahlen und gleichmäßigen Rastern simuliert, um eine schnellere Konvergenz zu erzielen.

Simulationen, die nicht Monte Carlo sind, werden beispielsweise in der rechnergestützten Fluiddynamik verwendet. Es ist einfach, die Fluiddynamik auf einer "Mikroskala" von einzelnen Teilen des Fluids zu modellieren. Diese Teile haben eine Anfangsgeschwindigkeit, einen Anfangsdruck und eine Anfangsgröße und werden von Kräften aus den benachbarten Teilen oder von festen Körpern beeinflusst. Simulationen berechnen das gesamte Verhalten der Flüssigkeit, indem sie alle Anteile und ihre Wechselwirkung berechnen. Effizientes Tun macht dies zu einer Wissenschaft. Dort werden keine Zufallszahlen benötigt.

In der Meteorologie oder der Klimaforschung verhält es sich ähnlich. Nun sind die Anfangswerte aber nicht genau bekannt: Sie haben die meteorologischen Daten nur an einigen Stellen, an denen sie gemessen wurden. Viele Daten müssen erraten werden.

Da diese komplizierten Probleme in ihren Eingabedaten häufig nicht fortlaufend sind, führen Sie die Simulationen mit unterschiedlichen Annahmen aus. Das Endergebnis wird unter den häufigsten Ergebnissen ausgewählt. So werden im Prinzip einige Wettervorhersagen simuliert.

Horst Grünbusch
quelle
5
Eine leichte Korrektur: Monte-Carlo-Simulationen können nicht zufällige Berechnungen verwenden. Es ist gültig, eine Simulation "monte-carlo" zu nennen, wenn die Anfangsbedingungen variieren, und dann nicht zufällige Berechnungen von dort anzuwenden. Viele CFD-Situationen erfordern Monte-Carlo, da die Randbedingungen statistisch definiert sind.
Cort Ammon
14

Die Monte-Carlo-Methode war der erste Ansatz, mit dem Computersimulationen für statistische Probleme eingesetzt wurden. Es wurde vom John von Neumann-, Stanisław Ulam- und Nicholas Metropolis-Team der Los Alamos-Labors entwickelt, die während des Zweiten Weltkriegs an dem Manhattan-Projekt arbeiteten. Es wurde erstmals 1949 von Metropolis & Ulam beschrieben und erschien erstmals in gedruckter Form. Es war möglich, weil die Wissenschaftler, die es entdeckten, auch einen der ersten Computer benutzen konnten , an denen sie arbeiteten. In ihrer Arbeit verwendeten sie Monte-Carlo-Methoden zur Simulation physikalischer Probleme, und die Idee war, dass Sie ein kompliziertes Problem simulieren könnten, indem Sie einige Beispiele für diesen Prozess abtasten. Es gibt mehrere interessante Artikel zur Geschichte von Monte Carlo, zB vonMetropolis selbst oder neuere, zB von Robert & Casella .

"Monte Carlo" war also der Name der ersten Methode, die zum Zweck der Computersimulation zur Lösung statistischer Probleme beschrieben wurde. Dann wurde der Name ein allgemeiner Name für eine ganze Familie von Simulationsmethoden und wird üblicherweise auf diese Weise verwendet.

Es gibt Simulationsmethoden, die nicht als Monte Carlo gelten . Während Monte Carlo die erste Verwendung der Computersimulation war, werden "Computersimulation" und "Monte Carlo" häufig synonym verwendet.

Es gibt unterschiedliche Definitionen von "Simulation", dh

Merriam-Webster- Wörterbuch:

3a: die nachahmende Darstellung der Funktionsweise eines Systems oder Prozesses durch die Funktionsweise eines anderen

Cambridge Wörterbuch:

etwas zu tun oder zu machen, das sich wie etwas Reales verhält oder so aussieht, aber nicht real ist

Wikipedia :

Nachahmung der Funktionsweise eines realen Prozesses oder Systems im Zeitverlauf

Was die Simulation benötigt, um zu funktionieren, ist die Fähigkeit, ein System oder einen Prozess nachzuahmen. Dies erfordert keine Zufälligkeit (wie bei Monte Carlo). Wenn jedoch alle Möglichkeiten ausprobiert werden, ist das Verfahren eher eine erschöpfende Suche oder ein allgemeines Optimierungsproblem . Wenn das zufällige Element beteiligt ist und ein Computer zum Ausführen einer Simulation eines Modells verwendet wird, ähnelt diese Simulation dem Geist der ursprünglichen Monte-Carlo-Methode (z. B. Metropolis & Ulam, 1949). Das Zufallselement als wesentlicher Bestandteil der Simulation wird beispielsweise von Ross (2006, Simulation. Elsevier). Die Antwort auf die Frage hängt jedoch stark von der Definition der Simulation ab, die Sie annehmen. Wenn Sie beispielsweise annehmen, dass deterministische Algorithmen, die eine Optimierung oder eine umfassende Suche verwenden, tatsächlich Simulationen sind, müssen wir eine Vielzahl von Algorithmen als Simulationen betrachten, was die Definition der Simulation an sich sehr unscharf macht.

Buchstäblich jedes statistische Verfahren verwendet ein Modell oder eine Annäherung an die Realität, die "ausprobiert" und bewertet wird. Dies stimmt mit den Wörterbuchdefinitionen der Simulation überein. Wir betrachten jedoch nicht alle Statistiken als simulationsbasiert. Die Frage und die Diskussion scheinen sich aus dem Fehlen der genauen Definition von "Simulation" zu ergeben. Monte Carlo scheint ein archetypisches (und erstes) Beispiel für die Simulation zu sein. Wenn wir jedoch eine sehr allgemeine Definition der Simulation betrachten, fallen viele Nicht-Monte-Carlo-Methoden in die Definition. Es gibt also Nicht-Monte-Carlo-Simulationen, aber alle eindeutig simulationsbasierten Methoden ähneln dem Geist von Monte Carlo, beziehen sich in irgendeiner Weise darauf oder wurden von ihm inspiriert. Aus diesem Grund wird "Monte Carlo" häufig als Synonym für "Simulation" verwendet.

Tim
quelle
3
Ich denke, "Stan" war nur Ulams Vorname, nicht der Nachname eines anderen.
Nick Cox
1
Stan ist in der Tat die Abkürzung für Stanislas . Aus diesem Grund wählte Andrew Gelman STAN für seine neue Simulationssprache.
Xi'an
Wäre bei einem kleinen, vielleicht grenzwertigen, kombinatorischen Problem eine erschöpfende Suche immer noch "Monte Carlo"?
Nick T
6
Ich verstehe es nicht: Wie beantwortet das die Frage?
o0 '.
1
@ Xi'an Es ist Stanisław, geschrieben mit "Ł" (gelesen als "woo" in Englisch).
Tim
13

Bei allen Simulationsmethoden werden Zufallszahlen in die Funktion eingesetzt, um einen Wertebereich für die Funktion zu finden.

Ich habe noch nie von dieser Definition von Simulation gehört. Beispielsweise werden in Wikipedia-Artikeln zu Simulationen und Computersimulationen Begriffe wie zufällig und stochastisch nur kurz erwähnt.

Ein einfaches Beispiel für eine Simulation, die keine Zufälligkeit beinhaltet und somit eindeutig keine Monte-Carlo-Simulation ist, wäre das Folgende:

Ich möchte das Verhalten eines einfachen Pendels simulieren und einige vereinfachende Annahmen treffen (masselose Schnur, pünktliche Masse, keine Reibung, keine äußeren Kräfte wie die Coriolis-Kraft). Dann erhalte ich ein mathematisches Pendel und kann Differentialgleichungen aufschreiben, die seine Bewegung beschreiben. Ich kann dann einen Löser für Differentialgleichungen wie eine Runge-Kutta-Methode verwenden , um die Flugbahn für gegebene Anfangsbedingungen zu simulieren. (Ich kann auch theoretisch argumentieren, dass ich keine weiteren Anfangsbedingungen berücksichtigen muss.)

Auf diese Weise erhalte ich eine ziemlich gute Simulation eines realen Pendels, ohne jemals eine Zufallszahl zu verwenden. Daher ist dies keine Monte-Carlo-Simulation.

Betrachten Sie in einem anderen Beispiel die logistische Karte , ein einfaches Bevölkerungsmodell ohne Zufälligkeit.

Wrzlprmft
quelle
7

Nein. Die Simulation eines Teilchens unter einer Kraft kann mit Runge-Kutta oder einem anderen deterministischen Algorithmus erfolgen, der nicht Monte Carlo ist.

Monte Carlo wird zur Berechnung von Integralen verwendet (Sie können es als Simulation bezeichnen, aber am Ende wird nur eine numerische Approximation eines Schätzers berechnet). Auch hierfür können Sie eine deterministische Methode verwenden (z. B. Trapezregel).

Im Allgemeinen können Sie Algorithmen trennen, um Integrale deterministisch und nicht deterministisch zu berechnen. Monte Carlo ist eine nicht deterministische Methode. Quasi-Monte Carlo ist eine andere. Die Trapezregel ist ein deterministischer Algorithmus.

Jorge Leitao
quelle
4

Lassen Sie mich auf eine vereinfachte Erklärung eingehen. Ein "Was-wäre-wenn" -Modell ist eine (deterministische) Simulation. Angenommen, Sie haben ein komplexes System wie eine Widget-Verarbeitungsanlage. Sie möchten in der Lage sein, einige Leistungsparameter, z. B. Kosten, abzuschätzen. Sie erstellen ein mathematisches Modell der Anlage und wählen dann verschiedene Annahmen für bestimmte Faktoren im Modell aus, z. B. wie schnell sich Widgets durch verschiedene Operationen bewegen, welche Prozentsätze in verschiedene Richtungen fließen oder wie viele Widgets Sie verarbeiten werden. Das Modell ist eine Simulation der Anlage und jede Reihe von Annahmen gibt Ihnen eine Schätzung dieses Leistungsparameters.

Führen Sie nun Unsicherheit ein. Sie wissen nicht, wie hoch die Nachfrage nach Widgets im nächsten Monat sein wird, aber Sie müssen die Kosten schätzen. Anstatt zu sagen, dass der Bedarf 1.000 Widgets beträgt, schätzen Sie die Wahrscheinlichkeitsverteilung für den Bedarf. Dann nehmen Sie zufällig Bedarfswerte aus dieser Verteilung und verwenden diese für Ihre Annahme. Während Sie dabei sind, können Sie Wahrscheinlichkeitsverteilungen auch für andere Annahmen verwenden. Sie verwenden das Modell immer wieder und stecken dabei Annahmen ein, die aus den verschiedenen Wahrscheinlichkeitsverteilungen stammen. Das Ergebnis wird eine Verteilung der Kostenschätzungen sein. Das ist der Monte-Carlo-Aspekt.

Monte Carlo ist ein "Feature" oder eine "Engine", die über einem Simulationsmodell liegt. Anstatt mit einem einzigen Satz von Annahmen für eine einzelne Schätzung zu simulieren, wird eine Sammlung von Simulationen unter Verwendung zufällig ausgewählter Annahmen durchgeführt.

fixer1234
quelle
2

Insbesondere in der Spieltheorie werden Ansätze, die Zufälligkeit in den Simulationen verwenden, als Monte-Carlo-Techniken bezeichnet. Es wird normalerweise als Teil der Monte Carlo Tree Search (MCTS) in modernen Programmen verwendet.

(Die ursprüngliche Frage hat nicht zwischen " Monte-Carlo-Algorithmus " und " Monte-Carlo-Methode " unterschieden, was möglicherweise die Meinungsverschiedenheit über einige der hier gestellten Antworten erklärt.)

Zum Beispiel werden im Game of Go (und allen anderen mir bekannten Spielen, die MCTS verwenden) die Simulationen als Playouts bezeichnet. Bei Zufallswiedergaben werden die strengsten Regeln angewendet. Leichte Playouts sind entweder ein Synonym für zufällige Playouts oder filtern einige leicht zu erkennende schlechte Züge heraus. Schwere Playouts verwenden mehr Heuristiken, um viel mehr Züge herauszufiltern. (Übrigens geht das Playout immer bis zum Ende des Spiels, so dass jedes Playout ungefähr die gleiche Zeit in Anspruch nimmt.) Aber alle werden als "Monte Carlo" -Simulationen bezeichnet.

Darren Cook
quelle