Probabilistische Algorithmen SS09

Aus ProgrammingWiki

< AuK
Wechseln zu: Navigation, Suche

Loading

Autoren:
Torsten Schröter - sitoschr@stud.hs-zigr.de
Tobias Gaertner   - sitogaer@stud.hs-zigr.de
Rene Schönfelder  - sirrscho@stud.hs-zigr.de
Mario Jeremias  - simajere@stud.hs-zigr.de


adtEEJ <a href="http://ixjnirfpjnwn.com/">ixjnirfpjnwn</a>, [url=http://ptqpbuveyvtc.com/]ptqpbuveyvtc[/url], [link=http://sxozczlziqar.com/]sxozczlziqar[/link], http://iucvllmcvzeq.com/

Inhaltsverzeichnis

(Pseudo)Zufallszahlen

Für probabilistische Algorithmen und Vorhersagen benötigt man Zufällige Ereignisse.

Die Frage, was kann man überhaupt als Zufall bezeichnen?, beantworten wir für uns so: Ein Zustand tritt dann zufällig ein, wenn er nicht vorhersagbar ist.

Der Computer ist auf Grund des Determinismus (eine bestimmte Eingabe führt bei identischer Verarbeitung stets zu der selben Ausgabe) ein schlechter Zufallszahlengenerator.


!!! Definition:

  • Ein Algorithmus ist determiniert, wenn dieser bei jeder Ausführung mit gleichen Startbedingungen und Eingaben gleiche Ergebnisse liefert.
  • Ein Algorithmus ist deterministisch, wenn zu jedem Zeitpunkt der Algorithmusausführung der nächste Handlungsschritt eindeutig definiert ist.


Der prinzipielle Anspruch an Zufallszahlen ist:

  • möglicht große bzw möglichst keine erkennbare Periode
  • gleichförmige Verteilung und
  • keinerlei Zusammenhänge zwischen den gewonnen Zahlen.


Die 1948 von LEHMER entwickelte Kongruenzmethode ist ein deterministisches Verfahren zum erzeugen sogenannter Pseudozufallszahlen. Sie erzeugt eine ”zufällige” Zahlenfolge ausgehend von einem Startwert (seed), dabei folgt sie der rekursiven Vorschrift:


mit


Es gibt dabei ungünstige Kombinationen, sodas möglicherweise nur eine sehr kleine Periode erreicht wird. In der Praxis hat sich folgendes bewehrt:



Diese Methode liefert uns jedoch bei gleichem seed immer die gleiche Zahlen-kette, noch dazu ist sie periodisch (hängt von der Größe von c ab).

Der Anspruch an Zufallszahlen variiert sehr stark je nach Anwendungsbereich. Für ein simples Würfelspiel reicht es schon aus, wenn man den Algorithmus nicht durchschauen kann...dh. die Ergebnisse ausreichend unvorhersehbar und ausreichend gleich verteilt sind. Für Anwendungen in der Kryptografie hingegen ist es unbedingt erforderlich nicht reproduzierbare Zahlen zu erzeugen - also benötigen wir ein nicht deterministisches Verfahren.


Wir benötigen also nichtdeterminierte bzw. nichtdeterministische Algorithmen.


Der Computer arbeitet jedoch streng determiniert, so ist uns dieses nicht direkt möglich, vielmehr können wir nur versuchen unseren seed schon sehr beliebig (möglichst zufällig) zu wählen.

Hierfür könnten wir zum Beispiel die UNIX-Systemzeit verwenden.


Ein Beispiel:

Testen sie die Java-Prozedur myRandom, zunächst mit selbst gewähltem seed.



Die Prozedur liefert uns eine große Zahl, jedoch jedes mal die gleiche...wenn wir nun jedes Mal eine beliebige Zahl als seed eingeben wählen würden, hätten wir ein durchaus unduchschaubares Ergebnis, JEDOCH nur wenn wir das Ergebnis noch nicht kennen. Noch besser währe es, wenn wir nicht einmal die Eingabezahl wüssten... Der implementierte Algorithmus kann das.

Rufen Sie die Prozedur ohne Eingabeparameter auf.

Der hierbei verwendete seed ist die UNIX-Systemzeit, wir erhalten (für uns) unvorhersagbare Zufallszahlen.


...ein kleiner Anreiz zum ausprobieren: java.lang.Math.abs(myRandom()%100);

Es gibt natürlich auch noch andere Möglichkeiten Zufallszahlen zu erzeugen

Um für manche Anwendungsfälle in der Praxis taugliche Zufallszahlen zu erzeugen werden physikalische Zufallszahlengeneratoren verwendet. Sie nutzten physikalische Prozesse wie elektrisches oder thermisches Rauschen, Bildrauschen von Web-Cams oder Radioaktiven Zerfall. Ein nettes Beispiel findet ihr hier: http://von-und-fuer-lau.de/randcam.html

Algorithmen

Las-Vegas-Algorithmen

Las-Vegas-Algorithmen sind randomisierte Algorithmen, die uns garantieren, dass jede berechnete Ausgabe korrekt ist. Somit ist ein falsches Resultat in diesem Modell der randomisierten Berechnung verboten. In der Literatur benutzt man aber zwei unterschiedliche Modelle der Las-Vegas-Algorithmen und zwar abhängig davon, ob auch eine Antwort "?" mit der Bedeutung "Ich weiß es nicht" bzw. "In diesem Lauf war ich nicht im Stande, die richtige Lösung zu berechnen", zulässig ist.

Bei der ersten, strengeren Möglichkeit, definiert sich ein Algorithmus A als Las-Vegas-Algorithmus für die Berechnung der Funktion F, wenn für jede Eingabe x von F gilt:

.

Bei dieser Definition des Las-Vegas-Algorithmus wird immer die erwartete Komplexität der Algorithmen untersucht, etwa die erwartete Zeitkomplexität . Hier ist es zu erwarten, dass man unterschiedlich lange Läufe auf einer Eingabe erhält. Wären nämlich alle Läufe ungefähr gleich lang, könnte man einfach einen genauso effizienten deterministischen Algorithmus entwerfen, indem immer ein fester Lauf des randomisierten Algorithmus simuliert wird. Da die Zufallsbits nur Einfluss auf die Vorgehensweise des Algorithmus haben, liefert der Las-Vegas-Algorithmus immer ein korrektes Ergebnis, wenn er terminiert. Die Zeitkomplexität ist in diesem Fall eine Zufallsvariable. Ein bekanntes Beispiel ist der Random-Quicksort-Algorithmus, der sein Pivotelement zufällig wählt, dessen Ausgabe aber immer sortiert ist. Dadurch lassen sich keine Best-Case und Worst-Case-Beispiele mehr konstruieren. Aber der Worst-Case kann natürlich auch dann noch eintreten, wenn zufällig das schlechteste Pivot-Element gewählt wird.


Die zweite Möglichkeit der Spezifikation von Las-Vegas-Algorithmen sagt aus, dass der Algorithmus A ein Las-Vegas-Algorithmus für eine Funktion F ist, wenn für jede Eingabe x gilt:

  • und

Wie zu erkennen ist, schließt die zweite Bedingung eine falsche Antwort aus, d. h. es wird entweder die richtige Antwort ausgegeben, oder die Antwort "?". Die erste Bedingung legt fest, dass ein richtiges Resultat von mindestens eine Wahrscheinlichkeit von größer oder gleich haben muss. Die Konstante ist dabei recht willkürlich gewählt und kann mit jedem beliebigen Wert zwischen 0 und 1 ersetzt werden, da sich die Wahrscheinlichkeit, das richtige Ergebnis berechnet zu haben, durch die Anzahl der unabhängigen Läufe von beliebig erhöhen lässt.

Um aus dem Modell, bei dem die Antwort "?" erlaubt ist, ein Modell zu erhalten, bei dem immer alle Aussagen korrekt sind, kann man wie folgt vorgehen: Wenn A ein Las-Vegas-Algorithmus ist, der mit beschränkter Wahrscheinlichkeit ein "?" ausgeben darf, dann wird A modifiziert, in dem immer, anstatt "?" auszugeben, der Algorithmus auf die selbe Eingabe neu gestartet. Das führt zu einem neuen Algorithmus A'. Wenn man annimmt, dass der Algorithmus dabei in einem Durchlauf immer mit der Wahrscheinlichkeit das richtige Ergebnis liefert, hat man schnell eine hohe Wahrscheinlichkeit, nach wenigen Durchläufen ein richtiges Ergebnis zu erhalten.


  • Soll die Zeitkomplexität des Algorithmus beschränkt werden, liegt die Wahrscheinlichkeit, dass der Algorithmus ein korrektes Ergebnis liefert, niedriger. Es gibt also Fälle, in denen der Algorithmus kein Ergebnis ausgibt.


Ein Beispiel für Las-Vegas-Algorithmen ist das n-Damen-Problem. Gegeben ist ein n x n Felder großes Spielbrett auf dem n Damen positioniert werden sollen, dabei soll jedoch gegeben sein, das sich die Damen gegenseitig nicht bedrohen. Dabei ist zu beachten das für n < 4 keine Lösung gibt. Bekannte deterministische Verfahren haben hierfür ein exponentiellen Aufwand. Eine Las-Vegas-Algorithmus für das Problem könnte wie folgt arbeiten. Es wird zufällig eine Dame in der ersten Reihe positioniert, im nächsten Schritt wird die Dame in Zeile 2 zufällig positioniert, wobei die bedrohten Felder ausgeschlossen werden. Dieser Vorgang wird wiederholt. Wenn der Algorithmus bis zur Zeile n kommt und seine Dame positionieren kann ist eine Lösung gefunden worden. Unter http://www.inf.hs-zigr.de/AuK-Buch/Seminare/damen.html wird diese Problemlösung gut veranschaulicht.


Die Wahrscheinlichkeit, dass ein Las-Vegas-Algorithmus terminiert, lässt sich durch eine Erhöhung der Rechenzeit erkaufen. Es kann jedoch auch sinnvoll sein, eine größere Wahrscheinlichkeit für das Scheitern in Kauf zu nehmen, wenn dadurch die Zeit abnimmt, einen Misserfolg zu erkennen.

Monte-Carlo-Algorithmus Gruppe 2

Ein Monte-Carlo-Algorithmus ist ein Algorithmus welcher immer ein Ergebnis liefert, allerdings mit einer festlegbaren Wahrscheinlichkeit ein fehlerhaftes Resultat zurückliefert. Er liefert demzufolge, keine Näherungslösungen sondern ebend entweder ein richtiges oder falsches Ergebnis - was sich jedoch nicht direkt feststellen lässt. Das gelieferte Ergebnis wird als "wahr" befunden.

Mithilfe von Monte-Carlo-Algorithmen lassen sich Probleme lösen die sonst nur schwer bis unlösbar sind.


Fehlerwarscheinlichkeit

Durch häufiges Wiederholen lässt sich die Warscheinlichkeit, dass der Algorithmus ein falsches Ergebnis liefert soweit eindämmen, dass ein Hardwareversagen um ein vielfaches wahrscheinlicher sein kann.

Multimengenvergleiche

Zum Anfang, was sind überhaupt Multimengen. Multimengen unterscheiden sich von normalen Mengen nur insoweit das jeder Wert bis mal vorkommen kann. Viel mehr gibt es dazu auch nicht zu sagen. Nun kommt man zu dem Problem der Äquivalenzprüfung.

Würde man zum Beispiel die Multimengen und auf Äquivalenz überprüfen wollen, müsste man die beiden Multimengen ordnen und dann auf Äquivalenz prüfen. Dies kostet im Mittel , besser wäre allerdings, dies vermag ein propabilistischer Algorithmus zu erreichen. Es wird verabredet das jeder Multimenge ein Polynom zugeordnet wird. Dieses Polynom wird nach folgendem Muster gebildet. Nun werden folgende Regeln verabredet: 

1. , wenn  für alle ganzen Zahlen  zutrifft. 

2. , wenn in 1. beschriebenes Verfahren für mindestens ein  fehlschlägt.

Was bedeutet das für uns. Nunja, sobald wir auf ein stoßen, für welches die Funktionswerte der beiden Polynome unterschiedlich sind so ist ziemlich sicher das die Multimengen unterschiedlich sind. Um die Wahrscheinlichkeit zu erhöhen wird der Test für zufällige wiederholt. Konkret schaut das dann wie folgt aus.

Wir haben die 3 Multimengen m1 ,m2 ,m3 zur Verfügung. m2 ist identisch zu m1, m3 ist eine gänzlich andere Multimenge Die Methode poly liefert den Polynomwert der Multimengen für einen gegebenen Wert.

Bitte mehrmals ausführen und Rückgaben beobachten.


Wenn man die Prozedur über alle 3 Multimengen laufen lässt bekommt man mit hoher Wahrscheinlichkeit verschiedene Werte. Es kann aber auch vorkommen das für alle 3 Multimengen der gleiche Polynomwert herauskommt. Man kann deshalb allerdings noch nicht von einer Äquivalenz ausgehen. Dafür sind mehrere Versuch mit zufälligen Eingabewerten notwendig. Dafür verwenden wir die Methode aequivalenztest, diese testet mit einem zufälligen Wert und wiederholt den Test.

Und noch eine komplette Ausgabe von Anfang bis Ende.

Fermat

Ganz klassisch lässt sich der Primzahlcharakter einer Zahl durch durchprobieren mit Probeteilern herausfinden, aber besonders bei großen Primzahlen ist diese Methode schrecklich ineffizient.

Auf Grundlage des "Kleinen Satzes von Fermat" kann man mittels randomisieren einen Monte-Carlo Algorithmus entwickeln. Dieser Primzahltest besitzt dann einen Aufwand von .


Der "Kleine Satz von Fermat sagt folgendes aus:

Nehmen wir den "Satz von Euler" hinzu: 

Für alle natürlichen Zahlen  und  mit  und , wobei , gilt 
Da unter der Bedingung das  gilt das  für Primzahlen ist, lässt sich dies im Satz von Fermat einsetzen.

Daraus lässt sich folgende Formel ableiten:

Wobei eine beliebige Ganzzahl ist.


Hier eine Implementierung des Primzahltests nach Fermat:


Die Standardimplementierung des Fermattests liefert schon recht zuverlässig aussagen über den Primzahlcharakter vieler Zahlen, allerdings scheitert der Algorithmus an den sogenannten Pseudoprimzahlen und den Carmichael-Zahlen. Im Intervall von gibt es nur 22 solcher Pseudoprimzahlen und gerademal 7 Carmichael-Zahlen.

Pseudoprimzahlen

Zahlen die fuer einige Basen den Test bestehen aber dennoch keine Primzahlen sind.

z.B:

Carmichael-Zahlen

Zahlen die zu allen teilerfremden Basen diesen Test bestehen. Die kleinste Carmichael-Zahl ist 561 (= 3 ∗ 11 ∗ 17).



Durch Randomisieren und Wiederholen lässt sich ein Primzahltest herstellen der auch Pseudoprimzahlen und Carmichael-Zahlen bei 10 Wiederholungen meistens entdeckt. Durch häufigeres wiederholen kann die Fehlerwarscheinlichkeit weiter gesenkt werden.

Primzahltest nach Solovay und Strassen

Bei dem Primzahltest von Solovay und Strassen handelt sich ein weiteres mal um einen weiteren Monte-Carlo-Algorithmus. Dieser Primzahltest liefert mit 50%iger Warscheinlichkeit eine korrekte Aussage, wobei mann durch mehrfaches Wiederholen diese Warscheinlichkeit beliebig steigern kann. Eine genaue Beschreibung des Test findet ihr hier.

Ausblick

Genetische Programmierung

Einführung

Eine der größten Herausforderungen im Bereich der Computerwissenschaften ist es den Computer dazu zu bringen ein Problem zu lösen, ohne ihm exakte Instruktionen zu geben wie er dieses Ziel erreicht. Genetische Programmierung geht von einem hohen Abstraktionsniveau aus indem gesagt wird was getan wird und im Anschluss wird ein Computer Programm erstellt welches dieses Problem löst. Das Modell der Genetischen Programmeriung orientiert sich bei der Programmerstellung an natürlichen Vorgängen wie Selektion, Kreuzung, Mutation und Genmanipulation.

Geschichtliche Entwicklung

Der bedeutenste Vertreter und Begründer der Genetischen Programmierung ist John Koza. Er hatte im Jahr 1987 mit seiner Forschung begonnen und von 1987 bis heute sind daraus 36 Lösungen entstanden. Das heißt pro Jahr 1,6 Lösungen. Wobei nur 2 dieser Erfindungen komplett neu sind.

System Zeitraum Petacycles Speedup Konkurrenzfähige Lösungen
Serielle Texas Instruments LISP Maschine 1987 - 1994 0,00216 1 0
64 nodes Transtech Parallel Computer 1994 - 1997 0,02 9 2
64 nodes Parsytec parallel Computer 1995 - 2000 0,44 204 12
70 node Alpha parallel Computer 1999-2001 3,2 1481 2
1000 nodes Pentium II Cluster 2000 - 2002 30 13900 12

Unter Petacycles sind Programmdurchläufe pro Tag zu verstehen

Klassifikation

Einsatzgebiete

  1. Lineare Regression und Function Synthesis
  2. Data Mining und Datenanalyse
  3. ELT, Entwurf von Schaltkreisen
  4. Maschinelles Lernen
  5. Geometrie/Physik

Initialisierung

Obwohl GP zum Erstellen von Programmen verwendet wird, sind die benutzten Sprachen in der Regel keine Turing-vollständigen Sprachen. Es sind eher direkt auf die Problemgröße zugeschnittene Sprachen.

Terminale

Die Menge der Terminale kann bestehen aus:

  1. Eingabevariablen
  2. Funktionen ohne Argumente
  3. Konstanten
Funktionen

Die Funktionsmenge kann unterschiedlich aussehen in Abhängigkeit des Anwendungsgebiets. Folgende Tabelle kann dies veranschaulichen:

Art Beispiel
Arithmetisch +,-,*,/
Mathematisch sin, cos, exp
Logisch AND, OR, NOT
Bedingungen IF, THEN, ELSE
Looping FOR, REPEAT


In GP werden die Programme für gewöhnlich als Syntaxbaum repräsentiert. Variablen und Konstanten werden Terminale genannt und Operationen werden als Funktionen bezeichnet. Des weiteren ist es verbreitet Ausdrücke in Prefixnotation zur repräsentieren. Aus wird dadurch dadurch fällt es leichter die Beziehungen zwischen den einzelnen Ausdrücken zu erkennen.

Die Bäume werden nach zwei verschiedenen Bildungsvorschriften aufgebaut. Diese sind einen "full" und "grow". Das heisst man legt fest das der Baum eine Tiefe von 2 besitzt und nur die Blätter Terminale sein dürfen, der Rest muss mit Funktionen belegt sein. Dieser Baum ist dann nach der "full" Methode initialisiert.

Full.gif

Bei der "grow" Methode gibt es diese Reglementierung nicht. Also kann ein Zweig schon bei Tiefe 1 durch ein Terminal abgeschlossen sein wie in unter stehender Grafik zu sehen. Allerdings muss wie gehabt der Baum die vorher festgelegt Tiefe haben.

Grow.gif

Wie man leicht erkennt können durch beide Methoden viele verschiedene Bäume entstehen, um die maximale Vielfalt an Individuen zu erreichen nutzt man eine Kombination aus beidem. Das so genannte "ramped half-and-half", dahinter verbirgt sich im Prinzip nur das die Hälfte der Population nach der "full" Methode und die andre hälfte nach der "grow" Methode konstruiert wird.

Selektion

Wie bei den meisten Evolutionären Algorithmen werden Individuen anhand ihrer Fitness bewertet. Das heißt das Programme mit guter Fitness eine hohe Chance haben mehr Kindprogramme zu erzeugen. Am weitesten verbreitet ist die sogenannte "tournament selection" gefolgt von "fitness-proportionate selection", allerdings kann man jeden Standard Selektionsalgorithmus benutzen.

Tournament Selection

Vorgehensweise Wähle eine gewisse Menge von Individuen aus der Population zufällig aus. Deren Eigenschaften werden verglichen und der beste Algorithmus wird als Vateralgorithmus ausgewählt. Das zwei Eltern nötig sind , werden pro Kind 2 Selektionvorgänge vollführt.

Kreuzungsverfahren

Zweig Austausch

Es wird je Elternteil ein zufälliger Kreuzungspunkt gewählt. An den korrespondierenden Punkten wird im resultierendem Kind-Algorithmus der Zweig des jeweiligen Elternteils eingefügt. Dabei wird darauf wert gelegt das die Auszutauschenden Zweige möglichst gering gehalten werden. In vielen fällen ist es sogar so das nur 2 Blätter getauscht werden. Um dem entgegen zu wirken kann man verabreden das in 90% der Fälle Funktionen ausgewählt werden und nur in 10% der Fälle die Blätter, also Terminale.

Mutation

Analog der Kreuzung wird ein zufälliger Startpunkt im Programm ausgewählt, nun wird ab diesem Punkt ein gesammter Zweig durch einen zufällig neu erstellten Zweig ersetzt. Alternativ gibt es noch die so genannte „Punkt Mutation“ welche das Äquivalent zur Bit-Flip-Operation in Genetischen Algorithmen ist. Es wird also nur ein Knoten/Blatt gegen ein anderes mit gleicher Stelligkeit ausgetauscht. Welche der Operationen ausgewählt wird, wird propablistisch bestimmt. Dabei hat der Kreuzungsvorgang in der Regel eine Wahrscheinlichkeits von 90% oder höher, die Wahrscheinlichkeit auf eine Mutation beträgt im Gegensatz dazu ca. 1%. Wenn die Wahrscheinlichkeiten addiert nicht 100% ergeben wird mit einer Wahrscheinlichkeit ein Individuum aus der Restpopulation reproduziert.

Beispiel

Folgendes Beispiel zeigt einen Programmdurchlauf in dessem Verlauf die Funktion im Interval approximiert wird.

  • Initialisierung

Zum Anfang werden 4 zufällige Programme erzeugt. Als erstes ein Programm welches entspricht. Das zweite Programm addiert das Terminal zum Produkt von , entspricht also . Das dritte entspricht . Zu guter letzt das vierte Programm entspricht . Unten stehende Grafik visualisiert das nochmal.

Generation0.png

  • Fitness Bewertung

Natürlicher Weise sind zufällig generierte Programme der optimal Lösung sehr fern. Allerdings gibt es auch in Generation 0 schon Lösungen die besser sind als andere. Unten stehende Grafik stellt die Parabel den jeweils gestrichelt dargestellten Funktionen der Programme gegenüber. Wie man sieht weichen die verschieden Funktionen unterschiedlich stark von der Musterlösung ab. Somit kann man Programm 1 eine Fitness von 7,7 vergeben, Programm 2 11,0, Programm 3 17,98 sowie Programm 4 hat einen Fitnesswert von 28,7. Fitnessevaluation.png

  • Selektion, Mutation, Kreuzung

Nun werden die Programme anhand ihrer Fitness als Elternkandidaten ausgewählt. Wichtig dabei ist das die Selektion nicht "greedy" erfolgt, somit haben auch Lösungen eine Chance die nicht ganz so optimal sind.

Starten wir also mit der Reproduktionsoperation, also dem simplen Übernehmen das Programms in die nächste Generation, in unserem Fall wird Programm auf Grund seiner Fitness dafür ausgewählt. Gehen wir nun davon aus das zufällig Programm 3 für den Mutationsprozess ausgewählt wird. Als nächstet wird propabilistisch ein Mutationsknoten gewählt. Hier wird das der linke Knoten der bisher entspricht. Nun wird der gesamte Ast(hier nur die 2) gelöscht. Nun wird ein zufälliger Ast neu erzeugt und angefügt. Hier .

Zum schluss die Kreuzung. Wir kreuzen dazu Programm 1 und Programm 4. In Programm 1 wird der Knoten als Kreuzungsknoten gewählt. In Programm wird dazu der Knoten genommen. Nun werden die beiden Äste getauscht. Das Resultat entspricht x.

Für den zweiten Kreuzungsvorgang werden die Programme 2 und 1 genutzt. Nun wählt der Kreuzungsalgorithmus in Programm 2 das als Kreuzungsknoten aus und in Programm 1 das . Daraus resultiert , dieses Programm hat dann einen Fitnesswert von 0. Generation1.png

  • Terminierung

Da die Fitness des letzten Programms unter 0,1 liegt ist das Abbruch-Kriterium erfüllt und dieses Programm wird als bisher Bestes ausgegeben.

Schwarmalgorithmen

Die Schwarmintelligenz ist ein Forschungsfeld der künstlichen Intelligent und hat nahe Bindungen an die Agententechnologie. Als Agent meinen wir hier ein Computerprogramm, welches zu einem gewissen eigenständigem Verhalten fähig ist. Auch die Begriffe verteilte künstliche Intelligenz sowie kollektive Intelligenz im Allgemeinen sind für Schwarmintelligent i.w.S. gebräuchlich. Dabei wird versucht, in einem Computerprogramm das Verhalten von intelligenten Schwärmen zu simulieren. Besonders geeignet sind Schwarmalgorithmen, um für sehr komplexe Probleme schnell gute (keine optimalen) Lösungen zu finden.

Schwärme in der Natur

Die Schwarmalgorithmen sind, wie neuronale Netze, genetische Algorithmen und vieles andere auch, aus der Natur abgeguckt. Etwa bei Ameisen, Termiten, Vögeln, Fischen, Bienen und anderen Tieren kann man beobachten, dass sie in einem Schwarm Aufgaben lösen, zu denen ein Individuum allein nicht fähig wäre.

Im Videobeispiel sehen wir etwa einen Fischschwarm, bei dem sich jeder Fisch einfach nur an der Entfernung zum jeweils nächsten Fisch und der Entfernung zu den Raufbischen orientiert. Es gibt also keinen Supervisor für alle Fische, der sagt, wer wo lang zu schwimmen hat.

Durch Schwarmverhalten schaffen es Termiten z. B. auch extrem komplexe Bauten zu errichten, obwohl keine Termite weiß, wie der gesamte Bau aussehen und es keine "Super-Termite" gibt, welche den anderen Anweisungen gibt.

Termit6.jpg.jpeg

Wenn wir uns überlegen, was passieren würde, wenn man ein paar Hundert Menschen hinsetzt, und sie unkoordiniert versuchen lässt, ein Haus zu bauen, erkennt man schnell, dass bei einem Schwarm diesen Tieren eine Art Intelligenz vorliegt.

Futtersuche von Ameisen

Die Suche nach Futter gehört für jedes Lebewesen zu einer existentiellen Aufgabe. Ameisen sind dabei bei der Bewältigung dieser Aufgabe besonders effizient. Dabei markieren die Ameisen beim Ausschwärmen aus dem Nest ihren Weg mit Pheromonen, die ihre Artgenossen als Wegweiser wahrnehmen. Sobald eine Ameise Futter gefunden hat, kehrt sie damit zum Nest zurück. Der Rückweg ist dabei der Weg, mit der größten Intensität an Pheromonen. Wenn die Ameise als Erste an ihrem Futter war, kehrt sie auf ihrem eigenen Weg wieder zurück, und hinterlässt auf dem Weg wieder Pheromone. Da alle Ameisen etwa die gleiche Geschwindigkeit haben, wird automatisch der kürzeste Weg zum Futter der mit der höchsten Intensität an Pheromonen, da die anderen Ameisen noch nicht wieder am Nest angekommen sind. Dabei ist aber zu beachten, dass jede Ameise nur mit einer bestimmten Wahrscheinlichkeit dem Weg mit der stärksten Ausprägung an Pheromonen folgt, so können Abkürzungen gefunden werden und neue Wege zu neuen Futterquellen erschlossen werden. Außerdem verliert das Pheromon mit der Zeit an Intensität, was wichtig ist, falls die Futterquelle aufgebraucht ist.

In diesen Videos ist nochmal die Futtersuche der Ameise veranschaulicht. Die Kleeblätter stellen dabei das Futter dar. Das schöne, an einer, im Computer erzeugten Simulation ist, dass man die Futtersuche der Ameise hier in einer Weise optimieren kann, die in der Realität nicht möglich ist. So wird zum Beispiel nur Pheromon auf die, von der Ameise begangene Strecke gelegt, wenn dieser Weg sie auch wirklich zum Futter geführt hat. Da die Ameise aber vorher nicht weiß, ob ihr Weg sie auch wirklich zu einer Futterquelle führt, ist das im echten Leben kaum umsetzbar.

Schön zu sehen sind auch die Ameisenstraßen, welche sich nach einer Zeit herausbilden und den kürzesten Weg vom Ameistennest zum Futter darstellen.

Die Ameise schafft es also automatisch, den kürzesten Weg zu ihrem Ziel zu finden. Dieses Problem erinnert uns, leicht abgewandelt, an das altbekannte Problem des Travelling Salesman. Mit Hilfe von sogenannten Ameisenalgorithmus kann man hierfür in wenigen Iterationen eine gute Lösung bekommen.

Ein Java-Applet, bei dem Ameisen sich des Traveling Salesman Problems annehmen, findet sich hier.

http://www.ameisenalgorithmus.de/appletantstour.htm

Eine manuelle Version des Problems ohne Ameisen gibt es hier.

http://www.ameisenalgorithmus.de/appletmanuelletour.htm

Die Ameisen laufen dabei erst einmal willkürlich einen bestimmten Kurs, wenn sie wieder am Zielpunkt sind, wird, abhängig von der benötigten Entfernung, die Stärke der Pheromone für die Strecke bestimmt, auf der die Ameise unterwegs war. Desto kürzer die Rundreise, desto mehr Pheromone. Die darauffolgende Ameise orientiert sich an der Gesamtheit der Pheromone auf dem Weg, und es ist Wahrscheinlicher, dass sie einen Weg benutzt, welcher schon viele Pheromone besitzt. So bekommt man schnell eine gute Näherungslösung mit einem relaitiv einfach zu implementierenden Algorithmus für das Problem.

Eine exakte Umsetzung dieses Problems, inc Code, findet sich hier: http://www.m-boehmer.de/pdf/Schwarmintelligenz_Artikel.pdf

Robotik

Eine andere Möglichkeit der Anwendung bei Schwarmalgorithmen ist die Robotik. Hier steht nicht die Optimierung im Vordergrund, sondern die Fähigkeit, dass sich mehrere Individuen zusammen schließen, um Probleme zu lösen, die sie allein nicht bewältigen können. So z.B. das Überqueren von Hindernissen, die größer sind als sie selbst, oder Schluchten, die breiter sind, als sie selbst.

Roboter.PNG

Diese Roboterschwärme arbeiten zusammen, ohne dass es eine zentrale Steuerung gibt. So wie Ameisen sich verständigen, in dem sie Pheromone hinterlassen, könnten Roboter etwa Lichtsignale aussenden, welche dann über Sensoren aufgenommen werden.

Darüber hinaus gibt es noch zahlreiche andere Anwendungsmöglichkeiten für Schwarmalgorithmen, wie etwa alle möglichen Optimierungsprobleme, geschickte Sortiervorgänge (manche Ameisen sortieren ihre Larven nach Größe) und vieles mehr.

Aufgaben

1

Produktive Diskussionsrunde

2

Implementieren Sie einen Generator für Pseudozufallszahlen nach der Kongruenzmethode. (Buch S. 124)

zum Beispiel mit


3

Implementiern sie einen Primzahlentest nach Fermat.

4

Setzen Sie sich an einem schönen Tag ins Freie, und beobachten Sie Ameisen bei der Futtersuche. Welche Beziehungen zu dem Ameisenalgorithmus können Sie erkennen? Welche Beispiele aus der Natur können noch einen Anreiz darstellen, sie als Vorbild für einen Algorithmus zu nutzen?

5

Entwerfen sie einen Quicksort-Algorithmus, welcher sein Pivot-Element zufällig wählt. Vergleichen sie die Effizienz mit der Quicksort-Variante, welche immer das erste Element als Pivot-Element nutzt.








Aufgabenverteilung

Folien

PA-Gruppe1.pdf (0.1 MB)
PA-Gruppe2.pdf (0.4 MB)

Quellen

http://www.riskglossary.com/link/monte_carlo_method.htm

Oliver Lau "Faites vos jeux! - Zufallszahlen erzeugen, erkennen und anwenden" (c't 2009, Heft 2)

http://www.addison-wesley.de/Service/Krueger/kap12006.htm

Schickinger, Steger - Diskrete Strunkturen - Band 2 - Wahrscheinlichkeitstheorie und Statistik

Juraj Hromkovič - Algorithmics for Hard Problems

Juraj Hromkovič - Randomisierte Algorithmen

http://www.m-boehmer.de/pdf/Schwarmintelligenz_Artikel.pdf

Jörg Rothe - Komplexitätstheorie und Kryptologie

http://www.lulu.com/items/volume_63/2167000/2167025/2/print/book.pdf

http://www.genetic-programming.com/

http://www.it-weise.de/projects/book.pdf

Von „https://programmingwiki.de/AuK/Probabilistische_Algorithmen_SS09“
Persönliche Werkzeuge