Seite 2: Tierra

Meine eigene Arbeit mit der digitalen Evolution folgt konzeptuell, wenn nicht sogar chronologisch dem Trend, dem Evolutionsprozeß eine wachsende Freiheit zu geben. Ich habe ein System selbstreplizierender Computerprogramme gebaut, bei dem das einzige klar definierte "Fitnesskriterium" dasselbe ist wie das, dem man in der organischen Evolution begegnet: die Möglichkeit, genetisches Material zu replizieren oder an künftige Generationen weiterzugeben. Mein System Tierra läßt das grundlegende darwinistische Szenario entstehen: selbstreplizierende Einheiten in einer endlichen Umwelt mit vererbbarer genetischer Variation in einem Computer.

Die Metapher

Bei Tierra sind die selbstreplizierenden Einheiten Maschinencodeprogramme, die nur Kopien von sich selbst im RAM-Speicher des Computers anlegen. So wird der Maschinencode zu einem Analogon des auf Nucleinsäuren basierenden genetischen Codes des organischen Lebens.

Die Replikation der Programme geschieht durch deren Ausführung durch die CPU (zentrale Recheneinheit) des Computers. Daher stellt die CPU-Zeit ein Analogon der Energie dar, die den Metabolismus (Stoffwechsel) des organischen Lebens abbildet.

Die Maschinencodeprogramme belegen im RAM-Speicher Platz, weswegen der Speicher ein Analogon des materiellen Raums des organischen Lebens darstellt. Jedes Programm "besitzt" den Speicherplatz, den es belegt, und hat das ausschließliche Recht, etwas in seinen Speicherplatz hineinzuschreiben. Aber jeder Prozeß kann die Maschineninstruktionen in jedem Teil des Speichers lesen oder ausführen. Folglich steht das Teilprivileg für den vom Programm belegten Raum als Analogon für eine halbdurchlässige Membran, die die organischen Zellen umgibt und zum Teil die interne chemische Struktur vor Störungen aus der Umwelt schützt.

Genetische Variation wird in die Population der replizierenden Programme durch zufällig sich verändernden Bits im Maschinencode eingeführt. Das ist ein Analogon der Mutationen, bei denen Nucleinsäuren in der DNS-Kette des organischen Lebens ersetzt werden.

Zusätzliches Rauschen kommt in Form gelegentlicher Fehler bei den Berechnungen durch die CPU in das System. Wenn die CPU beispielsweise zwei Zahlen addieren sollte, tritt manchmal ein falsches Ergebnis auf, das mit plus oder minus eins vom richtigen abweicht. Wenn die CPU alle Bits in einem Verzeichnis eine Position nach links rückt, werden die Bits manchmal zwei Positionen oder überhaupt nicht verschoben. Wenn Information zwischen zwei Orten bewegt wird, dann stammt sie manchmal fälschlicherweise von einem benachbarten Ort oder geht zu einem solchen. Diese unregelmäßig auftretenden Berechnungsfehler sind ein Analogon der chemischen Nebenprodukte des metabolischen Prozesses, der im Inneren der lebendigen organischen Zellen stattfinden. Diese Irrtümer sind keine genetischen Veränderungen, aber sie können dazu führen.

Wenn der Speicher eines Computers voll wird, beginnt das darwinistische Betriebssystem ältere oder stärker beschädigte Programme zu löschen, um Platz für die Geburt der nächsten Generation zu schaffen. Das Löschen eines Prozesses durch das Betriebssystem ist das Analogon des Todes.

Die Computerwelt wird mit einem einzigen digitalen Organismus als "Urahne" geimpft. Es ist ein Maschinencodeprogramm mit 80 Bytes, das sich zuerst selbst prüft, um seine Größe und seinen Ort im Speicher festzulegen. Es weist dann seinem Kind einen freien Speicherplatz zu, indem es das Speicherverwaltungssystem des darwinistischen Betriebssystems benutzt. Dann kopiert es Byte für Byte seinen Code von sich auf das Kind. Nach der Replikation entläßt es das Kindprogramm als einen unabhängigen Prozeß.

