Bounding Bloat in Genetic Programming

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

  author =       "Benjamin Doerr and Timo Koetzing and 
                 J. A. Gregor Lagodzinski and Johannes Lengler",
  title =        "Bounding Bloat in Genetic Programming",
  booktitle =    "Proceedings of the Genetic and Evolutionary
                 Computation Conference",
  series =       "GECCO '17",
  year =         "2017",
  isbn13 =       "978-1-4503-4920-8",
  address =      "Berlin, Germany",
  pages =        "921--928",
  size =         "8 pages",
  URL =          "",
  DOI =          "doi:10.1145/3071178.3071271",
  acmid =        "3071271",
  publisher =    "ACM",
  publisher_address = "New York, NY, USA",
  keywords =     "genetic algorithms, genetic programming, mutation, run
                 time analysis, theory",
  month =        "15-19 " # jul,
  abstract =     "While many optimization problems work with a fixed
                 number of decision variables and thus a fixed-length
                 representation of possible solutions, genetic
                 programming (GP) works on variable-length
                 representations. A naturally occurring problem is that
                 of bloat (unnecessary growth of solutions) slowing down
                 optimization. Theoretical analyses could so far not
                 bound bloat and required explicit assumptions on the
                 magnitude of bloat.

                 In this paper we analyse bloat in mutation-based
                 genetic programming for the two test functions ORDER
                 and MAJORITY. We overcome previous assumptions on the
                 magnitude of bloat and give matching or
                 close-to-matching upper and lower bounds for the
                 expected optimization time.

                 In particular, we show that the (1+1) GP takes (i)
                 ?(Tinit + n log n) iterations with bloat control on
                 ORDER as well as MAJORITY; and (ii) O(Tinit log Tinit +
                 n(log n)3) and Omega(Tinit + n log n) (and Omerga(Tinit
                 log Tinit) for n = 1) iterations without bloat control
                 on MAJORITY.",
  notes =        "Also known as \cite{Doerr:2017:BBG:3071178.3071271}
                 GECCO-2017 A Recombination of the 26th International
                 Conference on Genetic Algorithms (ICGA-2017) and the
                 22nd Annual Genetic Programming Conference (GP-2017)",

Genetic Programming entries for Benjamin Doerr Timo Koetzing J A Gregor Lagodzinski Johannes Lengler