GECCO '18- Proceedings of the Genetic and Evolutionary Computation Conference

In genetic programming (GP), population diversity represents a key aspect of evolutionary search and a major factor in algorithm performance. In this paper we propose a new schema-based approach for observing and steering the loss of diversity in GP populations. We employ a well-known hyperschema definition from the literature to generate tree structural templates from the population's genealogy, and use them to guide the search via localized mutation within groups of individuals matching the same schema. The approach depends only on genealogy information and is easily integrated with existing GP variants. We demonstrate its potential in combination with Offspring Selection GP (OSGP) on a series of symbolic regression benchmark problems where our algorithmic variant called OSGP-S obtains superior results.

The use of semantic information in genetic programming operators has shown major improvements in recent years, especially in the regression and boolean domain. As semantic information is domain specific, using it in other areas poses certain problems. Semantic operators require being adapted for the problem domain they are applied to. An attempt to create a semantic crossover for program synthesis has been made with rather limited success, but the results have provided insights about using semantics in program synthesis. Based on this initial attempt, this paper presents an improved version of semantic operators for program synthesis, which contains a small but significant change to the overall functionality, as well as a novel measure for the comparison of the semantics of subtrees. The results show that the improved semantic crossover is superior to the previous semantic operator in the program synthesis domain.

Most genetic programming systems use mutation and crossover operators to create child programs from selected parent programs. Typically the mutation operator will replace a randomly chosen subprogram in the parent with a new, randomly generated subprogram. In systems with linear genomes, a uniform mutation operator can be used that has some probability of replacing any particular gene with a new, randomly chosen gene. In this paper, we present a new uniform mutation operator called Uniform Mutation by Addition and Deletion (UMAD), which first adds genes with some probability before or after every existing gene, and then deletes random genes from the resulting genome. In UMAD it is not necessary that the new genes replace old genes, as the additions and deletions can occur in different locations. We find that UMAD, with relatively high rates of addition and deletion, results in significant increases in problem-solving performance on a range of program synthesis benchmark problems. In our experiments, we compare this method to a variety of alternatives, showing that it equals or outperforms all of them. We explore this new mutation operator and other well-performing high-rate mutation schemes to determine what traits are crucial to improved performance.

We present SignalGP, a new genetic programming (GP) technique designed to incorporate the event-driven programming paradigm into computational evolution's toolbox. Event-driven programming is a software design philosophy that simplifies the development of reactive programs by automatically triggering program modules (event-handlers) in response to external events, such as signals from the environment or messages from other programs. SignalGP incorporates these concepts by extending existing tag-based referencing techniques into an event-driven context. Both events and functions are labeled with evolvable tags; when an event occurs, the function with the closest matching tag is triggered. In this work, we apply SignalGP in the context of linear GP. We demonstrate the value of the event-driven paradigm using two distinct test problems (an environment coordination problem and a distributed leader election problem) by comparing SignalGP to variants that are otherwise identical, but must actively use sensors to process events or messages. In each of these problems, rapid interaction with the environment or other agents is critical for maximizing fitness. We also discuss ways in which SignalGP can be generalized beyond our linear GP implementation.

When search operators in genetic programming (GP) insert new instructions into programs, they usually draw them uniformly from the available instruction set. Prefering some instructions to others would require additional domain knowledge, which is typically unavailable. However, it has been recently demonstrated that the likelihoods of instructions' occurrence in a program can be reasonably well estimated from its input-output behavior using a neural network. We exploit this idea to bias the choice of instructions used by search operators in GP. Given a large sample of programs and their input-output behaviors, a neural network is trained to predict the presence of individual instructions. When applied to a new program synthesis task, the network is first queried on the set of examples that define the task, and the obtained probabilities determine the frequencies of using instructions in initialization and mutation operators. This priming leads to significant improvements of the odds of successful synthesis on a range of benchmarks.

Advances in Geometric Semantic Genetic Programming (GSGP) have shown that this variant of Genetic Programming (GP) reaches better results than its predecessor for supervised machine learning problems, particularly in the task of symbolic regression. However, by construction, the geometric semantic crossover operator generates individuals that grow exponentially with the number of generations, resulting in solutions with limited use. This paper presents a new method for individual simplification named GSGP with Reduced trees (GSGP-Red). GSGP-Red works by expanding the functions generated by the geometric semantic operators. The resulting expanded function is guaranteed to be a linear combination that, in a second step, has its repeated structures and respective coefficients aggregated. Experiments in 12 real-world datasets show that it is not only possible to create smaller and completely equivalent individuals in competitive computational time, but also to reduce the number of nodes composing them by 58 orders of magnitude, on average.

