- author = "John R. Woodward",
- title = "Complexity and Cartesian Genetic Programming",
- booktitle = "The 5th annual UK Workshop on Computational Intelligence",
- year = "2005",
- editor = "Boris Mirkin and George Magoulas",
- pages = "273--280",
- address = "London",
- month = "5-7 " # sep,
- email = "jrw@cs.bham.ac.uk",
- keywords = "genetic algorithms, genetic programming, Cartesian Genetic Programming",
- notonline = "http://www.cs.bham.ac.uk/~jrw/publications/",
-
URL = "
http://www.dcs.bbk.ac.uk/ukci05/ukci05proceedings.pdf",
- size = "8 pages",
-
abstract = "Genetic Programming (GP) \cite{banzhaf:1997:book}
often uses a tree form of a graph to represent
solutions in a search space. An extension to this
representation, Automatically Defined Functions (ADFs)
\cite{banzhaf:1997:book} is to allow the ability to
express modules. In \cite{woodward:Modularity} 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.
Cartesian Genetic Programming (CGP) \cite{miller:2000: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 \cite{woodward:Modularity}; the complexity of a function using a (Cartesian Program) CP representation is invariant (up to an additive constant) when using different terminal sets, provided the different terminal sets can both be represented. 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 = "UKCI 2005 http://www.dcs.bbk.ac.uk/ukci05/",
