Runtime Analysis of Cartesian Genetic Programming in Evolving Boolean Functions
For researchers in genetic programming and evolutionary computation, this work offers theoretical insights into CGP's runtime behavior, previously only observed empirically, and highlights the impact of selection strategies on efficiency.
This paper provides the first runtime analysis of Cartesian Genetic Programming (CGP) for evolving Boolean functions, proving an asymptotic bound of O(n D^5) for conjunctions with strict selection and O(n D^4) with non-strict selection, while showing exponential time for exclusive disjunction. Experiments confirm that incomplete training sets reduce fitness evaluations while maintaining generalization.
Cartesian Genetic Programming (CGP) is among the practical and popular forms of Genetic Programming as it uses a graph-based representation of programs. This paper presents a first runtime analysis of CGP in evolving Boolean functions using complete training sets. We prove an asymptotic bound $O(n D^5)$ for the expected number of fitness evaluations of CGP to construct a conjunction of $n$ inputs using at most $D \geq n-1$ binary gates, a minimal function set, and even with a strict survival selection. When the non-strict selection is used, the bound is improved to $O(n D^4)$. Our analysis reveals interesting characteristics of CGP induced search, which have been only observed empirically. In particular, enabling the acceptance of equally good solutions, including those with connected gates non-contributing to fitness, can lead to a speedup, and consequently a better asymptotic time bound. In contrast to conjunctions, we also prove a negative result which shows that CGP requires exponential time to evolve an exclusive disjunction. Experiments evolving conjunctions complement our theoretical findings. The use of incomplete training sets is found to further reduce the average number of fitness evaluations while maintaining a good level of generalisation.