Methods for genealogy and building block analysis in genetic programming

Genetic programming gradually assembles high-level structures from low-level entities or building blocks. This chapter describes methods for investigating emergent phenomena in genetic programming by looking at a population’s collective behavior. It details how these methods can be used to trace genotypic changes across lineages and genealogies. Part of the methodology, we present an algorithm for decomposing arbitrary subtrees from the population to their inherited parts, picking up the changes performed by either crossover or mutation across ancestries. This powerful tool creates new possibilities for future theoretical investigations on evolutionary algorithm behavior concerning building blocks and fitness landscape analysis.