Evostar 2015

• EuroGP
  
• EvoCOP
  
• EvoMUSART
  
• EvoApplications
  
  
  • EvoBIO
  • EvoCOMNET
  • EvoCOMPLEX
  • EvoENERGY
  • EvoFIN
  • EvoGAMES
  • EvoIASP
  • EvoINDUSTRY
  • EvoNUM
  • EvoPAR
  • EvoRISK
  • EvoROBOT
  • EvoSTOC
  EvoStar Best Paper Candidates
  EvoStar Best Paper Awards 2015
  

18th European Conference on Genetic Programming

• Accepted paper abstracts
• Best Paper Nominees
• Download EuroGP programme

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 environment. 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 2014, the EuroGP acceptance rate was 50% (37.5% for oral presentations).

Areas of Interest and Contributions

Topics include but are not limited to:

• Innovative applications of GP
• Theoretical developments
• GP performance and behaviour
• Fitness landscape analysis of GP
• Algorithms, representations and operators
• Real-world applications
• Search-based software engineering
• GP for program improvement
• Evolutionary design
• Evolutionary robotics
• Tree-based GP and Linear GP
• Graph-based GP and Grammar-based GP
• Evolvable hardware
• Self-reproducing programs
• Multi-population GP
• Multi-objective GP
• Fast/Parallel GP
• Probabilistic GP
• Evolution of automata or machine
• Software Engineering and GP
• Object-oriented GP
• Hybrid architectures including GP
• Coevolution in GP
• Modularity in GP
• Semantics in GP
• Unconventional evolvable computation
• Automatic software maintenance
• Evolutionary inductive programming

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.

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.

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.

Submission link: http://myreview.csregistry.org/eurogp15

Programme Committee

• Aniko Ekart, Aston University, United Kingdom
• Alberto Moraglio, University of Exeter
• Antonio Della Cioppa, University of Salerno, Italy
• Andrew J. Parkes, University of Nottingham
• Alexandros Agapitos, University College Dublin
• Alexei N. Skurikhin, Los Alamos National Laboratory, USA
• Lee Altenberg, BioSystems, Elsevier Journal
• Anthony Brabazon, University College Dublin, Ireland
• R. Muhammad Atif Azad, University of Limerick, Ireland
• Wolfgang Banzhaf, Memorial University of Newfoundland, Canada
• Colin Johnson, University of Kent, England
• Stefano Cagnoni, University of Parma, Italy
• Christian Gagné, Université Laval, Québec, Canada
• Conor Ryan, University of Limerick, Ireland
• Ignacio Arnaldo, MIT, USA
• Douglas Augusto, LNCC/UFJF, Brazil
• Heder Bernardino, LNCC/UFJF, Brazil
• Andrew McIntyre, Dalhousie University, Canada
• Tomasz Pawlak, Poznan University of Technology, Poland
• Peter Rockett, University of Sheffield, UK
• Luis Da Costa, Université Paris-Sud XI, France
• David Jackson, University of Liverpool, UK
• Erik Hemberg, MIT, USA
• Ernesto Tarantino, ICAR-CNR, Italy
• Ernesto Costa, University of Coimbra, Portugal
• William B. Langdon, University of Essex, UK
• Evelyne Lutton, INRIA, France
• Ender Ozcan, University of Nottingham
• Fernando Otero, University of Kent
• Francisco Fernandez de Vega, Universidad de Extremadura, Spain
• Federico Divina, Pablo de Olavide University, Spain
• Gianluigi Folino, ICAR-CNR, Italy
• James Foster, University of Idaho
• Gisele Pappa, Universidade Federal de Minas Gerais, Brasil
• Graham Kendall, Uiversity of Nottingham, UK
• Jin-Kao Hao, LERIA, University of Angers, France
• Helio Barbosa, LNCC & UFJF, Brazil
• Jan Koutnik, IDSIA, Switzerland
• Inman Harvey, University of Sussex, UK
• Ivan Tanev, Doshisha University, Japan
• Jorn Mehnen, Cranfield University, UK
• James McDermott, Massachusetts Institute of Technology
• Julian Miller, University of York, UK
• John Levine, University of Strathclyde
• Jorge Tavares, Microsoft
• Ahmed Kattan, Loughborough University, UK
• Krzysztof Krawiec, Poznan University of Technology, Poland
• Kwong Sak Leung, The Chinese University of Hong Kong, Hong Kong
• Jiri Kubalik, Czech Technical University in Prague, Czech Republic
• Leonardo Trujillo, Instituto Tecnológico de Tijuana, Mexico
• Lidia Yamamoto, University of Strasbourg, France
• Lee Spector, Hampshire College, USA
• Michael O'Neill, University College Dublin
• Penousal Machado, University of Coimbra, Portugal
• Marc Ebner, Universität Greifswald, Germany
• Marc Schoenauer, INRIA, France
• Radek Matousek, Brno University of Technology, Czech Republic
• Mengjie Zhang, Victoria University of Wellington, New Zealand
• Malcolm Heywood, Dalhousie University, Canada
• Miguel Nicolau, NCRA, UCD, Ireland
• Michael Korns, Korns Associates
• Man Leung Wong, Lingnan University, Hong Kong
• Mohamed Bahy Bader, University of Portsmouth
• Nicolas Bredeche, Univ. Pierre et Marie Curie
• Julio Cesar Nievola, PUCPR - Pontificia Universidade Catolica do Parana, Brazil
• Xuan Hoai Nguyen, Hanoi University, Vietnam
• Clara Pizzuti, Institute for High Performance Computing and Networking
• Bob McKay, Seoul National University, Korea
• Denis Robilliard, Univ Lille Nord de France
• Sara Silva, INESC-ID Lisboa, Portugal
• Lukas Sekanina, Brno University of Technology, Czech Republic
• Yin Shan, Medicare Australia
• Moshe Sipper, Ben-Gurion University, Israel
• Steven Gustafson, GE Global Research, USA
• Tatiana Kalganova, Brunel University, United Kingdom
• Ting Hu, Dartmouth College
• Thomas Ray, University of Oklahoma, USA
• Terence Soule, University of Idaho, USA
• Una-May OReilly, MIT, USA
• Leonardo Vanneschi, University Milano-Bicocca

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.

