Search results for "Genetic programming"
showing 10 items of 32 documents
On the role of non-effective code in linear genetic programming
2019
In linear variants of Genetic Programming (GP) like linear genetic programming (LGP), structural introns can emerge, which are nodes that are not connected to the final output and do not contribute to the output of a program. There are claims that such non-effective code is beneficial for search, as it can store relevant and important evolved information that can be reactivated in later search phases. Furthermore, introns can increase diversity, which leads to higher GP performance. This paper studies the role of non-effective code by comparing the performance of LGP variants that deal differently with non-effective code for standard symbolic regression problems. As we find no decrease in p…
Challenges of Program Synthesis with Grammatical Evolution
2020
Program synthesis is an emerging research topic in the field of EC with the potential to improve real-world software development. Grammar-guided approaches like GE are suitable for program synthesis as they can express common programming languages with their required properties. This work uses common software metrics (lines of code, McCabe metric, size and depth of the abstract syntax tree) for an analysis of GE’s search behavior and the resulting problem structure. We find that GE is not able to solve program synthesis problems, where correct solutions have higher values of the McCabe metric (which means they require conditions or loops). Since small mutations of high-quality solutions str…
Representations for evolutionary algorithms
2015
Successful and efficient use of evolutionary algorithms (EA) depends on the choice of the genotype, the problem representation (mapping from genotype to phenotype) and on the choice of search operators that are applied to the genotypes. These choices cannot be made independently of each other. The question whether a certain representation leads to better performing EAs than an alternative representation can only be answered when the operators applied are taken into consideration. The reverse is also true: deciding between alternative operators is only meaningful for a given representation. In EA practice one can distinguish two complementary approaches. The first approach uses indirect repr…
High Locality Representations for Automated Programming
2011
We study the locality of the genotype-phenotype mapping used in grammatical evolution (GE). GE is a variant of genetic programming that can evolve complete programs in an arbitrary language using a variable-length binary string. In contrast to standard GP, which applies search operators directly to phenotypes, GE uses an additional mapping and applies search operators to binary genotypes. Therefore, there is a large semantic gap between genotypes (binary strings) and phenotypes (programs or expressions). The case study shows that the mapping used in GE has low locality leading to low performance of standard mutation operators. The study at hand is an example of how basic design principles o…
On the Generalizability of Programs Synthesized by Grammar-Guided Genetic Programming
2021
Grammar-guided Genetic Programming is a common approach for program synthesis where the user’s intent is given by a set of input/output examples. For use in real-world software development, the generated programs must work on previously unseen test cases too. Therefore, we study in this work the generalizability of programs synthesized by grammar-guided GP with lexicase selection. As benchmark, we analyze proportionate and tournament selection too. We find that especially for program synthesis problems with a low output cardinality (e.g., a Boolean output) lexicase selection overfits the training cases and does not generalize well to unseen test cases. An analysis using common software metr…
A generalizability measure for program synthesis with genetic programming
2021
The generalizability of programs synthesized by genetic programming (GP) to unseen test cases is one of the main challenges of GP-based program synthesis. Recent work showed that increasing the amount of training data improves the generalizability of the programs synthesized by GP. However, generating training data is usually an expensive task as the output value for every training case must be calculated manually by the user. Therefore, this work suggests an approximation of the expected generalization ability of solution candidates found by GP. To obtain candidate solutions that all solve the training cases, but are structurally different, a GP run is not stopped after the first solution …
DAE-GP
2020
Estimation of distribution genetic programming (EDA-GP) algorithms are metaheuristics where sampling new solutions from a learned probabilistic model replaces the standard mutation and recombination operators of genetic programming (GP). This paper presents DAE-GP, a new EDA-GP which uses denoising autoencoder long short-term memory networks (DAE-LSTMs) as probabilistic model. DAE-LSTMs are artificial neural networks that first learn the properties of a parent population by mapping promising candidate solutions to a latent space and reconstructing the candidate solutions from the latent space. The trained model is then used to sample new offspring solutions. We show on a generalization of t…
On sampling error in evolutionary algorithms
2021
The initial population in evolutionary algorithms (EAs) should form a representative sample of all possible solutions (the search space). While large populations accurately approximate the distribution of possible solutions, small populations tend to incorporate a sampling error. A low sampling error at initialization is necessary (but not sufficient) for a reliable search since a low sampling error reduces the overall random variations in a random sample. For this reason, we have recently presented a model to determine a minimum initial population size so that the sampling error is lower than a threshold, given a confidence level. Our model allows practitioners of, for example, genetic pro…
On the Bias of Syntactic Geometric Recombination in Genetic Programming and Grammatical Evolution
2015
For fixed-length binary representations as used in genetic algorithms, standard recombination operators (e.g.,~one-point crossover) are unbiased. Thus, the application of recombination only reshuffles the alleles and does not change the statistical properties in the population. Using a geometric view on recombination operators, most search operators for fixed-length strings are geometric, which means that the distances between offspring and their parents are less than, or equal to, the distance between their parents. In genetic programming (GP) and grammatical evolution (GE), the situation is different since the recombination operators are applied to variable-length structures. Thus, most r…
Diverse partner selection with brood recombination in genetic programming
2018
The ultimate goal of learning algorithms is to find the best solution from a search space without testing each and every solution available in the search space. During the evolution process new solutions (children) are produced from existing solutions (parents), where new solutions are expected to be better than existing solutions. This paper presents a new parent selection method for the crossover operation in genetic programming. The idea is to promote crossover between two behaviourally (phenotype) diverse parents such that the probability of children being better than their parents increases. The relative phenotype strengths and weaknesses of pairs of parents are exploited to find out i…