EuroGP2002
5th European Conference on Genetic Programming
3-5 April 2002

Menu
Introduction
Programme
Invited speakers
GP Tutorial
Papers
Oral presentations
Poster presentations
EuroGP Debate
Committees

Joint event pages
Registration
Programme overview
All accepted papers
Local information
Accommodation
Travel

Main contacts
Programme co-chairs
James Foster
Evelyn Lutton
Local chair
Conor Ryan

  EuroGP2002

This information can also be downloaded in BibTeX format: egp2002.bib (46kb)

Accepted Papers - oral presentations


Evolving classifiers to model the relationship between strategy and corporate performance using grammatical evolution
BRABAZON A., O'NEILL M., RYAN C., MATTHEWS R.

Abstract:
This study examines the potential of grammatical evolution to construct a linear classifier to predict whether a firm's corporate strategy will increase or decrease shareholder wealth. Shareholder wealth is measured using a relative fitness criterion, the change in a firm's market-value-added ranking in the Stern-Stewart Performance 1000 list, over a four year period, 1992-1996. Model inputs and structure are selected by means of grammatical evolution. The best classifier correctly categorised the direction of performance ranking change in 66.38% of the firms in the training set and 65% in the out-of-sample validation set providing support for a hypothesis that changes in corporate strategy are linked to changes in corporate performance.

Session:
EuroGP Session 9: Grammatical evolution: April 5, 0930-1100


Explicit Control of Diversity and Effective Variation Distance in Linear Genetic Programming
BRAMEIER M., BANZHAF W.

Abstract:
We have investigated structural distance metrics for linear genetic programs. Causal connections between changes of the genotype and changes of the phenotype form a necessary condition for analyzing structural differences between genetic programs and for the two objectives of this paper: (i) The distance information between individuals is used to control structural diversity of population individuals actively by a two-level tournament selection. (ii) Variation distance of effective code is controlled for different genetic operators - including a mutation operator that works closely with the applied distance measure. Numerous experiments have been performed for three benchmark problems.

Session:
EuroGP Session 2: Experimental & theoretical analysis: April 3, 1400-1605


An Analysis of Koza's Computational Effort Statistic for Genetic Programming
CHRISTENSEN S., OPPACHER F.

Abstract:
As research into the theory of genetic programming progresses, more effort is being placed on systematically comparing results to give an indication of the effectiveness of sundry modifications to traditional GP. The statistic that is commonly used to report the amount of computational effort to solve a particular problem with 99% probability is Koza's I(M, i, z) statistic. This paper analyzes this measure from a statistical perspective. In particular, Koza's I tends to underestimate the true computational effort, by 25% or more forcommonly used GP parameters and run sizes. The magnitude of this underestimate is nonlinearly decreasing with increasing run count, leading tothe possibility that published results based on few runs may in fact be unmatchable when replicated at higher resolution. Additional analysis shows that this statistic also underreports the generation at which optimal results are achieved.

Session:
EuroGP Session 2: Experimental & theoretical analysis: April 3, 1400-1605


Evolving Fuzzy Decision Trees with Genetic Programming and Clustering
EGGERMONT J.

Abstract:
In this paper we present a new fuzzy decision tree representation for n-category data classification using genetic programming. The new fuzzy representation utilizes fuzzy clusters for handling continuous attributes. To make optimal use of the fuzzy classifications of this representation an extra fitness measure is used. The new fuzzy representation will be compared, using several machine learning data sets, to a similar non-fuzzy representation as well as to some other evolutionary and non-evolutionary algorithms from literature.

Session:
EuroGP Session 7: Implementation & representation issues: April 4, 1345-1550


Maintaining the Diversity of Genetic Programs
EKART A., NEMETH N.

Abstract:
An important problem of evolutionary algorithms is that throughout evolution they loose genetic diversity. Many techniques have been developed for maintaining diversity in genetic algorithms, but few investigations have been done for genetic programs. We define here a diversity measure for genetic programs based on our metric for genetic trees. We use this distance measure for studying the effects of fitness sharing. We then propose a method for adaptively maintaining the diversity of a population during evolution.

