Analysis of Cartesian Genetic Programming’s Evolutionary Mechanisms

Understanding how search operators interact with solution representation is a critical step to improving search. In Cartesian genetic programming (CGP), and genetic programming (GP) in general, the complex genotype to phenotype map makes achieving this understanding a challenge. By examining aspects such as tuned parameter values, the search quality of CGP variants at different problem difficulties, node behavior, and offspring replacement properties we seek to better understand the characteristics of CGP search. Our focus is two-fold: creating methods to prevent wasted CGP evaluations (skip, accumulate, and single) and creating methods to overcome CGPs search limitations imposed by genome ordering (reorder and DAG). Our results on Boolean problems show that CGP evolves genomes that are highly inactive, very redundant, and full of seemingly useless constants. On some tested problems we found that less than 1% of the genome was actually required to encode the evolved solution. Furthermore, traditional CGP ordering results in large portions of the genome that are never used by any ancestor of the evolved solution. Reorder and DAG allow evolution to utilize the entire genome. More generally, our results suggest that skip-reorder and single-reorder are most likely to solve hard problems using the least number of evaluations and the least amount of time while better avoiding degenerate behavior.