Probabilistische Algorithmen SS10

Aus ProgrammingWiki

< AuK
Wechseln zu: Navigation, Suche

Loading
Autoren:

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

Inhaltsverzeichnis

Einleitung

Diese Seite ist zum Themenkomplex Algorithmen und Komplexitä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. Probabilistisch heißt soviel wie warscheinlich, d.h. dass in diesen Algorithmen bestimmt Zufallsereignisse mit einer bestimmten Wahrscheinlichkeit auftreten. Randomisierend heißt zufällig und gemeint ist auch, dass in diesem Algorithmus mit Zufallszahlen arbeitet.

In diesem Themenkomplex werden verschiedene Arten von Algorithmen eingeleitet, diese sind:
  • Pseudozufallszahlengenerator
  • Monte-Carlo-Algorithmen
  • Las-Vegas-Algorithmen
  • Ant Colony Optimization Metaheurisitk

Um das Verständnis des Themas noch mehr zu fördern, sind hier noch die Präsentationsfolien.

PrasentationFolie.zip (0.7 MB)

Pseudozufallszahlen

Zufall

Der Zufall ist einer der meist diskutierten Begriffe der Wissenschaft.Die eigentliche Definition lautet, dass ein Ereigniss zufällig ist, wenn sie ohne Plan eintritt. Die gleiche Meinung hatte Epikur, der meinte, dass der Zufall die eigentliche Natur der Erscheinung ist.Der zweite Philosopher ,nähmlich der Demokrit, war der Absicht,dass das Zufällige das Unerkannte ist.Damit meinte er, dass der Zufall mit einer, für uns noch unbekannten, Gesetzmäßigkeit entsteht.Ob der Zufall objektiv oder subjektiv ist, streiten sich die Menschen seit der Antike.Man kann bis jetzt nur eins feststellen, dass in allen Programmiersprachen, die man bis jetzt geschafft hat zu entwickeln, die Zufallszahlen subjektiv sind.

Zufallszahlen in Programmiersprachen

In Programmiersprachen kann man Zufallsgrößen in Form von Zufallszahlen erzeugen.Jedoch in diesem Zusammenhang spricht man mehr von Pseudozufallszahlen, weil sie nach einem bestimmten Prozeß, der jedoch aufgrund des Konzeptes der Datenabstraktion für den Nutzer verborgen bleibt, simuliert werden.Man hat nur eine Aufrufschnittstelle in Form einer Methode, die als Pseudozufallszahlengenerator bezeichnet wird.Mit der kann man Pseudozufallszahlen in einem gewünschten Intervall erzeugen.

Hier noch ein paar Beispiele, wie die Zufallsgeneratoren und die zugehörigen Methoden in einigen Programmiersprachen aussehen. 

c# :  random zufall = new Ranndom();
      int x = zufall.nextInt(1,10);

Pascal: Randomize;
        Random(45);

c++ : rand()% 6+1

Scheme: (random 10)

Java: Random zufall = new Random();
      int x = zufall.nextInt(20);
   
      int x = (int)Math.random()* 4+1;

Es gibt Methoden, um die Pseudozufallszahlen zu erzeugen, die letztendlich gleichmäßig verteilt sind, d.h. jede Zahl mit der gleichen Warscheinlichkeit auftretten kann .Im folgenden Experiment wurden zwei Kontruktionen in der objektorientierten Programiersprache Java verwendet.Die erste ist int x = (int)(Math.round(Math.random() * (max - min)) + min); und die zweite int x = (int)(Math.floor(Math.random() * (max - min +1 )) + min); Auf den ersten Blick erkennt man keinen Unterschied zwischen den beiden Methoden.Aber wenn man sich das folgende Experiment anschaut, merkt man, dass die zweite Methode die gleichmäßig verteilte Zufallszahlen generiert und die erste nicht.

Kongruenzmethode

Die lineare Kongruenzmethode ist schon seit 1938 bekannt.Mit deren Hilfe kann man die Pseudozufallszahlen generieren. Dabei muss man die folgenden Regeln beachten:

  • ... ist der Seed (Keim,Startwert)
  • ...große Zweierpotenz
    • oder um ein lange Periode zu bekommen

Wenn der Seed fest ist, dann werden immer die gleichen Pseudozufallszahlen, die sich nach einer bestimmten Periode wiederholen, erzeugt.Dies sieht man oft als ein großer Vorteil bei Entwicklung bestimmter Simulationen. Es ist jedoch auch möglich bei jeder Ausführung der implementierten Methode unterschidliche Perioden von Pseudozufallszahlen zu erhalten. Dies macht man indem man den Seed zufällig mit der Systemzeit auswählt.


unterschiedliche Periode von Zufallszahlen :

gleiche Periode von Zufallszahlen :

Pseudozufallszahlen im Interval

Hier noch der Quellcode für die Kongruenzmehode ins Scheme:

Pseudozufallszahlen_kongruenz.zip (0.1 MB)

Monte-Carlo-Algorithmen

Geschichte

