- author = "Benjamin Doerr and Timo Koetzing and J. A. Gregor Lagodzinski and Johannes Lengler",
- title = "The impact of lexicographic parsimony pressure for {ORDER/MAJORITY} on the run time",
- journal = "Theoretical Computer Science",
- year = "2020",
- volume = "816",
- pages = "144--168",
- month = "6 " # may,
- keywords = "genetic algorithms, genetic programming, Bloat control, Theory, Runtime analysis",
-
URL = "
https://doi.org/10.1016/j.tcs.2020.01.011",
-
DOI = "
doi:10.1016/j.tcs.2020.01.011",
- timestamp = "Fri, 03 Apr 2020 09:22:19 +0200",
-
biburl = "https://dblp.org/rec/journals/tcs/DoerrKLL20.bib",
- bibsource = "dblp computer science bibliography, https://dblp.org",
-
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, that is, the unnecessary growth of solution
lengths, which may slow down the optimization process.
So far, the mathematical runtime analysis could not
deal well with bloat and required explicit assumptions
limiting bloat.
In this paper, we provide the first mathematical runtime analysis of a GP algorithm that does not require any assumptions on the bloat. Previous performance guarantees were only proven conditionally for runs in which no strong bloat occurs. Together with improved analyses for the case with bloat restrictions our results show that such assumptions on the bloat are not necessary and that the algorithm is efficient without explicit bloat control mechanism.
More specifically, we analyzed the performance of the GP on the two benchmark functions Order and Majority. When using lexicographic parsimony pressure as bloat control, we show a tight runtime estimate of iterations both for Order and Majority. For the case without bloat control, the bounds and (and for ) hold for Majority",
- notes = "some maths in abstract not shown",
