Der Verlust der Kontrolle

Digitale Evolution II

Im Bereich des Künstlichen Lebens gibt es viele unterschiedliche Ansätze. Tom Ray, interessiert vor allem an Modellen der digitalen Evolution, stellt die wichtigsten Entwicklungen (Genetische Algorithmen, Genetisches Programmieren, künstliche und natürliche Selektion) vor und versucht anhand "Tierra" deutlich zu machen, warum natürliche Selektion ohne vorgegebene Fitnessfunktion für ihn der fruchtbarste Ansatz ist und wie entscheidend dafür die geeignete Maschinensprache ist.

Digitale Evolution I
Synthetische Evolution - Synthetisches Leben? - Synthese und Simulation - Evolution und das Medium.

Digitale Evolution III: Experimentelle Evolution
Evolution und Maschinensprache - Die Evolution der Sprache - Ein anderes Verhältnis zur Evolution - Zuwachs an Komplexität - Ein digitales Analogon der kambrischen Explosion - Vorteile der vernetzten Umwelt - Autokatalytische Evolution - Die Steuerung der Evolution - Grenzen der Imagination - Vergeßt den Turing Test! - Die Last der Vorurteile - Experimentelle Evolution - Rückkehr zu unseren Wurzeln

Homepage von Tom Ray

Genetische Algorithmen

Auch wenn es eine ganze Reihe unterschiedlicher Richtungen in unserem Verhältnis zur synthetischen Evolution gibt, möchte ich mich auf unsere bewußten Bemühungen zur Aufgabe der Kontrolle konzentrieren, wodurch die Evolution sich frei auf eine Weise entfalten soll, die der bei der Schaffung des organischen Lebens auf der Erde am nächsten kommt.

Vielleicht die erste und am besten bekannte Arbeit mit der digitalen Evolution erfolgte durch die sogenannten Genetischen Algorithmen (GA). Genetische Algorithmen benutzen normalerweise Bitstränge, um Lösungen für irgendein technisches Problem zu codieren. Indem man Bitstränge in einer großen Population mutieren und miteinander kreuzen läßt, wiederholt die "Fitness" der Lösungen bewertet und die besten Lösungen bevorzugt repliziert, kann der genetische Algorithmus nach optimalen Lösungen suchen.

Beim Design der GA ist die Codierung des Lösungsraums durch die Bitstränge begrenzt. Für gewöhnlich hat der Bitstrang eine bestimmte Länge, wobei wie bei den Koeffizienten einer Gleichung den aufeinanderfolgenden Abschnitten der Kette die Repräsentation zuvor festgelegter Quantitäten zugewiesen wird. Daher ist die Lösungsform von vornherein festgelegt und kein Bestandteil des evolutionären Prozesses.

Obgleich die Wissenschaftler im Bereich der GA gerne den Begriff der "natürlichen Selektion" verwenden, um ihren Evolutionsprozeß zu beschreiben, kommt sie hier in keiner Weise zur Geltung. Es handelt sich um eine künstliche Selektion. Der Programmierer des GA schreibt einen Algorithmus der "Fitnessfunktion", der festlegt, welche Mitglieder der Population von Bitsträngen bevorzugt werden. Bitstränge werden dadurch bevorzugt, daß sie eher als andere Stränge repliziert werden, während weniger erwünschte in einer bestimmten Generation auch ganz ausgelöscht werden können.

Bemerkenswert ist auch, daß die Stränge in einem GA sich nicht selbst replizieren. Sie werden von einem Simulationssystem nach der Bewertung durch die Fitnessfunktion kopiert. Sie können genau oder mit einigen "Mutationen" in Form von Bitflips kopiert werden. In vielen Fällen wird nur ein Abschnitt des Bitstrangs in Kombination mit einem komplementären Abschnitt eines anderen erwünschten Bitstrangs kopiert. Flexiblere GA-Strukturen erfordern keine festgelegte Länge der Bitstränge, so daß hier auch Einfügungen oder Zerstörungen von Bits stattfinden können.

