Post on 05-Apr-2015
transcript
Digitales Leben
Tierra, Avida & Physis
Autor: Donald Barkowski
Übersicht
MotivationTierraGenetische ProgrammierungAvidaPhysis
Motivation
Definition von Artificial Life:„Das Studieren von Leben mit Hilfe von menschengeschaffenen Analogien zu lebenden Systemen“
Begriffsprägung:Konferenz „Artificial Life I“ (1987)
Motivation
zwei Ausprägungen von Artificial Lifestrong alife: Leben ist unabhängig
vom Mediumweak alife: Leben existiert nur auf
Kohlenstoffbasis
Motivation
Das Spiel Core War (Scientific American, Mai 1984)Assemblerprogramme kämpfen um
HauptspeicherKampfstrategie: Stein-Schere-PapierSieg: Gegner wird nicht mehr
ausgeführtkeine Mutationen
Motivation
spezielle Programmiersprache: Redcodewenige verschiedene Befehlekurze Befehlealle Speicherzugriffe modulo
Speichergrößekeine externen Register
Motivation
Weiterentwicklung: Core WorldMutationen: zufällige
Codeänderungenkeine Evolution von stabilen oder
komplexen Programmen wegen schlechter Unterstützung durch Programmiersprache; Mutationen meist nicht lebensfähig
Motivation
Erfahrungen durch Core worldProgrammiersprache:
nur relative Sprungadressen(Touring-)VollständigkeitAbgeschlossenheitInterpreter besser als direkte Ausführung, wenn
auch langsamer
virtuelle Welt:keine Sprünge außerhalb reserviertem
Speicherbereich (Modulo-Arithmetik)
Übersicht
MotivationTierraGenetische ProgrammierungAvidaPhysis
Tierra
ab Ende 1989 von Tom Ray entwickelt
Motivation: Beobachtung von Leben abseits von Kohlenstoffverbindungen
“Our current knowledge of life and evolution is based on a sample size of one: life on Earth.”
Tierra
neuer BefehlssatzMutationen und RekombinationFitness = Fortpflanzungs- und
Überlebensfähigkeit
Fast alle Versuche, den evolutionären Aspekt von Tierra zu verbessern, sind gescheitert
Tierra
Eigene Welt: virtual machinefü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
Tierra
Eigenes „darwinistisches“ Betriebssystemverwaltet 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
Tierra
dank Tierra erstmalig beobachtet:zielgerichtete und erfolgreiche
Evolution von ProgrammenBedeutung von Koevolution im
(virtuellen) Evolutionsprozess
Tierra
ABER: ⊖keine Einflussnahme auf
Evolutionsziel⊖alle Prozesse im gleichen Speicher
⇒ Ergebnisse nicht reproduzierbar
Übersicht
MotivationTierraGenetische 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ät
Fitness 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!!
Übersicht
MotivationTierraGenetische ProgrammierungAvidaPhysis
Avida
Artificial Life+
genetischeProgrammierung
Avida
Anlehnung an Tierra, aber:getrennter Speicher für Programmeeigene virtuelle CPU für jedes
Programmmodifizierbare Fitnessfunktion
(Belohnung für erwünschte Eigenschaft)
Avida
Die virtuelle CPU:
Köpfe
GenomRegister
Stack
Instruction Pointer Puffer
Avida
Befehlssatz: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
Avida
wichtiges Konzept: „nop“-Anweisungenkeine 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
Avida
Befehlssatz (Ausschnitt)Befehl Auswirkungh-alloc Reserviere Speicher für einen Nachkommen
h-search Finde ein komplementäres Muster und platziere den Flow-Head dahinter
mov-head Bewege den ?IP? an die gleiche Stelle wie den Flow-Head
h-copy Kopiere einen Befehl vom Lese- zum Schreibkopf und schiebe beide eine Position weiter
if-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
Avida
ein 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.
Avida
Nachteil: Der Benutzer bestimmt den Befehlssatz und legt damit auch die (virtuelle) Hardware fest
Übersicht
MotivationTierraGenetische ProgrammierungAvidaPhysis
Physis
Information über den ausführenden Prozessor ist Teil des Genoms
entwickelt ab 2000Ähnlich zu Tierra
und Avida, aber universeller einsetzbar
Physis
Universelle Prozessorarchitektur, auf der viele Prozessortypen implementiert werden können
Interaktion zwischen Prozessen möglich (z.B. Parasitismus)
detaillierte Messungen und Beobachtungen möglich
Physis
Standard-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
Physis
Tatsächlich: Laufzeitvorteile
Noch Fragen???
? ? ?
Literatur
Volker 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)