Die virtuelle Maschine

Der Versuch, den darwinistischen Prozeß auf einem herkömmlichen Computer zu schaffen, sollte aus einer Vielzahl von Gründen unmöglich sein. Die wichtigsten Gründe sind:

1. Bei herkömmlichen Computern ereignen sich keine Bitvertauschungen im Maschinencode und keine Berechnungsfehler.
2. Der Versuch, Maschinencodes auszuführen, die zufällig durch Bitvertauschungen verändert werden, wird schnell zu Fehlern im System führen, die den Computer zusammenbrechen lassen.
3. Die Operationssysteme von Computern mit vielen Prozessoren ermöglichen es Prozessen, Nachkommen freizusetzen, aber sie löschen alte Prozesse nicht notwendigerweise so, daß dies zu einem für das darwinistische Szenario erforderlichen Generationswechsel führt.

Wenn man diese Probleme auf einem herkömmlichen Computer lösen will, müßte das System erheblich verändert werden. Sobald man das realisiert hat und sofern man Programme auf dem System sich evolutionär entwickeln lassen kann, würde die Möglichkeit bestehen, daß sie sich wie ein Computervirus auf andere Computer derselben Art (beispielsweise von Macintosh zu Macintosh) ausbreiten, obwohl es unwahrscheinlich ist, daß sich Evolution oder selbst Reproduktion unbeabsichtigt auf infizierten Maschinen fortsetzen, wenn sie nicht auf dieselbe Weise abgeändert wurden wie die erste Maschine.

Man kann all diese Probleme durch einen neuen Computer lösen, der speziell für den Zweck evolvierender Programme gebaut wurde. Dieser neue Computer besitzt eine Architektur und ein Betriebssystem, die den darwinistischen Prozeß unterstützen. Das Design eines jeden neuen Computers (oder jedes komplexen Produkts) beginnt heute mit dessen Simulation durch Computersoftware. Man kann Software herstellen, die dasselbe Verhalten wie der Computer ausführt, den man zu bauen beabsichtigt. Das ist die Grundlage des "soft PC", mit dem man IBM kompatible Software auf einem Macintosh oder einer Sun laufen lassen kann.

Die Computersimulation eines Computers nennt man einen "virtuellen Computer". Weil das Verhalten des virtuellen Computers identisch mit dem der realen Maschine ist, wenn man vom großen Nachteil der Geschwindigkeit absieht, muß man den neuen Computer nicht als Hardware realisieren. Der darwinistische Computer trägt den Namen Tierra und existiert nur als virtueller Computer, der aber auf den meisten Plattformen (DOS, Windows, Macintosh, Unix, VMS, Amiga) laufen kann und so teure, spezialisierte und schnell veraltete Hardware unnötig macht.

Überdies gewährt das virtuelle System eine absolute Sicherheit, da die digitalen Organismen nur im virtuellen System agieren können. Auf jedem herkömmlichen System sind sie nur Daten, die nicht mehr bewirken können wie eine Textdatei eines Textverarbeitungsprogramms.

Ergebnisse der Evolutionsversuche

Die bislang beobachteten Ergebnisse der Evolutionsversuche stellen eine Vielzahl von Lösungen des Problems der Selbstreplikation von Maschinencodeprogrammen dar. Man könnte diese Lösungen in zwei große Klassen aufteilen: "ökologische Lösungen" und "Optimierungen". Ökologische Lösungen gehen aus Interaktionen zwischen Programmen hervor, die einen gemeinsamen Speicherplatz haben, während Optimierungen Innovationen innerhalb einzelner Algorithmen sind, die zu einer schnelleren Replikation führen.

Ökologische Innovation

