Transcript slides - Stefano Nichele

1
Cellular automata modeling two species of gastropod
Chris King, University of Auckland - MATHS 745 2009
GECCO 2011 Graduate Student Workshop
”Discrete Dynamics of Cellular Machines:
Specification and Interpretation”
Stefano Nichele
2011, July 12th
Stefano Nichele, 2011
2
Agenda
• Introduction: Cellular Automata
• Formal Definition
(CA are simple!)
• CA Classes
• Edge of Chaos
• Research Questions
• Experimental Setup
• Preliminary Results
• Conclusion and Future Work
• Bibliography
(CA are complex!)
3
Introduction
•
Motivation: using biological inspiration from evolution and development
towards hardware capable of unconventional computation
•
Artificial Developmental Systems: analyzed and evaluated by viewing
the system as a discrete dynamic system. The development process is
treated as series of discrete events, each representing a point in time
on the developmental path from zygote to multi-cellular organism
•
Which theoretical and experimental approaches can be used to find
methods for the specification of input data and interpretation of the
discrete dynamics of cellular machines?
4
von Neumann architecture
• 1 complex processor
• tasks executed sequentially
cellular computing
•
•
•
•
•
myriad of small and unreliable parts: cells
simple elements governed by local rules
cells have no global view – no central controller
local interactions with neighbours
global behavior: emergent
Szedő Gábor, MBE_MIT, 2000
5
Cellular Automaton
•
Countable array of discrete cells i
•
Discrete-time update rule Φ
(operating in parallel on local neighborhoods
of a given radius r)
•
Alphabet: σit ∈ {0, 1,..., k- 1 } ≡ A
•
Update function: σit + 1 = Φ(σi - rt , …., σi + rt)
•
State of CA at time t: st ∈ AN (N=number of cells)
•
Global update Φ: AN → AN
•
st = Φ s t - 1
6
Example 1 - Conway’s Game of Life
Wikipedia, Conway’s Game of Life, 26/05/2011
7
Example 2 – 2nd law of thermodynamics
• From ordered and simple initial conditions, according to the
second law of thermodynamics, the entropy of a system
(disorder and randomness) increases and irreversibility is quite
probable (but not impossible, as stated by Poincaré’s theorem of
reversibility)
8
Wolfram, 1984
Class 1
Evolution ”dies”
Irreversible
Outcome is
determined with
probability 1
9
Class 2
Fixed point or
periodic cycle
Some parts of initial
state are filtered-out
and others are
propagated forever
10
Class 3
Chaotic behavior
Completely reversible
Not random, not noise
Reversible if and only if, for every current
configuration of the CA, there is exactly
one past configuration
11
Class 4
Complex localized
structures
Non-reversible
The current site values could have arisen
from more than one previous configuration
Only class with nontrivial automata
Chaotic behavior is considered to be trivial
because it is not random and thereby it is
completely reversible
12
Developmental System
• A CA can be considered as a developmental system, in which
an organism can develop (e.g. grow) from a zygote to a multicellular organism (phenotype) according to specific local rules,
represented by a genome (genotype).
• The genome specifications and the gene regulatory information
control the cells’ growth and differentiation.
• The behavior of the CA is represented by the emergent
phenotype, which is subject to shape and size modification,
along the developmental process.
13
Research Questions
1. Is there any relationship between computation performed by
CA and their regulatory input and cellular actions?
2. Is it possible to develop an organism of a given complexity?
3. Can we predict the developmental behavior of the phenotype
from the genotype composition?
Investigation of the correlations between Cellular Automata
(CA) behavior (development process) and cellular regulative
properties (genome information)
14
Computation at the Edge of Chaos
A region in the CA rule space where there is a phase transition
between ordered and chaotic behavioral regimes (Langton, 1990)
Developmental lambda:
q
  1
tot
  1