Genetic programming has been considered as a powerful approach to automated design of production scheduling heuristics in recent years. Flexible and variable representations allow genetic programming to discover very competitive scheduling heuristics to cope with a wide range of dynamic production environments. However, evolving sophisticated heuristics to handle multiple scheduling decisions can greatly increase the search space and poses a great challenge for genetic programming. To tackle this challenge, a new genetic programming algorithm is proposed to incrementally construct the map of explored areas in the search space and adaptively guide the search towards potential heuristics. In the proposed algorithm, growing neural gas and principal component analysis are applied to efficiently generate and update the map of explored areas based on the phenotypic characteristics of evolved heuristics. Based on the obtained map, a surrogate assisted model will help genetic programming determine which heuristics to be explored in the next generation. When applied to evolve scheduling heuristics for dynamic flexible job shop scheduling problems, the proposed algorithm shows superior performance as compared to the standard genetic programming algorithm. The analyses also show that the proposed algorithm can balance its exploration and exploitation better than the existing surrogate-assisted algorithm.

This study considers a resource constrained job scheduling problem. Jobs need to be scheduled on different machines satisfying a due time. If delayed, the jobs incur a penalty which is measured as a weighted tardiness. Furthermore, the jobs use up some proportion of an available resource and hence there are limits on multiple jobs executing at the same time. Due to complex constraints and a large number of decision variables, the existing solution methods, based on meta-heuristics and mathematical programming, are very time-consuming and mainly suitable for small-scale problem instances. We investigate a genetic programming approach to automatically design reusable scheduling heuristics for this problem. A new representation and evaluation mechanisms are developed to provide the evolved heuristics with the ability to effectively construct and refine schedules. The experiments show that the proposed approach is more efficient than other genetic programming algorithms previously developed for evolving scheduling heuristics. In addition, we find that the obtained heuristics can be effectively reused to solve unseen and large-scale instances and often find higher quality solutions compared to algorithms already known in the literature in significantly reduced time-frames.

The redundant mapping from genotype to phenotype is common in evolutionary algorithms, where multiple genotypes can map to the same phenotype. Such a redundancy has been suggested to make an evolutionary system robust as well as evolvable. However, the impact of the redundant genotype-to-phenotype mapping and its resulted robustness and evolvability have not been well characterized quantitatively. In this article, we used a Boolean linear genetic programming system to construct a weighted and directed phenotype network, where vertices are phenotypes and a weighted link represents the number of possible point mutations that can transition genotypes from one phenotype to another. The direction of the links ensures moving from less fit phenotypes to fitter or equally fit ones. We used two fitness functions to investigate how it influences the network structure. Then we employed the Hyperlink-Induced Topic Search (HITS) algorithm to quantitatively characterize the evolvability and accessibility of phenotypes in the network. We found more robust phenotypes are both more evolvable and accessible. Our results help elucidate the effects of redundant mapping and the relationship of robustness, evolvability, and accessibility.

In this paper we provide a broad benchmarking of recent genetic programming approaches to symbolic regression in the context of state of the art machine learning approaches. We use a set of nearly 100 regression benchmark problems culled from open source repositories across the web. We conduct a rigorous benchmarking of four recent symbolic regression approaches as well as nine machine learning approaches from scikit-learn. The results suggest that symbolic regression performs strongly compared to state-of-the-art gradient boosting algorithms, although in terms of running times is among the slowest of the available methodologies. We discuss the results in detail and point to future research directions that may allow symbolic regression to gain wider adoption in the machine learning community.

Estimation of distribution programming (EDP) replaces standard GP variation operators with sampling from a learned probability model. To ensure a minimum amount of variation in a population, EDP adds random noise to the probabilities of random variables. This paper studies the bias of EDP's variation operator by performing random walks. The results indicate that the complexity of the EDP model is high since the model is overfitting the parent solutions when no additional noise is being used. Adding only a low amount of noise leads to a strong bias towards small trees. The bias gets stronger with an increased amount of noise. Our findings do not support the hypothesis that sampling drift is the reason for the loss of diversity.

Furthermore, we suggest using property vectors to study the bias of variation operators. Property vectors can represent the distribution of a population's relevant property, such as tree depth or tree size. The Bhattacharyya coefficient of two property vectors is a measure of the similarity of the two distributions of population properties. The results for EDP and standard GP illustrate that search bias can be assessed by representing distributions using property vectors and measuring their similarity using the Bhattacharyya coefficient.