Single- and Multi-Objective Genetic Programming: New Bounds for Weighted ORDER and MAJORITY

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

  author =       "Anh Nguyen and Tommaso Urli and Markus Wagner",
  title =        "Single- and Multi-Objective Genetic Programming: New
                 Bounds for Weighted ORDER and MAJORITY",
  booktitle =    "Foundations of Genetic Algorithms",
  year =         "2013",
  editor =       "Frank Neumann and Kenneth {De Jong}",
  pages =        "161--172",
  address =      "Adelaide, Australia",
  month =        "16-20 " # jan,
  organisation = "SigEvo",
  publisher =    "ACM",
  keywords =     "genetic algorithms, genetic programming,
                 Multi-objective Optimisation, Theory, Runtime
  isbn13 =       "978-1-4503-1990-4",
  URL =          "",
  URL =          "",
  DOI =          "doi:10.1145/2460239.2460254",
  acmid =        "2460254",
  size =         "12 pages",
  abstract =     "We consolidate the existing computational complexity
                 analysis of genetic programming (GP) by bringing
                 together sound theoretical proofs and empirical
                 analysis. In particular, we address computational
                 complexity issues arising when coupling algorithms
                 using variable length representation, such as GP
                 itself, with different bloat-control techniques. In
                 order to accomplish this, we first introduce several
                 novel upper bounds for two single- and multi-objective
                 GP algorithms on the generalised Weighted ORDER and
                 MAJORITY problems. To obtain these, we employ
                 well-established computational complexity analysis
                 techniques such as fitness-based partitions, and for
                 the first time, additive and multiplicative drift.

                 The bounds we identify depend on two measures, the
                 maximum tree size and the maximum population size, that
                 arise during the optimisation run and that have a key
                 relevance in determining the run time of the studied GP
                 algorithms. In order to understand the impact of these
                 measures on a typical run, we study their magnitude
                 experimentally, and we discuss the obtained findings.",
  notes =        "Anh Quang Nguyen Jan 2013: 2013foga-gp.pdf is
                 preproceedings version. Jan 2014: note title

                 Section 6 'theoretical investigations to complement the
                 recent results on the runtime of two genetic
                 programming algorithms \cite{Durrett:2011:foga}

                 Also known as \cite{Nguyen:2013:SMG:2460239.2460254}.

Genetic Programming entries for Anh Quang Nguyen Tommaso Urli Markus Wagner