Transcript PPT - Artis

Complex Genetic Evolution
of Self-Replicating Loops
Chris Salzberg1,2 Antony Antony3 Hiroki Sayama1
1 University
of Electro-Communications, Japan
2 University of Tokyo, Japan
3 University of Amsterdam, the Netherlands
[email protected]
Summary

We re-examined the evolutionary
dynamics of self-replicating loops on CA,
by using new tools for complete genetic
identification and genealogy tracing

We found in the loop populations:
1.
2.
3.
Diversities in macro-scale morphologies and
mutational biases
Genetic adaptation
Genetic diversification and continuing
exploration
2
Background: CA-based Alife

Universal constructor (Von Neumann 1966;
Codd 1968; Takahashi et al. 1990;
Pesavento 1995)

Self-replicating loops (Langton 1984; Byl
1989; Reggia et al. 1993)

Self-inspecting loops/worms (Ibanez et al.
1995; Morita et al. 1995, 1996)

Self-replicating loops with additional
capabilities of construction/computation
(Tempesti 1995; Perrier et al. 1996; Chou et
al. 1998)

Spontaneous emergence and evolution of
self-replicators (Lohn et al. 1995; Chou et al.
1997; Sayama 1998, 2000, 2003; Salzberg
et al. 2003, 2004; Suzuki et al. 2003, 2004)
3
Supposedly Limited Evolutionary
Dynamics in CA

McMullin (2000):
“[SR loop] does not embody anything like a
general constructive automaton and therefore
has little or no evolutionary potential.”

Suzuki et al. (2003):
“Though there are many other variations of CA
models for self-replication, their evolvability
does not differ very much.”
4
Question

Did we truly understand what was going
on in this seemingly simple dynamics of
our CA-based evolutionary systems?

We didn’t know we didn’t, until we have
developed the formal framework and the
sophisticated tools for detailed analysis
and visualization for those systems.
5
Subject: Evoloop



An evolvable SR
loop by Sayama
(1999) constructed
on nine-state fiveneighbor fully
deterministic CA
Robust statetransition rules give
rise to evolutionary
behavior
Mutation/selection
mechanisms are
totally emergent 6
New Tools for Detailed Analysis

At every birth, the newborn loop’s genotype &
phenotype and its genealogical information is
detected and recorded in an event-driven fashion
phenotype
8
8
genotype
G

G
G
G C G C G
T
T
G CC CC G
Each genotype-phenotype pair is indexed in the
Species Database
7
Observation (1):
Diversities in Macro-Scale
Morphologies and Mutational
Biases
8
Huge Genetic State-Space

Permutation of genes (G, T) and core
states (C) under constraints estimates the
number of viable genotypes to be 2n-2
n-2
Size n
# of species
Size n
# of species
Size n
# of species
4
15
9
11,440
14
9,657,700
5
56
10
43,758
15
37,442,160
6
210
11
167,960
16
145,422,675
7
792
12
646,646
17
565,722,720
8
3,003
13
2,496,144
18 2,203,961,430
9
Diversity in Growth Patterns (size-4)
10
Diversity in Growth Patterns (size-6)
11
Diversity in Mutational Biases (size-6)
(new result not included in paper)
12
Observation (2):
Genetic Adaptation
13
Two Measures of (Possible)
Fitness

Survival rate (sustainability in competition):
— Characterized
by an average of relative
population ratios of a species after a given
period of time in competition with another
species

Colony density index (growth speed):
— Characterized
by a quadratic coefficient of a
parabola fitted to the population growth curve
of each species in an infinite domain
14
Variety and Correlation (size-4)
15
Evolution in vivo
(starting from size-8)
16
Evolution Optimizes “Fitness”
Evolutionary transition
actually observed in
the previous slide
17
Observation (3):
Genetic Diversification and
Continuing Exploration
18
Non-Mutable Subsequences
GGGGCGC GCCTCCTG G



Certain subsequences are found non-mutable:
G{C*}T{C*}TG
A long non-mutable sub-sequence injected to
ancestor causes a relatively large lower bound
of viable sizes upon its descendants, a reduced
size-based selection pressure, and a highly
biased mutational tendency to larger species
Such “GMO” loops show long-lasting
evolutionary exploration processes
19
control
with long non-mutable subsequences
with subsequences + hostile environment
(new result not included in paper)
20
Conclusions

Huge diversity, non-trivial genetic
adaptation and diversification unveiled in
the evoloop system

Hierarchical emergence demonstrated,
where macro-scale evolutionary changes
of populations arises from micro-scale
interactions between elements much
smaller than individual replicators,
traversing multiple scales
21
References & Acks

Salzberg, C. (2003) Emergent Evolutionary Dynamics of SelfReproducing Cellular Automata. M.Sc. Thesis. Universiteit van
Amsterdam, the Netherlands.

Salzberg, C., Antony, A. & Sayama, H. Visualizing evolutionary
dynamics of self-replicators: A graph-based approach. Artificial
Life, in press.

Sayama, H. The SDSR loop / Evoloop Homepage.
http://complex.hc.uec.ac.jp/sayama/sdsr/

Antony, A. & Salzberg, C. The Artis Project Homepage.
http://artis.phenome.org/
This work is supported in part by the Hayao Nakayama Foundation for
Science, Technology & Culture, and the International Information Science
Foundation, Japan.
22