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.
===Beispiel===
Hier noch ein Beispiel für einen Monte-Carlo-Algorithmus. Dies ist ein Integralrechner für 2 Funktionen einmal <math>e^{-x^2}</math> und für <math>- \frac{1}{100} x^2 + 4</math>. Die erste Funktion ist dabei interessant, da man diese nicht wirklich integrieren kann. Angehängt ist noch ein wxMaxima Arbeitsblatt mit dem man die Ergebnisse des Programmes noch einmal überprüfen kann.
<document>Brooks_Integralrechner.zip</document>
==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.
===Beispiele===
Dies ist jetzt ein Beispiel eines Las-Vegas-Algorithmus, der sich ein weinig an die Vertiefiefungsaufgabe anlehnt. Es gibt zehn Orte in Görlitz und der Algorithmus generiert 20 zufällige Route. Anschließend vergleicht er diese und gibt die kürzeste Route aus.
<document>Brooks_Vertiefungsaufgabe.zip</document>
==Ant Colony Optimization==
===Einleitung===
Ameisen verhalten sich in komlexen Mustern und Menschen fanden diese Muster schon immer interressant. Die interessanteste Erscheinung sind die sogenannten Ameisenstraßen. Diese Ameisenstraßen haben die wichtige Eigenschaft die kürzeste sStrecke zwischen zwei Punkten zu sein, dem Ameisenhaufen und der Futterquelle. Biologen haben dieses Phänomen untersucht um rauszufinden wie diese Straßen gebildet werden. Deneaubourg hat 1989 Experimente mit Ameisen unter sehr kontrollierten bedingenungen durchgeführt und man konnte interessante Resultate bemerken. Man hat rausgefunden, dass Ameisen, wenn sie sich bewegen eine Spur aus Pheromonen hinterlassen, die wiederrum von anderen Ameisen gelesen werden können. Dieses Verhaltenmuster nennt man Stigmergie und ist sehr wichtig, um diese Straßen zu bauen. Da die Ameisen es schaffen optimale Wege zu schaffen, begannen auch Informatiker sich für Ameisen zu interressieren und versuchten mit künstlichen Ameisen optimale Wege zu finden. Ein wichtiger informatiker auf diesem Gebiet ist Marco Dorigo. Er hat die ACO-Metaheuristik entwickelt, mit der wir uns hier beschäftigen.
===Doppel-Brücken-Experimente===
Im folgenden wollen wir die Experimente von Deneaubourg und Kollegen betrachten. In den Doppel-Brücken-Experimenten sind den Ameisen immer 2 Wege zwischen Nest und Futter gegeben. Im ersten Versuch sind beide Abzweige gleich lang, im zweiten Versuch ist der eine Abzweig doppelt so lang wie der andere und im dritten Versuch ist der Versuchaufbau ähnlich dem zweiten, außer, dass am Anfang der kurze Abzweig entfernt wird und nach einer bestimmten Zeit wieder eingesetzt wird.
====Experiment 1====
[[Bild:Brooks_SameLengthDoubleBridge.png]]
Beide Abzweige sind gleich lang.
Am Anfang entscheiden sich die Ameisen vollkommen zufällig. Durch zufällige Fluktuationen wird ein Abzweig von mehr Ameisen genutzt, daher steigt auf diesem Abzweig die Pheromonkonzentration. Aufgrund der Pheromonkkonzentration, entscheiden sich immer mehr Ameisen für diesen Abzweig. Dies geschieht solange, bis fast alle Ameisen nur noch den einen Weg benutzen.
[[Bild:Brooks_SameLengthDoubleBridgeFinal.png]]
Welchen sie letztendlich auswählen ist zufällig
====Experiment 2====
[[Bild:Brooks_DiffLengthDoubleBridge.png]]
Der untere Abzweig ist doppelt so lang wie der obere. Am anfang ist die Auswahl des Weges wieder völlig zufällig.
[[Bild:Brooks_DiffLengthDoubleBridgeFinal.png]]
Da die Ameisen, die den oberen Weg gewählt haben, in kürzerer Zeit zum Futter und wieder zurück kommen, steigt auf diesem Abzweig die Pheromonkonzentration schneller. Die neuen Ameisen wählen den Weg mit der höheren Pheromonkonzentration, was in diesem Fall der kürzere Weg ist. Dies resultiert darin, dass nachh einer Weile fast alle Ameisen den kürzeren Weg benutzen.
====Experiment 3====
[[Bild:Brooks_DiffLengthDoubleBridge1.png]]
Der Versuchsaufbau entspricht dem von Experiment 2, außer das der kurze Weg am Anfang heraugenommen wird.
[[Bild:Brooks_DiffLengthDoubleBridge2.png]]
Nach ca. 30 min haben sich die Ameisen auf diesen Weg eingepegelt.
[[Bild:Brooks_DiffLengthDoubleBridge2Final.png]]
Wenn man nun wieder den kurzen Weg einsetzt kann man erkennen, dass die Ameisen es nicht schaffen den suboptimalen Weg zu 'vergessen'. Dass liegt daran das die Pheromone nicht schnell genug verfliegen um ein korrigieren des Pfades möglich zu machen.
====Ergebnisse====
Die Eigenschaften der Ameisen die für uns wichtig sind, sind folgende:
* sie bewegen sich mit einer konstanten Geschwinigkeit
* sie kommunizieren indirekt über Pheromone(Stigmergie)
* sie hinterlassen Pheromone auf dem Hin- und Rückweg
* Die Wahrscheinlichkeit, dass eine Ameise einen Weg wählt,
steigt mit der Pheromonkonzentration des Weges
Außerdem muss man noch die Pheromonverdunstungsrate betrachten
===S-ACO===
====Betrachtungsänderungen====
Wir wollen nun einen Überblick geben auf was man achten muss, wenn man künstliche Ameisen 'herstellen möchte'. Wir werden dieses System S-ACO(Simple-ACO) nennen. Wir wollen disen Pfad von oben vereinfachen und werden ihn daher einfach auf einen Graph abbilden, z.B. können wir den Versuchsaufbau des Experiments 2 mit 2 verscheidenen Graphen darstellen.
[[Bild:Brooks_Graph1.PNG]] [[Bild:Brooks_Graph2.PNG]]
:Der erste Graph stellt genau der Aufbau da, eine kante ist doppelt so lang wie die andere. Beim zweiten Graph dagegen ist der längere Weg eine Kombination aus 2 gleich langen Kanten, somit ist der eine Weg wieder doppelt so lang wie der andere.
:Zusätzlich zu der Abbildungsänderung, ändern wir auch noch das Zeitmodell. Bei den echten Ameisen haben wir ein stetiges Zeitmodell betrachtet, wenn wir jedoch Ameisen simulieren wollen, ist es angebracht ein diskretes Zeitmodell zu verwenden. So kann man die Geschwindigkeit der Ameisen mit z.B. <math>\frac{1\mbox{ Laengeneinheit}}{1\mbox{ Zeiteinheit}}</math> angibt
====Verhalten der künstlichen Ameisen====
Das Verhalten der künstlichen Ameisen setzt sich im Groben aus 3 Schritten zusammen:
# Konstruktion probabilistischer Lösungen, ohne
Pheromonerneuerung beim Vorwärtslaufen
# Konstruktion eines deterministischen Rückweges mit
Schleifenelimination und Pheromonerneuerung
# Evaluation der Qualität der Lösungen und damit auch die
Bestimmung der Quantität der Pheromone, die
zurückgelassen werden, mithilfe der Lösungsqualität
====1. Schritt: Pfad suchen====
Im ersten Schritt betrachten wir die Phase in der die künstliche Ameise vom Ameisenhaufen zur Futterquelle gelangen. Die Ameise bewegt sich dabei von Knoten zu Knoten und liest in Jedem Knoten die lokalen Informationen der ausgehenden Kanten, außer die der Kante von der sie gekommen ist, es sei denn es gibt keine andere Kante. Nun weiß die Ameise auf welcher Kante wie viele Pheromone sind. Sie wählt ihre nächste Kante mit einer bestimmten Wahrscheinlichkeit, wobei sie Kanten mit hoher Pheromonkonzentration bevorzugt. Dabei müsssen man sagen, dass die Ameisen in dieser Phase keine Pheromone abgeben um Schleifen zu vermeiden, denn am Anfang sind nirgendswo Pheromone und dadurch hat jede Kante die gleiche Wahrscheinlichkeit ausgewählt zu werden. Wenn die Ameisen jetzt schon Pheromone abgeben würden, dann auch auf Schleifen, die sie gehen würde. Dies wollen wir vermeiden.
====2. Schritt: Rückweg finden====
Hat eine Ameise es geschafft das Futter zu erreichen, dann muss sie überlegen wie sie zurückkommt. Um einen guten Rückweg zu finden, wird der Hinweg überarbeitet und alle Schleifen entfernt. Dies macht man mit einem einfachen Algorithmus, der wie folgt arbeitet:
:Die Ameise erreicht das Futter über eine Sequenz von Knoten, beginnend beim Nest(0) und endend beim Futter(9).
z.B. 0-2-3-5-2-7-3-5-2-3-9
jetzt wird vom Anfang an überprüft ob die aktuelle Knotennummer noch einmal vorkommt. bei 2 wird man aufmerksam weil man merkt, dass die 2 dreimal vorkommt. nun kann man alle knoten zwischen der ersten und der letzten 2 herausnehmen. Dies wird so oft wiederholt bis keine Knoten mehr vorhanden sind.
Lösung: 0-2-3-9
====3. Schritt: Pheromone abgeben====
Am Ende muss man noch überlegen wie viel Pheromone auf den Kanten abgegeben werden sollen. Dabei kann man zwischen 2 unterschiedlichen Arten der Pheromonerneuerung auswählen:
* Die Ameisen geben eine konstante Menge Pheromone ab
* Die Ameisen geben eine Menge Pheromone ab, die abhängig ist von der Qualität der Lösung(Länge der Strecke), z.B.: je kürzer die Strecke, je mehr Pheromone werden abgegeben, realisiebar durch die Formel <math>\frac{1}{\mbox{Laenge der Strecke}}</math>
====Pheromonverdunstung====
Es ist auch entscheidend wie schnell vohandene Pheromone wieder verfliegen. Es hat sich gezeigt, dass wenn man dieses Problem außer Acht lässt es passieren kann, dass sich die Ameisen zu schnell auf einen suboptimalen Pfad einstellen und diesen dann auch nich mehr 'vergessen' können. Darüber hinaus hat sich gezeigt, dass sich eine niedrige Phäromonkonzentration, positiv auf den 'Erkundungstrieb' der künstlichen Ameisen auswirkt, dadurch können Ameisen längere Pfade vergessen und neue Pfade erkunden.
====Einstellungen====
Das System, das wir durch die oben beschriebenen Mechanismen definiert ist, hat verschiedene Parameter, die man verändern kann, z.B. Ameisenanzahl, Art der Pheromonabgabe, Schrittgröße, etc.
Wir beschreiben im folgenden die Bedingungen für diese Parameter.
* Je größer die Anzahl der künstlichen Ameisen, je größer ist die Wahrscheinlichkeit, dass sie die optimale Lösung finden, führt aber zu einer längeren Berechnungszeit
* Wenn die Menge der Pheromone, die abgegeben werden, abhängig sind von der Länge des Pfades, ist die Wahrscheinlichkeit größer, die optimale Lösung zu finden
* Die Pheromonverdunstungsrate ist kritisch, ist sie zu groß, neigen die Ameisen dazu sich sich auf einen zufälligen Pfad einzupegeln, ist die Rate zu klein verhalten sich die Ameisen genauso oder der Algorithmus konvergiert garnicht.
Wenn wir Diese Einstellungen beachten können wir mit unserem S-ACO System den kürzesten Weg zwischen Nest und Futter finden. Dies sollte exemplarisch wie man mit der ACO-Metaheuristik, ein Problem löst, in dem Fall die Suche nach dem kürzesten Weg zwischen 2 Punkten. Dieses Konzept können wir jetzt auf andere Probleme beziehen, darunter viele Optimierungsprobleme.
====Anwendungsbereiche====
* Traveling Salesman Problem
* verschiedene Optimierungsprobleme, die mit Routenplanung zu tun haben, z.B.: Maschinenbelegungsproblem, Routenplanung von Nachschubversorgung
* Wege durch Telefonnetzwerke oder Internet
* Personaleinsatz bei Flugesellschaften
*Proteinfaltung: 20 Aminosäuren werden mit 100 Aminosäuren zu Proteinen kombiniert: <math>20^{100}</math> verschiedene Proteine
==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