Digitales Leben

Digitales Leben

Tierra, Avida & Physis

Autor: Donald Barkowski

ÜbersichtMotivationTierraGenetische ProgrammierungAvidaPhysis

MotivationDefinition von Artificial Life:

„Das Studieren von Leben mit Hilfe von menschengeschaffenen Analogien zu lebenden Systemen“

Begriffsprägung:Konferenz „Artificial Life I“ (1987)

Motivationzwei Ausprägungen von Artificial

Lifestrong alife: Leben ist unabhängig

vom Mediumweak alife: Leben existiert nur auf

Kohlenstoffbasis

MotivationDas Spiel Core War (Scientific

American, Mai 1984)Assemblerprogramme kämpfen um

HauptspeicherKampfstrategie: Stein-Schere-PapierSieg: Gegner wird nicht mehr

ausgeführtkeine Mutationen

Motivationspezielle Programmiersprache:

Redcodewenige verschiedene Befehlekurze Befehlealle Speicherzugriffe modulo

Speichergrößekeine externen Register

MotivationWeiterentwicklung: Core World

Mutationen: zufällige Codeänderungen

keine Evolution von stabilen oder komplexen Programmen wegen schlechter Unterstützung durch Programmiersprache; Mutationen meist nicht lebensfähig

MotivationErfahrungen durch Core world

Programmiersprache:nur relative Sprungadressen(Touring-)VollständigkeitAbgeschlossenheitInterpreter besser als direkte Ausführung, wenn

auch langsamervirtuelle Welt:

keine Sprünge außerhalb reserviertem Speicherbereich (Modulo-Arithmetik)

ÜbersichtMotivationTierraGenetische ProgrammierungAvidaPhysis

Tierraab Ende 1989 von Tom

Ray entwickeltMotivation: Beobachtung

von Leben abseits von Kohlenstoffverbindungen

“Our current knowledge of life and evolution is based on a sample size of one: life on Earth.”

Tierraneuer BefehlssatzMutationen und RekombinationFitness = Fortpflanzungs- und

Überlebensfähigkeit

Fast alle Versuche, den evolutionären Aspekt von Tierra zu verbessern, sind gescheitert

TierraEigene Welt: virtual machine

führt Maschinenbefehle ausCode flexibel genug für Evolution:

unterstützt Mutation (bitweise Änderung) und Rekombination (Austausch von Programmsegmenten)

mutierter Code oft genug ausführbarTopologie: Entfernung = Zugriffszeit

TierraEigenes „darwinistisches“ Betriebssystem

verwaltet RAM (Material, Soup) und CPU (Energie)

Reaper„tötet“ bei Bedarf älteste Programmeschafft freie Speicherbereiche für Nachwuchs

Slicerteilt Prozessen Zeitscheiben zu (nicht-

deterministisch)verwaltet (virtuellen) Prozessor

Wirt-Parasit-Experiment

viele Wirte (rot) kurz nach der Injektion: einige Parasiten (gelb) vorhanden

Wirt-Parasit-Experiment

Parasiten haben sich stark vermehrt Wirte in Bedrängnis erstes Auftreten von resistenten Wirten (blau)

Wirt-Parasit-Experiment

Parasiten werden räumlich verdrängt nicht-resistente Wirte schwinden weiter resistente Wirte vermehren sich und verdrängen Parasiten

Wirt-Parasit-Experiment

Parasiten werden selten (sterben bald aus) nicht-resistente Wirte schwinden weiter resistente Wirte dominante Lebensform

Tierradank Tierra erstmalig beobachtet:

zielgerichtete und erfolgreiche Evolution von Programmen

Bedeutung von Koevolution im (virtuellen) Evolutionsprozess

TierraABER:

⊖keine Einflussnahme auf Evolutionsziel

⊖alle Prozesse im gleichen Speicher⇒ Ergebnisse nicht reproduzierbar

ÜbersichtMotivationTierraGenetische ProgrammierungAvidaPhysis

Genetische Programmierung

Aufgabe:Generierung eines Computerprogramms anhand von Trainingsdaten

Weiterentwicklung von Evolutionären Algorithmen: nicht die Lösung wird entwickelt, sondern der Lösungsweg

Spezialfall von Genetischen Algorithmen: Der Algorithmus entsteht direkt in einer (Pseudo-)Programmiersprache

Genetische Programmierung

Programmiersprache: z.B. LISPLesbarkeiteinfache Struktur

Darstellung des Codes: Bauminnere Knoten:

FunktionenBlätter: TerminaleMaximalhöhe

Genetische Programmierung

Mutation: spontane Veränderung der Knoten / Blätter

Rekombination: Austausch von Teilbäumen (Crossover)

Genetische Programmierung

Ansprüche an die Fitnessfunktionmöglichst exakte Erfassung der

Qualitätauch differenzierte Bewertung von

Teillösungenevtl. mehrere Kriterien

Berücksichtigung von Laufzeit/KomplexitätFitness im „darwinistischen“ Sinne

Genetische Programmierung