Ökologische Anpassungen entstehen aus der Bedingung, daß eine vorherrschende Eigenschaft der Umwelt die Anwesenheit der digitalen Organismen selbst ist. Daher können digitale Organismen evolutionär Anpassungen an die Anwesenheit anderer Organismen zustande bringen, wie dies beispielsweise bei Parasitismus, Immunität, Kooperation und Betrügereien der Fall ist. Anpassungen gab es bei der Ausbeutung von zwei wertvollen Ressourcen, über die die digitalen Organismen verfügten: Prozessorzeit und Information in Form ihres genetischen Maschinencodes.

1. PARASITEN: Eine der zuerst entdeckten Anpassungsleistungen war ein informationeller Parasitismus, durch den der Organismus fast die Hälfte seines eigenen Codes verlor und dessen Funktion durch die Ausführung des relevanten Codes in benachbarten Organismen ersetzte. Diese parasitären Organismen konnten sich fast zwei Mal so schnell wie ihre Wirte replizieren, weil sie nur die Hälfte der Information auf ihre Nachkommen kopieren mußten.
2. LOKTA-VOLTERRA ZYKLEN: Die Parasiten können aber nicht die Wirte aus dem Speicher verdrängen, weil sie wegen einer entscheidenden Informationsmenge von ihnen abhängen. Die Wirt- und Parasitenpopulationen treten in Lotka-Volterra Populationszyklen ein.
3. IMMUNITÄT: Weil die Wirte sich evolutionär entwickeln, bilden sie manchmal Immunsysteme, die sie von den Parasiten befreien. Normalerweise kehren die Parasiten aber nach einer bestimmten Zeit wieder zurück, und Wirte und Parasiten sind abwechselnd im Vorteil, da die Parasiten die Verteidigung der Wirte überwinden und diese wieder neue Abwehrmittel entwickeln.
4. HYPERPARASITEN: Da der informationelle Parasitismus die Ausführung des Codes beinhaltet, der einem anderen digitalen Organismus gehört, erzeugt er eine Angriffsfläche, die von einer neuen Klasse von Anpassungsformen ausgebeutet wurde. Bestimmte Wirte haben ein Mittel gefunden, die CPUs von Parasiten zu übernehmen, die ihren Code ausführen. Sie stehlen wiederum die CPUs von den Parasiten. Die Anwesenheit solcher "Hyperparasiten" in der Umwelt kann zu einem schnellen Aussterben der Parasiten führen.
5. KOOPERATION: Man konnte kooperative Algorithmen sich unter der Bedingung entwickeln sehen, daß eine einzige Art der digitalen Organismen (wie die Hyperparasiten) den Speicher vollständig belegen. Bei diesen Organismen kann sich ein einzelnes Individuum alleine nicht replizieren, aber wenn zwei oder mehr Individuen derselben Art im Speicher zusammentreffen, können sie sich durch eine kooperative Kombination der zwei Kopien des Algorithmus replizieren.
6. BETRÜGER: Eine solche Kooperation schafft aber eine neue Schwachstelle, denn in diese kooperierenden Ansammlungen können "Betrüger" eindringen, die sich zwischen die kooperierenden Individuen einfügen und die CPUs stehlen, wenn sie von Individuum zu Individuum weitergereicht werden.
7. DIE SICH EVOLUTIONÄR ENTWICKELNDE ÖKOLOGIE: Die Evolution ökologischer Anpassungen ist ein andauernder Prozeß. Anscheinend wird jede beliebige Form des Algorithmus, die den Speicher beherrscht, zu einem Ziel der Ausbeutung (oder der Abwehr) seitens anderer Organismen. Wenn der vorherrschende Organismus zum Ziel einer neuen Form der Ausbeutung oder der Abwehr wird, geht seine Herrschaft an den Organismus mit der neuen Anpassung über und der Zyklus setzt von neuem ein.

Optimierung

Ich unterscheide "Optimierungen" von der "ökologischen Anpassung", da sie Innovationen im individuellen Algorithmus hervorrufen, ohne daß Interaktionen mit anderen Individuen geschehen.

