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.
The idea for this was inspired by
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...
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)
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.