Upload
gisa-schierman
View
105
Download
2
Embed Size (px)
Citation preview
EvoLab@SGH Martin Reiche, 2005 1
„Von nichts kommt nichts!“
Oder doch?
Evolution im Computer
EvoLab@SGH Martin Reiche, 2005 2
Themenbereiche Evolution als Informationserzeugung Formale Modellierung einer Orientierungsleistung Zustandsautomat „Kombinatorische Explosion“ und „reiner Zufall“ Optimierung, Zielfunktion, „Fitnesslandschaft“ Modellierung des Evolutionsprozesses als
„Algorithmus“ Außerordentliche Leistungsfähigkeit und Universalität
der Evolution Wesen und Wirkung von Reproduktion, Selektion,
Mutation, Fitness Explizites vs. implizites Wissen/Lernen, Abstraktion
EvoLab@SGH Martin Reiche, 2005 3
Leben und Information Das Leben auf der Erde besteht aus einzelnen
Individuen, die ständig neu geboren werden und wieder sterben.
Was nicht stirbt, ist der Bauplan, nach dem ihr Körper aufgebaut ist und der ihr Verhalten steuert.
Dieser Bauplan ist Ergebnis der Evolution.Er wird immer wieder kopiert und verändert.
Jeden Plan können wir als Information darüber begreifen, wie etwas zu geschehen hat.
Die Evolution erzeugt also Information.
EvoLab@SGH Martin Reiche, 2005 4
Information und Computer Ein Computer ist eine Maschine zur
Informationsverarbeitung. Kann er nicht auch Information „produzieren“,
so wie die Evolution? Und was bedeutet das eigentlich? Wir wissen doch:
„Von nichts kommt nichts!“
EvoLab@SGH Martin Reiche, 2005 5
Zweck von EvoLab (allgemein)
Wir stellen dem Computer eine Aufgabe, für die er selbständig eine Lösung, einen Plan finden soll. Dabei soll er wie bei der Evolution der Lebewesen verfahren.
Dazu bräuchte man nicht unbedingt einen PC: Bleistift, Papier und Würfel täten es auch, allerdings würde das dann sehr zeitaufwändig...
EvoLab@SGH Martin Reiche, 2005 6
Zweck von EvoLab (speziell)
Der Computer soll „künstliche Ameisen“ züchten, die in der Lage sind, einer Spur zu folgen.
Er soll die Information erzeugen, die eine Ameise erfolgreich steuert.
EvoLab@SGH Martin Reiche, 2005 7
Sicht einer Ameise
EvoLab@SGH Martin Reiche, 2005 8
Wirkungskreislauf beim Verfolgen einer Spur
Welt
Auge
Gehirn
Beine
EvoLab@SGH Martin Reiche, 2005 9
Zustandsautomaten
Sicht:
ZA 1(variabel)
ZA 2(fest)
Relative Bewegung: , , ,
Absolute Bewegung: N, W, S, O
, , , , , , ,
EvoLab@SGH Martin Reiche, 2005 10
Darwins Beobachtungen (1)
Alle Arten weisen ein derart hohes Fortpflanzungspotential auf, dass ihre Populationsgröße exponentiell zunehmen würde, wenn alle Individuen, die geboren werden, sich erfolgreich fortpflanzten.
EvoLab@SGH Martin Reiche, 2005 11
Exponentielles Wachstum
der Menschheit
EvoLab@SGH Martin Reiche, 2005 12
Darwins Beobachtungen (2+3)
Die meisten Populationen sind normalerweise mit Ausnahme saisonaler Schwankungen in ihrer Größe stabil.
Die natürlichen Ressourcen sind begrenzt.
EvoLab@SGH Martin Reiche, 2005 13
Darwins Folgerungen (1)
Die Produktion von mehr Nachkommen, als die Umwelt tragen kann, führt unter den Individuen einer Population zu einem Kampf ums Überleben, wobei in jeder Generation nur ein Bruchteil des Nachwuchses überlebt.
EvoLab@SGH Martin Reiche, 2005 14
Darwins Beobachtungen (4+5)
Die Individuen einer Population variieren enorm in ihren Merkmalen; keine zwei Individuen sind exakt gleich.
Ein Großteil dieser Variabilität ist erblich.
EvoLab@SGH Martin Reiche, 2005 15
Darwins Folgerungen (2)Das Überleben im Existenzkampf beruht nicht auf Zufall, sondern hängt unter anderem von den Erbanlagen der überlebenden Individuen ab.
Die durch ihre ererbten Merkmale am besten an die Umwelt angepassten Individuen hinterlassen wahrscheinlich mehr Nachkommen als weniger gut angepasste.
EvoLab@SGH Martin Reiche, 2005 16
Industriemelanismus
EvoLab@SGH Martin Reiche, 2005 17
Fitnesslandschaft – der eindimensionale Fall (1)
EvoLab@SGH Martin Reiche, 2005 18
Fitnesslandschaft – der eindimensionale Fall (2)
EvoLab@SGH Martin Reiche, 2005 19
Fitnesslandschaft – der zweidimensionale Fall
EvoLab@SGH Martin Reiche, 2005 20
Gib‘ dem Zufall eine Chance!
Erreichte Fitness Anzahl
0 97.702.041
1 2.223.557
2 69.426
3 2.300
4 383
5 0
6 0
7 2.293
8 und größer 0
Summe: 100.000.000
EvoLab@SGH Martin Reiche, 2005 21
Der Evolutions-Algorithmus
Start
Fertig!
Fitness aller 200 Genome bestimmen
maximale Fitness erreicht?
Die 20 besten Genome als Eltern wählen
200 Genome mit zufälligen Regeln
belegen
nein
ja
Durch Kreuzung aus den 20 Eltern 200 neue Genome herstellen
Einige Genome zufällig verändern
Selektion
Reproduktion
Mutation
EvoLab@SGH Martin Reiche, 2005 22
Crossing-Over (1)
a
b
c
Elter 1 Elter 2 Tochter
EvoLab@SGH Martin Reiche, 2005 23
Crossing-Over (2)
Genom 1:
rekombiniert
mit Genom 2: ergibt
Tochter-genom:
EvoLab@SGH Martin Reiche, 2005 24
Mutation
vorher:
nachher:
EvoLab@SGH Martin Reiche, 2005 25
Zwei Arten zu LernenExplizites Lernen Implizites Lernen
umgangssprachlich Auswendiglernen Verstehen
Beispiel TelefonbuchAddition von
Dezimalzahlen
Erfasst die Regelmäßigkeit der Aufgabenstellung
nein ja
Funktioniert auch, wenn keine Regelmäßigkeit vorhanden ist
ja nein
Gelerntes lässt sich auf ähnliche Phänomene übertragen
nein ja
Speicherbedarf wächst mit Lernumfang
ja nein
EvoLab@SGH Martin Reiche, 2005 26
EvoLab und die natürliche Evolution
Natürliche Evolution
EvoLab
Generationenfolge mit Selektion und Mutation
ja ja
Individuen können sich in ihre Umwelt orientieren
ja ja
Wesen der IndividuenMaterieller Körper mit
StoffwechselBitmuster, „Zahlen“
Umwelt Natur Computer
Komplexität der Individuen hoch gering
Evolution hat festes Zielnein
(nicht erkennbar)ja
Individuen interagieren (Wettbewerb, Kooperation)
ja nein
Definition der Fitness komplex einfach