Comparison of tree and graph encodings as function of problem complexity

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

  author =       "Michael Schmidt and Hod Lipson",
  title =        "Comparison of tree and graph encodings as function of
                 problem complexity",
  booktitle =    "GECCO '07: Proceedings of the 9th annual conference on
                 Genetic and evolutionary computation",
  year =         "2007",
  editor =       "Dirk Thierens and Hans-Georg Beyer and 
                 Josh Bongard and Jurgen Branke and John Andrew Clark and 
                 Dave Cliff and Clare Bates Congdon and Kalyanmoy Deb and 
                 Benjamin Doerr and Tim Kovacs and Sanjeev Kumar and 
                 Julian F. Miller and Jason Moore and Frank Neumann and 
                 Martin Pelikan and Riccardo Poli and Kumara Sastry and 
                 Kenneth Owen Stanley and Thomas Stutzle and 
                 Richard A Watson and Ingo Wegener",
  volume =       "2",
  isbn13 =       "978-1-59593-697-4",
  pages =        "1674--1679",
  address =      "London",
  URL =          "",
  DOI =          "doi:10.1145/1276958.1277288",
  publisher =    "ACM Press",
  publisher_address = "New York, NY, USA",
  month =        "7-11 " # jul,
  organisation = "ACM SIGEVO (formerly ISGEC)",
  keywords =     "genetic algorithms, genetic programming, expression
                 graphs, expression trees, symbolic regression",
  abstract =     "In this paper, we analyse two general-purpose encoding
                 types, trees and graphs systematically, focusing on
                 trends over increasingly complex problems. Tree and
                 graph encodings are similar in application but offer
                 distinct advantages and disadvantages in genetic
                 programming. We describe two implementations and
                 discuss their evolvability. We then compare performance
                 using symbolic regression on hundreds of random
                 nonlinear target functions of both 1-dimensional and
                 8-dimensional cases. Results show the graph encoding
                 has less bias for bloating solutions but is slower to
                 converge and deleterious crossovers are more frequent.
                 The graph encoding however is found to have
                 computational benefits, suggesting it to be an
                 advantageous trade-off between regression performance
                 and computational effort.",
  notes =        "GECCO-2007 A joint meeting of the sixteenth
                 international conference on genetic algorithms
                 (ICGA-2007) and the twelfth annual genetic programming
                 conference (GP-2007).

                 ACM Order Number 910071",

Genetic Programming entries for Michael D Schmidt Hod Lipson