Abbruchbedingung:bestimmte Anzahl von Generationenexakte Lösunghinreichend genaue Lösung

Genetische Programmierung

mögliche Selektionskriterien:immer fitteste Individuen nehmenstochastischer Prozess: auch schlechter

angepasste Individuen können überleben

meistens: zufällige Auswahl einer Gruppe, dann Selektion mit Fitnessfunktion (Ziehen mit Zurücklegen)

Genetische Programmierung

Algorithmus:

Genetische Programmierung

Effizienzverbesserungen:bessere Sprachen (auf Kosten der

Lesbarkeit)ADFs (automatisch definierte

Funktionen)Analogie zum klassischen

Programmieren: UnterprogrammaufrufeFestlegungen bezüglich StrukturAufwand schwer abschätzbar

Genetische Programmierung

Problembezogen / ErgebnisorientiertReplikation nicht Bestandteil des

Algorithmuskein Artificial Lifewichtig: Reproduktion/Aufbereitung

des Ergebnisses muss möglich sein!!

ÜbersichtMotivationTierraGenetische ProgrammierungAvidaPhysis

Avida

Artificial Life+

genetischeProgrammierung

AvidaAnlehnung an Tierra, aber:

getrennter Speicher für Programmeeigene virtuelle CPU für jedes

Programmmodifizierbare Fitnessfunktion

(Belohnung für erwünschte Eigenschaft)

AvidaDie virtuelle CPU:

Köpfe

Genom Register

Stack

Instruction Pointer Puffer

AvidaBefehlssatz:

individuelle Auswahl möglichevtl. selbstdeklarierte Funktionen

Anforderungen:Vollständigkeit (auch: alles lässt sich ohne

großen Aufwand berechnen)Robustheit: Anweisungen führen in jedem

Kontext (sinnvolle) Aktionen ausmöglichst geringe Redundanz

Avidawichtiges Konzept: „nop“-Anweisungen

keine Aktion zur Ausführungszeitverändern u.U. den vorangehenden Befehl

3 „Befehlsklassen“bilden Labels (Sprungziele) im Codekomplementäre nops:

nop-A & nop-Bnop-B & nop-Cnop-C & nop-B

AvidaBefehlssatz (Ausschnitt)

Befehl Auswirkungh-alloc Reserviere Speicher für einen Nachkommenh-search Finde ein komplementäres Muster und platziere

den Flow-Head dahintermov-head Bewege den ?IP? an die gleiche Stelle wie den

Flow-Headh-copy Kopiere einen Befehl vom Lese- zum Schreibkopf

und schiebe beide eine Position weiterif-label Führe die nächste Instruktion nur dann aus, wenn

das Komplement zum gegebenen Muster als letztes kopiert worden ist

h-divide Trenne einen Nachkommen zwischen Lese- und Schreibkopf heraus

Avidaein einfachstes Genom (nur selbstreproduzierend)# --- Setup --h-alloc # Allocate extra space at the end of the genome to copy the offspring into. h-search # Locate an A:B template (at the end of the organism) and place the Flow-Head after it nop-C # nop-A # mov-head # Place the Write-Head at the Flow-Head (which is at beginning of offspring-to be). nop-C # [ Extra nop-C commands can be placed here w/o harming the organism! ] # --- Copy Loop --h-search # No template, so place the Flow-Head on the next line (to mark the beginning of the

copyloop) h-copy # Copy a single instruction from the read head to the write head (and advance both heads!) if-label # Execute the line following this template only if we have just copied an A:B template. nop-C # nop-A # h-divide # ...Divide off offspring! (note if-statement above!) mov-head # Otherwise, move the IP back to the Flow-Head at the beginning of the copy loop. nop-A # End label. nop-B # End label.

AvidaNachteil: Der Benutzer bestimmt

den Befehlssatz und legt damit auch die (virtuelle) Hardware fest

ÜbersichtMotivationTierraGenetische ProgrammierungAvidaPhysis

PhysisInformation über

den ausführenden Prozessor ist Teil des Genoms

entwickelt ab 2000Ähnlich zu Tierra

und Avida, aber universeller einsetzbar

PhysisUniverselle Prozessorarchitektur,

auf der viele Prozessortypen implementiert werden können

Interaktion zwischen Prozessen möglich (z.B. Parasitismus)

detaillierte Messungen und Beobachtungen möglich

PhysisStandard-Prozessor (mit festem

Befehlssatz)

Physis

Nach der Evolution:1. Nachbau des Prozessors gemäß

der Beschreibung

Physis

Nach der Evolution:2. Programmcode auf dem neuen

Prozessor ausführen

PhysisTatsächlich: Laufzeitvorteile

Noch Fragen???

? ? ?

LiteraturVolker Nissen: Einführung in

Evolutionäre Algorithmen (vieweg 1997)Tierra: www.his.atr.jp/~ray/tierra/Physis: physis.sourceforge.net/

physis.sourceforge.net/old/index.htmlAvidad: http://dllab.caltech.edu/avida/www.wikipedia.orgRichard E. Lenski, et al: The evolutionary

origin of complex features (nature 2002)