EuroGP abstracts

The Effect of Distinct Geometric Semantic Crossover Operators in Regression Problems
Julio Albinati, Gisele L. Pappa, Fernando E. B. Otero, Luiz Otávio V. B. Oliveira
This paper investigates the impact of geometric semantic crossover operators in a wide range of symbolic regression problems. First, it analyses the impact of using Manhattan and Euclidean distance geometric semantic crossovers in the learning process. Then, it proposes two strategies to numerically optimize the crossover mask based on mathematical properties of these operators, instead of simply generating them randomly. An experimental analysis comparing geometric semantic crossovers using Euclidean and Manhattan distances and the proposed strategies is performed in a test bed of twenty datasets. The results show that the use of different distance functions in the semantic geometric crossover has little impact on the test error, and that our optimized crossover masks yield slightly better results. For SGP practitioners, we suggest the use of the semantic crossover based on the Euclidean distance, as it achieved similar results to those obtained by more complex operators.

Learning Text Patterns using Separate-and-Conquer Genetic Programming
Alberto Bartoli, Andrea De Lorenzo, Eric Medvet, Fabiano Tarlao
The problem of extracting knowledge from large volumes of unstructured textual information has become increasingly important. We consider the problem of extracting text slices that adhere to a syntactic pattern and propose an approach capable of generating the desired pattern automatically, from a few annotated examples. Our approach is based on Genetic Programming and generates extraction patterns in the form of regular expressions that may be input to existing engines without any post-processing. Key feature of our proposal is its ability of discovering automatically whether the extraction task may be solved by a single pattern, or rather a set of multiple patterns is required. We obtain this property by means of a separate-and-conquer strategy: once a candidate pattern provides adequate performance on a subset of the examples, the pattern is inserted into the set of final solutions and the evolutionary search continues on a smaller set of examples including only those not yet solved adequately. Our proposal outperforms an earlier state-of-the-art approach on three challenging datasets.

Improving Geometric Semantic Genetic Programming with Safe Tree Initialisation
Grant Dick
Researchers in genetic programming (GP) are increasingly looking to semantic methods to increase the efficacy of search. Semantic methods aim to increase the likelihood that a structural change made in an individual will be correlated with a change in behaviour. Recent work has promoted the use of geometric semantic methods, where offspring are generated within a bounded interval of the parents' behavioural space. Extensions of this approach use random trees wrapped in logistic functions to parameterise the blending of parents. This paper identifies limitations in the logistic wrapper approach, and suggests an alternative approach based on safe initialisation using interval arithmetic to produce offspring. The proposed method demonstrates greater search performance than using a logistic wrapper approach, while maintaining an ability to produce offspring that exhibit good generalisation capabilities.

