Complexity and Cartesian Genetic Programming

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

@InProceedings{eurogp06:WoodwardC,
  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",
}

Genetic Programming entries for John R Woodward

Citations