Der GA stellt ein Extrem im Spektrum der Kontrolle dar: die totale Kontrolle. Die GA-Software kontrolliert die Form der Lösung, die Fitnessfunktion, die Natur der genetischen Operatoren und die Methode der Replikation ganz und gar. Hingewiesen sei aber darauf, daß die GA nicht immer mit der oben beschriebenen klassischen Form übereinstimmen müssen. Es gibt viele Innovationen und hybride Formen.

Genetisches Programmieren

Bei einer neueren Entwicklung, die man genetisches Programmieren (GP) nennt, sind die Lösungen durch Bäume von lisp-ähnlichen Ausdrücken definiert. Die genetischen Verfahren der Mutation und der Kreuzung können an jedem Knoten des Baums wirken. Im Fall der Kreuzung wird zufällig ein Knoten bei (normalerweise) zwei unterschiedlichen Bäumen ausgewählt. Die Knoten und alle ihre höheren Zweige und Blätter werden zwischen den Bäumen einfach ausgetauscht.

Bei der Mutation kann der Knoten eines Baumes durch einen zufällig ausgewählten Knoten mit derselben Zahl von absteigenden Zweigen ersetzt werden, wobei die höheren Zweige und Blätter unverändert bleiben. Es kann auch ein Knoten mit mehr oder weniger Ästen an dessen Stelle eingesetzt werden, wobei einige höhere Zweige hinzugefügt oder entfernt werden müssen. Schließlich kann der Knoten mit allen seinen höheren Zweigen und Blättern ersetzt werden Im Fall der Ersetzung und Hinzufügung von Zweigen bei der Mutation ist die Erzeugungsquelle der ersetzenden Blätter und ihrer Strukturen willkürlich und kann durch einen Zufallsgenerator bewirkt werden.

Die Form der Lösung muß bei dieser Methode nicht von vornherein definiert werden und kann daher evolvieren. Das eröffnet einen kreativeren Gebrauch des Evolutionsprozesses und wurde vor allem von John Koza bei einem weiten Feld von Problemen eingesetzt.

Eine bereits beobachtete Eigenschaft der GP-Evolution ist die Tendenz, daß die Baumgröße während der Evolutionszeit zunimmt. Das läßt sich als Evolution zu einer höheren Komplexitätsstufe deuten, wodurch eines der Hauptziele der synthetischen Evolution erreicht würde. Genauso wahrscheinlich aber ist auch, daß mit dem Fehlen jeder Selektion zunehmender Größe oder der relativen Kosten von dieser, die Zunahme der Größe sich nur dem Einbau von bedeutungslosem "Junk"-Code verdankt. Beim GP wird dieser Code trotzdem vom System bewertet, wobei größere Bäume zur Bewertung eine größere Rechenzeit erfordern. Deswegen ist es wünschenswert, daß GPs Mechanismen enthalten, die gegen diese Tendenz zum bedeutungslosen Größenwachstum arbeiten.

Auch wenn GP einen frei formbaren Lösungsraum ermöglicht, hat es mit den GA die totale Kontrolle über die Natur der "Fitnessfunktion" und den Replikationsprozeß gemeinsam.

Ästhetische Selektion

Karl Sims setzte die Methode des genetischen Programmierens zusammen mit auf ästhetischen Kriterien des Benutzers basierenden Selektion ein, um abstrakte Bilder zu generieren. Das ist ein Schritt hin zum Verlust der Definition der "Fitnessfunktion". Bei dem traditionellen GA und GP ist die Fitnessfunktion fest im Computer codiert. Bei den genetischen Bildern von Sims entsteht sie durch die ästhetisch motivierten Entscheidungen des menschlichen Benutzers innerhalb jeder Generation von Bildern. Diese Selektionskriterien sind launisch und verändern sich bei jeder Generation, wenn die Genetiker neue Entscheidungsmuster erzeugen.