On the Generalization Ability of Geometric Semantic Genetic Programming
Ivo Gonçalves, Sara Silva, Carlos M. Fonseca
Geometric Semantic Genetic Programming (GSGP) is a recently proposed form of Genetic Programming (GP) that searches directly the space of the underlying semantics of the programs. The fitness landscape seen by the GSGP variation operators is unimodal with a linear slope by construction and, consequently, easy to search. Despite this advantage, the offspring produced by these operators grow very quickly. A new implementation of the same operators was proposed that computes the semantics of the offspring without having to explicitly build their syntax. This allowed GSGP to be used for the first time in real-life multidimensional datasets. GSGP presented a surprisingly good generalization ability, which was justified by some properties of the geometric semantic operators. In this paper, we show that the good generalization ability of GSGP was the result of a small implementation deviation from the original formulation of the mutation operator, and that without it the generalization results would be significantly worse. We explain the reason for this difference, and then we propose two variants of the geometric semantic mutation that deterministically and optimally adapt the mutation step. They reveal to be more efficient in learning the training data, and they also achieve a competitive generalization in only a single operator application. This provides a competitive alternative when performing semantic search, particularly since they produce small individuals and compute fast.

Automatic Derivation of Search Objectives for Test-Based Genetic Programming
Krzysztof Krawiec, Paweł Liskowski
In genetic programming (GP), programs are usually evaluated by applying them to tests, and fitness function indicates only how many of them have been passed. We posit that scrutinizing the outcomes of programs' interactions with individual tests may help making program synthesis more effective. To this aim, we propose DOC, a method that autonomously derives new search objectives by clustering the outcomes of interactions between programs in the population and the tests. The derived objectives are subsequently used to drive the selection process in a single- or multiobjective fashion. An extensive experimental assessment on 15 discrete program synthesis tasks representing two domains shows that DOC significantly outperforms conventional GP and implicit fitness sharing.

Evolutionary Design of Transistor Level Digital Circuits using Discrete Simulation
Vojtech Mrazek, Zdenek Vasicek
The objective of the paper is to introduce a new approach to the evolutionary design of digital circuits conducted directly at transistor level. In order to improve the time consuming evaluation of candidate solutions, a discrete event-driven simulator was introduced. The proposed simulator operates on multiple logic levels to achieve reasonable trade-off between performance and precision. A suitable level of abstraction reflecting the behaviour of real MOSFET transistors is utilized to minimize the production of incorrectly working circuits. The proposed approach is evaluated in the evolution of basic logic circuits having more than 20 transistors. The goal of the evolutionary algorithm is to design a circuit having the minimal number of transistors and exhibiting the minimal delay. In addition to that, various parameter settings are investigated to increase the success rate of the evolutionary design.

M3GP - Multiclass Classification with GP
Luis Muñoz, Sara Silva, Leonardo Trujillo
Data classification is one of the most ubiquitous machine learning tasks in science and engineering. However, Genetic Programming is still not a popular classification methodology, partially due to its poor performance in multiclass problems. The recently proposed M2GP - Multidimensional Multiclass Genetic Programming algorithm achieved promising results in this area, by evolving mappings of the p-dimensional data into a d-dimensional space, and applying a minimum Mahalanobis distance classifier. Despite good performance, M2GP employs a greedy strategy to set the number of dimensions d for the transformed data, and fixes it at the start of the search, an approach that is prone to locally optimal solutions. This work presents the M3GP algorithm, that stands for M2GP with multidimensional populations. M3GP extends M2GP by allowing the search process to progressively search for the optimal number of new dimensions d that maximize the classification accuracy. Experimental results show that M3GP can automatically determine a good value for d depending on the problem, and achieves excellent performance when compared to state-of-the-art-methods like Random Forests, Random Subspaces and Multilayer Perceptron on several benchmark and real-world problems.

Evolving Ensembles of Dispatching Rules using Genetic Programming for Job Shop Scheduling
John Park, Su Nguyen, Mengjie Zhang, Mark Johnston
Job shop scheduling (JSS) problems are important optimisation problems that have been studied extensively in the literature due to their applicability and computational difficulty. This paper considers static JSS problems with makespan minimisation, which are NP-complete for more than two machines. Because finding optimal solutions can be difficult for large problem instances, many heuristic approaches have been proposed in the literature. However, designing effective heuristics for different JSS problem domains is difficult. As a result, hyper-heuristics (HHs) have been proposed as an approach to automating the design of heuristics. The evolved heuristics have mainly been priority based dispatching rules (DRs). To improve the robustness of evolved heuristics generated by HHs, this paper proposes a new approach where an ensemble of rules are evolved using Genetic Programming (GP) and cooperative coevolution, denoted as Ensemble Genetic Programming for Job Shop Scheduling (EGP-JSS). The results show that EGP-JSS generally produces more robust rules than the single rule GP.

