## 3 Iterative Search Algorithms
### Population-Based Algorithms
#### 3.3.3 Geometric Semantic Genetic Programming (GSGP)  
Geometric semantic genetic programming (GSGP) is a variant of GP in which the so-called geometric semantic operators (GSOs) replace the standard crossover and mutation operators [38]. GSOs gained popularity in the GP community [39; 40; 41; 42; 43] because of their geometric property of inducing a unimodal error surface (characterized by the absence of locally optimal solutions) for any SML problem, which quantifies the quality of candidate solutions by means of a distance metric between the target and their output values (also known as semantics). The formal proof of this property can be found in [38; 44]. Figure 5: Procedural steps of the genetic algorithm. A _geometric semantic crossover_ (GSC) generates, as the unique offspring of parents \(T_{1},T_{2}:\mathbb{R}^{n}\to\mathbb{R}\), the expression: \(T_{XO}=(T_{1}\cdot T_{R})+((1-T_{R})\cdot T_{2})\), where \(T_{R}\) is a random real function whose output values range in the interval \([0,1]\). [PERSON] and coauthors [38] show that GSC corresponds to geometric crossover in the semantic space (i.e., the point representing the offspring stands on the segment joining the points representing the parents). Consequently, the GSC inherits the key property of geometric crossover: the offspring is never worse than the worst of the parents. A _geometric semantic mutation_ (GSM) returns, as the result of the mutation of an individual \(T:\mathbb{R}^{n}\to\mathbb{R}\), the expression: \(T_{M}=T+ms\cdot(T_{R1}-T_{R2})\), where \(T_{R1}\) and \(T_{R2}\) are random real functions with a codomain in \([0,1]\) and \(ms\) is a parameter called the mutation step. Similarly to GSC, [PERSON] and coauthors show that GSM corresponds to a box mutation on the semantic space. Consequently, the operator induces a unimodal error surface on any SML problem. The demonstration of how GSM induces a unimodal error surface can be found in Figure 6, which represents a chain of possible individuals that could be generated by applying GSM several times and their corresponding semantics (left and right subfigures, respectively). Here, for the sake of visualization, we present a simple 2D semantic space, where each solution is represented by a point (this corresponds to the case when there are only two training instances). The known global is represented with a red star. Each point in the figure is \"surrounded\" by a gray dotted square of side \(ms\), which corresponds to the mutation's step inside which the GSM allows solutions to move. As one can see, GSM's application allows for moving a given solution in any position inside the square, including the one that approximates it to the target. Thus, GSM implies that there is always a possibility of getting closer to the target. This implies that no local optima, except the global optimum, can exist, and the fitness landscape for this problem is unimodal. The gray arrows map the genotypic space to the phenotypic and highlight GSM's capability of generating a transformation on the trees' syntax, which has an expected effect on their semantics [44]. However, as [PERSON] et al. [38] noted, GSOs create offspring that are substantially larger than their parents are. Moreover, the fast growth of the individuals' size rapidly turns the fitness evaluation to slow, making the system unusable. As a solution to this problem, [PERSON] et al. [45] proposed a computationally efficient implementation of GSOs, making them usable in practice. Figure 6: A simple visual demonstration of GSM’s genotype-phenotype mapping and its property of introducing a unimodal error surface on any SML problem. Adapted from [44]. Given the growing importance of GSOs, we decided to include them in our library, following the efficient implementation guidelines proposed in [26].