AuK/Probabilistische Algorithmen SS10
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Scheme</language>
'''Autoren:'''
#Mateusz Zwierz ([mailto:simazwie@stud.hs-zigr.de simazwie@stud.hs-zigr.de])
#Hans Markwart ([mailto:sihamark@stud.hs-zigr.de sihamark@stud.hs-zigr.de])
==Einleitung==
Diese Seite ist zum Themenkomplex Algorithmen und Komlexität und beschäftigt sich mit dem Thema Probabilistische Algorithmen. Probabilistische, randomisierende oder auch stochastische Algorithmen sind Algorithmen die in irgendeiner Weise mit Zufallszahlen bzw Pseudo-Zufallszahlen arbeiten.
==Pseudozufallszahlen==
<code id="4c02583ebf3d3" hidden>
(require-library 'sisc/libs/srfi/srfi-19)
(import srfi-19)
(define c 262144)
</code>
<code id="4c02a17e463ea">
(define pszfzl
(lambda (z)
(let ((a 16807)(b 0))
(if (eq? z 0)
4567
(modulo (+ (* a (pszfzl (- z 1))) b) c)))))
(define randomize
(lambda ()
(/ (pszfzl (modulo (time-second (current-time)) c)) c)))
(define myrandom
(lambda (n)
(let ((a (randomize)))
(* a n))))
</code>
<eval id="4c02a17e46bd9">(randomize)</eval>
==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 <math>\pi</math> 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:
<popup name="search">
(define a
(lambda (t el ls)
(cond
((<= t 0) 0)
((=(car ls)el) (car ls))
(else
(a (- t 1) el (cdr ls))))))
(define search
(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)))))
(define ls '(1 2 3 6 6 6))
</popup>
<code id="4c02956bc4d8f" hidden>
(define random-maker
(let* ((multiplier 48271)
(modulus 2147483647)
(apply-congruence
(lambda (current-seed)
(let ((candidate (modulo (* current-seed multiplier) modulus)))
(if (zero? candidate)
modulus
candidate))))
(coerce
(lambda (proposed-seed)
(if (integer? proposed-seed)
(- modulus (modulo proposed-seed modulus))
19860617)))) ;; an arbitrarily chosen birthday
(lambda (initial-seed)
(let ((seed (coerce initial-seed)))
(lambda args
(cond ((null? args)
(set! seed (apply-congruence seed))
(/ (- modulus seed) modulus))
((null? (cdr args))
(let* ((proposed-top
(ceiling (abs (car args))))
(exact-top
(if (inexact? proposed-top)
(inexact->exact proposed-top)
proposed-top))
(top
(if (zero? exact-top)
1
exact-top)))
(set! seed (apply-congruence seed))
(inexact->exact (floor (* top (/ seed modulus))))))
((eq? (cadr args) 'reset)
(set! seed (coerce (car args))))
(else
(display "random: unrecognized message")
(newline))))))))
(define random
(let ((seed (time-nanosecond (current-time))))
; (display seed)
(random-maker seed)))
(require-library 'sisc/libs/srfi/srfi-19)
(import srfi-19) ; stellt current-time usw. bereit
(define random (random-maker (time-nanosecond (current-time))))
(define a
(lambda (t el ls)
(cond
((<= t 0) 0)
((=(car ls)el) (car ls))
(else
(a (- t 1) el (cdr ls))))))
(define search
(lambda (ns t el ls)
(cond
((= (a (random t) el ls) 0) 'false)
((= (a (random t) el ls) el) 'true)
(else( search (- ns 1) (random t) el ls)))))
(define ls '(1 2 3 6 6 6))</code>
<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:
<math>t(x)=p(x) \cdot success(x)+(1-p(x)) \cdot (failure(x)t(x))</math>
wobei <math>p(x)</math> die Wahrscheinlichkeit der Lösung von x ist, dabei gilt: <math>0<p(x)<1</math>
<math>success(x)</math> bzw. <math>failure(x)</math> sind die Ausführungszeiten bei Erfolg oder Versagen
Wenn man diese Gleichung noch ein wenig umstellt kommt man auf folgende Gleichung:
<math>t(x)=success(x)+ \left( \frac{1}{p(x)} - 1 \right) \cdot failure(x)</math>
Aus dieser Formel erkennt man, dass wenn die Wahrscheinlichkeit <math>p(x)</math> steigt auch die Zeit faiure steigt. Man muss also eine gute Wahrscheinlichkeit <math>p(x)</math> 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==
===Einleitung===
Ant Colony Optimization(ACO) ist eine Metaheuristik für Verfahren der kombinatorischen Optimisierung und basiert auf dem Verhalten von echten Ameisen. Diese haben die Möglichkeit über Pheromone(Stigmergie) optimale Wege von ihrem Ameisenhügel zu Futterquellen zu finden. Damit gehört es zu den Problemen der Schwarmintelligenz, da viele Individuen, die vlt nicht hoch entwickelt sind, durch Kommunikation in der Lage sind intelligente Verhaltensweisen zu erzeugen. Die ACO-Metaheuristik ist anwendbar auf verschiedenste Optimisierungsprobleme. Marco Dorigo ist ein sehr bekannter Forscher auf dem Gebiet der ACO-algorithmen und der künstlichen Intelligenz. Er stützt sich in seinen Simulationen sehr auf die Forschungsergebnisse von Deneaubourg und Kollegen, diese haben das kollektive Verhalten von Ameisen unter strengen Bedingungen erforscht.
===Verhalten von echten Ameisen===
Aus den Experimenten von Deneaubourg und Kollegen erkennt man bestimmte Verhaltensmuster der Ameisen. Da die Ameisen sowohl Pheromone riechen als auch absondern können, ergeben sich interessante Verhaltensweisen. Wenn Ameisen an einen Punkt ankommen wo sie sich entscheiden müssen, erhöht sich die Wahrscheinlichkeit einen bestimmten Weg zu nehmen mit dessen Pheromonkonzentration, wenn noch keine Pheromone Vorhanden sind wird der Weg zufällig gewählt. So ergibt sich ein autokatalytischer prozess der darin resultiert, dass sich Ameisenstraßen bilden, dem kürzesten Weg zwischen Ameisenhügel und Futterquelle.
==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