Breeding Gliders
with Cellular Automata
Breed a population of CA's to be Closer to Langton's "Edge of Chaos",
and Gliders will naturally emerge.
Check out this program (download below). It animates many different kinds of
cellular automata (CA) rules, and let's you breed a population of them to become
increasingly complex Life universes, analogous to Conway's Game of Life. You
can breed them such that coherent space-time structures (gliders) emerge. This
breeder uses an experimental interface, in which evolutionary dynamics goes
on in the background and you simply judge various CA's. As you judge them, the
population evolves according to a Darwinian fitness ranking that you affect
by your judgements.
The idea for this was inspired by Kirk Israel, through one of our conversations,
while I was teaching a class at Tufts University in 1995.
BACKGROUND
For some background on Cellular Automata, check out the research of Chris Langton
(Alife II proceedings, 1992). I seem to recall Karl Sims wrote something on
evolving CA's (a SIGGRAPH paper, I'll look it up for next update of this page).
Also see a BEAUTIFUL treatment of many classic CA's in... John Walker/Rudy Rucker's
CA's. Also, a site with info on CA's,
edited by Howard Gutowitz, from Artificial Life Online , has a lot
of info as well. A good book to get is "Cellular Automata Machines", by Toffoli
and Margolus, 1987, MIT Press). Also look at Jean-Claude Heudin's
overview of CA's in Virtual Worlds . Also,
Poundstone's "The Recursive Universe" is a good book, for a nice intro on Conway's
Life. These are of course just a few examples of references.
NOTE:
This is free software. It is for educational and research purposes only.There
are no viruses here. It downloads very fast. It runs on Windows or NT *(This
program will not evolve the likeness of Elvis)
DOWNLOAD
NOW
WHAT YOU DO:
Simply watch the CA as it animates and judge it as either bad, medium, or good.
After you judge it, another CA will animate. Judge that one. Repeat this process
many times until you are happy with the results. When you hit upon a CA with
gliders you really like, save it as a file (the interface is simple at this
point, and will be enhanced later).
Many of the CA's you see will die quickly, and others will "freeze up", after
about 10 steps. These will automatically be judged as bad, and thrown out. Some
will be very chaotic. After a period allowing it to settle, CA's that are still
too chaotic will be judged bad and thrown out as well. The "status" of the CA
will be displayed as either DEAD, FROZEN, CHAOTIC, or OK. If the CA comes out
OK, and if you like it, give it a good or medium judgement. It will take several
minutes , but gradually, more interesting ones will appear, and bad ones will
occur less frequently. Make sure you judge some of them as good. Remember: your
judgements provide the Darwinian fitness values that help guide the direction
of evolution. The process continues indefinately.
HOW DOES THE CA ACTUALLY WORK?
The implementation I have made works as follows: CA's are finite-state automata
occuring at the sites of a 2D lattice. The lattice wraps around to avoid boundary
issues. Each cell (a square at a lattice site) can have one of many states (up
to 8). As the clock ticks, each cell changes its state, depending on its current
state and the various states of its eight neighbors. This CA uses the counting
scheme: each cell counts the number of neighbors of each of the states. Based
on these numbers, it uses a transition rule to take on a new state. Similar
to Conway's Game of Life, this CA considers it's own state in addition to the
counts of neighbor states. In fact, in the large genetic space of possible CA's
evolvable here, Conway's Life exists! But don't count on stumbling upon it any
time soon!
HOW DOES IT EVOLVE?
There are a number of possible transition rules for determining the dynamics
of a CA. Here, there are 50 rules. They are a population of rules, simply called
"CA's" for convenience. At the start, the population of CA's is randomized.
Most of these, at the start, will be either too chaotic, too orderly, or just
plain uninteresting. But some will have potential.
FITNESS
At the start, each CA is given an average fitness value (a value of 0.5, in
the range of 0.0-1.0). When you judge a CA as bad, medium, or good, you are
assigning a fitness of 0.0, 0.5, or 1.0 to the CA. Also, at every breeding cycle,
all the fitness values decay by a tiny amount, such as: (fitness * 0.99). In
doing so, the fitness of older CA's are able to slowly fade into the past as
new CA's are introduced into the population. After a while, the fitness profile
will vary quite a bit with values ranging from 0.0 to 1.0, and many values inbetween
(not just 0.5, because of the decaying of previous medium and good judgements).
The purpose of this is psychological: you, the breeder, are likely to favor
your more recent CA's than the ones of the remote past, and so you would rather
not have some old CA that was once the best (but is now not the best) to stay
as a strong influence. read on for more info on mating, and this should become
more clear.
GENES
CA's can mate with each other to make offspring CA's which inherit the genes
of the parent CA's. A CA's genes are what determine the transition rules for
each of its cells. For a given CA, the exact same rule is used on each cell,
thus, genetic variety does not occur among cells of one CA, but rather among
different CA's. The genes determine things like which states a cell will be
in when it checks its neighbor count, which states it counts, and how many neigbors
of a specific state it takes for the cell to change its own state. Other genes
determine the new state the cell takes on. As you can imagine, there are many
possible permutations of transition rules possible with only a handful of genes.
I have merely scratched the surface. Other folks have devised much larger genetic
search spaces than this one. This is something I will be exploring, so as to
make many more CA's possible. I am, however, just as interested in making this
a real-time appplication, which is fun and educational, so I am considering
ways to keep the CA running fast on average computers, and on having relatively
fast evolutionary convergence.
HOW DO THE CA's MATE?
While you are judging CA's, some of them are having sex in the background, behind
the scenes. (no need for you to see this - it is not interesting or arousing
at all). Two CA's mate per breeding cycle. Every time you make a judgement,
two random CA's mate and have one offspring. In fact each CA you judge is the
offspring of two parent CA's who have just mated. The CA's that mate are statistically
more fit than the rest, meaning, they have been given good fitness values by
you, at some point. Also, for every breeding cycle, one CA is killed off to
make room for the new offspring. The one that is killed off is the one with
the lowest fitness value. Since the more fit CA's are doing the mating, their
offspring have a better chance of looking interesting to you.
AVOID TOO MUCH CHAOS, AVOID TOO MUCH ORDER
On either side of Langton's "Edge of Chaos", where the truly stylin' CA's hang
out, is order, on one side, and chaos, on the other. Some CA's you will notice
are very chaotic and random-looking, while others will settle into simple periodicity,
or simply die. My intuition is that the CA's that are most attractive to us
are the one's that naturally lie on the cusp, the transition between order and
chaos. One thing's for sure, this is where the most interesting gliders are.
(c) copyright 2000, Jeffrey Ventrella
