Home

NetLogo

Methoden

Umsetzungen

Aktuelles

Forschung

Sonstiges

Links

Kontakt

Monte-Carlo Methode

Die Idee hinter der Monte-Carlo Methode ist einfach. Für ein Suchproblem werden tausende bis abertausende zufällige Lösungsvorschläge generiert. Für jeden Vorschlag wird die Leistungsfähigkeit anhand einer Evaluierungsfunktion ermittelt und die jeweils beste bisher gefundene Lösung gespeichert. Openshaw (Openshaw & Openshaw 1997, S. 102) meint hierzu: "It is crude, but can be surprisingly effective."

Das gegebene Problem muß auf irgendeine Art und Weise parametrisierbar sein. Der Lösungsgenerator muß so programmiert werden, daß die zufällig erstellten Lösungen das Problem zumindest theoretisch auch lösen können. Angenommen, es sind drei Werte für die Variablen A, B und C gesucht, die die Funktion X = A + B - C maximieren. Aus der Empirie sei bekannt, daß, aus welchen Gründen auch immer, die Variablen A, B und C im Bereich zwischen Null und 100 liegen müssen. Der Lösungsgenerator wird nun so eingestellt, daß den Variablen Werte zwischen Null und 100 zugewiesen werden. Daraufhin ermittelt er nach der gegebenen Formel den Wert für X. Ist der Wert für X höher als der bisher erreichte beste Wert, wird X = bester Wert gesetzt. Der beste erzielbare Wert für X ist der Formel nach 200. Im Versuch auf einem Rechner der unteren Leistungsklasse benötigt NetLogo etwa eine Sekunde, um die Funktion auf X-Werte um 180 zu trimmen. Nach zehn Sekunden wird relativ verläßlich ein Wert von über 190 ermittelt, nach 20 Sekunden ist ein Ergebnis zu erwarten, das nicht mehr als 1 % von der optimalen Lösung abweicht.

Dieses abstrakte Beispiel soll veranschaulichen, daß diese Methode, obwohl sie, wie der Name sagt, mehr einem Glücksspiel ähnelt, sehr leistungsfähig sein kann. Die Qualität der erzielten Lösung hängt von der investierten Rechendauer ab. Ein wesentlicher Vorteil der Methode ist, daß sie parallelisiert werden kann. Das heißt, daß auf mehreren Rechnern gleichzeitig nach Lösungen gesucht werden kann. Ob die Methode für ein Problem geeignet ist, hängt in erster Linie davon ab, ob es in eine computergerechte Form gebracht werden kann und muß im Einzelfall entschieden werden. Da das Verfahren sehr einfach umzusetzen ist, mag ein Versuch in jedem Fall lohnen. Dabei ist zu berücksichtigen, daß die Methode nicht erschöpfend ist.