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.
Some crossover and mutation operators have been developed with the use of semantics. Beadle and Johnson @cite_40 proposed a crossover operator that measures the semantic equivalence between parents and offsprings; and rejects the offspring that is semantically equivalent to its parents. Quang Uy @cite_42 proposed a semantic crossover and mutation. The crossover operator searches for a crossover point in each parent in such way that subtrees were semantically similar, and the mutation operator allows the replacement of an individual subtree only if the new subtree is semantically similar. Hara @cite_16 proposed the Semantic Control Crossover that uses the semantics to combine individuals where a global search was performed in the first generations and a local search in the last ones. Graff used subtrees semantics and partial derivatives to proposed crossover @cite_18 @cite_49 and mutation @cite_36 operators.
@cite_18 @cite_36 @cite_42 @cite_40 @cite_49 @cite_16
1985901961 2061011797 66126747 2157723426 1966140552 2072918701 2294762224 1994258343 2164305954 1998837010 2011559870 1991640459 2508930158 2075524109 2160436193 2160241726 1606499289 2187785713 2125260159 2076402663
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. We investigate the effects of semantically-based crossover operators in genetic programming, applied to real-valued symbolic regression problems. We propose two new relations derived from the semantic distance between subtrees, known as semantic equivalence and semantic similarity. These relations are used to guide variants of the crossover operator, resulting in two new crossover operators--semantics aware crossover (SAC) and semantic similarity-based crossover (SSC). SAC, was introduced and previously studied, is added here for the purpose of comparison and analysis. SSC extends SAC by more closely controlling the semantic distance between subtrees to which crossover may be applied. The new operators were tested on some real-valued symbolic regression problems and compared with standard crossover (SC), context aware crossover (CAC), Soft Brood Selection (SBS), and No Same Mate (NSM) selection. The experimental results show on the problems examined that, with computational effort measured by the number of function node evaluations, only SSC and SBS were significantly better than SC, and SSC was often better than SBS. Further experiments were also conducted to analyse the perfomance sensitivity to the parameter settings for SSC. This analysis leads to a conclusion that SSC is more constructive and has higher locality than SAC, NSM and SC; we believe these are the main reasons for the improved performance of SSC. There is great interest for the development of semantic genetic operators to improve the performance of genetic programming. Semantic genetic operators have traditionally been developed employing experimentally or theoretically-based approaches. Our current work proposes a novel semantic crossover developed amid the two traditional approaches. Our proposed semantic crossover operator is based on the use of the derivative of the error propagated through the tree. This process decides the crossing point of the second parent. The results show that our procedure improves the performance of genetic programming on rational symbolic regression problems. 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. There is a great interest in the Genetic Programming (GP) community to develop semantic genetic operators. Most recent approaches includes the genetic programming framework for symbolic regression called Error Space Alignment GP, the geometric semantic operators, and our previous work the semantic crossover based on the partial derivative error. To the best of our knowledge, there has not been a semantic genetic operator similar to the point mutation. In this contribution, we start filling this gap by proposing a semantic point mutation based on the derivative of the error. This novel operator complements our previous semantic crossover and, as the results show, there is an improvement in performance when this novel operator is used, and, furthermore, the best performance in our setting is the system that uses the semantic crossover and the semantic point mutation. 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. 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. Mutation and crossover are the main search operators of different variants of evolutionary algorithms. Despite the many discussions on the importance of crossover nobody has proved rigorously for some explicitly defined fitness functions f"n: 0,1 ^n->R that a genetic algorithm with crossover can optimize f"n in expected polynomial time while all evolution strategies based only on mutation (and selection) need expected exponential time. Here such functions and proofs are presented for a genetic algorithm without any idealization. For some functions one-point crossover is appropriate while for others uniform crossover is the right choice. Crossover forms one of the core operations in genetic programming and has been the subject of many different investigations. We present a novel technique, based on semantic analysis of programs, which forces each crossover to make candidate programs take a new step in the behavioural search space. We demonstrate how this technique results in better performance and smaller solutions in two separate genetic programming experiments. 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. Understanding the impact of crossover on performance is a major problem in the theory of genetic algorithms (GAs). We present new insight on working principles of crossover by analyzing the performance of crossover-based GAs on the simple functions OneMax and Jump. First, we assess the potential speedup by crossover when combined with a fitness-invariant bit shuffling operator that simulates a lineage of independent evolution on a function of unitation. Theoretical and empirical results show drastic speedups for both functions. Second, we consider a simple GA without shuffling and investigate the interplay of mutation and crossover on Jump. If the crossover probability is small, subsequent mutations create sufficient diversity, even for very small populations. Contrarily, with high crossover probabilities crossover tends to lose diversity more quickly than mutation can create it. This has a drastic impact on the performance on Jump. We complement our theoretical findings by Monte Carlo simulations on the population diversity. Mutation operators such as Gaussian, Levy and Cauchy have been used with evolutionary programming (EP). According to the no free lunch theorem, it is impossible for EP with a single mutation operator to outperform always. For example, Classical EP (CEP) with Gaussian mutation is better at searching in a local neighborhood while the Fast EP (FEP) with the Cauchy mutation performs better over a larger neighborhood. Motivated by these observations, we propose an ensemble approach where each mutation operator has its associated population and every population benefits from every function call. This approach enables us to benefit from different mutation operators with different parameter values whenever they are effective during different stages of the search process. In addition, the recently proposed Adaptive EP (AEP) using Gaussian (ACEP) and Cauchy (AFEP) mutations is also evaluated. In the AEP, the strategy parameter values are adapted based on the search performance in the previous few generations. The performance of ensemble is compared with a mixed mutation strategy, which integrates several mutation operators into a single algorithm as well as against the AEP with a single mutation operator. Improved performance of the ensemble over the single mutation-based algorithms and mixed mutation algorithm is verified using statistical tests. In recent years, a number of methods have been proposed that attempt to improve the performance of genetic programming by exploiting information about program semantics. One of the most important developments in this area is semantic backpropagation. The key idea of this method is to decompose a program into two parts—a subprogram and a context—and calculate the desired semantics of the subprogram that would make the entire program correct, assuming that the context remains unchanged. In this paper we introduce Forward Propagation Mutation, a novel operator that relies on the opposite assumption—instead of preserving the context, it retains the subprogram and attempts to place it in the semantically right context. We empirically compare the performance of semantic backpropagation and forward propagation operators on a set of symbolic regression benchmarks. The experimental results demonstrate that semantic forward propagation produces smaller programs that achieve significantly higher generalization performance. Abstract The purpose of this paper is to present a new and an alternative differential evolution (ADE) algorithm for solving unconstrained global optimization problems. In the new algorithm, a new directed mutation rule is introduced based on the weighted difference vector between the best and the worst individuals of a particular generation. The mutation rule is combined with the basic mutation strategy through a linear decreasing probability rule. This modification is shown to enhance the local search ability of the basic DE and to increase the convergence rate. Two new scaling factors are introduced as uniform random variables to improve the diversity of the population and to bias the search direction. Additionally, a dynamic non-linear increased crossover probability scheme is utilized to balance the global exploration and local exploitation. Furthermore, a random mutation scheme and a modified Breeder Genetic Algorithm (BGA) mutation scheme are merged to avoid stagnation and or premature convergence. Numerical experiments and comparisons on a set of well-known high dimensional benchmark functions indicate that the improved algorithm outperforms and is superior to other existing algorithms in terms of final solution quality, success rate, convergence rate, and robustness. Beginning with the early days of the genetic algorithm and the schema theorem it has often been argued that the crossover operator is the more important genetic operator. The early Royal Road functions were put forth as an example where crossover would excel, yet mutation based EAs were subsequently shown to experimentally outperform GAs with crossover on these functions. Recently several new Royal Roads have been introduced and proved to require expected polynomial time for GAs with crossover, while needing exponential time to optimize for mutation-only EAs. This paper does the converse, showing proofs that GAs with crossover require exponential optimization time on new Ignoble Trail functions while mutation based EAs optimize them efficiently. Due to experimental evidence it is incontestable that crossover is essential for some fitness functions. However, theoretical results without assumptions are difficult. So-called real royal road functions are known where crossover is proved to be essential, i.e., mutation-based algorithms have an exponential expected runtime while the expected runtime of a genetic algorithm is polynomially bounded. However, these functions are artificial and have been designed in such a way that crossover is essential only at the very end (or at other well-specified points) of the optimization process.Here, a more natural fitness function based on a generalized Ising model is presented where crossover is essential throughout the whole optimization process. Mutation-based algorithms such as (μ+λ) EAs with constant population size are proved to have an exponential expected runtime while the expected runtime of a simple genetic algorithm with population size 2 and fitness sharing is polynomially bounded. There is a lot of experimental evidence that crossover is, for some functions, an essential operator of evolutionary algorithms. Nevertheless, it was an open problem to prove for some function that an evolutionary algorithm using crossover is essentially more efficient than evolutionary algorithms without crossover. In this paper, such an example is presented and its properties are proved. We reinvestigate a fundamental question: How effective is crossover in genetic algorithms in combining building blocks of good solutions? Although this has been discussed controversially for decades, we are still lacking a rigorous and intuitive answer. We provide such answers for royal road functions and OneMax, where every bit is a building block. For the latter, we show that using crossover makes every + i¾ genetic algorithm at least twice as fast as the fastest evolutionary algorithm using only standard bit mutation, up to small-order terms and for moderatei¾ andi¾ . Crossover is beneficial because it can capitalize on mutations that have both beneficial and disruptive effects on building blocks: crossover is able to repair the disruptive effects of mutation in later generations. Compared to mutation-based evolutionary algorithms, this makes multibit mutations more useful. Introducing crossover changes the optimal mutation rate on OneMax from to . This holds both for uniform crossover and k-point crossover. Experiments and statistical tests confirm that our findings apply to a broad class of building block functions. Several techniques have been developed for identifying similar code fragments in programs. These similar fragments, referred to as code clones, can be used to identify redundant code, locate bugs, or gain insight into program design. Existing scalable approaches to clone detection are limited to finding program fragments that are similar only in their contiguous syntax. Other, semantics-based approaches are more resilient to differences in syntax, such as reordered statements, related statements interleaved with other unrelated statements, or the use of semantically equivalent control structures. However, none of these techniques have scaled to real world code bases. These approaches capture semantic information from Program Dependence Graphs (PDGs), program representations that encode data and control dependencies between statements and predicates. Our definition of a code clone is also based on this representation: we consider program fragments with isomorphic PDGs to be clones. In this paper, we present the first scalable clone detection algorithm based on this definition of semantic clones. Our insight is the reduction of the difficult graph similarity problem to a simpler tree similarity problem by mapping carefully selected PDG subgraphs to their related structured syntax. We efficiently solve the tree similarity problem to create a scalable analysis. We have implemented this algorithm in a practical tool and performed evaluations on several million-line open source projects, including the Linux kernel. Compared with previous approaches, our tool locates significantly more clones, which are often more semantically interesting than simple copied and pasted code fragments. 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.