TY  - JOUR
A1  - Kötzing, Timo
A1  - Lagodzinski, Gregor J. A.
A1  - Lengler, Johannes
A1  - Melnichenko, Anna
T1  - Destructiveness of lexicographic parsimony pressure and alleviation by a concatenation crossover in genetic programming
T2  - Theoretical computer science
N2  - For theoretical analyses there are two specifics distinguishing GP from many other areas of evolutionary computation: the variable size representations, in particular yielding a possible bloat (i.e. the growth of individuals with redundant parts); and also the role and the realization of crossover, which is particularly central in GP due to the tree-based representation. Whereas some theoretical work on GP has studied the effects of bloat, crossover had surprisingly little share in this work. <br /> We analyze a simple crossover operator in combination with randomized local search, where a preference for small solutions minimizes bloat (lexicographic parsimony pressure); we denote the resulting algorithm Concatenation Crossover GP. We consider three variants of the well-studied MAJORITY test function, adding large plateaus in different ways to the fitness landscape and thus giving a test bed for analyzing the interplay of variation operators and bloat control mechanisms in a setting with local optima. We show that the Concatenation Crossover GP can efficiently optimize these test functions, while local search cannot be efficient for all three variants independent of employing bloat control. (C) 2019 Elsevier B.V. All rights reserved.
KW  - genetic programming
KW  - mutation
KW  - theory
KW  - run time analysis
Y1  - 2019
UR  - https://publishup.uni-potsdam.de/frontdoor/index/index/docId/58543
SN  - 0304-3975
VL  - 816
SP  - 96
EP  - 113
PB  - Elsevier
CY  - Amsterdam
ER  -