EuroGP Logo

16th European Conference on Genetic Programming

EuroGP is the premier annual conference on Genetic Programming, the oldest and the only meeting worldwide devoted specifically to this branch of evolutionary computation. It is always a very enjoyable event attracting participants from all continents, offering excellent opportunities for networking, informal contact, exchange of ideas and discussions with fellow researchers in a friendly and relaxed setting.

Accepted Papers

High quality papers describing new original research are sought on topics strongly related to the evolution of computer programs, ranging from theoretical work to innovative applications. The conference will feature a mixture of oral presentations and poster sessions. In 2012, EuroGP acceptance rate was 50% (39% for oral presentations).

Areas of Interest and Contributions

Topics include but are not limited to:

Publication Details

Accepted papers will be presented orally or as posters at the Conference and will be printed in the proceedings published by Springer Verlag in the Lecture Notes in Computer Science (LNCS) series.

Previous editions of EuroGP were published in the following Springer Verlag LNCS volumes

The papers which receive the best reviews will be nominated for the Best Paper Award.

Special Joint Session

EuroGP encourages submissions applying genetic programming to problems in computational biology and, conversely, new biologically inspired extensions of the genetic programming framework for a special joint session of EuroGP with . These papers can be submitted either to EuroGP or .

Submission Details

Submissions must be original and not published elsewhere. They will be peer reviewed by at least three members of the program committee. The reviewing process will be double-blind, so please omit information about the authors in the submitted paper. Submit your manuscript in Springer LNCS format to http://myreview.csregistry.org/eurogp13/. Page limit: 12 pages

The authors of accepted papers will have to improve their paper on the basis of the reviewers’ comments and will be asked to send a camera ready version of their manuscripts. At least one author of each accepted work has to register for the conference, attend the conference and present the work.

Important Dates

Submission deadline: 1 November 2012 Extended to 11 November 2012
Conference dates: 3-5 April 2013

Programme Committee (to be confirmed)

Further Information

A comprehensive bibliography of genetic programming literature and links to related material is accessible at the Genetic Programming Bibliography web page, part of the Collection of Computer Science Bibliographies maintained and managed by William Langdon, Steven Gustafson, and John Koza.

Genetic Programming Algorithms

EuroGP Accepted Papers

EuroGP TALKS

Adaptive Distance Metrics for Nearest Neighbour Classification based on Genetic Programming
Alexandros Agapitos, Michael O'Neill, Anthony Brabazon
Nearest Neighbour (NN) classification is a widely-used, effective method for both binary and multi-class problems. It relies on the assumption that class conditional probabilities are locally constant. However, this assumption becomes invalid in high dimensions, and severe bias can be introduced, which degrades the performance of the method. The employment of a locally adaptive distance metric becomes crucial in order to keep class conditional probabilities approximately uniform, whereby better classification performance can be attained. This paper presents a locally adaptive distance metric for NN classification based on a supervised learning algorithm (Genetic Programming) that learns a vector of feature weights for the features composing an instance query. Using a weighted Euclidean distance metric, this has the effect of adaptive neighbourhood shapes to query locations, stretching the neighbourhood along the directions for which the class conditional probabilities don't change much. Initial empirical results on a set of real-world classification datasets showed that the proposed method enhances the generalisation performance of standard NN algorithm, and that it is a competent method for pattern classification as compared to other learning algorithms.

-------------------------------------------------------------------------

Controlling Bloat through Parsimonious Elitist Replacement and Spatial Structure (EuroGP Best Paper Candidate)
Grant Dick, Peter Whigham
The concept of bloat --- the increase of program size without a corresponding increase in fitness --- presents a significant drawback to the application of genetic programming. One approach to controlling bloat, dubbed spatial structure with elitism (SS+E), uses a combination of spatial population structure and local elitist replacement to implicitly constrain unwarranted program growth. However, the default implementation of SS+E uses a replacement scheme that prevents the introduction of smaller programs in the presence of equal fitness. This paper introduces a modified SS+E approach in which replacement is done under a lexicographic parsimony scheme. The proposed model, spatial structure with lexicographic parsimonious elitism (SS+LPE), exhibits an improvement in bloat reduction and, in some cases, more effectively searches for fitter solutions.


-------------------------------------------------------------------------