Umfassende Untersuchungen zur Entwicklung und Erarbeitung des Verfahren der statischen Versuche begann Mitte der 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 insbesondere 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 ältestes Beispiel zur Benutzung des betrachteten Verfahren gilt, das bufonsche Problem, welches von dem Franzosen Buffon gestellt wurde. Darin geht es, um die Berechnung der transzenden Zahl 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 falsche Egebnisse liefern kann. Jedoch durch mehrmalige Realisierung sinkt die Warscheinlichkeit, dass ein falsches Ergebniss geliefert 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 wir haben 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 geliefert.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:

Anwendungsbereiche

Man kann 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.

Pi Berechnung

Mit der Monte Carlo Methode lässt sich ganz einfach das buffonsche Problem lösen,indem man kann mit Hilfe von Zafallszahlen die transzendente Zahl ermittelt. Man betrachtet dabei einen Kreis, der von einem Quadrat umgeben ist.Um die Berechnung zu vereinfachen, nimmt man nur ein Viertel des Quadrates.So ist die Seitenlänge des Quadratviertels genauso lang wie der Radius des Kreises.Dann setzt man das Quadratviertel ins Koordinatensystem ein und erzeugt die Pseudozufallszahlen für die Koordinaten und ,welche im rechtsoffenen Interval liegen.Wenn die Hypotenuse der beiden Koordinaten, die nach dem Satz von Pythagoras berechnen werden kann,eine Länge hat, die kleiner als 1 ist, dann liegt der erzeugte Punkt auf der Kreisfläche.Je mehr Punkte man erzeugt, desto genauer wird die Zahl .

B1.png B3.png

Das sind die nötigen Formeln, die man braucht, um die Zahl zu ermitteln:

Beispiel:

Hier noch der Quellcode für die Piberechnung in Scheme:

Piiberechnung.zip (0.1 MB)

Integralberechnung

Ein weiteres Bespiel für die Anwendung des Verfahren der statischen Versuche ist die Integralberechnung. Man muss die Pseudozufallszahlen für die Koordinaten und erzeugen. Danach setzt man die generierten Werte in die Funktion ein. Zum Schluss muss man überprüfen, welche Punkte auf der Fläche liegen.

Mateusz B4.png

Das erfolgt mit den folgenden Regeln.

Dies ist ein Integralrechner für 2 Funktionen einmal und für . 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.

Brooks_Integralrechner.zip (0.4 MB)

Primzahltest

Auch zahlreiche Primzahltests lassen sich mit den Monte Carlo Algorithmen simulieren.Darunter ist der bekannte Fermat Primzahltest. Wenn einer der beiden Formeln für alle mit stimmt, dann hat man mit einer Primzahl zu tun. 


bzw.

Quellcode in Scheme:

Primzahlscheme.zip (0.1 MB)

Weitere Beispiele

Weitere Beispiele befinden sich auch noch im Buch.

Hier noch ein paar Simulationen,in den ein Monte Carlo Algorithmus eine Anwendung gefunden hat, im folgenden sind Simulation von der Diffusion von Silberatomen abgebildet. Diese Simulation wäre mit einem deterministischen Algorithmus zu aufwändig, deshalb benutzt man die Monte Carlo Methode um dies zu simulieren.

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 die Wahrscheinlichkeit der Lösung von x ist, dabei gilt: bzw. 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 steigt auch die Zeit faiure steigt. Man muss also eine gute Wahrscheinlichkeit 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.

Brooks_Vertiefungsaufgabe.zip (0.2 MB)

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

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.

Brooks SameLengthDoubleBridgeFinal.png

Welchen sie letztendlich auswählen ist zufällig

Experiment 2

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.

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

Brooks DiffLengthDoubleBridge1.png

Der Versuchsaufbau entspricht dem von Experiment 2, außer das der kurze Weg am Anfang heraugenommen wird.

Brooks DiffLengthDoubleBridge2.png

Nach ca. 30 min haben sich die Ameisen auf diesen Weg eingepegelt.

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.

Brooks Graph1.PNG 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. angibt

Verhalten der künstlichen Ameisen

Das Verhalten der künstlichen Ameisen setzt sich im Groben aus 3 Schritten zusammen:

  1. Konstruktion probabilistischer Lösungen, ohne

Pheromonerneuerung beim Vorwärtslaufen

  1. Konstruktion eines deterministischen Rückweges mit

Schleifenelimination und Pheromonerneuerung

  1. 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

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: verschiedene Proteine

Übungen

  1. Implementieren Sie eine Methode um pi zuberechnen. Wahlweise in Scheme oder Java.
  2. Schreiben Sie ein Javaprogramm, welches entweder das Maximum von oder das Minimum von berechnet.
    MinMaxLoes.zip (0.1 MB)
  3. Zusatz: Schreiben Sie ein Program das die Nullstellen von berechnet.
    NullstelleLoes.zip (0.1 MB)

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
Von „https://programmingwiki.de/AuK/Probabilistische_Algorithmen_SS10“
Persönliche Werkzeuge