Karl Sims: virtuelle Lebewesen

Karl Sims setzt ein ähnlich flexibles genetisches System ein, um Lösungen des Problems zu spezifizieren, ein aus Bausteinen konstruiertes "Lebewesen" zu sein, die durch flexible Gelenke verbunden sind und von durch Schaltkreise gesteuerte "Muskeln" bewegt werden. Sims bettete diese Bausteinlebewesen in Simulationen der realen Physik wie in Wasser oder auf eine Oberfläche ein. Dann wurden sie aufgrund ihrer Leistungen bei unterschiedlichen Aufgaben wie Schwimmen, Schwimmer zu einer Lichtquelle, Bewegung über eine Oberfläche, Springen auf einer Oberfläche und dem Versuch, einen quadratischen Baustein im Kampf mit einem anderen Lebewesen in seinen Besitz zu bekommen.

Diese Experimente brachten eine erstaunliche und faszinierende Zahl von Lebewesen hervor. Einige waren vertraut wie die schwimmenden "Schlangen-" oder gehenden "Krabbenformen". Andere erfüllten ihre Aufgaben effizient, aber brachten sie mit völlig ungewöhnlichen Bewegungsmustern und Körperformen zuwege. Diese ungeregelte Entstehung von Formen erinnert an die Schöpfung von Tieren in der kambrischen Explosion, in der viel mehr experimentelle Formen erschaffen wurden als jene, die bis heute überlebt haben und uns vertraut sind.

Die Arbeit von Sims ist im Prinzip mit einem GA oder einer GP vergleichbar, aber die Genotypen basieren auf Graphen und nicht auf Strängen oder Baumstrukturen. Wie bei jeder Optimierung ist die Fitnessfunktion (z.B. die maximale Geschwindigkeit) von vornherein festgelegt. Dennoch ging es nicht darum, eine optimale Lösung zu finden, sondern eine Lösungsvielfalt für jede Fitnessfunktion entstehen zu lassen. Das System war so aufgebaut, daß eine beeindruckende Lösungsvielfalt möglich war und sich auch herausbildete.

Sims stellte die Ergebnisse nicht in Form einer Optimierungskurve dar, die veranschaulicht, wie sich die Leistung (z.B. die maximale Geschwindigkeit) mit der Zeit der Evolution verbesserte, sondern in Form einer Naturgeschichte. Er zeigte die Form und das Verhalten einer Vielfalt von Individuen, die sich im Evolutionsprozeß entwickelt haben.

Ein Verlust der Fitnessfunktion fand im Experiment dann statt, wenn es darum ging, sich einen Baustein anzueignen. Der Besitz eines Bausteines brachte einen Kampf zwischen ko-evolvierernden Populationen mit sich, der an Paaren von Individuen entschieden wurde. Deshalb war die Form des gegnerischen Lebewesens ein sich evolutionär entwickelnder Bestandteil der Fitnesslandschaft. In diesem Fall lag eine große Komponente der Fitnessfunktion außerhalb der Systemspezifizierung, weswegen es einen bedeutsamen Anteil an natürlicher Selektion enthielt.

Ko-Evolution

Eine allgemeine Eigenschaft der traditionellen GA und GP ist die Bewertung der von anderen Angehörigen der Population isolierten Genome durch die "Fitnessfunktion". Die Genome interagieren lediglich mit der Fitnessfunktion (und in manchen Fällen mit den Daten), aber nicht untereinander. Das schließt die Evolution von kollektiven Problemlösungen aus, die sehr wirkungsvoll sein können.