Session:
EuroGP Session 2: Experimental & theoretical analysis: April 3, 1400-1605


Discovery of the Boolean Functions to the Best Density-Classification Rules Using Gene Expression Programming
FERREIRA C.

Abstract:
Cellular automata are idealized versions of massively parallel, decentralized computing systems capable of emergent behaviors. These complex behaviors result from the simultaneous execution of simple rules at multiple local sites. A widely studied behavior consists of correctly determining the density of an initial configuration, and both human and computer-written rules have been found that perform with high efficiency at this task. However, the two best rules for the density-classification task, Coevolution1 and Coevolution2, were discovered using a coevolutionary algorithm in which a genetic algorithm evolved the rules and, therefore, only the output bits of the rules are known. However, to understand why these and other rules perform so well and how the information is transmitted throughout the cellular automata, the Boolean expressions that orchestrate this behavior must be known. The results presented in this work are a contribution in that direction.

Session:
EuroGP Session 6: Applications II: April 4, 1100-1230


N-version Genetic Programming via Fault Masking
IMAMURA K., HECKENDORN R. B., SOULE T., FOSTER J. A.

Abstract:
We introduce a new method, N-Version Genetic Programming (NVGP), for building fault tolerant software by building an ensemble of automatically generated modules in such a way as to maximize their collective fault masking ability. The ensemble itself is an example of n-version modular redundancy for fault tolerance, where the output of the ensemble is the most frequent output of n independent modules. By maximizing collective fault masking, NVGP approaches the fault tolerance expected from n version modular redundancy with independent faults in component modules. The ensemble comprises individual modules from a large pool generated with genetic programming, using operators that increase the diversity of the population. Our experimental test problem classified promoter regions in Escherichia coli DNA sequences. For this problem, NVGP reduced the number and variance of errors over single modules produced by GP, with statistical significance.

Session:
EuroGP Session 6: Applications II: April 4, 1100-1230


Linear-Graph GP- A new GP Structure
KANTSCHIK W., BANZHAF W.

Abstract:
In recent years different genetic programming (GP) structures have emerged. Today, the basic forms of representation for genetic programs are tree, linear and graph structures. In this contribution we introduce a new kind of GP structure which we call linear-graph, it is a further development of the linear-Tree structure. We describe the linear-graph structure, as well as crossover and mutation for this new GP structure in detail. We compare linear-graph programs with linear and tree programs by analyzing their structure and results on different test problems.

Session:
EuroGP Session 7: Implementation & representation issues: April 4, 1345-1550


Grammatical Evolution Rules: The mod and the Bucket Rule
KEIJZER M., O'NEILL M., RYAN C., CATTOLICO M.

Abstract:
We present an alternative mapping function called the Bucket Rule, for Grammatical Evolution, that improves upon the standard modulo rule. Grammatical Evolution is applied to a set of standard Genetic Algorithm problem domains using two alternative grammars. Applying GE to GA problems allows us to focus on a simple grammar whose effects are easily analysable.

Session:
EuroGP Session 9: Grammatical evolution: April 5, 0930-1100


Combining Decision Trees and Neural Networks for Drug Discovery
LANGDON W. B., BARRETT S. J., BUXTON B. F.

Abstract:
Last year [Langdon and Buxton, 2001c] we presented a new system in which genetic programming (GP) automatically fuses together classifiers using the ir receiver operating characteristics (ROC) to yield superior ensembles. This year we demonstrate it combining decision trees (C4.5) and artificial neural net works (ANN) on a difficult pharmaceutical data mining (KDD) drug discovery application. Specifically predicting compound activity with a P450 enzyme. Training data came from high through put screening (HTS) runs held in GlaxoSmithKline (GSK)'s cheminformatics database. The evolved model may be used to predict behaviour of virtual (i.e. yet to be manufactured chemicals). Measures to reduce over fitting are also described.

Session:
EuroGP Session 5: Applications I: April 4, 0930-1030


A Pipelined Hardware Implementation of Genetic Programming using FPGAs and Handel-C
MARTIN P.

