Simulated Evolution Demo

This demo is taken from one of the examples in Artificial Life, by Stephen Levy (1992). It demonstrates "simulated evolution", also called the "genetic algorithm."

The demo creates a small population of "creatures", and puts them to a test. Based on how well they do on the test, they survive to reproduce and form a new generation. As repeated generations are produced, you can see how the performance of the creatures improves.

The goal of our creature will be to follow a trail of dots on a grid (the "food".) The more food the creature finds within the time limit, the higher its score.

The creature has a current position on the grid, is pointing in one of four directions, and can take one of four actions. It can step forwards, turn left, turn right, or do nothing. The creature has only one input -- whether or not there is food directly in front of it. Its memory is implemented as a state machine with 32 states.

On each step, the state machine takes the state number plus the food bit for an index into a table of 64 outputs. The output is the new state index and the action (left, right, step or nothing.) This gives a complete "genome" of 64*7 = 448 bits.

The table in the figure shows the simplest genome that does anything useful. The rules of the machine which are not used are greyed. Starting in state 0, if there's no food in front of it, the creature turns right. If there is food, it takes a step. It remains in state 0 in both cases.

Evolution

We start the simulation with a population of random genomes. We rate them all against the trail, running the state machine for Steps steps (the default is 200.) After rating them, we take the creatures at random in pairs. Based on the Compete parameter (default is 75%), we take the best of the pair and throw away the worst. If Compete were 100%, all creatures are subjected to this test. If Compete were 50%, only half of them would be compared.

The remaining population is bred and mutated. Breeding two creatures consists of picking a random number N from 0 to 63. The child is created by taking the first N rules of one parent, and the last 64-N rules of the other parent. The percentage of the population that breeds is controlled by Breed and defaults to 75%.

Finally, we mutate some of the children. We do this by randomly inverting a bit in the child genome. The Mutate parameter controls the odds that a child will be a mutant, and defaults to 1 in 200.

Competition, breeding and mutation create a new generation. We rate all of the new creatures against the trail, and the process repeats. As new generations are produced, the creatures that do poorly on the trail die off, and versions that do well spread through the population.

The Demo

To run the demo, go here and hit the "Next Gen" button halfway down on the right, to create new generations. Requires Java 1.4 or better. Read on for an explanation of the program and controls.

Controls

There are numerous controls on the demo page. At the top, see the trail and table for the sample creature. The sample will default to the best creature in the current generation. By hitting the Step and Reset buttons, you can walk the sample creature through the trail, to see how it works. Hit Best or Random to select creatures from the current population.

To control the population, hit the New and Next Gen buttons. At the bottom of the page, you will see a graph of the current population statistics. The left graph shows the best score, average score, and the population diversity. The diversity is the number of functionally different "strains" of creature as a percentage of the population. At the beginning, all creatures are random, and almost all unique, so the percentage is nearly 100%. As improved creatures start to dominate the population, the diversity will drop.

The right graph shows the number of creatures for each range of scores. In the beginning, you will have an exponential distribution mostly around 0, since the random creatures don't get very far along the trail. As the population improves, low-scoring creatures die off and high-scoring ones start to dominate, and the distribution will shift.

Once you have worked through the simulation several times with the default parameters, you can change these to see the effects on population evolution. When you hit New, you have the chance to change the population size. The Steps dropdown allows you to increase the number of steps allowed when the creature is tested against the trail. The Breed, Compete and Mutate dropdowns allow you to control these parameters.

Finally, you can use the Trail Locked checkbox to unlock the trail and redraw it with the mouse. The left button sets the trail, and the right button erases it. Lock the trail again when you are done, to keep casual clicks on the window from altering it. Hit the Default button to restore the original trail.

Observations

First, note that in the default population of 10,000 creatures, the best randomly created creature actually follows nearly half the trail. Hit the Random button to see other samples, and you will realize that few creatures manage this.

Second, note that as you hit the Next Gen button, the average score (green dots on the bottom-left graph) will steadily improve, but the diversity (red dots) will rapidly decline. This is because the superior creatures are rapidly spreading through the population.

You will see the score of the best creature in each generation advance and then retreat. This is because of the way reproduction is implemented. Only random pairs of the creatures compete and reproduce. If a creature is not selected for competition, it will die out. If it is selected for reproduction, it's offspring may score worse than either parent. So the best creature in a generation does not necessarily survive.

Note that the 10,000 creature population is not large enough to reliably produce a creature which runs the entire trail. After 30 or 40 generations, the diversity will crash down to only a few dozen strains. This is not enough for really new creatures to be produced, and so evolution will stagnate. In biological terms, the population is overspecialized and inbred. Create new generations several times though, and you may get one that solves the entire trail.

As you pick random creatures in a generation, you may notice that although the bold rules of the genome are identical, the greyed ones vary randomly. This is because only the bold rules are actually used, and are subject to evolution. The grey rules are not used, so they are not selected against. This is equivalent to "junk DNA" in a biological organism -- portions of the DNA that are never expressed as proteins. Over 90% of human DNA is thought to be "junk."

Play with the parameters to get a feel for how they affect evolution. Surprisingly, in this demo, mutation hardly matters. You can turn it up to odds of 1 in 2, and still only see a bit of noise at the low end of the distribution. This represents the creation of many low-scoring mutants, and although it increases the number of strains, it has little effect on the course of evolution.

Increasing competition spreads winners through the population more quickly, but at the cost of diversity. Too much competition will cause the population to stagnate more quickly. Too little competition keeps winners from having any reproductive advantage and slows evolution. At 50% competition, the average does not improve at all (there's is no reproductive advantage to being a winner.) Similarly, lots of breeding increases variation, but since breeding kills one parent, it reduces the chances of survival for a winner. But too little breeding causes stagnation.

Increasing population size increases the odds that a winning creature will be created. Decreasing population tends to cause a collapse of diversity more quickly, resulting in stagnation. More steps will allow less efficient creatures to still have a chance at scoring. 200 makes for faster testing of creatures, but it is difficult to find a creature that can eat all 89 food spots in 200 state machine steps. 300 is more realistic if your creatures are getting close to solving the entire trail.

Finally, after you've evolved a good population, try changing the trail on them. If you make a large change, the scores will drop dramatically. These creatures are very specialized for their environment, and are not general trail followers! Scores will recover quickly as new generations adapt to the new trail.

The shape of the trail does cause one interesting change in the populations. If the early parts of the trail are completely connected (as in the default), then there is a simple two-state solution that follows much of the trail. This is the creature shown in the sample table above. It just turns until it has food in front of it, then steps forward. Since this solution is so small, it will breed true nearly all the time (the random number used in breeding would have to split the two states. Any other number will not affect it.) In the early stages, that gives this simple solution a reproductive advantage. It can completely dominate a small population before any more interesting solutions arise. Break the trail in its early sections to see what effect this has on the course of evolution.

Run Demo

To run the demo, go here. Requires Java 1.4 or better.

by Michael Goodfellow.
For more, see Free The Memes!
    Home
Projects
Email Me

Mike's Newspaper
Writings
Projects
Sea of Memes
Photos