Complexity and Cartesian Genetic Programming

Citation

Woodward J (2005) Complexity and Cartesian Genetic Programming. In: Mirkin B & Magoulas G (eds.) UK CI 2005: Proceedings of the 2005 UK Workshop on Computational Intelligence. UKCI 2005: The 5th annual UK Workshop on Computational Intelligence -, London, 05.09.2005-07.09.2005. London: Birkbeck University of London, pp. 273-280. http://www.dcs.bbk.ac.uk/ukci/ukci05proceedings.pdf

Abstract
Genetic Programming (GP)  often uses a tree form of a graph to represent solutions in a search space. An extension to this representation, Automatically Defined Functions (ADFs)  is to allow the ability to express modules. In a previous paper we proved that the complexity of a function is independent of the primitive sets (function set and terminal set) if the representation has the ability to express modules. This is essentially due to the fact that if a representation can express modules, then it can effectively define its own primitives at a constant cost.