Abstract:
A complete Genetic Programming (GP) system implemented in a single FPGA is described in this paper. The GP system is capable of solving problems that require large populations and by using parallel fitness evaluations can solve problems in a much shorter time that a conventional GP system in software. A high level language to hardware compilation system called Handel-C is used for implementation.

Session:
EuroGP Session 7: Implementation & representation issues: April 4, 1345-1550


No Coercion and No Prohibition, A Position Independent Encoding Scheme for Evolutionary Algorithms - The Chorus System
RYAN C., AZAD A., SHEAHAN A., O'NEILL M.

Abstract:
We describe a new encoding system, Chorus, for grammar based Evolutionary Algorithms. This scheme is coarsely based on the manner in nature in which genes produce proteins that regulate the metabolic pathways of the cell. The phenotype is the behaviour of the cells metabolism, which corresponds to the development of the computer program in our case. In this procedure, the actual protein encoded by a gene is the same regardless of the position of the gene within the genome.

We show that the Chorus system has a very convenient Regular Expression - type schema notation that can be used to describe the presence of various phenotypes or phenotypic traits. This schema notation is used to demonstrate that massive areas of neutrality can exist in the search landscape, and the system is also shown to be able to dispense with large areas of the search space that are unlikely to contain useful solutions.

Session:
EuroGP Session 9: Grammatical evolution: April 5, 0930-1100


Exons and Code Growth in Genetic Programming
SOULE T.

Abstract:
The phenomenon of code growth is well documented in genetic programming. Several well supported theories exist to explain code growth, each of which focuses on introns, sections of code that do not contribute to fitness. However, several researchers have pointed out that these theories, and code growth itself, does not seem to depend upon the presence of introns. In this paper we show for the first time that code growth can occur, albeit quite slowly, even with exons that have a significant impact on fitness.

Session:
EuroGP Session 3: Code Bloat: April 3, 1630-1730


Routine Duplication of Post-2000 Patented Inventions by Means of Genetic Programming
STREETER M. J., KEANE M. A., KOZA J. R.

Abstract:
Previous work has demonstrated that genetic programming can automatically create analog electrical circuits, controllers, and other devices that duplicate the functionality and, in some cases, partially or completely duplicate the exact structure of inventions that were patented between 1917 and 1962. This pap er reports on a project in which we browsed patents of analog circuits issued after January 1, 2000 on the premise that recently issued patents represent current research that is considered to be of practical and scientific importance. The paper describes how we used genetic programming to automatically create circuits that duplicate the functionality or structure of five post -2000 patented inventions. This work employed four new techniques (motivated by the theory of genetic algorithms and genetic programm ing) that we believe increased the efficiency of the runs. When an automated method duplicates a previously patented human -designed invention, it can be argued that the automated method satisfies a Patent -Office-based variation of the Turing test.

Session:
EuroGP Session 5: Applications I: April 4, 0930-1030


Uniform Subtree Mutation
VAN BELLE T., ACKLEY D