Die Lebewesen von Sims, die um den Besitz von Bausteinen konkurrieren, sind das erste der von uns aufgeführten Beispiele, bei dem es eine direkte Interaktion zwischen den Mitglieder sich evolutionär entwickelnder Populationen gibt. Hillis setzte genetische Algorithmen zur Evolution von Algorithmen ein, die Listen von 16 Zahlen sortieren. Die Fitness dieser Algorithmen wurde auf der Grundlage des prozentualen Anteils der Testlisten bewertet, die richtig sortiert wurden. Er beobachtete, daß dieser Evolutionsprozeß nicht effizient war, weil die Evolution sehr schnell Sortierungsalgorithmen entwickelte, die die meisten Listen richtig sortieren konnten. Daher gab es bei den meisten Testlisten keinen Unterschied, an dem die Selektion ansetzen konnte. Es trat überdies eine evolutionäre Tendenz auf, an einem "lokalen Optimum" zum Stillstand zu kommen.

Um die Effizienz dieses Prozesses zu verbessern, räumte Hillis die Möglichkeit ein, daß die Testlisten durch eine ko-evolvierende Reihe genetischer Algorithmen bestimmt werden konnten. Die Fitness der Testlisten bestand im Gegenteil der Fitness des Sortiermechanismus, also der Zahl der Sortiermechanismen, die die Liste nicht richtig sortieren konnten.

In dem System, bei dem die Sortiermechanismen und die Testlisten sich ko-evolutionär entwickelten, war die Evolution der Sortiermechanismen hinsichtlich der erforderlichen Rechenleistung viel effizienter und konnte kürzere Sortieralgorithmen herstellen als beim Versuch ohne Ko-Evolution. Wichtig ist auch, daß bei der Ko-Evolution die Sortiermechanismen keine Tendenz zeigten, in einem lokalen Optimum steckenzubleiben.

Natürliche Selektion

Obwohl die Mehrzahl der Evolutionsexperimente im digitalen Medium klare technische Zwecke hatte, erforschten manche einfach den Evolutionsprozeß in einem unvertrauten Medium. In diesem Fall wurden die Bedingungen für die freie Evolution so geschaffen, daß die natürliche Selektion bei selbstreplizierenden Computerprogrammen stattfinden konnte. Daraus entsteht eine nicht gelenkte diversifizierende Phylogenese "digitaler Organismen" in einer ökologischen Gemeinschaft im Cyberspace.

Larry Yaeger installierte ein auf genetischen Algorithmen basierendes System mit dem Programm "PolyWorld", das sich frei durch natürliche Selektion evolutionär entwickelte. Der GA legte die Eigenschaften der "Organismen" fest, die auf einer simulierten flachen Oberfläche leben, auf der sich Barrieren befinden können. Auch "Nahrung" wird auf der Oberfläche verteilt.

Die Organismen besaßen bunte polygonale Körper, visuelle Systeme und neuronale Netze, die an ihren Synapsen durch den Hebbschen Mechanismus lernten. Der Output der neuronalen Netze determiniert das Verhalten der Organismen durch vorneweg spezifizierte Neuronen völlig, deren Output die Aktivierung von sieben Verhaltensweisen festlegten: Fressen, Paaren, Kämpfen, Bewegung, Drehen, Aufmerksamkeit und Leuchten. Alle Verhaltensweisen, einschließlich der Aktivität des neuronalen Netzes, verbrauchen Energie, die durch Nahrungsaufnahme wieder aufgefüllt werden kann.

Der GA-Bitstrang definiert die strukturellen und einige funktionellen Eigenschaften der Organismen durch Werte für Größe, Stärke, maximale Geschwindigkeit, den grünen Farbwert, die Mutationsrate, die Lebensspanne, die zur Reproduktion nötige Energiegröße und elf Eigenschaften der neuronalen Netze.

"PolyWorld" kann zu Beginn mit zufällig generierten Genomen geimpft werden. Manchmal können diese sich nicht effektiv reproduzieren. Dann stirbt die Welt. Manchmal etablieren sich stabile Populationen, und es entsteht eine Vielfalt von Verhaltensweisen und Ökologien.