Generation of VNS Components with Grammatical Evolution for Vehicle Routing
John Drake, Nikolaos Kililis, Ender Özcan
The vehicle routing problem (VRP) is a family of problems whereby a fleet of vehicles must service the commodity demands of a set of geographically scattered customers from one or more depots, subject to a number of constraints. Early hyper-heuristic research focussed on selecting and applying a low-level heuristic at a given stage of an optimisation process. Recent trends have led to a number of approaches being developed to automatically generate heuristics for a number of combinatorial optimisation problems. Previous work on the VRP has shown that the application of hyper-heuristic approaches can yield successful results. In this paper we investigate the potential of grammatical evolution as a method to evolve the components of a variable neighbourhood search (VNS) framework. In particular two components are generated; constructive heuristics to create initial solutions and neighbourhood move operators to change the state of a given solution. The proposed method is tested on standard benchmark instances of two common VRP variants.


-------------------------------------------------------------------------

Understanding Expansion Order and Phenotypic Connectivity in piGE
David Fagan, Erik Hemberg, Michael O'Neill, Sean McGarraghy
Since its inception, piGE has used evolution to guide the order of how to construct derivation trees. It was hypothesised that this would allow evolution to adjust the order of expansion during the run and thus help with search. This research aims to identify if a specific order is reachable, how reachable it may be, and goes on to investigate what happens to the expansion order during a piGE run. It is concluded that within piGE we do not evolve towards a specific order but a rather distribution of orders. The added complexity that an evolvable order gives piGE can make it difficult to understand how it can effectively search, by examining the connectivity of the phenotypic landscape it is hoped to understand this. It is concluded that the addition of an evolvable derivation tree expansion order makes the phenotypic landscape associated with piGE very densely connected, with solutions now linked via a single mutation event that were not previously connected.


-------------------------------------------------------------------------

PhenoGP: Combining Programs to Avoid Code Disruption
Cyril Fonlupt, Denis Robilliard
In conventional Genetic Programming (GP), n programs are simultaneously evaluated and only the best programs will survive from one generation to the next. It is a pity as some programs might contain useful code that might be hidden or not evaluated due to the
presence of introns. For example in regression, 0 * (perfect code) will unfortunately not be assigned a good fitness and this program might be discarded due to the evolutionary process. In this paper, we develop a new form of GP called PhenoGP (PGP). PGP individuals consist of ordered lists of programs to be executed in which the ultimate goal is to find the best order from simple building-blocks programs. If the fitness remains stalled during the run, new building-blocks programs are generated. PGP seems to compare fairly well with canonical GP.


-------------------------------------------------------------------------

Reducing Wasted Evaluations in Cartesian Genetic Programming
Brian Goldman, William Punch
Cartesian Genetic Programming (CGP) is a form of Genetic Programming (GP) where a large proportion of the genome is identifiably unused by the phenotype. This can lead mutation to create offspring that are genotypically different but phenotypically identical, and therefore do not need to be evaluated. We investigate theoretically and empirically the effects of avoiding these otherwise wasted evaluations, and provide evidence that doing so reduces the median number of evaluations to solve four benchmark problems, as well as reducing CGP's sensitivity to the mutation rate. The similarity of results across the problem set in combination with the theoretical conclusions supports the general need for avoiding these unnecessary evaluations.


-------------------------------------------------------------------------

Balancing Learning and Overfitting in Genetic Programming with Interleaved Sampling of Training Data (EuroGP Best Paper Candidate)
Ivo Gonçalves, Sara Silva
Generalization is the ability of a model to perform well on cases not seen during the training phase. In Genetic Programming generalization has recently been recognized as an important open issue, and increased efforts are being made towards evolving models that do not overfit. In this work we expand on recent developments that showed that using a small and frequently changing subset of the training data is effective in reducing overfitting and improving generalization. Particularly, we build upon the idea of randomly choosing a single training instance at each generation and balance it with periodically using all training data. The motivation for this approach is based on trying to keep overfitting low (represented by using a single training instance) and still presenting enough information so that a general pattern can be found (represented by using all training data). We propose two approaches called interleaved sampling and random interleaved sampling that respectively represent doing this balancing in a deterministic or a probabilistic way. Experiments are conducted on three high-dimensional real-life datasets on the pharmacokinetics domain. Results show that most of the variants of the proposed approaches are able to consistently improve generalization and reduce overfitting when compared to standard Genetic Programming. The best variants are even able of such improvements on a dataset where a recent and representative state-of-the-art method could not. Furthermore, the resulting models are short and hence easier to interpret, an important achievement from the applications' point of view.


-------------------------------------------------------------------------


