# The Effect of Multi-Generational Selection in Geometric Semantic Genetic Programming
## 3 Geometric Semantic GP with Multi-Generational Selection
### Geometric Semantic Genetic Programming  
In classical GP, the crossover (recombination) and mutation operators act on the genotype of the individual involved, usually modifying or changing parts of the subtrees in the case of a tree-based representation. However, the effects on the phenotype of the individuals are difficult to formalize, and even small modifications to the genotype can create a significant change in the phenotype. Therefore, in addition to the standard \"syntactic\" operators of GP, there have been multiple studies on _semantic_ operators [22]. By relying on these operators, it is possible to predict the effect of crossover and mutation on the phenotype of the solutions. In 2012, [PERSON] and coauthors [2] defined a way of performing semantic crossover and mutation where the effect was obtaining a _geometric_ crossover and _geometric_ mutation in the semantic space, two concepts defined and studied in [23]. Given a metric space \((X,d)\) where \(X\) is a set and \(d\colon X\times X\to\mathbb{R}_{+}\) is a distance, a crossover is said to be geometric if, for each \(x,y\in X\), each element resulting from the crossover of \(x\) and \(y\) belongs to the set \(\{z\in A\mid d(x,z)+d(z,y)=d(x,y)\}\), i.e., the result of the crossover is inside the segment connecting \(x\) and \(y\). A mutation operator is said to be geometrical and, in particular, a geometric \(\epsilon\)-mutation, if, for each \(x\in X\), the individuals resulting from the mutation are all inside the ball \(B_{\epsilon}(x)\), i.e., the ball of radius \(\epsilon\) centered in \(x\). One of the advantages of working with geometric operators is that it is possible to reason on the geometrical effect of the different operators; e.g., a geometric crossover always generates offspring in the convex hull given by the current population (see Figure 1). In particular, one interesting space where it is possible to define genetic operators is the _semantic space_. That is, given a set of samples \(X=\{\vec{x}^{1},\ldots,\vec{x}^{m}\}\subset\mathbb{R}^{n}\) and a function \(T:\mathbb{R}^{n}\to\mathbb{R}\), representing a GP individual, we can define the _semantics of \(T\)_, denoted by \(s(T)\) as the vector \((T(\vec{x}^{1}),T(\vec{x}^{2}),\ldots,T(\vec{x}^{m}))\in\mathbb{R}^{m}\). If we perform a _geometric_ crossover between the semantics of two trees \(T_{1}\) and \(T_{2}\), the semantics of _any_ individual resulting from the crossover will have outputs (on the elements of the set \(X\)) intermediate between the ones of \(T_{1}\) and \(T_{2}\). Similarly, a _geometric_ mutation on the semantic space will generate a perturbation of the outputs of the parent individual. There is, however, the question of how to define operators working on the semantic space by manipulating the syntactic space. The conundrum was solved by [PERSON] et al. [2] in 2012 with the definition of semantic mutation and crossover, as detailed below. **Semantic Crossover. ** Let \(T_{1}\) and \(T_{2}\) be two functions from \(\mathbb{R}^{n}\) to \(\mathbb{R}\) representing two GP trees and let \(R\colon\mathbb{R}^{n}\to[0,1]\) be a randomly generated tree. Then the _semantic crossover_ between \(T_{1}\) and \(T_{2}\) using the random tree \(R\) is defined as:  
\[\text{Cross}(T_{1},T_{2},R)(\vec{x})=R(\vec{x})T_{1}(\vec{x})+(1-R(\vec{x}))T_ {2}(\vec{x})\qquad\qquad\text{for all }\vec{x}\in\mathbb{R}^{n}.\]  
Notice that the outputs of \(\text{Cross}(T_{1},T_{2},R)(\vec{x})\) will be intermediate with respect to the outputs of \(T_{1}\) and \(T_{2}\). Thus, the crossover is geometric in the semantic space. To constrain the output of \(R\) inside the interval \([0,1]\), a simple technique is to generate a random tree and pass its output to a sigmoid function. **Semantic Mutation. ** Let \(T\colon\mathbb{R}^{n}\to\mathbb{R}\) be the function defined by a GP tree, \(R\colon\mathbb{R}^{n}\to\mathbb{R}\) be a randomly generated tree, and \(m\in\mathbb{R}_{+}\) be a positive real number, called the _mutation step_.