1
k
15
Experimental Setup - 1
• Minimalistic developmental system
• 3 cell types (type 0: quiescent, type 1
and type 2 for multicellularity)
• All possible 35 = 243 regulatory input
combinations are represented in a
development table
• 2D CA, von Neumann neighborhood
16
Experimental Setup - 2
• Investigation in all the λ space
• Possible correlation between
– properties of the developmental mapping
– behavior of the automata
•
•
•
•
•
developmental complexity
structural complexity
CA attractor length
CA trajectory length
CA transient length.
17
Preliminary Results
experiments are not finalized
3x3 CA
early results show a
correlation between genomic
composition and
developmental properties
State space:
3x3 = 3^9 = 19 683
6x6 = 3^36 = 1,5 x 10 ^ 17
18
Conclusion and Future Work
• Now running 4 by 4, 5 by 5 and 6 by 6 (Tufte and
Nichele, 2011 – IN PRESS).
• Promising results: λ can be an indicator of how the
organism will develop.
• Other complexity measures? Growth rate, change
rate, structural complexity.
• λ can be used to drive evolution in desired parts of
the search space.
19
Wolfram, 2000
“This mollusk is essentially running a
biological software program.
That program appears to be very
complex.
But once you understand it, it's actually
very simple.”
20
Bibliography
[1] C. Langton. Computation at the Edge of Chaos: Phase Transitions and Emergent Computation. Physica D Volume 42 (1990) pp. 12-37
[2] S. Wolfram. Universality and Complexity in Cellular Automata. Physica D Volume 10 Issue 1-2 (1984) pp. 1-35
[3] N. Packard. Adaptation Toward the Edge of Chaos. Dynamic Patterns in Complex Systems. Kelso, Mandell, Shlesinger, World Scientific,
Singapore Press (1988), ISBN 9971-50-485-5 pp. 293-301
[4] M. Mitchell, J. Crutchfield, P. Hraber. Dynamics, Computation and the “Edge of Chaos”: A Re-Examination. Santa Fe Institute Working
Paper 93-06-040, Complexity: Metaphors, Models and Reality, Addison-Wesley (1994) pp.497-513
[5] J. Crutchfield and K. Young. Computation at the Onset of Chaos. Complexity, Entropy and Physics of Information, Addison-Wesley (1989)
[6] J. Miller. Evolving a Self-Repairing, Self-Regulating, French Flag Organism. Gecco 2004. Springer-Verlag Lecture Notes in Computer
Science 3102, (2004) pp. 129-139
[7] G. Tufte and P. Haddow. Extending Artificial Development: Exploiting Environmental Information for the Achievement of Phenotypic
Plasticity. Springer Verlag Berlin Heidelberg, ICES 2007 – LNCS 4684, (2007) pp. 297-308
[8] S. Ulam. Los Alamos National Laboratory 1909-1984. Los Alamos: Los Alamos Science. Vol. 15 special issue, (1987) pp. 1-318
[9] J. Von Neumann. Theory and Organization of complicated automata. A. W. Burks, (1949) pp. 29-87 [2, part one]. Based on transcript of
lectures delivered at the University of Illinois in December 1949.
[10] J. H. Holland. Genetic Algorithms and Adaptation. Technical Report #34 Univ. Michigan, Cognitive Science Department (1981)
[11] E. Berlekamp, J. H. Conway, R. Guy. Winning ways for your mathematical plays. Academic Press, New York, NY (1982)
[12] M. Sipper, The Emergence of Cellular Computing, Computer, vol. 32, no. 7, (1999) pp. 18-26, doi:10.1109/2.774914
[13] M. Mitchell, P. T. Hraber and J. T. Crutchfield. Revisiting the Edge of Chaos: Evolving Cellular Automata to Perform Computation. Complex
Systems, vol. 7, (1993) pp. 89-130
[14] A. Turing. On computable numbers, with an application to the Entscheidungsproblem, Proceedings of the London Mathematical Society,
Series 2, 42, (1936) pp 230–265
[15] S. Wolfram. A New Kind of Science. Wolfram Media Inc, (2002), 1197pages – ISBN 1-57955-008-8
[16] G. Tufte and S. Nichele . On the Correlation Between Developmental Diversity and Genomic Composition, to appear in GECCO ’11:
Proceedings of the 20th annual conference on Genetic and evolutionary computation, New York, NY, USA (2011). ACM. (IN PRESS)
21