- 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 = "
http://doi.acm.org/10.1145/3071178.3071271",
-
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)",