Automated Design of Probability Distributions as Mutation Operators for Evolutionary Programming Using Genetic Programming
Libin Hong, John Woodward, Jingpeng Li, Ender Özcan
The mutation operator is the only source of variation in Evolutionary Programming. In the past these have been human nominated and included the Gaussian,Cauchy,and the Levy distributions. We automatically design mutation operators (probability distributions) using Genetic Programming. This is done by using a standard Gaussian random number generator as the terminal set and and basic arithmetic operators as the function set. In other words, an arbitrary random number generator is a function of a randomly (Gaussian) generated number passed through an arbitrary function generated by Genetic Programming. Rather than engaging in the futile attempt to develop mutation operators for arbitrary benchmark functions (which is a consequence of the No Free Lunch theorems), we consider tailoring mutation operators for particular function classes. We draw functions from a function class (a probability distribution over a set of functions). The mutation probability distribution is trained on a set of function instances drawn from a given function class. It is then tested on a separate independent test set of function instances to confirm that the evolved probability distribution has indeed generalized to the function class. Initial results are highly encouraging: on each of the ten function classes the probability distributions generated using Genetic Programming outperform both the Gaussian and Cauchy distributions.

-------------------------------------------------------------------------

Robustness and Evolvability of Recombination in Linear Genetic Programming
Ting Hu, Jason H. Moore, Wolfgang Banzhaf
The effect of neutrality on evolutionary search has been recognized to be crucially dependent on its distribution at the phenotypic level. Quantitatively characterizing robustness and evolvability in genotype and phenotype spaces greatly helps to understand the influence of neutrality on Genetic Programming. Most existing robustness and evolvability studies focus on mutations with a lack of investigation of recombinational operations. Here, we extend a previously proposed quantitative approach of measuring mutational robustness and evolvability in Linear GP. By considering a simple LGP system that has a compact representation and enumerable genotype and phenotype spaces, we quantitatively characterize the robustness and evolvability of recombination at the phenotypic level. In this simple yet representative LGP system, we show that recombinational properties are correlated with mutational properties. Utilizing a population evolution experiment, we demonstrate that recombination significantly accelerates the evolutionary search process and particularly promotes robust phenotypes for innovative phenotypic explorations.

-------------------------------------------------------------------------

On the Evolvability of a hybrid Ant Colony-Cartesian Genetic Programming Methodology
Sweeney Luis, Marcus Vinicius dos Santos
A method that uses Ant Colonies as a Model-based Search to Cartesian Genetic Programming (CGP) to induce computer programs is presented. Candidate problem solutions are encoded using a CGP representation. Ants generate problem solutions guided by pheromone traces of entities and nodes of the CGP representation. The pheromone values are updated based on the paths followed by the best ants, as suggested in the Rank-Based Ant System. To assess the evolvability of the system we applied a modifed version of a method introduced to measure rate of evolution. Our results show that such method effectively reveals how evolution proceeds under different parameter settings. The proposed hybrid architecture shows high evolvability in a dynamic environment by maintaining a pheromone model that elicits high genotype diversity.

-------------------------------------------------------------------------

Discovering Subgroups by means of Genetic Programming
José M. Luna, José R. Romero, Cristóbal Romero, Sebastián Ventura
This paper deals with the problem of discovering subgroups in data by means of a grammar guided genetic programming algorithm, each subgroup including a set of related patterns. The proposed algorithm combines the requirements of discovering comprehensible rules with the ability of mining expressive and flexible solutions thanks to the use of a context-free grammar. A major characteristic of this algorithm is the small number of parameters required, so the mining process is easy for end-users. The algorithm proposed is compared with existing subgroup discovery evolutionary algorithms. The experimental results reveal the excellent behaviour of this algorithm, discovering comprehensible subgroups and behaving better than the other algorithms. The conclusions obtained were reinforced through a series of non-parametric tests.

-------------------------------------------------------------------------

Program Optimisation with Dependency Injection
James McDermott, Paula Carroll
For many real-world problems, there exist non-deterministic heuristics which generate valid but possibly sub-optimal solutions. The program optimisation with dependency injection method, introduced here, allows such a heuristic to be placed under evolutionary control, allowing search for the optimum. Essentially, the heuristic is "fooled" into using a genome, supplied by a genetic algorithm, in place of the output of its random number generator. The method is demonstrated with generative heuristics in the domains of 3D design and communications network design. It is also used in novel approaches to genetic programming.

-------------------------------------------------------------------------

