Evolutionary dynamics of structured genetic algorithms

People: Xin Wang and Felix Hol

The spatial structure of an evolving (meta)population can have profound effects on its evolutionary dynamics. We investigate and quantify the ability of populations with different population structures to evolve.

The model

The computational model we use for our study extends on work by Mitchell & Crutchfield (and coworkers) in which a genetic algorithm (GA) evolves a population of cellular automata (CA) rules to perform a density classification task. The CAs are one-dimensional binary-state cellular automata and have neighborhood size (radius) r=3. The lattice starts out with L cells that are either 0 or 1. At each time step every cell examines its local neighborhood and updates its state according to the CA rule. Crutchfield and Mitchell have defined a simple computational task in which the CA needs to decide whether the lattice initially contains more or less than 50% 1's. The CA answers this question by settling to all 0's when the majority of the initial condition (IC) is 0 and all 1's when the IC consists of 1's for more than half.

The number of possible CA rules with r=3, is 2^2r+1 (=2¹²⁸); this number is far too large for an exhaustive search for the best CA rule. We will use genetic algorithms (GA) to evolve CA rules to perform the density classification task. These GAs will have will have different spatial structures such as a well mixed CA population, CAs distributed on lattices and CAs as nodes in small world/scale free networks. We are interested in a) what kind of GA gives the best performance, in other words, shows that highest evolvability, and, b) given the population structure that comes out best, can we optimize this structure in terms of robustness, evolvability and speed. We aim to investigate (b) by using dynamic population structures.

References

• Crutchfield and Mitchell PNAS 1995 [1]
• Mitchell et al Physica D [2]
• Wrigth 1932 [3]