Exact Results From A Coarse Grained Formulation Of The Dynamics Of Variable-length Genetic Algorithms
Christopher Rhodes Stephens, Riccardo Poli, Alden H. Wright, Jonathan E. Rowe · 2002
We consider the dynamics of variable-length Genetic Algorithms (GAs) with strings of length N ≤ Nm using a recently developed exact, coarse-grained formulation where the relevant coarse-grained degrees of freedom are block schemata. We derive an exact formal solution of the equations showing how a hierarchical structure in time and degree of coarse-graining emerges, the effect of recombination being to successively form more fine-grained objects from their more coarse-grained building blocks, where in this case the building blocks can come from strings of different lengths. We examine the limit distributions of the dynamics in the case of a flat fitness landscape, one-point homologous crossover and no mutation. By taking advantage of the existence of a set of conserved quantities in the dynamics we provide exact solutions for the cases Nm = 2, 3 and use these to investigate the phenomenon of inter-length-class allele diffusion. We also study the general case showing what exact results may be easily derived using our particular coarse-grained formulation.