Searching for Novel Classifiers
Enrique Naredo, Leonardo Trujillo, Yuliana Martínez
Natural evolution is an open-ended search process without an a priori fitness function that needs to be optimized. On the other hand, evolutionary algorithms (EAs) rely on a clear and quantitative objective. The Novelty Search algorithm (NS) substitutes fitness-based selection with a \emph{novelty} criteria; i.e., individuals are chosen based on their uniqueness. To do so, individuals are described by the behaviors they exhibit, instead of their phenotype or genetic content. NS has mostly been used in evolutionary robotics, where the concept of behavioral space can be clearly defined. Instead, this work applies NS to a more general problem domain, classification. To this end, two behavioral descriptors are proposed, each describing a classifier's performance from two different perspectives. Experimental results show that NS-based search can be used to derive effective classifiers. In particular, NS is best suited to solve difficult problems, where exploration needs to be encouraged and maintained.

-------------------------------------------------------------------------

Learning Reusable Initial Solutions for Multi-objective Order Acceptance and Scheduling Problems with Genetic Programming (EuroGP Best Paper Candidate)
Su Nguyen, Mengjie Zhang, Mark Johnston, Kay Chen Tan
Order acceptance and scheduling (OAS) is an important issue in make-to-order production systems that decides the set of orders to accept and the sequence in which these accepted orders are processed to increase total revenue and improve customer satisfaction. This paper aims to explore the Pareto fronts of trade-off solutions for a multi-objective OAS problem. Due to its complexity, solving this problem is challenging. A two-stage learning/optimising (2SLO) system is proposed in this paper to solve the problem. The novelty of this system is the use of genetic programming to evolve a set of scheduling rules that can be reused to initialise populations of an evolutionary multi-objective optimisation (EMO) method. The computational results show that 2SLO is more effective than the pure EMO method. Regarding maximising the total revenue, 2SLO is also competitive as compared to other optimisation methods in the literature.


-------------------------------------------------------------------------

Automated Problem Decomposition for the Boolean Domain with Genetic Programming (EuroGP Best Paper Candidate)
Fernando Otero, Colin Johnson
Researchers have been interested in exploring the regularities and modularity of the problem space in genetic programming (GP) with the aim of decomposing the original problem into several smaller subproblems. The main motivation is to allow GP to deal with more complex problems. Most previous works on modularity in GP emphasise the structure of modules used to encapsulate code and/or promote code reuse, instead of in the decomposition of the original problem. In this paper we propose a problem decomposition strategy that allows the use of a GP search to find solutions for subproblems and combine the individual solutions into the complete solution to the problem.


-------------------------------------------------------------------------


A Multi-objective Optimization Energy Approach to Predict the Ligand Conformation in a Docking Process (EuroGP Best Paper Candidate)
Angelica Sandoval-Perez, David Becerra, Diana Vanegas, Daniel Restrepo-Montoya,
Fernando Nino
This work proposes a multi-objective algorithmic method for modeling the prediction of the conformation and configuration of ligands in receptor-ligand complexes by considering energy contributions of molecular interactions. The proposed approach is an improvement over others in the field, where the principle insight is that a Pareto front helps to understand the tradeoffs in the actual problem. The method is based on three main features: (i) Representation of molecular data using a trigonometric model; (ii) Modeling of molecular interactions with all-atoms force field energy functions and (iii) Exploration of the conformational space through a multi-objective evolutionary algorithm. The performance of the proposed model was evaluated and validated over a set of well known complexes. The method showed a promising performance when predicting ligands with high number of rotatable bonds.


-------------------------------------------------------------------------

Semantic Bias in Program Coevolution
Tom Seaton, Julian F. Miller, Tim Clarke
We investigate two pathological coevolutionary behaviours, disengagement and cycling, in GP systems. An empirical analysis is carried out over constructed GP problems and the Game of Tag, a historical pursuit and evasion task. The effects of semantic bias on the occurrence of pathologies and consequences for performance are examined in a coevolutionary context. We present findings correlating disengagement with semantic locality of the genotype to phenotype map using a minimal competitive coevolutionary algorithm.


-------------------------------------------------------------------------