1. DER KOMPAKTE CODE: Eine Form der Optimierung erfolgt durch die Reduktion der Instruktionen im Algorithmus, und die Grenze dieses Prozesses scheint bei einem (nicht-parasitären) Replikator von 22 Byte zu liegen. Dieser Replikator hat fast nur ein Viertel der Größe seiner ersten Vorfahren von 80 Bytes und pflanzt sich sechs Mal so schnell fort.
2. DER EFFIZIENTE CODE: Optimierung führt nicht unbedingt zum kompaktesten Code. Manche Optimierungen erreichen eine bessere Effizienz mittels eines komplexeren Codes. Ein Beispiel dafür ist die Technik, "die Schleife zu erweitern". Das Ursprungsprogramm enthält eine Schleife, die einen Byte auf den Nachkommen überträgt. Das Programm kopiert sein ganzes Genom, indem es diese Schleife 80 Mal ausführt. Wir haben Algorithmen gefunden, die sich evolutionär entwickelt haben, die pro Schleife zwei oder drei Bytes kopieren, wodurch sie ihre Effizienz vergrößern. Die Effizienz läßt sich quantititiv bestimmen, wenn man die gesamte Zahl der im Replikationsprozeß ausgeführten Maschineninstruktionen durch die Anzahl der Bytes im Organismus teilt, was zu einem Maß für die Zyklen führt, die zur Kopie eines Byte notwendig sind. Beispielsweise führte ein Vorfahre mit 82 Bytes 8,39 Zyklen für die Kopie eines Byte aus. Dessen kleinster Nachkomme war 23 Bytes groß. Er kopierte pro Schleife ein Byte und benötigte im besten Fall 4,96 Zyklen für die Kopie eines Byte. Ein etwas längerer Nachfahre mit 26 Bytes kopierte pro Schleife zwei Bytes und führte nur 3,73 Zyklen für die Kopie eines Byte aus. Ein anderer mit 43 Bytes kopierte drei Bytes pro Schleife und benötigte nur 3,33 Zyklen für die Kopie eines Byte.
3. DER PARALLELE CODE: Eine andere Methode zur Beschleunigung der Replikation ist die Parallelisierung. Wir haben dies im Fall der "Hyperparasiten" gesehen, die CPUs von den Parasiten stehlen und so gleichzeitig mehr als einen Nachkommen erzeugen können. Die Instruktionen für "Teilen" und "Verbinden" wurden jedoch verbessert und ermöglichten es, daß ein Prozeß sich in viele Stränge aufteilen und diese später wieder zu einem einzigen Strang verbinden konnte. Bei einem neuen Ausgangsorganismus teilt sich der Prozeß in zwei Stränge auf, bevor die Schleife zum Kopieren der Bytes beginnt. Die zwei Prozessoren teilen sich dann die Kopierarbeit, so daß der eine Prozessor die erste Hälfte des Codes kopiert, während der andere die zweite Hälfte kopiert. Nach der Ausführung der Schleife werden diese Stränge wieder zusammengeführt. Durch die Evolution haben diese Algorithmen ihren Parallelismus bis auf 32 Prozessoren erweitert. Der Algorithmus für die 32 Prozessoren schaltet die Schleife aus. Jeder Prozessor kopiert einfach zwei Bytes. Wir haben 16 Prozessororganismen mit Algorithmen für 60 Bytes gefunden. Da sich 60 nicht durch 16 ohne Rest teilen läßt, ist die Arbeitsteilung komplizierter. Bei den Lösungen überlappen sich die Daten, die von den nebeneinander befindlichen Prozessoren kopiert werden.

Systemvergleich

Wir haben die zunehmende Aufgabe der Kontrolle bei synthetischen evolutionären Systemen betrachtet, die zu Systemen führt, deren Evolutionsprozeß zu dem der organischen Evolution weitgehend parallel verläuft.

