Evolutionary Computation and Artificial Life (202-1-5171), Semester A, 2004-2005

Exercise 5

Implement a genetic algorithm to evolve two-dimensional uniform cellular automata that solve the density task. That is, the 2d grid must converge to all 0s or all 1s in accordance with time step zero's majority of 0s or 1s, respectively. Just like we saw in class.

Use a Moore neighborhood (9 neighbors), which means the genome encodes a rule table of 512 bits: leftmost bit encodes the next state of neighborhood 000000000, until rightmost bit that encodes the next state of neighborhood 111111111.

Fitness is computed over a few dozen (or hundreds) of random initial configurations. The random initial configurations are to be drawn from a biased (uniform) distribution: first pick random number between [0,1], then use this value as the probability for 1s in configuration. Try two fitness values: 1) number of cells in grid in correct state at final time step, averaged over all (random) configurations, and 2) credit given only if entire grid at final time step is in correct configuration (all 0s or all 1s), and fitness = number of correct final grids. First fitness value gives credit to partial solutions, second does not. See which works better.

Submit:
1) Java program. (WITH documentation, although this should be redundant... Code must always be documented.)
2) Plot of fitness versus time of three runs for three different-sized CAs: 10x10, 20x20, 30x30.
3) Behavior of your evolved CAs on random initial configurations, shown as time slices, i.e., pictures of 2D grids at various times during the CA's computation..
4) Any improvements/tricks you've invented.
5) Any interesting conclusions you've reached.