Probabilistische Algorithmen SS10

Autoren:

1. Mateusz Zwierz (simazwie@stud.hs-zigr.de)
2. Hans Markwart (sihamark@stud.hs-zigr.de)

Einleitung

Pseudozufallszahlen

Monte-Carlo-Algorithmen

Geschichte

Umfassende Untersuchungen zur Entwicklung und Erarbeitung des Verfahren der statischen Versuche begann Mitte vierziger Jahre des vorigen Jahrhunderts. Die systematische Forschung wurde dann im Zusammehang mit Arbeiten am Atombombenproject durchgeführt. Da gang es grundsätzlich, um die Simulation der Divusion von Neutronen.Die erste systematische Darstellung wurde 1949 von Metropolis und Ulam vorgelegt. Für die Entwicklung und Erarbeitung des Monte Carlo Algorithmus haben sich besonders drei Wisenschaftler beigetragen. Ein Mathematiker österreichisch ungarischer Herkunft Janos Neumann de Margitta, bekannt als John von Neumann, ein italienischer Kernphysiker Enrico Fermi, der im Jahre 1938 den Nobelpreis für Physik erhalten hat und der schon oben erwähnte polnische Mathematiker Stanislaw Marek Ulam. Die ersten Tabellen von Zufallszahlen wurden unter Verwendung der Ergebnisse der Rouletenspiele aufgestellt.Dies hatte einen wesentlichen Einfuß auf die Namensgebung für das betrachtete Verfahren, weil die Zufallszahlen ausschlagsgebende Rolle in ihm spielen. Von besonderer Bedeutung waren auch die leistungsfähigen Rechnern, die nützliche Impulse für die Weiterentwicklung brachten. Später hat man diese Methode mehr und mehr für die Lösung stochastischer und deterministischer Probleme verwendet. Als altestes Beispiel zur Benutzung des betrachteten Verfahren gilt, das bufonsche Problem, welches von dem Franzosen Buffon gestellt wurde. Da geht es, um die Berechnung der transzenden Zahl \pi durch zufälliges Werfen einer Nadel.

Monte Carlo

Monte Carlo ist eine numerische Methode stochastischer Natur zur Lösung mathematischer, aber auch deterministischer Prozesse und Probleme unter Benutzung von Zufallsgrößen und ihrer Simulation, sowie Modellierung.Das zu lösende Probelem wird durch ein stochastisches Modell ersetzt. Dann werden die Realisierungen der im Modell enthaltenen Zufallsgrößen entsprechend der gegebenen Verteilungsfunktion oder anderer statistischer Kenngrößen mit Hilfe von Pseudozufallszahlen simuliert.Das Vorgehen wird für N Realisierungen wiederholt, wobei jede Erzeugung der Realisierung von der anderen unabhägig ist.Die Ergebnisse der Realisierungen werden statisch ausgewertet und zum Schluß erfolgt eine Interpretation für die ursprüngliche Aufgabenstellung. Jedoch kann man mit diesem Verfahren die herkömmlichen Methoden nicht ersetzen.Die Resultate werden immer angenährt. Um die Genauigkeit zu erhöhen, muss man die Anzahl der Realisierungen erhöhen, was dazu führt, dass der Rechenaufwand größer wird.Der zweite Nachteil und gleichzeitig ein wichtiges Merkmal ist, dass die Methode kann entweder richtige oder auch falsche Egebnisse zurückliefern. Jedoch durch mehrmalige Realisierung sinkt die Warscheinlichkeit, dass ein falsches Ergebniss zurückgeliefrt wird, sehr stark ab. Diese Nachteile spielen keine Rolle, wenn man mit diesem randomiesierten Verfahren bestimmte Klassen von Problemen in ein paar Minuten lösen kann, die mit den deterministischen Ansätzen unlösbar sind bzw. reintheoretisch lösbar sind, aber die Zeit des Berechnungsprozesses mehrere Milliarden von Jahren beträgt. Die Monte Carlo Methode verbindet Elemente der Warscheinlichkeitsrechnung, der mathematischen Statistik und der numerischen Analysis. Die Funktionsweise kann man an einem Beispiel genau beleuchten.Angenommen haben wir eine Liste, die vier Miliarden Einträge hat. Die Liste ist in zwei Teile gegleidert.Im ersten Teil ist nur die Variable a vorhanden und im zweiten nur die Variable n. Jetzt soll man eine Methode entwickeln, die überprüfen soll, ob die Variable n in der Liste vorhanden ist.Von der deterministischen Seite würde die Methode jedes Element, wleches in der Liste vorhanden ist, mit dem Suchelement verglichen.Wenn die beiden stimmen würden, würde ein boolscher Wert true zurückgeliefert.Jedoch die suchende Variable n steht im zweiten Teil der Liste. Aus diesem Grund die Rechenarbeit des deterministischen Algorithmus in diesem Fall würde einfach zu hoch sein. Ein besserer Lösungsweg stellt die Monte Carlo Methode. Man erzeugt die Zufallsgrößen in Form von Zufallszahlen. Jede erzeugte Zufallszahl repräsentiert eine Variable in der Liste.Es kann sein, dass die Zufallszahl eine Variable im Berech des ersten Teiles der Liste repräsentiert.Dann wird natürlich ein falsches Ergebniss zurückgeliefert.Die erzeugte Zufallszahl knn aber auch im zweiten Teil der Liste liegen und dann wird selbstverständlich ein richtiges Ergebniss zurükgeliefert.

