text: In a steady-state evolution, tournament selection traditionally uses the fitness function to select the parents, and negative selection chooses an individual to be replaced with an offspring. This contribution focuses on analyzing the behavior, in terms of performance, of different heuristics when used instead of the fitness function in tournament selection. The heuristics analyzed are related to measuring the similarity of the individuals in the semantic space. In addition, the analysis includes random selection and traditional tournament selection. These selection functions were implemented on our Semantic Genetic Programming system, namely EvoDAG, which is inspired by the geometric genetic operators and tested on 30 classification problems with a variable number of samples, variables, and classes. The result indicated that the combination of accuracy and the random selection, in the negative tournament, produces the best combination, and the difference in performances between this combination and the tournament selection is statistically significant. Furthermore, we compare EvoDAG's performance using the selection heuristics against 18 classifiers that included traditional approaches as well as auto-machine-learning techniques. The results indicate that our proposal is competitive with state-of-art classifiers. Finally, it is worth to mention that EvoDAG is available as open source software.
  @cite_7: We propose Locally Geometric Crossover (LGX) for genetic programming. For a pair of homologous loci in the parent solutions, LGX finds a semantically intermediate procedure from a previously prepared library, and uses it as replacement code. The experiments involving six symbolic regression problems show significant increase in search performance when compared to standard subtree-swapping cross-over and other control methods. This suggests that semantically geometric manipulations on subprograms propagate to entire programs and improve their fitness.
  @cite_8: In genetic programming, a search algorithm is expected to produce a program that achieves the desired final computation state (desired output). To reach that state, an executing program needs to traverse certain intermediate computation states. An evolutionary search process is expected to autonomously discover such states. This can be difficult for nontrivial tasks that require long programs to be solved. The semantic backpropagation algorithm proposed in this paper heuristically inverts the execution of evolving programs to determine the desired intermediate computation states. Two search operators, random desired operator and approximately geometric semantic crossover, use the intermediate states determined by semantic backpropagation to define subtasks of the original programming task, which are then solved using an exhaustive search. The operators outperform the standard genetic search operators and other semantic-aware operators when compared on a suite of symbolic regression and Boolean benchmarks. This result and additional analysis conducted in this paper indicate that semantic backpropagation helps evolution to identify the desired intermediate computation states and makes the search process more efficient.
  @cite_21: In this paper we give a representation-independent topological defi- nition of crossover that links it tightly to the notion of fitness landscape. Building around this definition, a geometric topological framework for evolu- tionary algorithms is introduced that clarifies the connection between represen- tation, genetic operators, neighbourhood structure and distance in the land- scape. Traditional genetic operators for binary strings are shown to fit the framework. The advantages of this interpretation are discussed.
  @cite_24: In the Genetic Programming (GP) community there has been a great interest in developing semantic genetic operators. These type of operators use information of the phenotype to create ospring. The most recent approaches of semantic GP include the GP framework based on the alignment of error space, the geometric semantic genetic operators, and backpropagation genetic operators. Our contribution proposes two semantic operators based on projections in the phenotype space. The proposed operators have the characteristic, by construction, that the ospring's tness is as at least as good as the tness of the best parent; using as tness the euclidean distance. The semantic operators proposed increment the learning capabilities of GP. These operators are compared against a traditional GP and Geometric Semantic GP in the Human oral bioavailability regression problem and 13 classication problems. The results show that a GP system with our novel semantic operators has the best performance in the training phase in all the problems tested.
  @cite_19: 
  @cite_27: 
  @cite_2: This study presents an extensive account of Locally Geometric Semantic Crossover (LGX), a semantically-aware recombination operator for genetic programming (GP). LGX is designed to exploit the semantic properties of programs and subprograms, in particular the geometry of semantic space that results from distance-based fitness functions used predominantly in GP. When applied to a pair of parents, LGX picks in them at random a structurally common (homologous) locus, calculates the semantics of subprograms located at that locus, finds a procedure that is semantically medial with respect to these subprograms, and replaces them with that procedure. The library of procedures is prepared prior to the evolutionary run and indexed by a multidimensional structure (kd-tree) allowing for efficient search. The paper presents the rationale for LGX design and an extensive computational experiment concerning performance, computational cost, impact on program size, and capability of generalization. LGX is compared with six other operators, including conventional tree-swapping crossover, semantic-aware operators proposed in previous studies, and control methods designed to verify the importance of homology and geometry of the semantic space. The overall conclusion is that LGX, thanks to combination of the semantically medial operation with homology, improves the efficiency of evolutionary search, lowers the variance of performance, and tends to be more resistant to overfitting.
  @cite_47: The semantic geometric crossover (SGX) proposed by has achieved very promising results and received great attention from researchers, but has a significant disadvantage in the exponential growth in size of the solutions. We propose a crossover operator named subtree semantic geometric crossover (SSGX), with the aim of addressing this issue. It is similar to SGX but uses subtree semantic similarity to approximate the geometric property. We compare SSGX to standard crossover (SC), to SGX, and to other recent semantic-based crossover operators, testing on several symbolic regression problems. Overall our new operator out-performs the other operators on test data performance, and reduces computational time relative to most of them. Further analysis shows that while SGX is rather exploitative, and SC rather explorative, SSGX achieves a balance between the two. A simple method of further enhancing SSGX performance is also demonstrated.
  @cite_16: Genetic Programming (GP) is an evolutionary method for generating tree structural programs. Normal subtree crossover in GP randomly selects a crossover point in each parental tree, and offspring are created by exchanging the selected subtrees. In the normal crossover, it is difficult to control the global and local search because the similarity between the subtrees is not considered. In this paper, we propose a new crossover operation based on the semantic distance between the subtrees. We call this operation Semantic Control Crossover. By using the Semantic Control Crossover, the global search can be performed in the early stage of search, and the search property can be shifted to the local search as the search proceeds. As the results of experiments, the Semantic Control Crossover showed better performance than the conventional crossover.
  @cite_10: We propose a crossover operator that works with genetic programming trees and is approximately geometric crossover in the semantic space. By defining semantic as program's evaluation profile with respect to a set of fitness cases and constraining to a specific class of metric-based fitness functions, we cause the fitness landscape in the semantic space to have perfect fitness-distance correlation. The proposed approximately geometric semantic crossover exploits this property of the semantic fitness landscape by an appropriate sampling. We demonstrate also how the proposed method may be conveniently combined with hill climbing. We discuss the properties of the methods, and describe an extensive computational experiment concerning logical function synthesis and symbolic regression.
summary: Moraglio @cite_21 @cite_27 proposed Geometric Semantic Genetic Programming (GSGP). Their work called the attention of the GP scientific community because the crossover operator produces an offspring that stands in the segment joining the parents' semantics. Therefore, offspring fitness cannot be worse than the worst fitness of the parents. Given two parents @math and @math , the crossover operator generates an offspring as @math , where @math is a real value between @math and @math . This property transforms the fitness landscape into a cone. Unfortunately, the offspring is always bigger than the sum of the size of its parents; this makes the operator unusable in practice. Later, some operators appear intending to improve Moraglio's GSGP. For example, Approximately Geometric Semantic Crossover (SX) @cite_10 , Deterministic Geometric Semantic Crossover @cite_16 , Locally Geometric Crossover (LGX) @cite_7 @cite_2 and Approximated Geometric Crossover (AGX) @cite_8 , Semantic Crossover and Mutation based on projections @cite_24 @cite_19 and Subtree Semantic Geometric Crossover (SSGX) @cite_47 .