Complexity and Cartesian Genetic Programming
The 5th annual UK Workshop on Computational
Intelligence, Seite 273--280. London, (5-7 September 2005)Zusammenfassung
Genetic Programming (GP) 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)
banzhaf:1997:book is to allow the ability to
express modules. In 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)
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 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
miller:2000:CGP, then it can effectively define
its own terminals at a constant cost.