Repeated Patterns in Genetic Programming

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

  author =       "W. B. Langdon and W. Banzhaf",
  title =        "Repeated Patterns in Genetic Programming",
  journal =      "Natural Computing",
  year =         "2008",
  volume =       "7",
  number =       "4",
  pages =        "589--613",
  month =        dec,
  keywords =     "genetic algorithms, genetic programming, SINE, ALU,
                 Frequent subgraphs, frequent subtrees, Mackey-Glass,
                 Poly-10, nuclear protein localisation, tinyGP, GPquick,
                 evolution of program shape, sensitivity analysis",
  ISSN =         "1567-7818",
  URL =          "",
  DOI =          "doi:10.1007/s11047-007-9038-8",
  size =         "26 pages",
  abstract =     "Evolved genetic programming trees contain many
                 repeated code fragments. Size fair crossover limits
                 bloat in automatic programming, preventing the
                 evolution of recurring motifs. We examine these complex
                 properties in detail using depth v. size Catalan binary
                 tree shape plots, subgraph and subtree matching,
                 information entropy, sensitivity analysis, syntactic
                 and semantic fitness correlations. Programs evolve in a
                 self-similar fashion, akin to fractal random trees,
                 with diffuse introns. Data mining frequent patterns
                 reveals that as software is progressively improved a
                 large proportion of it is exactly repeated subtrees as
                 well as exactly repeated subgraphs. We relate this
                 emergent phenomenon to building blocks in GP and
                 suggest GP works by jumbling subtrees which already
                 have high fitness on the whole problem to give
                 incremental improvements and create complete solutions
                 with multiple identical components of different
  notes =        "Published online: 26 May 2007


Genetic Programming entries for William B Langdon Wolfgang Banzhaf