This paper provides a structured, unified, formal and empirical perspective on all geometric semantic crossover operators proposed so far, including the exact geometric crossover by Moraglio, Krawiec, and Johnson, as well as the approximately geometric operators. We start with presenting the theory of geometric semantic genetic programming, and discuss the implications of geometric operators for the structure of fitness landscape. We prove that geometric semantic crossover can by construction produce an offspring that is not worse than the fitter parent, and that under certain conditions such an offspring is guaranteed to be not worse than the worse parent. We review all geometric semantic crossover operators presented to date in the literature, and conduct a comprehensive experimental comparison using a tree-based genetic programming framework and a representative suite of nine symbolic regression and nine Boolean function synthesis tasks. We scrutinize the performance (program error and success rate), generalization, computational cost, bloat, population diversity, and the operators' capability to generate geometric offspring. The experiment leads to several interesting conclusions, the primary one being that an operator's capability to produce geometric offspring is positively correlated with performance. The paper is concluded by recommendations regarding the suitability of operators for the particular domains of program induction tasks.
@ARTICLE { PawlakWielochKrawiec:2015:GPEM,
ABSTRACT = { This paper provides a structured, unified, formal and empirical perspective on all geometric semantic crossover operators proposed so far, including the exact geometric crossover by Moraglio, Krawiec, and Johnson, as well as the approximately geometric operators. We start with presenting the theory of geometric semantic genetic programming, and discuss the implications of geometric operators for the structure of fitness landscape. We prove that geometric semantic crossover can by construction produce an offspring that is not worse than the fitter parent, and that under certain conditions such an offspring is guaranteed to be not worse than the worse parent. We review all geometric semantic crossover operators presented to date in the literature, and conduct a comprehensive experimental comparison using a tree-based genetic programming framework and a representative suite of nine symbolic regression and nine Boolean function synthesis tasks. We scrutinize the performance (program error and success rate), generalization, computational cost, bloat, population diversity, and the operators' capability to generate geometric offspring. The experiment leads to several interesting conclusions, the primary one being that an operator's capability to produce geometric offspring is positively correlated with performance. The paper is concluded by recommendations regarding the suitability of operators for the particular domains of program induction tasks. },
AUTHOR = { Pawlak, Tomasz P. and Wieloch, Bartosz and Krawiec, Krzysztof },
DOI = { 10.1007/s10710-014-9239-8 },
ISSN = { 1573-7632 },
JOURNAL = { Genetic Programming and Evolvable Machines },
NUMBER = { 3 },
PAGES = { 351--386 },
TITLE = { Review and comparative analysis of geometric semantic crossovers },
URL = { http://dx.doi.org/10.1007/s10710-014-9239-8 },
VOLUME = { 16 },
YEAR = { 2015 },
1 = { http://dx.doi.org/10.1007/s10710-014-9239-8 },
}