- author = "John R. Woodward",
- title = "Complexity and Cartesian Genetic Programming",
- editor = "Pierre Collet and Marco Tomassini and Marc Ebner and Steven Gustafson and Anik\'o Ek\'art",
- booktitle = "Proceedings of the 9th European Conference on Genetic Programming",
- publisher = "Springer",
- series = "Lecture Notes in Computer Science",
- volume = "3905",
- year = "2006",
- address = "Budapest, Hungary",
- month = "10 - 12 " # apr,
- organisation = "EvoNet",
- keywords = "genetic algorithms, genetic programming, Cartesian Genetic Programming",
- ISBN = "3-540-33143-3",
- pages = "260--269",
-
DOI = "
doi:10.1007/11729976_23",
- bibsource = "DBLP, http://dblp.uni-trier.de",
-
abstract = "Genetic Programming (GP) \cite{banzhaf:1997:book}
often uses a tree form of a graph to represent
solutions. An extension to this representation,
Automatically Defined Functions (ADFs) is to allow the
ability to express modules. In Woodward we proved that
the complexity of a function is independent of the
primitive set (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.
Cartesian Genetic Programming (CGP) is a relative new type of representation used in Evolutionary Computation (EC), and differs from the tree based representation in that outputs from previous computations can be reused. This is achieved by representing programs as directed acyclic graphs (DAGs), rather than as trees. Thus computations from subtrees can be reused to reduce the complexity of a function. We prove an analogous result to that in Woodward the complexity of a function using a (Cartesian Program) CP representation is independent of the terminal set (up to an additive constant), provided the different terminal sets can both be simulated. This is essentially due to the fact that if a representation can express Automatic Reused Outputs \cite{miller:2000:CGP}, then it can effectively define its own terminals at a constant cost.",
- notes = "Part of \cite{collet:2006:GP} EuroGP'2006 held in conjunction with EvoCOP2006 and EvoWorkshops2006",