Attributed Grammatical Evolution using Shared Memory Spaces and Dynamically Typed Semantic Function Specification
James Vincent Patten, Conor Ryan
In this paper we introduce a new Grammatical Evolution (GE) system designed to support the specification of problem semantics in the form of attribute grammars (AG). We discuss the motivations behind our system design, from its use of shared memory spaces for attribute storage to the use of a dynamically type programming language, Python, to specify grammar semantics. After a brief analysis of some of the existing GE AG system we outline two sets of experiments carried out on four symbolic regression type (SR) problems. The first set using a context free grammar (CFG) and second using an AG. After presenting the results of our experiments we highlight some of the potential areas for future performance improvements, using the new functionality that access to Python interpreter and storage of attributes in shared memory space provides.

Indirectly Encoded Fitness Predictors Coevolved with Cartesian Programs
Michaela Sikulova, Jiri Hulva, Lukas Sekanina
We investigate coevolutionary Cartesian genetic programming that coevolves fitness predictors in order to diminish the number of target objective vector (TOV) evaluations, needed to obtain a satisfactory solution, to reduce the computational cost of evolution. This paper introduces the use of coevolution of fitness predictors in CGP with a new type of indirectly encoded predictors. Indirectly encoded predictors are operated using the CGP and provide a variable number of TOVs used for solution evaluation during the coevolution. It is shown in 5 symbolic regression problems that the proposed predictors are able to adapt the size of TOVs array in response to a particular training data set.

Tapped Delay Lines for GP Streaming Data Classification with Label Budgets
Ali Vahdat, Jillian Morgan, Andrew R. McIntyre, Malcolm I. Heywood, A. Nur Zincir-Heywood
Streaming data classification requires that a model be available for classifying stream content while simultaneously detecting and reacting to changes to the underlying process generating the data. Given that only a fraction of the stream is `visible' at any point in time (i.e. some form of window interface) then it is difficult to place any guarantee on a classifier encountering a `well mixed' distribution of classes across the stream. Moreover, streaming data classifiers are also required to operate under a limited label budget (labelling all the data is too expensive). We take these requirements to motivate the use of an active learning strategy for decoupling genetic programming training epochs from stream throughput. The content of a data subset is controlled by a combination of Pareto archiving and stochastic sampling. In addition, a significant benefit is attributed to support for a tapped delay line (TDL) interface to the stream, but this also increases the dimensionality of the task. We demonstrate that the benefits of assuming the TDL can be maintained through the use of oversampling without recourse to additional label information. Benchmarking on 4 dataset demonstrates that the approach is particularly effective when reacting to shifts in the underlying properties of the stream. Moreover, an online formulation for class-wise detection rate is assumed, where this is able to robustly characterize classifier performance throughout the stream.

Cartesian GP in Optimization of Combinational Circuits with Hundreds of Inputs and Thousands of Gates
Zdenek Vasicek
A new approach to the evolutionary optimization of large digital circuits is introduced in this paper. In contrast with evolutionary circuit design, the goal of the evolutionary circuit optimization is to minimize the number of gates (or other non-functional parameters) of already functional circuit. The method combines a circuit simulation with a formal verification in order to detect the functional inequivalence of the parent and its offspring. An extensive set of 100 benchmarks circuits is used to evaluate the performance of the method as well as the utilized evolutionary approach. Moreover, the role of neutral mutations in the context of evolutionary optimization is investigated. In average, the method enabled a 34% reduction in gate count even if the optimizer was executed only for 15 minutes.

EuroGP POSTERS abstracts

Genetic Programming for Feature Selection and Question-Answer Ranking in IBM Watson
Urvesh Bhowan, D. J. McCloskey
IBM Watson is an intelligent open-domain question answering system capable of finding correct answers to natural language questions in real-time. Watson uses machine learning over a large heterogeneous feature set derived from many distinct natural language processing algorithms to identify correct answers. This paper develops a Genetic Programming (GP) approach for feature selection in Watson by evolving ranking functions to order candidate answers generated in Watson. We leverage GP's automatic feature selection mechanisms to identify Watson's key features through the learning process. Our experiments show that GP can evolve relatively simple ranking functions that use much fewer features from the original Watson feature set to achieve comparable performances to Watson. This methodology can aid Watson implementers to better identify key components in an otherwise large and complex system for development, troubleshooting, and/or customer or domain-specific enhancements.

