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==
==Pseudozufallszahlen==
<code id="4c02583ebf3d3" hidden>
(require-library 'sisc/libs/srfi/srfi-19)
(import srfi-19)
</code>
==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 sich erst einmal die Funktionsweise eines Las Vegas Algorithmus anschauen. 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 oder kein Ergebnis zu liefern. Darüberhinaus muss man den Algorithmus n-mal wiederholen bis man ein Egebnis bekommt. Da man nich vorhersagen kann ob der Algorithmus ein Ergebnis liefert, kann man auch nicht vorhersagen wie viele Wiederholungen man braucht und letztendlich kann man auch nicht sagen wie lange es dauert.
==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