Simulierte Evolution: Biologie und Informatik

Eine der modernsten Methoden der Informatik zur automatischen Adaption der “Verhaltensweise” von Algorithmen an veränderliche oder nicht systematisch erfaßbare Bedingungen ist die Simulation natürlicher Abläufe im Sinne der Vererbungslehre.

Martin Schönhacker

Man züchtet sozusagen Algorithmen, die sich durch einen Zyklus von Vererbung, Veränderung und Selektion den jeweiligen Anforderungen anpassen:

Die Menschen nutzen seit Jahrtausenden eine Kombination von Züchtung und Auslese, um ertragreicheres Getreide, schnellere Rennpferde oder schönere Rosen zu züchten. Es ist allerdings nicht so einfach, diese Verfahren auf Computerprogramme zu übertragen. Das Hauptproblem ist, das Analogon eines genetischen Codes zu finden: eine abstrakte Darstellung, welche die Struktur eines Programms beschreiben kann wie die DNA den Aufbau einer Maus.

Man nennt diese Programme “Evolutionäre Algorithmen” (EAs) bzw. “Genetische Algorithmen” (GAs). Ein einfacher Algorithmus zur Mutation und Selektion kann zum Beispiel so aussehen:

1. Erzeuge eine initiale Menge von Individuen.

2. Bewerte alle Individuen hinsichtlich ihrer Tauglichkeit.

3. Selektion: Wähle das beste Individuum aus.

4. Mutation: Erzeuge aus dem besten Individuum eine Menge von n-1 Mutanten.

5. Bewerte alle Mutanten hinsichtlich ihrer Tauglichkeit.

6. Falls noch kein Individuum mit der vorgegebenen maximalen Tauglichkeit dabei ist, bilde eine neue Selektionsmenge. [Anmerkung: das ist eine Teilmenge, deren Individuen wie in Punkt 2 auf ihre Tauglichkeit untersucht werden müssen.]

7. Fahre fort bei Punkt 3.

Nun ist noch die Frage, wie die Eigenschaften der Individuen im Programm codiert werden können, und wie man sich den Prozeß der Mutation vorstellen darf. Oft handelt es sich um Bit-Ketten (sozusagen binär codierte “Genome”), und die Mutation kann dann etwa bedeuten, einige Bits zufällig auszuwählen und ihren Zustand zu ändern.

Allerdings gibt es auch systematischere Verfahren, die dann zum Beispiel kompliziertere Datenstrukturen für die Genome sowie der biologischen Realität nachgebildete Operationen verwenden. Man kann etwa eine Datenstruktur aus zwei “Chromosomenfäden” verwenden, wie sie bei der Erbinformation des Menschen existiert, und in der Mutation die Erbinformation jeweils zweier Individuen verknüpfen, indem ein neues Genom jeweils aus von zwei Individuen (gewissermaßen den “Eltern”) stammenden Teilinformationen zusammengesetzt wird.

Weil die Entwicklung bei der simulierten Evolution noch mitten im Laufen ist, gibt es relativ wenig Information darüber in den gängigen Lehrbüchern über Algorithmen. Ergiebiger ist wieder einmal das Internet:

Die beste Einstiegsseite für genetische Algorithmen ist sicherlich das Illinois Genetic Algorithms Laboratory (IlliGAL) unter der Leitung von David E. Goldberg: http://gal4.ge.uiuc.edu/illigal.home.html. Von dort findet man auch leichten Zugang zu weiteren GA- oder EA-Seiten.

Wem das Suchen von Informationen im Internet dann doch zu mühselig ist, dem sei das Buch “Prinzipia Evolvica” empfohlen, aus dem die zitierten Textausschnitte stammen. Es bietet keine großen wissenschaftlichen “Neuigkeiten”, sondern eine sehr gründlich zusammengestellte und ausführlich durch Referenzen dokumentierte Darstellung des momentanen Standes der Entwicklung in Sachen simulierte Evolution. Die beiliegende CD-ROM enthält eine Unmenge (373 MB!) mehr oder weniger brauchbarer Beispiele zu fast allen behandelten Themen in Form von Mathematica-Notebooks, die mit dem ebenfalls enthaltenen kostenlosen Programm MathReader angezeigt werden können.