1. EVOLVIERENDE GENETISCHE STRUKTUR: Bei allen hier betrachteten synthetischen Evolutionssystemen wird das genetische System letztlich von einem Bitstrang repräsentiert. Bei manchen Systemen (genetische Algorithmen, die Sortierer von Hill, PolyWorld) ist die Zusammensetzung dieses Strangs fixiert. Bei anderen kann sich die Zusammensetzung des Stranges evolutionär verändern, so daß die vom Strang repräsentierte "Lösung" nicht fixiert ist, sondern sich durch Evolution abwandelt (genetisches Programmieren, genetische Bilder, die isolierten und konkurrierenden Lebewesen von Sims, Tierra).
2. INTERAKTION: Bei einigen Systemen werden die individuellen, sich evolutionär verändernden Entitäten durch eine externe Fitnessfunktion bewertet, aber können nicht mit anderen Angehörigen der Population interagieren (genetische Algorithmen, genetisches Programmieren, genetische Bilder, die isolierten Lebewesen von Sims). In anderen Systemen wird die Fitness der einzelnen Entitäten teilweise durch ihre Interaktion mit den anderen Angehörigen der Population bestimmt (die Sortierer von Hills, die konkurrierenden Lebewesen von Sims, PolyWorld, Tierra).
3. NATÜRLICHE SELEKTION: Bei den meisten Systemen wird die Selektion von einer externen "Fitnessfunktion" ausgeführt, die festgelegt ist und sich nicht im Lauf der Evolution verändert (genetische Algorithmen, genetisches Programmieren, die isolierten Lebewesen von Sims, die Sortierer von Hills). Beim genetischen Bildprogramm wird die Selektion von der ästhetischen Laune des Benutzers ausgeführt, bei den virtuellen Lebenwesen von Sims, die um den Besitz des Bausteines konkurrieren, ist die externe Fitnessfunktion festgelegt: es die Fähigkeit, einen Baustein zu besitzen. Gleichzeitig aber hängt diese Fähigkeit auf komplexe Weise von den anderen konkurrierenden Lebewesen ab. Daher liegt hier eine partielle natürliche Selektion vor. Nur bei wenigen Programmen ist die Selektion völlig natürlich, d.h. lediglich abhängig von der Fähigkeit zu überleben und sich zu reproduzieren (PolyWorld, Tierra).

Evolution und Maschinensprache

In einer Untersuchung wurden die Evolutionsmuster von vier verschiedenen, aber sehr ähnlichen Maschinensprachen verglichen. Zwei der vier Sprachen zeigten einen weitaus umfassendere Evolution als die anderen, gemessen als Optimierung durch die Abnahme der Größe. Bei den zwei Sprachen, die nur relativ geringfügige Evolutionsmöglichkeiten besaßen, ließ sich ein strikter Gradualismus der Evolution beobachten, während es bei den anderen beiden plötzliche Sprünge gab. Bei einem gab es eine graduelle Evolution zwischen den Sprüngen, beim anderen einen totalen Stillstand.

Es liegt auf der Hand, daß viele Aspekte des Evolutionsprozesses von der Struktur der zugrundeliegenden genetischen Sprache abhängig sind. Aber es gibt keine Theorie, die die Sprachstruktur mit ihrem Evolutionsmuster verbindet. Das ist eine Lücke in unserer Evolutionstheorie, die vor der synthetischen Evolution nicht deutlich war.

Dieser Mangel ist ein ernstes Problem für viele Techniker, die mit der Evolution als einem Werkzeug für das Design oder für Optimierung arbeiten. In jedem Fall schafft der Techniker für die Beschreibung des Lösungsraumes zuerst ein genetisches System, und die Sprache evolviert später. Manche dieser Sprachen werden für die Evolution hervorrragend geeignet sein und andere gar nicht. Aber es gibt keine Theorie, um die Programmierung dieser Sprachen so anzuleiten, daß sie ihre Möglichkeit der Evolution verbessern.

Die Evolution der Sprache

Die organische Evolution auf der Erde organisiert die Formen und Prozesse von Materie und Energie von der molekularen Ebene bis hin zum Ökosystem. Wer von der Gaia-Hypothese ausgeht, würde sagen, daß sie dies bis zur gesamten Biosphäre organisiert. Unterhalb der molekularen Ebene und oberhalb des Ökosystems spielt Evolution keine Rolle. Wir werden ähnliche Grenzen für die Reichweite der Evolution auch in synthetischen Systemen finden.