Abstract:
Genetic programming methods often suffer from `code bloat,' in which evolving solution trees rapidly become unmanageably large. To provide a measure of sensitivity to tree size in a natural way, we introduce a simple uniform subtree mutation (USM) operator that provides an approximately constant probability of mutation per tree node, rather than per tree. To help model circumstances where tree size cannot be ignored, we introduce a new notion of computational effort called size effort. Initial empirical tests show that genetic programming using only uniform subtree mutation reduces evolved tree sizes dramatically, compared to crossover, but does impact solution quality somewhat. In some cases, however, using using a combination of USM and crossover yielded both smaller trees and superior performance, as measured both by size effort and traditional metrics.

Session:
EuroGP Session 3: Code Bloat: April 3, 1630-1730


A New View on Symbolic Regression
WEINERT K., STAUTNER M.

Abstract:
Symbolic regression is a widely used method to reconstruct mathematical correlations. This paper presents a new graphical representation of the individuals reconstructed in this process. This new three dimensional representation allows the user to recognize certain possibilities to improve his setup of the process parameters. Furthermore this new representation allows a wider usage of the generated three dimensional objects with nearly every CAD program for further use. To show the practical usage of this new representation it was used to reconstruct mathematical descriptions of the dynamics in a machining process namely in orthogonal cutting.

Session:
EuroGP Session 7: Implementation & representation issues: April 4, 1345-1550


Parallel Surface Reconstruction
WEINERT K., SURMANN T., MEHNEN J.

Abstract:
The task of surface reconstruction is to find a mathematical representation of a surface which is given only by a set of discrete sampling points. The mathematical description in the computer allows to save or transfer the geometric data via internet, to manipulate (e.g. for aerodynamic or design specific reasons) or to optimize the machining of the work pieces. The reconstruction of the shape of an object is a difficult mathematical and computer scientific problem. For this reason a GP/ES-hybrid algorithm has been used. Due to the high complexity of the problem and in order to speed up the reconstruction process, the algorithm has been enhanced to work as a multipopulation GP/ES that runs in parallel on a network of standard PCs.

Session:
EuroGP Session 6: Applications II: April 4, 1100-1230


Needles in Haystacks Are Not Hard to Find with Neutrality
YU T., MILLER J.

Abstract:
We propose building neutral networks in needle-in-haystack fitness landscapes to assist an evolutionary algorithm to perform search. The experimental results on four different problems show that this approach improves the search success rates in most cases. In situations where neutral networks do not give performance improvement, no impairment occurs either. We also tested a hypothesis proposed in our previous work. The results support the hypothesis: when the ratio of adaptive/neutral mutations during neutral walk is close to that of fitness improvement step, the evolutionary search has a high success rate. Moreover, the ratio magnitudes indicate that more neutral mutations (than adaptive mutations) are required for the algorithms to find a solution in this type of search space.

Session:
EuroGP Session 2: Experimental & theoretical analysis: April 3, 1400-1605


Accepted Papers - poster presentations


Evolutionary Algorithm Approach to Bilateral Negotiations
BABER V.

Abstract:
The Internet is quickly changing the way business-to-consumer and business-to-business commerce is conducted. The technology has created an opportunity to get beyond single-issue negotiation by determining sellers' and buyers' preferences across multiple issues, thereby creating possible joint gains for all parties. We develop simple multiple issue algorithms and heuristics that could be used in electronic auctions and electronic markets. In this study, we show how a genetic algorithm based technique, coupled with a simple heuristic can achieve good results in business negotiations. The negotiations' outcomes are evaluated on two dimensions: joint utility and number of ex-changes of offers to reach a deal. The results are promising and indicate possible use of such ap-proaches in actual electronic commerce systems.

Session:
EuroGP Session 4: Poster session and conference reception: April 3, 1730-1930


A Puzzle to Challenge Genetic Programming
BURKE E., GUSTAFSON S., KENDALL G.

Abstract:
This report represents an initial investigation into the use of genetic programming to solve the N-prisoners puzzle. The puzzle has generated a certain level of interest among the mathematical community. We believe that this puzzle presents a significant challenge to the field of evolutionary computation and to genetic programming in particular. The overall aim is to generate a solution that encodes complex decision making. Our initial results demonstrate that genetic programming can evolve good solutions. We compare these results to engineered solutions and discuss some of the implications. One of the consequences of this study is that it has highlighted a number of research issues and directions and challenges for the evolutionary computation community.We conclude the article by presenting some of these directions which range over several areas of evolutionary computation, including multi-objective fitness, coevolution and cooperation, and problem representations.

Session:
EuroGP Session 4: Poster session and conference reception: April 3, 1730-1930


Automatic Generation of Control Programs for Walking Robots Using Genetic Programming
BUSCH J., ZIEGLER J., BANZHAF W., ROSS A., SAWITZKI D., AUE C.

Abstract:
We present the system SIGEL that combines the simulation and visualization of robots with a Genetic Programming system for the automated evolution of walking. It is designed to automatically generate control programs for arbitrary robots without depending on detailed analytical information of the robots' kinematic structure. Different fitness functions as well as a variety of parameters allow the easy and interactive configuration and adaptation of the evolution process and the simulations.

Session:
EuroGP Session 4: Poster session and conference reception: April 3, 1730-1930


Coevolution Produces an Arms Race Among Virtual Plants
EBNER M., GRIGORE A., HEFFNER A., ALBERT J.

Abstract:
Creating interesting virtual worlds is a difficult task. We are using a variant of genetic programming to automatically create plants for a virtual environment. The plants are represented as context-free Lindenmayer systems. OpenGL is used to visualize and evaluate the plants. Our plants have to collect virtual sunlight through their leaves in order to reproduce successfully. Thus we have realized an interaction between the plant and its environment. Plants are either evaluated separately or all individuals of a population at the same time. The experiments show that during coevolution plants grow much higher compared to rather bushy plants when plants are evaluated in isolation.

Session:
EuroGP Session 4: Poster session and conference reception: April 3, 1730-1930


Comparing Synchronous and Asynchronous Parallel and Distributed GP Models
FERNANDEZ F., GALEANO G., GOMEZ J. A.

Abstract:
In this paper we present a study that analyses the respective advantages and disadvantages of the synchronous and asynchronous versions of island-based genetic programming. We also look at different measuring systems for comparing parallel genetic programming with panmitic mo del. At the same time we show an interesting relationship between the bloat phenomenon and the number of individuals we use. Finally, we study a relationship between the number of subpopulations in parallel GP and the advantages of the asynchronous model.

Session:
EuroGP Session 4: Poster session and conference reception: April 3, 1730-1930


New Results on Fuzzy Regression by Using Genetic Programming
GOLUBSKI W.

Abstract:
In this paper we continue the work on symbolic fuzzy regression problems. That means that we are interesting in finding a fuzzy function f with best matches given data pairs (xi,yi) 1<= i <= k of fuzzy numbers. We use a genetic programming approach for finding a suitable fuzzy function and will present test results about linear, quadratic and cubic fuzzy functions.

Session:
EuroGP Session 4: Poster session and conference reception: April 3, 1730-1930


Some Experimental Results with Tree Adjunct Grammar Guided Genetic Programming
HOAI N. X., MCKAY R. I., ESSAM D.

Abstract:
Tree-adjunct grammar guided genetic programming (TAG3P) [5] is a grammar guided genetic programming system that uses context -free grammars along with tree-adjunct grammars as means to set language bias for the genetic programming system. In this paper, we show the experimental results of TAG3P on two problems: symbolic regression and trigonometric identity discovery. The results show that TAG3P works well on those problems.

Session:
EuroGP Session 4: Poster session and conference reception: April 3, 1730-1930


Transformation of Equational Specification by Means of Genetic Programming
IBARRA A., LANCHARES J., MENDIAS J., HIDALGO J. I., HERMIDA R.

Abstract:
High Level Synthesis (HLS) is a designing methodology aimed to the synthesis of hardware devices from behavioural specifications. One of the techniques used in HLS is formal verification. In this work we present an evolutionary algorithm in order to optimize circuit equational specifications by means of a special type of genetic operator. We have named this operator algebraic mutation, carried out with the help of the equations that Formal Verification Synthesis offers. This work can be classified within the development of an automatic tool of Formal Verification Synthesis by using genetic techniques. We have applied this technique to a simple circuit equational specification and to a much more complex algebraic equation. In the first case our algorithm simplifies the equation until the best specification is found and in the second a solution improving the former is always obtained.

Session:
EuroGP Session 4: Poster session and conference reception: April 3, 1730-1930


Deriving genetic programming fitness properties by static analysis
JOHNSON C.

Abstract:
The aim of this paper is to introduce the idea of using static analysis of computer programs as a way of measuring fitness in genetic programming. Such techniques extract information about the programs without explicitly running them, and in particular they infer properties which hold across the whole of the input space of a program. This can be applied to measure fitness, and has a number of advantages over measuring fitness by running members of the population on test cases. The most important advantage is that if a solution is found then it is possible to formally trust that solution to be correct across all inputs. This paper introduces these ideas, discusses various ways in which they could be applied, discusses the type of problems for which they are appropriate, and ends by giving a simple test example and some questions for future research.

Session:
EuroGP Session 4: Poster session and conference reception: April 3, 1730-1930


Brute-Force Approach to Automatic Induction of Machine Code on CISC Architectures
KÜHLING F., WOLFF K., NORDIN P.

Abstract:
The usual approach to address the brittleness of machine code in evolution is to constrain mutation and crossover to ensure syntactic closure. In the novel approach presented here we use no constraints on the operators, they all work blindely on the binaries in memory, but we instead encapsulate the code and trap all resulting exceptions. The new approach presented here for machine code evolution on CISC architectures is based on the observation that modern CPUs can cope with incorrect programmes and report errors to the operating system. This way it is possible to return to very simple genetic operators with the objective of increased performance. Furthermore the instruction set used by evolved programmes is no longer limited by the genetic programming system but only by the CPU it runs on. The mapping between evolution plattform and execution plattform becomes alomst complete, ensuring correct low-level behaviour of all CPU functions.

Session:
EuroGP Session 4: Poster session and conference reception: April 3, 1730-1930


An investigation into the use of different search strategies with Grammatical Evolution
O'SULLIVAN J., RYAN C.

Abstract:
We present an investigation into the performance of Grammatical Evolution using a number of different search strategies, Simulated Annealing, Hill Climbing, Random Search and Genetic Algorithms. Comparative results on three different problems are examined. We analyse the nature of the search spaces presented by these problems and offer an explanation for the contrasting performance of each of the search strategies. Our results show that Genetic Algorithms provide a consistent level of performance across all three problems successfully coping with sensitivity of the system to discrete changes in the selection of productions from the associated grammar.

Session:
EuroGP Session 4: Poster session and conference reception: April 3, 1730-1930


Allele Diffusion in Linear Genetic Programming and Variable-Length Genetic Algorithms with Subtree Crossover
POLI R., ROWE J. E., STEPHENS C. R., WRIGHT A. H.

Abstract:
In this paper we study, theoretically, the search biases produced by GP subtree crossover when applied to linear representations, such as those used in linear GP or in variable length GAs. The study naturally leads to generalisations of Geiringer s theorem and of the notion of linkage equilibrium, which, until now, were applicable only to fixed-length representations. This indicates the presence of a diffusion process by which, even in the absence of selective pressure and mutation, the alleles in a particular individual tend not just to be swapped with those of other individuals in the population, but also to diffuse within the representation of each individual. More precisely, crossover attempts to push the population towards distributions of primitives where each primitive is equally likely to be found in any position in any individual.

Session:
EuroGP Session 4: Poster session and conference reception: April 3, 1730-1930


Genetic Algorithms Using Grammatical Evolution
RYAN C., NICOLAU M., O'NEILL M.

Abstract:
This paper describes the GAUGE system, Genetic Algorithms Using Grammatical Evolution. GAUGE is a position independent Genetic Algorithm that uses Grammatical Evolution with an attribute grammar to dictate what position a gene codes for. GAUGE suffers from neither under-specification nor over-specification, is guaranteed to produce syntactically correct individuals, and does not require any repair after the application of genetic operators. GAUGE is applied to the standard onemax problem, with results showing that its genotype to phenotype mapping and position independence nature do not affect its performance as a normal genetic algorithm. A new problem is also presented, a deceptive version of the Mastermind game, and we show that GAUGE possesses the position independence characteristics it claims, and outperforms several genetic algorithms, including the competent genetic algorithm messyGA.

Session:
EuroGP Session 4: Poster session and conference reception: April 3, 1730-1930


Genetic control applied to asset managements
WERNER J. C., FOGARTY T. C.

Abstract:
This paper address the problem of investment optimisation, with deals with obtain stock time series from data extracted of graphics available in internet, predict assets price by adaptive algorithms, optimise the portfolio with genetic algorithms and obtain a recursive model of portfolio composition on-fly using genetic programming, all steps integrated to obtain an automatic management. The final result is a real-time update portfolio composition for each asset.

Session:
EuroGP Session 4: Poster session and conference reception: April 3, 1730-1930