Automatic Evolution of Parallel Recursive Programs
Gopinath Chennupati, Muhammad R. Atif Azad, Conor Ryan
Writing recursive programs for fine-grained task-level execution on parallel architectures, such as the current generation of multi-core machines, often require the application of skilled parallelization knowledge to fully realize the potential of the hardware. This paper automates the process by using Grammatical Evolution (GE) to exploit the multi-cores through the evolution of natively parallel programs. We present Multi-core Grammatical Evolution (MCGE-II), which employs GE and OpenMP specific pragmatic information to automatically evolve task-level parallel recursive programs. MCGE-II is evaluated on six recursive C programs, and we show that it solves each of them using parallel code. We further show that MCGE-II significantly decreases the parallel computational effort as the number of cores increase, when tested on an Intel processor.

Proposal and Preliminary Investigation of a Fitness Function for Partial Differential Models
Igor S. Peretta, Keiji Yamanaka, Paul Bourgine, Pierre Collet
This work proposes and presents a preliminary investigation of a fitness evaluation scheme supported by a proper genotype representation intended to guide an under development expansion to EASEA/EASEA-CLOUD platforms to evolve partial differential equations as models for a specific system of interest, starting with measures from that system. A simple proof of concept using a dynamic bidirectional surface wave is presented, showing that the proposed fitness evaluation scheme is very promising to enable automate system modelling, even when dealing with up to +-10% noise-added data.

Evolutionary Methods for the Construction of Cryptographic Boolean Functions
Stjepan Picek, Domagoj Jakobovic, Julian F. Miller, Elena Marchiori, Lejla Batina
Boolean functions represent an important primitive when constructing many stream ciphers. Since they are often the only nonlinear element of such ciphers, without them the algorithm would be trivial to break. Therefore, it is not surprising there exist a substantial body of work on the methods of constructing Boolean functions. Among those methods, evolutionary computation (EC) techniques play a significant role. Previous works show it is possible to use EC methods to generate high-quality Boolean functions that even surpass those built by algebraic constructions. However, up to now, there was no work investigating the use of Cartesian Genetic Programming (CGP) for producing Boolean functions suitable for cryptography. In this paper we compare Genetic Programming (GP) and CGP algorithms in order to reach the conclusion which algorithm is better suited to evolve Boolean functions suitable for cryptographic usage. Our experiments show that CGP performs much better than the GP when the goal is obtaining as high as possible nonlinearity. Our results indicate that CGP should be further tested with different fitness objectives in order to check the boundaries of its performance.

Templar - a Framework for Template-Method Hyper-Heuristics
Jerry Swan, Nathan Burles
In this work we introduce Templar, a software framework for customising algorithms via the generative technique of template-method hyper-heuristics. We first discuss the need for such an approach, presenting Quicksort as an example. We provide a functional definition of template-method hyper-heuristics, describe how this is implemented by Templar, and show how Templar may be invoked using simple client-code. Finally, we describe experiments using Templar to define a 'hyper-quicksort' with the aim of reducing power consumption - the results demonstrate that the generated algorithm has significantly improved performance on the test set.

Circuit Approximation Using Single- and Multi-Objective Cartesian GP Zdenek Vasicek, Lukas Sekanina
In this paper, the approximate circuit design problem is formulated as a multi-objective optimization problem in which the circuit error and power consumption are conflicting design objectives. We compare multi-objective and single-objective Cartesian genetic programming in the task of parallel adder and multiplier approximation. It is analyzed how the setting of the methods, formulating the problem as multi-objective or single-objective, and constraining the execution time can influence the quality of results. One of the conclusions is that the multi-objective approach is useful if the number of allowed evaluations is low. When more time is available, the single-objective approach becomes more efficient.

EuroGP Best Paper Candidates

Cartesian GP in Optimization of Combinational Circuits with Hundreds of Inputs and Thousands of Gates
Zdenek Vasicek

On the Generalization Ability of Geometric Semantic Genetic Programming
Ivo Gonçalves, Sara Silva, Carlos M. Fonseca

Attributed Grammatical Evolution using Shared Memory Spaces and Dynamically Typed Semantic Function Specification
James Vincent Patten and Conor Ryan

The Effect of Distinct Geometric Semantic Crossover Operators in Regression Problems
Julio Albinati, Gisele Lobo Pappa, Luiz Otavio V.B. Oliveira, Fernando Otero