Complexity and Cartesian Genetic Programming

Created by W.Langdon from gp-bibliography.bib Revision:1.3872

@InProceedings{woodward:2005:UKCIa,
  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/",
}

Genetic Programming entries for John R Woodward

Citations