Bei allen vorgestellten Programmen ist die untere Grenze die Repräsentationssprache, innerhalb derer die Evolution sich abspielt. Bei den Genetischen Algorithmen legt jede Implementierung die Bedeutung jeder Bitgruppe im Strang wie bei den Werten der Koeffizienten in einer Gleichung fest. Beim Genetischen Programmieren enthält die Lisp-ähnliche Sprache eine festgelegte Menge von Sprachfunktionen, die die Knoten (z.B. Addieren, Subtrahieren, Bits Verschieben) und die Äste (z.B. ganze oder reale Zahlen, Zufallsgeneratoren für Zahlen oder andere Rauschfunktionen) der Bäume bilden können. Bei Tierra besteht die Sprache aus wenigen Maschinenbefehlen.

Es wurde viel darüber diskutiert, wie man die Evolution auf die Repräsentationssprache selbst wirken lassen könnte. Eine äußerst produktive Realisierung dieser Idee ist durch automatisch definierte Funktionen möglich. Dabei benutzt Lisp-Ausdrucksbäume, bei denen ein besonderer genetischer Operator jeden untergeordneten Baum in eine sprachliche Grundfunktion verändern kann. Diese untergeordneten Bäume nennt man Module. Sie werden im wesentlichen zu eingefrorenen Baumfragmenten, die vor der Mutation geschützt sind. Als neue Elemente der zugrundeliegenden Sprache können sie vom Mutationsoperator als Einheiten eingefügt werden und sind so vor der Fragmentierung durch den Kreuzungsoperator geschützt. Deswegen können sie sich als Einheiten in der Population verbreiten.

Auf diese Weise kann die sprachliche Repräsentation höhere Funktionsebenen entwickeln. "Die Emergenz eines nützlichen Moduls", haben Angeline und Pollack beobachtet, "reduziert die Größe des Genotyps und folglich die Zahl der verfügbaren Kreuzungs- und Mutationspunkte. Das konzentriert den Evolutionsprozeß auf die Verbesserung der sich evolutionär bildenden Programme auf einer höheren Abstraktionsebene und zerstört nicht zuvor entdeckte Baublöcke." Ein solcher Ansatz sollte vermutlich weiterhin verfolgt werden.

Obwohl automatisch definierte Funktionen eine Methode sind, um die Evolution höherer Funktionsebenen zu ermöglichen, konzentriert sich die Diskussion über die Evolution der Repräsentation auf das entgegengesetzte Ziel: auf die Suche nach einer niedrigeren Repräsentationsebene, mit der sich die optimale Form der sprachlichen Repräsentation auf ihrer gegenwärtig realisierten Ebene durch Evolution herausfinden läßt.

Diese Idee wird oft im Kontext einer Diskussion über die Designprobleme sich evolutionär entwickelnder Sprachen vorgeschlagen, wie wir dies weiter oben erwähnt haben. Man kann sich fragen, ob die natürliche Selektion die evolutionäre Entwicklung fördert, wenn ein solches System zur Evolution der sprachlichen Repräsentation gebaut werden könnte.

Ich kenne keine Beispiele, die diese Idee implementiert haben. Obwohl das eine interessante Forschungsrichtung wäre, zweifle an deren möglicher Produktivität. Es muß eine Ebene unterhalb der Evolution geben, in die sie nicht eingreift: die Physik. Wir müssen letztlich akzeptieren, daß die Evolution in der Physik eingebettet ist, die sich nicht evolutionär entwickelt.

Teil 1: Künstliches Leben

Teil 3: Experimentelle Evolution
Ein anderes Verhältnis zur Evolution
Ein digitales Analogon der kambrischen Explosion
Die Auslösung einer spontanen Komplexitätssteigerung
Vergeßt den Turing-Test
Experimentelle Simulation

Aus dem Englischen übersetzt von Florian Rötzer