|
Diese
Seite gibt eine kleine Einführung in das Thema evolutionäre
Programmierung.
Es werden zwei Programme vorgestellt, die diese Klasse von Optimierungs-Verfahren
nutzen:
Von
Mäusen und Füchsen
Eine Räuber-Beute-Simulation:
Achtung, Hypnose-Gefahr!
Stundenplan-Erstellung
mit evolutionären Algorithmen
Eine Software
zur Stundenplan-Erstellung und -Optimierung.
Die
Natur ist genial ... ? ... schwer vorzustellen.
Aber sie ist mit Sicherheit sehr fleißig, sehr ausdauernd und hat
verdammt viel Zeit. Alles in allem gute Voraussetzungen, um in absehbarer
Zeit interessante Ergebnisse zustande zu bekommen. In absehbarer
Zeit? Das Darmbakterium Escherichia coli mußte in seiner jüngeren
Geschichte eine Vielzahl an ungesunden Experimenten über sich ergehen
lassen. Aber daher weiß man, daß es ungefähr 10 hoch 2 400 000 Möglichkeiten
gibt, den genetischen Bauplan dieses bedauernswerten Geschöpfes
anzuordnen. Den aktuellen Bauplan durch "Auswürfeln" zu erhalten,
sprengt problemlos den zeitlichen Rahmen des Universums - das klassische
Argument gegen die Idee der Evolution schlechthin. Aber das der
Evolution innewohnende Zufallselement hat nicht viel mit einfachem
Würfeln zu tun. Die Mutabilität des genetischen Materials ist zwar
Grundlage des Evolutionsprozesses, führt aber erst in Verbindung
mit Selektion und anderen Mechanismen zur Rassen - und Artbildung.
Wieso
Evolutionsmechanismen überhaupt funktionieren, ist noch weitgehend
unklar. Erklärungsversuche stützen sich auf eine Charakterisierung
der Evolution als kumulativer, hochgradig paralleler Prozess. Auch
sollte man nicht vergessen, daß die Bindung an ein bestimmtes Ökosystem
stets eine bestimmte "Richtung" der Evolution erzwingt. Eine andere
Umschreibung dieses Sachverhaltes findet sich in der Bezeichnung
"ökologische Nische" wieder. Trotzdem ist der Zufall die teibende
Kraft bei der Artenbildung. Die Evolution verfolgt also gewissermaßen
ein Ziel, weiß aber andererseits nicht was sie tut - oder anders
herum.
Wenn
die Evolution das überaus komplexe Ökosystem der Erde hervorbringen
kann, liegt die Vermutung nahe, daß Evolutionsmechanismen auch auf
einfachere, vergleichsweise banale Probleme angewandt werden können.
Versuche dieser Art wurden lange Zeit belächelt. Erstens hielt man
eine Nachahmung der biologischen Evolutionsprinzipien für unpraktikabel,
da das natürliche Vorbild nur in so riesigen Zeitmaßstäben wirksam
ist. Zweitens resultierte die Ablehnung aus anfänglichen Mißerfolgen,
die ihrerseits jedoch aus Fehlinterpretationen der Evolutionsmechanismen
resultierten. Diese Fehlinterpretationen basierten genau genommen
auf einer falschen und leider noch heute präsenten Übersetzung von
Darwins "Struggle for life" durch einen eifrigen deutschen Professor.
Es bezeichnet nicht den "Kampf" ums Überleben, sondern die tägliche
Mühsal und Schinderei - also die Auseinandersetzung mit den täglichen
Unbilden der Existenz. Die Fehlübersetzung betrifft auch das damit
verbundene "survival of the fittest". Nicht das Überleben der
"Stärksten", sonder das der besser an die Umwelt angepaßten
Arten steht hier im Vordergrund. Eine bessere Angepaßtheit an die
Umwelt sichert nicht zwangläufig das Überleben, erhöht jedoch die
Überlebens-Wahrscheinlichkeit. Mit dem Einzug schnellerer Computer
wurden Ende der 60er Jahre diesseits und jenseits des Atlantiks
zeitgleich Optimierungsverfahren entwickelt, die unter dem Sammelbegriff
Evolutionäre Algorithmen zusammengefaßt werden.
Evolutionäre
Algorithmen - Wozu?
Man benutzt sie, um schlicht und ergreifend Probleme zu lösen. Die
Palette der Probleme, auf welche diese Algorithmen angewandt werden
können, ist im Vergleich zu anderen Verfahren riesig. Vor allem
aber wendet man sie auf Probleme an, die nicht mit den klassischen
Verfahren (z.B. Gradienten- oder Simplex-Verfahren) gelöst werden
können bzw. für die überhaupt kein Lösungsverfahren bekannt ist
- und davon gibt es eine ganze Menge.
Evolutionäre
Algorithmen - die Funktionsprinzipien:
Evolution bezeichnet den kollektiven Lernprozeß einer Menge von
Individuuen - der Population. Gesteuert wird der Prozeß durch
Mechanismen des Informations-Austausches zwischen den Individuen
und durch zufällige äußere Einflüsse. Ein Individuum kann
vereinfacht als Menge von Infomationen betrachtet werden, die sich
aus festen Blöcken von Teil-Informationen zusammensetzt. Jeder Informations-Block
hat dabei eine ganz bestimmte Bedeutung - analog der Tatsache, daß
jedes Gen der DNS die Ausprägung eines bestimmten Teils unseres
Organismus definiert - etwa die Augenfarbe. Tauscht man für zwei
Individuen Blöcke gleicher Bedeutung gegeneinander aus, können
zwei neue Individuen mit veränderten Eigenschaften entstehen. Dieser
Austauschvorgang wird i. allg. als Rekombination bezeichnet.
Triebkraft der Evolution ist jedoch die zufällige Veränderung von
Informationen durch äußere Einflüsse - die Mutation.
Die durch Rekombination und Mutation neu entstandenen Individuen
konkurrieren nun mit der Eltern-Population. Dabei haben die
Individuen die größten Überlebens-Chancen, deren Eigenschaften die
beste Anpassung an die jeweilige Umwelt darstellen. Da also die
besser angepaßten Individuum die weniger gut angepaßten nicht vollständig
verdrängen, besteht die Population i.allg. aus einem Spektrum unterschiedlicher
Individuuen. Diese Vielfalt ermöglicht ein flexibleres Reagieren
auf eventuelle Veränderungen der Umwelt und hebt so die Überlebens-Wahrscheinlichkeit
für die Art als Ganzes, da sich z.B. ein scheinbar nutzloses oder
gar nachteiliges Merkmal eines Individuums bei einer Veränderung
der Umwelt als vorteilhaft erweisen kann.
|
 |