@inproceedings{1b3c9fcdc43648819521fb08ef079bf7,
title = "Bounding bloat in genetic programming",
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 analyze 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) φ(T;nit + n log n) iterations with bloat control on ORDER as well as MAJORITY; and (ii) O(Tinit logTinit + n(logn)3) and Ω(Tinit + nlogn) (and Ω (Tinit log Tinit) for n = 1) iterations without bloat control on MAJORITY.",
keywords = "Genetic programming, Mutation, Run time analysis, Theory",
author = "Benjamin Doerr and Timo Kotzing and Lagodzinski, \{J. A.Gregor\} and Johannes Lengler",
note = "Publisher Copyright: {\textcopyright} 2017 ACM.; 2017 Genetic and Evolutionary Computation Conference, GECCO 2017 ; Conference date: 15-07-2017 Through 19-07-2017",
year = "2017",
month = jul,
day = "1",
doi = "10.1145/3071178.3071271",
language = "English",
series = "GECCO 2017 - Proceedings of the 2017 Genetic and Evolutionary Computation Conference",
publisher = "Association for Computing Machinery, Inc",
pages = "921--928",
booktitle = "GECCO 2017 - Proceedings of the 2017 Genetic and Evolutionary Computation Conference",
}