Monte-Carlo-Algorithmus

Monte-Carlo-Algorithmen sind randomisierte Algorithmen, die mit einer nichttrivial nach oben beschränkten Wahrscheinlichkeit ein falsches Ergebnis liefern dürfen. Dafür sind sie im Vergleich zu deterministischen Algorithmen häufig effizienter. Ihr Nachteil besteht darin, dass das berechnete Ergebnis falsch sein kann. Durch Wiederholen des Algorithmus mit unabhängigen Zufallsbits kann jedoch die Fehlerwahrscheinlichkeit gesenkt werden (Probability Amplification. Im Gegensatz zu Monte-Carlo-Algorithmen dürfen Las-Vegas-Algorithmen nur korrekte Lösungen berechnen.

Der Name Monte-Carlo hängt laut N. Metropolis 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“.

Monte-Carlo-Algorithmen dienen als Basis für Monte-Carlo-Simulationen.

Ein- und zweiseitiger Fehler

Monte-Carlo-Algorithmen gibt es für

Diese Konzepte werden im folgenden Abschnitt verdeutlicht, in dem Komplexitätsklassen für Probleme mit Monte-Carlo-Algorithmen definiert werden.

Komplexitätsklassen für Entscheidungsprobleme mit randomisierten Algorithmen

Die angegebenen Schranken für die Wahrscheinlichkeiten müssen jeweils für alle Eingaben gelten; die Wahrscheinlichkeiten beziehen sich jeweils nur auf die vom Algorithmus verwendeten Zufallsbits (und nicht auf die Eingabe, die Eingabe wird also nicht als zufällig aufgefasst). Mit Hilfe von Probability Amplification kann man zeigen, dass die Konstante 2/3 aus der Definition von BPP durch jede andere Konstante aus dem Intervall (1/2,1) ersetzt werden kann, ohne die Menge BPP zu ändern; ebenso kann in den Definitionen von RP und co-RP die Konstante 1/2 durch jede Konstante aus dem Intervall (0,1) ersetzt werden.

Obwohl BPP und RP Mengen von Problemen sind, werden im allgemeinen Sprachgebrauch häufig Begriffe wie BPP-Algorithmen oder RP-Algorithmen benutzt, um Algorithmen mit den oben definierten Eigenschaften zu bezeichnen.

Zur Verdeutlichung der Definition von RP: Wenn ein RP-Algorithmus die Ausgabe Ja liefert, wissen wir mit Sicherheit, dass die Ausgabe Ja korrekt ist (da die Definition sicherstellt, dass bei korrekter Ausgabe Nein dies auf jeden Fall auch ausgegeben wird). Wenn dagegen ein RP-Algorithmus die Ausgabe Nein liefert, wissen wir nichts über die korrekte Ausgabe (da nach der Definition die Ausgabe Nein möglich ist, wenn Ja oder Nein korrekt wäre).

Methoden

Alle folgenden Algorithmen gehören zu den Markov-Chain-Monte-Carlo-Verfahren, d.h. die Erzeugung der Zustände geschieht auf der Basis der Konstruktion einer Markow-Kette.

Metropolis-Algorithmus

Der von Nicholas Metropolis publizierte Metropolisalgorithmus zur Untersuchung statistisch-mechanischer Systeme mittels Computersimulation leitet sich von der Monte-Carlo-Integration ab. Ein Spezialfall des Algorithmus ist das Gibbs-Sampling.

Sequenzielle Monte-Carlo-Methode (SMC)

Sequenzielle Monte-Carlo-Methoden eignen sich zur Bayesschen Zustandsschätzung von dynamischen Systemen. Ziel ist es, den Systemzustand als Funktion der Zeit auf Basis einer Reihe von Beobachtungen des Systems und A-priori-Kenntnissen der Systemdynamik zu schätzen. Dazu wird die komplizierte Wahrscheinlichkeitsdichte des Zustandes diskret durch eine Menge von Partikeln approximiert. Sequentielle Monte-Carlo-Methoden werden auch Partikelfilter genannt.

Quanten-Monte-Carlo-Methoden (QMC)

Quanten-Monte-Carlo-Methoden werden zur Berechnung physikalischer Observablen in quantenfeldtheoretischen Modellen benutzt. Beispiele sind Modelle aus der theoretischen Festkörperphysik wie das Hubbard-Modell oder das tJ-Modell.

Kinetische Monte-Carlo-Methode

Die kinetische Monte-Carlo-Methode erlaubt es den zeitlichen Fortschritt eines Systems zu simulieren.

Cluster-Algorithmen

Cluster-Algorithmen sind nicht-lokale Verfahren. Hierzu zählen der Swendsen-Wang-Algorithmus und der Wolff-Algorithmus.

Hybrid-Monte-Carlo-Algorithmus

Der Hybrid-Monte-Carlo-Algorithmus ist ein Monte-Carlo-Algorithmus zur Erzeugung von Systemen im kanonischen Zustand. Das Verfahren stellt eine Kombination aus Molekulardynamik und Zufallsbewegung her.

Literatur

Trenner
Basierend auf einem Artikel in: Wikipedia.de
Seitenende
Seite zurück
© biancahoegel.de
Datum der letzten Änderung: Jena, den: 03.06. 2024