Review and Comparative Analysis of Geometric Semantic Crossovers

Tomasz P. Pawlak, Bartosz Wieloch, Krzysztof Krawiec

Abstract

This paper provides a structured, uniﬁed, 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 ﬁtness landscape. We prove that geometric semantic crossover can by construction produce an offspring that is not worse than the ﬁtter 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 previously presented 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. In there, we scrutinize the performance (program error and success rate), generalization, computational cost, bloat, population diversity, and operator’s 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.

Access full text

Full text is available at SpringerLink (open access).

BibTeX

@article{Pawlak:2015:GPEM,
  year={2015},
  issn={1389-2576},
  journal={Genetic Programming and Evolvable Machines},
  volume={16},
  number={3},
  doi={10.1007/s10710-014-9239-8},
  title={Review and comparative analysis of geometric semantic crossovers},
  url={http://dx.doi.org/10.1007/s10710-014-9239-8},
  publisher={Springer US},
  keywords={Geometry; Semantics; Fitness landscape; Crossover; Theory; Experiment},
  author={Pawlak, Tomasz P. and Wieloch, Bartosz and Krawiec, Krzysztof},
  pages={351-386},
  language={English}
}

Suplementary material

The Java source code of Geometric Semantic Crossover, Approximately Geometric Semantic Crossover, Locally Geometric Semantic Crossover, Krawiec & Lichocki Crossover and other parts of the experimental suite presented in the paper, together with the compiled Jar are available under conditions of Academic Free License. Java 1.7+ is required to compile the Jar from source. Instructions how to create configuration files and run the experiment are available in ECJ manual. The classes under interest of this study can be found in the following namespaces:

ec.app.semanticGP.* (problem definitions)
ec.gp.semantic.* (operators and basic semantic stuff)
library.* (semantic library helper classes)

« back