Von Christoph Drösser

Wie aus den ersten Einzellern die komplexe Welt der heutigen Lebewesen entstanden ist, bleibt weiterhin eine der großen naturwissenschaftlichen Fragen. Zwar ist Darwins Evolutionstheorie inzwischen allgemein akzeptiert (von einigen US-Bundesstaaten abgesehen), jedoch bleiben noch viele Fragen offen. Wie haben Mutation, Selektion und Rekombination von Erbmaterial zusammengewirkt, um Strukturen wie Sinnesorgane und Nervensystem hervorzubringen? Ein Hauptproblem der Evolutionsforscher: Sie haben kein "Labor", können nur der realen Evolution zuschauen – und die geht nervtötend langsam vonstatten.

Schützenhilfe könnten die Biologen jetzt von einer Disziplin bekommen, von der man sie nicht unbedingt erwartet hätte: von der Informatik. "Genetische Algorithmen" nennen sich Programme, die ein Problem (meist eine Optimierungsaufgabe) lösen, indem sie die Darwinschen Mechanismen imitieren. In den sechziger Jahren von dem Amerikaner John Holland entwickelt, werden die Genetischen Algorithmen im Zeitalter der Supercomputer und Parallelrechner immer besser. Und sie könnten auch den Biologen zu neuen Erkenntissen über die Evolution verhelfen.

Bei Optimierungsproblemen geht es zum Beispiel darum, den höchsten Punkt einer (mathematischen) Gebirgslandschaft, den kürzesten Weg zwischen zwei Punkten, die windschlüpfrigste Karosserieform zu erfinden. Natürlich bietet die Mathematik dafür konventionelle Lösungen an: etwa die Differentialrechnung, mit der Oberstufenschüler Extremwertaufgaben lösen. Dazu muß man nur sehr viel über das zu lösende Problem wissen, und die Methode läßt sich nur auf bestimmte Funktionen anwenden. Genetische Algorithmen dagegen sind vollkommen "dumm": Sie wissen gar nichts über das Problem – und finden trotzdem mit einer Mischung aus Zielstrebigkeit und Zufall meist ein passable Lösung. Sie lassen sich daher auf eine Vielzahl von Problemen anwenden, deren mathematische Lösung unbekannt oder zu aufwendig ist.

Ein Standardbeispiel für eine schwierige Optimierung ist das "Problem des Handlungsreisenden": Ein Vertreter will auf einem Rundkurs eine bestimmte Anzahl von Städten besuchen und dabei eine möglichst kurze Strecke zurücklegen. Während man bei vier Städten nur drei mögliche Routen durchprobieren muß, wächst der Rechenaufwand mit steigender Städtezahl ins Unermeßliche (Mathematiker sagen "exponentiell"): Bei 15 Städten gibt es schon 653 837 184 000 theoretische Rundwege. Für Probleme mit über 100 Städten sind die exakten Minimalwege meist unbekannt, und eine USA-Karte mit 532 Städten ist eine beliebte Standardaufgabe, an der sich neue Lösungsansätze beweisen müssen.

Und so geht ein Genetischer Algorithmus das Problem an: Am Anfang steht eine "Population" von zufällig erzeugten Wegen – ein Weg ist dabei eine Folge, in der jede der Zahlen 1 bis n genau einmal vorkommt. Diese Wege sind die "Lebewesen", von den Informatikern "Strings" genannt – in diesem Beispiel vielleicht 64 an der Zahl. Jeder der Wege hat eine Gesamtlänge, die natürlich viel zu groß ist. Trotzdem sind einige der Strings etwas besser als die anderen, und die erhalten eine etwas größere Chance, in der nächsten Generation vertreten zu sein: Das ist Darwins Selektion. Wohlgemerkt geht es nicht darum, daß der Stärkste alle anderen aus dem Feld schlägt – diese "brutale" Version der Evolution würde die Verschiedenheit des "Erbguts" beseitigen und zu schnell zu einer schlechten Lösung führen.

Als nächstes geht’s ans "Paaren": Zwei "Eltern" finden sich per Zufall und werden "gekreuzt", indem ein Abschnitt aus dem einen in den anderen eingesetzt und dieser dann so repariert wird, daß er jede Stadt nur einmal enthält. So setzen wir etwa aus dem Weg 18473652 das fettgedruckte Mittelstück in den Weg 17382456 ein: Es entsteht 173657382456 und nach Streichen der "doppelten" Städte der gültige Weg 17365824. Ahnlich kriegt der erste Weg ein Stück vom zweiten eingepflanzt – und so haben die zwei "Eltern" zwei "Kinder" gezeugt, der Algorithmus beginnt mit der nächsten Generation von vorne und bricht erst dann ab, wenn keine kürzeren Wege mehr erzeugt werden. Wer ein bißchen über die Evolution. weiß, der vermißt vielleicht die Mutation, die zufällige Änderung von Genen. Auch die wird in den Genetischen Algorithmen verwandt, indem man ab und zu in einem der Strings eine Ziffer zufällig verändert. Allerdings haben die Informatiker herausgefunden, daß Mutationsraten über einem Promille nicht sehr sinnvoll sind – sie zerstören oft wichtige Gene und führen zuviel "Rauschen" in die Entwicklung ein.