Graph based genetic algorithms
Daniel Ashlock, Mark D. Smucker, J. Walker · 2003
Genetic algorithms use crossover to blend pairs of putative solutions to a problem in hopes of creating novel solutions. At its best, crossover takes distinct good features from each of the two structures involved in the crossover. This creates a conflict: progress results from crossing over distinct types of structures but such crossover produces new structures that are like their parents, reducing the diversity on which successful crossover depends. We describe and test genetic algorithms that use a combinatorial graph to limit choice of crossover partner. This gives a computationally cheap method of picking a level of tradeoff between having heterogeneous crossover (crossover between genetically distinct individuals) and preservation of population diversity. Statistics for estimating the degree to which a given graphical population structure favors population diversity or heterogeneous crossover are given. These statistics are computed for ten example graphs. These graphs are then used as population structures for genetic algorithms of three test problems: a trivial string evolver, the plus-one-recall-store (PORS) test suite for genetic programming (D. Ashlock and M. Joenks, 1998; D. Ashlock and J.L. Lathrop, 1998), and simple string controllers for Astro Teller's Tartarus problem (A. Teller, 1994).