A Probabilistic Model of Size Drift

title = "A Probabilistic Model of Size Drift",

booktitle = "Genetic Programming Theory and Practice",

publisher = "Kluwer",

year = "2003",

editor = "Rick L. Riolo and Bill Worzel",

chapter = "8",

pages = "119--135",

keywords = "genetic algorithms, genetic programming, Evolutionary algorithms with variable-size structures, complexity drift, code growth, Bloat, introns, rooted-tree schemata, effective and noneffective code, fitness-size model, small size effect, diffusion, fitness landscapes",

ISBN = "1-4020-7581-2",

URL = "

http://www.springer.com/computer/ai/book/978-1-4020-7581-0",

DOI = "

doi:10.1007/978-1-4419-8983-3_8",

abstract = "Drift towards growing size of genotypes is one outstanding and constantly disputed invariant in an overwhelming number of applications of evolutionary algorithms with variable-size structures. In contrast to previous work to reveal its fundamentals, we probabilistically analyse genotype growth by building on the idea of a 'representation-less' model by Banzhaf and Langdon. Our model, called the fitness-size model, corresponds to a simple evolutionary algorithm using overproduction selection and mutation working on abstract objects retaining only fitness and size information.

The probalistic analysis offer some surprises counter to present credence. The analysis predicts that average effective and noneffective lengths (and thus overall size) tend to be invariant over time. The same is true for the variance of the effective length. In contrast, the variance of the noneffective size features increases linearly in time, and its variation shows the trademark of a diffusion process.Drift to increasing size manifest s if search biases favour boundary conditions. We present experimental results with both the implementation of the theoretical model and a standard genetic programming algorithm. Statistical results with the two implementations are similar and fit the theoretical predictions.",

notes = "Part of \cite{RioloWorzel:2003}",