Ein Beispiel in der funktionsorientierten Programmiersprache Scheme:

 (lambda (t el ls)
   (cond
        ((<= t 0) 0)
        ((=(car ls)el) (car ls))
        (else
         (a (- t 1) el (cdr ls))))))

 (lambda (ns t el ls)
 (cond
   ((= (a  t el ls) 0) 'false)
   ((= (a t el ls) el) 'true)
   (else( search (- ns 1) t el ls)))))

<eval id="4c02956bc5556"> (search 2 6 1 ls) </eval>

Anwendungsbereiche

kann man Probleme deterministischer Art lösen zb. Berechnung der Integrale, Lösung von gewöhnlichen und partiellen Differentialgleichungen,Berechnung von Eigenwerten, Randwertprobleme bei Differentialgleichungen,sowie stochastische Probleme, wie zb. Zuverlässigkeit von Konstruktionen und Erzeugnissen, Wind und Erdbebenerscheinungen, Verschmutzungsmodelle , Lagerhaltungsprobleme, Ablaufplannungsprobleme Untersuchung des Neutronendurchganges durch eine Platte.Die Methode hat auch Anwendung im Bereich der Kommunikation bei der Informationsübertragung und Kryptographie, aber auch in unterschiedlichen Bedienungssysteme. Auch verwendet man sie, für ie Implementierung zeitkritischer Anwendungen.

Las-Vegas-Algorithmen

Allgemeines

Las Vegas Algorihtmen sind eine Unterart von probabilistischen Algorithmen, ähnlich wie Monte Carlo Algorithmen. Der Name wurde geprägt von László Babai, wegen der Ähnlichkeit zu Monte Carlo Algorithmen und Las Vegas auch bekannt ist für seinen Glücksspielcharakter. Babai erarbeitete diese Art von Algorithmen ca. 1979 um die Graphenisomorphie zu überprüfen.

Eigenschaften

Die wichtigste Unterschied zu Monte Carlo Algorithmen ist, dass anstatt Näherungswerte zurückzugeben, Las vegas Algorithmen immer ein richtiges Ergebnis zurückgeben. Darüber hinaus gibt es noch einen Spezialfall, unzwar wenn der Algorithmus in eine Sackgasse führt, aber da es heißt, dass ein Las Vegas Algorithmen immer ein richtiges Ergebnis zurückliefert muss man es schaffen aus einer Sackgasse zurückzukommen. Die Antwort ist ganz einfach, wenn der Algorithmus in eine Sackgasse führt wiederholt man einfach den Algorithmus noch einmal mit der gleichen Eingabe. Die Wahrscheinlichkeit, dass nach wiederholter Ausführung des Algorithmus kein Ergebnis gefunden wird wird mit zunehmender Anzahl der Wiederholungen immer kleiner.

Zeitkomplexität

Um die Zeitkomplexität zu berechnen muss man erst einmal die Funktionsweise eines Las Vegas Algorithmus betrachten. Ein Las Vegas Algorithmus widerholt sich solange selbst bis er ein Ergebnis liefert. Der Algorithmus ist probabilistisch, d.h. er arbeitet mit Zufallszahlen, d.h man kann nicht vorhersagen wie viele Schritte ein Algorithmus braucht um ein korrektes oder kein Ergebnis zu liefern. Darüber hinaus muss man den Algorithmus n-mal wiederholen bis man ein Egebnis bekommt. Da man nicht vorhersagen kann ob der Algorithmus ein Ergebnis liefert, kann man auch nicht vorhersagen wie viele Wiederholungen man braucht und deshaöb kann man auch nicht sagen wie lange er braucht um zu terminieren. Die erwartete Zeit bis der Algorithmus ein korrektes Ergebnis berechnet ergibt sich wie folgt:

wobei p(x) die Wahrscheinlichkeit der Lösung von x ist, dabei gilt: 0<p(x)<1 success(x) bzw. failure(x) sind die Ausführungszeiten bei Erfolg oder Versagen

Wenn man diese Gleichung noch ein wenig umstellt kommt man auf folgende Gleichung:

Aus dieser Formel erkennt man, dass wenn die Wahrscheinlichkeit p(x) steigt auch die Zeit faiure steigt. Man muss also eine gute Wahrscheinlichkeit p(x) wählen, damit die Zeit die der Algorithmus braucht um einen Versagen zu erkennen, nicht zu groß wird und die Effizienz des Algorithmus verschlechtert.

Sherwood-Algorithmen

Eine spezielle Form der Las-Vegas-Algorithmen sind die Sherwood-Algorithmen. Bei diesen Las-Vegas-Algorithmen ist die Möglichkeit in eine Sackgase zu geraten ausgeschlossen, d.h. der Algorithmus terminiert immer und gibt ein richtiges Ergbnis zurück. Dieser name leitet sich von Robin Hood ab, der im Sherwood Forest lebte und nach dem Motto lebte: "Nimm' es den Reichen und gib es den Armen!". Der Sherwood-Algorithmus hat die Eigenschaft, bei fast allen Eingaben, das Ergebnis mit dem mittleren Aufwand zu berechnen. Bei einem deterministischen Algorithmus gibt es immer Eingaben, bei denen sich der Algorithmus sehr gut oder sehr schlecht verhält. Mithilfe eines Zufallselementes kann man diesen großen Unterschied abdämpfen, sodass sich der Algorithmus für jede Eingabe mit dem mittleren Aufwand rechnet. Dies nennt man auch den Robin-Hood-Effekt. Ein gutes Beispiel ist das Probibalistische Quicksort, bei diesem Verfahren wird das Pivotelement zufällig gewählt, somit ist der Aufwand unabhängig von der Sortiertheit der Eingabeliste.

Ant Colony Optimization

Quellen

Weblinks

[1] http

//en.wikipedia.org/wiki/Marco_Dorigo

[2] http

//en.wikipedia.org/wiki/Las_Vegas_algorithm

[3] http

//en.wikipedia.org/wiki/Ant_colony_optimization

Literatur

[1] Christian Wagenknecht

Algorithmen und Komplexität.- Fachbuchverlag Leipzig, 2003.- ISBN 3-446-22314-2

[2] Marco Dorigo, Thomas Stützle

Ant Colony Optimization.- A Bradford Book, The MIT Press, 2004.- ISBN 0-262-04219-3

[3] Juraj Hromkovic

Randomisierte Algorithmen.- B. G. Teubner Verlag, 20034.- ISBN 3-519-00470-4