Grammar Based Crossover Operator in Genetic Programming

摘要

This paper introduces a new crossover operator for the genetic programming (GP)paradigm, the grammar-based crossover (GBX). This operator works with any grammar-guided genetic programming system. GBX has three important features: it prevents the growth of tree-based GP individuals (a phenomenon known as code bloat), it provides a satisfactory trade-off between the search space exploration and the exploitation capabilities by preserving the context in which subtrees appear in the parent trees and, finally, it takes advantage of the main feature of ambiguous gramrnars, namely, that there is more than one derivation tree for some sentences (solutions). These features give GBX a high convergence speed and low probability of getting trapped in local optima, as shown throughout the comparison of the results achieved by GBX with other relevant crossover operators in two experiments: a laboratory problem and a real-world task: breast cancer prognosis.