Computational Complexity Analysis of Genetic Programming - Initial Results and Future Directions
Frank Neumann, Una-May O’Reilly and Markus Wagner
The computational complexity analysis of evolutionary algorithms
working on binary strings has significantly increased the rigorous
understanding on how these types of algorithm work. Similar results
on the computational complexity of genetic programming would fill
an important theoretic gap. They would significantly increase the
theoretical understanding on how and why genetic programming algo-
rithms work and indicate, in a rigorous manner, how design choices
of algorithm components impact its success. We summarize initial
computational complexity results for simple tree-based genetic
programming and point out directions for future research.