A New Implementation of Geometric Semantic GP and its Application to Problems in Pharmacokinetics (EuroGP Best Paper Candidate)
Leonardo Vanneschi, Mauro Castelli, Luca Manzoni, Sara Silva
Moraglio et al. have recently introduced new genetic operators for genetic programming, called geometric semantic operators. These operators induce a unimodal fitness landscape for all the problems consisting in matching input data with known target outputs (like regression and classification). This feature facilitates genetic programming evolvability, which makes these operators extremely promising. Nevertheless, Moraglio et al. leave open problems, the most important one being the fact that these operators, by construction, always produce offspring that are larger than their parents, causing an exponential growth in the size of the individuals, which actually renders them useless in practice. In this paper we overcome this limitation by presenting a new efficient implementation of the geometric semantic operators. This allows us, for the first time, to use them on complex real-life applications, like the two problems in pharmacokinetics that we address here. Our results confirm the excellent evolvability of geometric semantic operators, demonstrated by the good results obtained on training data. Furthermore, we have also achieved a surprisingly good generalization ability, a fact that can be explained considering some properties of geometric semantic operators, which makes them even more appealing than before.


EuroGP POSTERS

Examining the Diversity Property of Semantic Similarity based Crossover
Tuan Anh Pham, Quang Uy Nguyen, Xuan Hoai Nguyen, Michael O'Neill
Population diversity has long been seen as a crucial factor for the efficiency of Evolutionary Algorithms in general, and Genetic Programming (GP) in particular. This paper experimentally investigates the diversity property of a recently proposed crossover, Semantic Similarity based Crossover (SSC). The results show that while SSC helps to improve locality, it leads to the loss of diversity of the population. This could be the reason that sometimes SSC fails in achieving superior performance when compared to standard subtree crossover. Consequently, we introduce an approach to maintain the population diversity by combining SSC with a multi-population approach. The experimental results show that this combination maintains better population diversity, leading to further improvement in GP performance. Further SSC parameters tuning to promote diversity gains even better results.

-------------------------------------------------------------------------

How Early and with How Little Data? Using Genetic Programming to Evolve Endurance Classifiers for MLC NAND Flash Memory
Damien Hogan, Tom Arbuckle, Conor Ryan
Despite having a multi-billion dollar market and many operational advantages, Flash memory suffers from a serious drawback, that is, the gradual degradation of its storage locations through use. Manufacturers currently have no method to predict how long they will function correctly, resulting in extremely conservative longevity specifications being placed on Flash devices. We leverage the fact that the durations of two crucial Flash operations, program and erase, change as the chips age. Their timings, recorded at intervals early in chips' working lifetimes, are used to predict whether storage locations will function correctly after given numbers of operations. We examine how early and with how little data such predictions can be made. Genetic Programming, employing the timings as inputs, is used to evolve binary classifiers that achieve up to a mean of 97.88% correct classification. This technique displays huge potential for real-world application, with resulting savings for manufacturers.

-------------------------------------------------------------------------

Asynchronous Evaluation based Genetic Programming: Comparison of Asynchronous and Synchronous Evaluation and its Analysis
Tomohiro Harada, Keiki Takadama
This paper compares an asynchronous evaluation based GP with a synchronous evaluation based GP to investigate the evolution ability of an asynchronous evaluation on the GP domain. As an asynchronous evaluation based GP, this paper focuses on Tierra-based Asynchronous GP we have proposed, which is based on a biological evolution simulator, Tierra. The intensive experiment compares TAGP with simple GP by applying them to a symbolic regression problem, and it is revealed that an asynchronous evaluation based GP has better evolution ability than a synchronous one.


-------------------------------------------------------------------------


Global Top-Scoring Pair Decision Tree for Gene Expression Data Analysis
Marcin Czajkowski, Marek Kretowski
Extracting knowledge from gene expression data is still a major challenge. Relative expression algorithms use the ordering relationships for a small collection of genes and are successfully applied for micro-array classification. However, searching for all possible subsets of genes requires a significant number of calculations, assumptions and limitations. In this paper we propose an evolutionary algorithm for global induction of top-scoring pair decision trees. We have designed several specialized genetic operators that search for the best tree structure and the splits in internal nodes which involve pairwise comparisons of the gene expression values. Preliminary validation performed on real-life micro-array datasets is promising as the proposed solution is highly competitive to other relative expression algorithms and allows exploring much larger solution space.


-------------------------------------------------------------------------


A Grammar-Guided Genetic Programming Algorithm for Multi-Label Classification
Alberto Cano, Amelia Zafra, Eva L. Gibaja, Sebastián Ventura
Multi-label classification is a challenging problem which demands new knowledge discovery methods. This paper presents a Grammar-Guided Genetic Programming algorithm for solving multi-label classification problems using IF-THEN classification rules. This algorithm, called G3P-ML, is evaluated and compared to other multi-label classification techniques in different application domains. Computational experiments show that G3P-ML often obtains better results than other algorithms while achieving a lower number of rules than the other methods.