fachpublikation.de

Hauptseite fachpublikation.de

Verzeichnis aller Publikationen

Verzeichnis aller Autoren

Schlagwortverzeichnis

Dokumente kostenlos publizieren
 

Impressum fachpublikation.de

 

 

Dipl. biol. Semjon Krolzik: Genetische Algorithmen


1.3 Wie ist der Genetische Algorithmus definiert?

Schritt 1: Generierung einer zufälligen Ausgangspopulation

Schritt 2: Die Fitness (Nähe zur Lösung) jedes Individuums und der Population wird ermittelt

Schritt 3: In Abhängigkeit der Fitness wird eine genetische Operation durchgeführt.

Schritt 4: Es wird mit Schritt 2 fortgefahren bis ein Individuum eine optimale Fitness besitzt, oder eine maximale Generationenzahl erreicht ist

Genetische Operationen:

  • Mutation
  • pfeil.gif (111 Byte) Rekombination: Cross-Over (einfaches, doppeltes oder mehrfach)
  • Reproduktion (Übertragung in die nächste Generation)

Eine Mutation ist eine zufällige Veränderung an einer bestimmten Stelle der Informationsrepräsentation (z.B. die Umwandlung einer 0 in eine 1 an einer vorher festgelegten Stelle). Mutationen sollten im Genetischen Algorithmus signifikant seltner auftreten als Rekombinationen.

1.4 Wie funktionieren die Genetischen Algorithmen

Die biologische Evolution (als Modell von Charles Darwin eingeführt) arbeit nach dem Prinzip "Survival of the fittest". Nach diesem Prinzip müssen auch Genetische Algorithmen arbeiten, wenn sie in einer Optimierung eine einfache Lösung in eine bessere überführen sollen. Die Frage ist aber, wer oder was ist "the fittest". Der Kernpunkt des Genetischen Algorithmus ist deshalb die Beschreibung einer Fitnessfunktion, die zuverlässig für eine mögliche Lösung deren Nähe (Fitness) zur optimalen Lösung beschreibt oder zumindest eine bessere Lösung höher bewerten kann als eine schlechtere.
Ein interessantes (wenn auch einfaches Beispiel) ist die pfeil.gif (111 Byte) BlackBox von Scott R. Ladd. Sie errät eine zufällige 64bit Zahl. Da bei einer 64bit Zahl etwa 1019 mögliche Lösungen existieren ist das nicht ganz trivial, da der Algorithmus nicht einfach alle Zahlen durchraten kann.
Die Ausgangspopulation für diesen Algorithmus sind beispielsweise 100 zufällig ausgewählt 64bit Zahlen.
Der Algorithmus übergibt der Black Box jede mögliche Lösung, diese vergleicht sie mit der richtigen Lösung und gibt eine Bewertung zurück. Die Fitness der eingereichten möglichen Lösung ist also die Bewertung: Je besser die Bewertung, desto höher die Fitness.
Im Genetischen Algorithmus werden die Individuen der Population proportional zu ihrer Fitness reproduziert, d.h. in die nächste Generation übernommen (Analog zur biologischen Evolution "Survival of the fittest"). Allerdings werden auch Individuen geringerer Fitness übernommen. Dadurch wird die Varianz in der Information gewahrt. Ansonsten würde möglicherweise irgendwann nur noch die bis dahin beste Lösung die Population bevölkern und ohne Varianz könnte keine Weiterentwicklung zur wirklich besten Lösung stattfinden (Eine Rekombination zweier gleicher Individuen erzeugt auch wieder zwei gleiche Individuen).
Vor der Reproduktion können die Individuen noch durch Mutation und/oder Rekombination verändert werden.
Da sich die Information in der Population durch Mutation und vor allem Rekombination ständig ändert, ist es möglich irgendwann die optimale Lösung zu erreichen. Wichtig ist dabei, daß es sich um eine gerichtete Änderung handelt. Das heißt die Veränderungen finden in Richtung auf die optimale Lösung statt: Wird die Fitness eines Individuums durch eine Mutation herabgesetzt, kommt es höchstwahrscheinlich nicht zur Reproduktion. Ungünstige Entwicklungen werden also aussortiert. Entwicklungen in Richtung auf die optimale Lösung dagegen gefördert. Zur Rekombination kommen überwiegend Individuen mit hoher Fitness, so daß die Fitness nach der Rekombination im Schnitt zunimmt.

Der Algorithmus endet wenn die optimale Lösung oder eine vorher festgelegte Generationenzahl erreicht wurde.

Der Ablauf des Genetischen Algorithmus läßt sich am besten anhand eines Flussdiagramms veranschaulichen.

Ein weiteres anschauliches Programm das Genetische Algorithmen zur Lösung eines Problems nutzt ist der pfeil.gif (111 Byte) "Maze Solver" (Labyrinth Löser) von Paul Falstad.

 

Seite zurück  Eingangsseite  Seite vor


Home | WorldWideBooks | imMEDIAtely


Stand der letzten Aktualisierung: 8. Januar 2000
Bei Fragen und Anregungen zu dieser Website wenden Sie sich bitte an: webmaster@fachpublikation.de