Download ppt - Digitales Leben Tierra, Avida & Physis Autor: Donald Barkowski

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


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


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


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


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


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


Programmiersprache: z.B. LISPLesbarkeiteinfache Struktur

Darstellung des Codes: Bauminnere Knoten:

FunktionenBlätter: TerminaleMaximalhöhe


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

Rekombination: Austausch von Teilbäumen (Crossover)


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


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


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)


Algorithmus:


Effizienzverbesserungen:bessere Sprachen (auf Kosten der

Lesbarkeit)ADFs (automatisch definierte

Funktionen)Analogie zum klassischen

Programmieren: UnterprogrammaufrufeFestlegungen bezüglich StrukturAufwand schwer abschätzbar


Problembezogen / ErgebnisorientiertReplikation nicht Bestandteil des

Algorithmuskein Artificial Lifewichtig: Reproduktion/Aufbereitung

des Ergebnisses muss möglich sein!!

Übersicht


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


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)

http://www.wikipedia.org/