EuroGP2001 18-20 April 2001
Lake Como (Milan), Italy
home | post conference information | papers | EvoWorkshops | committees   


 

Papers

Accepted oral presentations
Accepted poster presentations
Abstracts
Instructions for authors
AV Equipment & poster sizes



     

EuroGP2001 abstracts

Oral presentations

Heuristic Learning based on Genetic Programming

Nicole Drechsler - Frank Schmiedle - Daniel Grosse - Rolf Drechsler

Abstract:

In this paper we present an approach to learning heuristics based on Genetic Programming (GP). Instead of directly solving the problem by application of GP, GP is used to develop a heuristic that is applied to the problem instance. By this, the typical large runtimes of evolutionary methods have to be invested only once in the learning phase. The resulting heuristic is very fast. The technique is applied to a field from the area of VLSI CAD, i.e. minimization of Binary Decision Diagrams (BDDs). We chose this topic due to its high practical relevance and since it matches the criteria where our algorithm works best, i.e. large problem instances where standard evolutionary techniques cannot be applied due to their large runtimes. Our experiments show that we obtain high quality results that outperform previous methods, while keeping the advantage of low runtimes.

Keywords:

Heuristic Learning, VLSI CAD, BDD, Binary Decision Diagrams

10 pages


Evolving Color Constancy for an Artificial Retina

Marc Ebner

Abstract:

Objects retain their color in spite of changes in the wavelength and energy composition of the light they reflect. This phenomenon is called color constancy and plays an important role in computer vision research. We have used genetic programming to automatically search the space of programs to solve the problem of color constancy for an artificial retina. This retina consists of a two dimensional array of elements each capable of exchanging information with its adjacent neighbors. The task of the program is to compute the intensities of the light illuminating the scene. These intensities are then used to calculate the reflectances of the object. Randomly generated color Mondrians were used as fitness cases. The evolved program was tested on artificial Mondrians and natural images.

Keywords:

Color Constancy, Artificial Retina, Image Processing

12 pages


Adaptive Genetic Programming Applied to New and Existing Simple Regression Problems

Jeroen Eggermont - Jano I. van Hemert

Abstract:

In this paper we continue our study on adaptive genetic programming. We use Stepwise Adaptation of Weights (SAW) to boost performance of a genetic programming algorithm on simple symbolic regression problems. We measure the performance of a standard GP and two variants of SAW extensions on two different symbolic regression problems from literature. Also, we propose a model for randomly generating polynomials which we then use to further test all three GP variants.

Keywords:

Adaptation, Symbolic Regression, Problem Generator, Program Trees

13 pages


An Evolutionary Approach to Automatic Generation of VHDL Code for Low-Power Digital Filters

Massimiliano Erba - Roberto Rossi - Valentino Liberali - Andrea Tettamanzi

Abstract:

An evolutionary algorithm is used to design a finite impulse response digital filter with reduced power consumption. The proposed design approach combines genetic optimization and simulation methodology, to evaluate a multi-objective fitness function which includes both the suitability of the filter transfer function and the transition activity of digital blocks. The proper choice of fitness function and selection criteria allows the genetic algorithm to perform a better search within the design space, thus exploring possible solutions which are not considered in the conventional structured design methodology. Although the evolutionary process is not guaranteed to generate a filter fully compliant to specifications in every run, experimental evidence shows that, when specifications are met, evolved filters are much better than classical designs both in terms of power consumption and in terms of area, while maintaining the same performance.

Keywords:

Evolvable Hardware, Evolutionary Algorithms, Electronic Design, Digital Filters, VHDL

15 pages


Studying the Influence of Communication Topology and Migration on Distributed Genetic Programming

F. Fernandez - L. Vanneschi - M. Tomassini

Abstract:

In this paper we present a systematic experimental study of some of the parameters influencing parallel and distributed genetic programming (PADGP) by using three benchmark problems. We first present results on the system's communication topology and then we study the parameters governing individual migration between subpopulations: the number of individuals sent and the frequency of exchange. Our results suggest that fitness evolution is more sensitive to the migration factor than the communication topology.

Keywords:

Distributed Genetic Programming, Parallelism, Multipopulation structures, Parallel evolutionary algorithms

13 pages


CAGE: A Tool for Parallel Genetic Programming Applications

Gianluigi Folino - Clara Pizzuti - Giandomenico Spezzano

Abstract:

A new parallel implementation of genetic programming based on the cellular model is presented and compared with the island model approach. Although the widespread belief that cellular model is not suitable for parallel genetic programming implementations, experimental results show a better convergence with respect to the island approach, a good scale-up behaviour and a nearly linear speed-up.

Keywords:

Parallel programming, Cellular model

11 pages


Ripple Crossover in Genetic Programming

Maarten Keijzer - Conor Ryan - Michael O'Neill - Mike Cattolico - Vladin Babovic

Abstract:

This paper isolates and identifies the effects of the crossover operator used in Grammatical Evolution. This crossover operator has already been shown to be adept at combining useful building blocks and to outperform engineered crossover operators such as Homologous Crossover. This crossover operator, Ripple Crossover is described in terms of Genetic Programming and applied to two benchmark problems.

Its performance is compared with that of traditional sub-tree crossover on populations employing the standard functions and terminal set, but also against populations of individuals that encode Context Free Grammars. Ripple crossover is more effective in exploring the search space of possible programs than sub-tree crossover. This is shown by examining the rate of premature convergence during the run. Ripple crossover produces populations whose fitness increases gradually over time, slower than, but to an eventual higher level than that of sub-tree crossover.

Keywords:

Grammatical evolution, Context Free Grammars, Crossover, Intrinsic Polymorphism

14 pages


Evolving Receiver Operating Characteristics for Data Fusion

W. B. Langdon - B. F. Buxton

Abstract:

It has been suggested that the ``Maximum Realisable Receiver Operating Characteristics'' for a combination of classifiers is the convex hull of their individual ROCs [Scott et al., 1998]. As expected in at least some cases better ROCs can be produced. We show genetic programming (GP) can automatically produce a combination of classifiers whose ROC is better than the convex hull of the supplied classifier's ROCs.

Keywords:

Data Fusion, Data Mining, Knowledge Discovery, Receiver Operating Characteristics, ROC, Combining Classifiers

10 pages


An Adaptive Mapping for Developmental Genetic Programming

Steve Margetts - Antonia J. Jones

Abstract:

In this article we introduce a general framework for constructing an adaptive genotype-to-phenotype mapping, and apply it to developmental genetic programming. In this preliminary investigation, we run a series of comparative experiments on a simple test problem. Our results show that the adaptive algorithm is able to outperform its non-adaptive counterpart.

Keywords:

Developmental Genetic Programming, Adaptive Genotype to Phenotype Mappings, MAX Problem

11 pages


A schema theory analysis of the evolution of size in genetic programming with linear representations

Nicholas Freitag McPhee - Riccardo Poli

Abstract:

In this paper we use the schema theory presented elsewhere in this volume to better understand the changes in size distribution when using GP with standard crossover and linear structures. Applications of the theory to problems both with and without fitness suggest that standard crossover induces specific biases in the distributions of sizes, with a strong tendency to over sample small structures, and indicate the existence of strong redistribution effects that may be a major force in the early stages of a GP run. We also present two important theoretical results: An exact theory of bloat, and a general theory of how average size changes on flat landscapes with glitches. The latter implies the surprising result that a single program glitch in an otherwise flat fitness landscape is sufficient to drive the average program size of an infinite population, which may have important implications for the control of code growth.

Keywords:

Schema theory, Linear representations, Bloat, Length distributions, Fitness landscape glitches, One-then-zeros problem

18 pages


Exact Schema Theorems for GP with One-Point and Standard Crossover Operating on Linear Structures and their Application to the Study of the Evolution of Size

Riccardo Poli - Nicholas Freitag McPhee

Abstract:

In this paper, firstly we specialise the exact GP schema theorem for one-point crossover to the case of linear structures of variable length, for example binary strings or programs with arity-1 primitives only. Secondly, we extend this to an exact schema theorem for GP with standard crossover applicable to the case of linear structures. Then we study, both mathematically and numerically, the schema equations and their fixed points for infinite populations for both a constant and a length-related fitness function. This allows us to characterise the bias induced by standard crossover. This is very peculiar. In the case of a constant fitness function, at the fixed-point, structures of any length are present with non-zero probability. However, shorter structures are sampled exponentially much more frequently than longer ones.

Keywords:

Schema theory, Crossover, Crossover bias, Standard Crossover, Fixed points, Variable-length Genetic Algorithms,

16 pages


General Schema Theory for Genetic Programming with Subtree-Swapping Crossover

Riccardo Poli

Abstract:

In this paper a new, general and exact schema theory for genetic programming is presented. The theory includes a microscopic schema theorem applicable to crossover operators which replace a subtree in one parent with a subtree from the other parent to produce the offspring. A more macroscopic schema theorem is also provided which is valid for crossover operators in which the probability of selecting any two crossover points in the parents depends only on their size and shape. The theory is based on the notions of Cartesian node reference systems and variable-arity hyperschemata both introduced here for the first time. In the paper we provide examples which show how the theory can be specialised to specific crossover operators and how it can be used to derive an exact definition of effective fitness and a size-evolution equation for GP.

Keywords:

Schema theory, Crossover, Subtree-swapping Crossover, Standard Crossover, Evolution of size, Bloat, Variable-length Genetic Algorithms

16 pages


Evolving modules in Genetic Programming by subtree encapsulation

Simon C. Roberts - Daniel Howard - John R. Koza

Abstract:

In tree-based genetic programming (GP), the most frequent subtrees on later generations are likely to constitute useful partial solutions. This paper investigates the effect of encapsulating such subtrees by representing them as atoms in the terminal set, so that the subtree evaluations can be exploited as terminal data. The encapsulation scheme is compared against a second scheme which depends on random subtree selection. Empirical results show that both schemes improve upon standard GP.

Keywords:

Modularisation, Code Reuse, Subtree Encapsulation, Image Processing,

16 pages


Evolution of Affine Transformations and Iterated Function Systems using Hierarchical Evolution Strategy

Anargyros Sarafopoulos

Abstract:

Often optimization problems involve the discovery of many scalar coefficients. Although genetic programming (GP) has been applied to the optimization and discovery of functions with an arbitrary number of scalar coefficients, recent results indicate that a method for fine-tuning GP scalar terminals can assist the discovery of solutions. In this paper we demonstrate an approach where genetic programming and evolution strategies (ES) are seamlessly combined. We apply our GP/ES hybrid, which we name Hierarchical Evolution Strategy, to the problem of evolving affine transformations and iterated function systems (IFS). We compare the results of our approach with GP and notice an improvement in performance in terms of discovering better solutions and speed.

Keywords:

Strongly Typed GP, STGP, Evolution Strategies, Iterated Function Systems

16 pages


Evolving Turing machines for Biosequences Recognition and Analysis

Edgar E. Vallejo - Fernando Ramos

Abstract:

This article presents a genetic programming system for biosequence recognition and analysis. In our model, a population of Turing machines evolves the capability of biosequence recognition using genetic algorithms. We use HIV sequences as the working example. Experimental results indicate that evolved Turing machines are capable of recognizing HIV sequences in a collection of training sets. In addition, we demonstrate that the evolved Turing machines can be used to approximate the multiple sequence alignment problem.

Keywords:

Bioinformatics, DNA, Turing machines, Multiple Sequence aligment

12 pages


Neutrality and the Evolvability of Boolean Function Landscape

Tina Yu - Julian Miller

Abstract:

This work is a study of neutrality in the context of Evolutionary Computation systems. In particular, we introduce the use of explicit neutrality with an integer string coding scheme to allow neutrality to be measured during evolution. We tested this method on a Boolean benchmark problem. The experimental results indicate that there is a positive relationship between neutrality and evolvability: neutrality improves evolvability. We also identify four characteristics of adaptive/neutral mutations that are associated with high evolvability. They may be the ingredients in designing effective Evolutionary Computation systems for the Boolean class problem.

Keywords:

Neutrality, Evolvability, Boolean function landscape, Neutral mutation, Exploration vs. Exploitation, Graph-based Genetic Programming

14 pages


Polymorphism and Genetic Programming

Tina Yu

Abstract:

Types have been introduced to Genetic Programming (GP) by researchers with different motivation. We present the concept of types in GP and introduce a typed GP system, PolyGP, that supports polymorphism through the use of three different kinds of type variable. We demonstrate the usefulness of this kind of polymorphism in GP by evolving two polymorphic programs (nth and map) using the system. Based on the analysis of a series of experimental results, we conclude that this implementation of polymorphism is effective in assisting GP evolutionary search to generate these two programs. PolyGP may enhance the applicability of GP to a new class of problems that are difficult for other polymorphic GP systems to solve.

Keywords:

Polymorphism, Strongly Typed GP, STGP, Multi-objective optimisation, Typed GP, Constraint handling, PolyGP

16 pages

Posters

Programmable Smart Membranes: Using Genetic Programming to Evolve Scalable Distributed Controllers for a Novel Self-Reconfigurable Modular Robotic Application

Forrest H Bennett III - Brad Dolin - Eleanor G. Rieffel

Abstract:

Self-reconfigurable modular robotics represents a new approach to robotic hardware, in which the "robot" is composed of many simple, identical interacting modules. We propose a novel application of modular robotics: the programmable smart membrane, a device capable of actively filtering objects based on numerous measurable attributes. Creating control software for modular robotic tasks like the smart membrane is one of the central challenges to realizing their potential advantages. We use genetic programming to evolve distributed control software for a 2-dimensional smart membrane capable of distinguishing objects based on color. The evolved controllers exhibit scalability to a large number of modules and robustness to the initial configurations of the robotic filter and the particles.

Keywords:

modular robot, distributed control, smart membrane, self-reconfigurable, scalable, robust

12 pages


A GP Artificial Ant for image processing: preliminary experiments with EASEA

Enzo Bolis - Christian Zerbi - Pierre Collet - Jean Louchet - Evelyne Lutton

Abstract:

This paper describes how animat-based "food foraging" techniques may be applied to the design of low-level image processing algorithms. First, we show how we implemented the food foraging application using the EASEA software package. We then use this technique to evolve an animat and learn how to move inside images and detect high-gradient lines with a minimum exploration time. The resulting animats do not use standard "scanning + filtering" techniques but develop other image exploration strategies close to contour tracking. Experimental results on grey level images are presented.

Keywords:

Image processing, Contour detection, EASEA, Animat

10 pages


Feature Extraction for the k-Nearest Neighbour Classifier with Genetic Programming

Martijn C.J. Bot

Abstract:

In pattern recognition the curse of dimensionality can be handled either by reducing the number of features, e.g. with decision trees or by extraction of new features.

We propose a genetic programming (GP) framework for automatic extraction of features with the express aim of dimension reduction and the additional aim of improving accuracy of the k-nearest neighbour (k-NN) classifier. We will show that our system is capable of reducing most datasets to one or two features while k-NN accuracy improves or stays the same. Such a small number of features has the great advantage of allowing visual inspection of the dataset in a two-dimensional plot.

Since k-NN is a non-linear classification algorithm, we compare several linear fitness measures. We will show the a very simple one, the accuracy of the minimal distance to means (mdm) classifier outperforms all other fitness measures.

We introduce a stopping criterion gleaned from numeric mathematics. New features are only added if the relative increase in training accuracy is more than a constant d, for the mdm classifier estimated to be 3.3

Keywords:

Feature Extraction, Machine Learning

12 pages


An Indirect Block-Oriented Representation for Genetic Programming

Eva Brucherseifer - Peter Bechtel - Stephan Freyer - Peter Marenbach

Abstract:

When Genetic Programming (GP) is applied to system identification or controller design different codings can be used for internal representation of the individuals. One common approach is a block-oriented representation where nodes of the tree structure directly correspond to blocks in a block diagram. In this paper we present an indirect block-oriented representation, which adopts some aspects of the way humans perform the modelling in order to increase the GP system's performance. A causality measure based on an edit distance is examined to compare the direct an the indirect representation. Finally, results from a real world application of the indirect block-oriented representation are presented.

Keywords:

Block-oriented representation, Biotechnology, Process modelling, Controller design, Causality

12 pages


Raising the Dead; Extending Evolutionary Algorithms with a Case-based Memory

Jeroen Eggermont - Tom Lenaerts - Sanna Poyhonen - Alexandre Termier

Abstract:

In dynamically changing environments, the performance of a standard evolutionary algorithm deteriorates. This is due to the fact that the population, which is considered to contain the history of the evolutionary process, does not contain enough information to allow the algorithm to react adequately to changes in the fitness landscape. Therefore, we added a simple, global case-based memory to the process to keep track of interesting historical events. Through the introduction of this memory and a storing and replacement scheme we were able to improve the reaction capabilities of an evolutionary algorithm with a periodically changing fitness function.

Keywords:

Dynamic Fitness, Global Memory

11 pages


Layered Learning in Genetic Programming for a Co-operative Robot Soccer Problem

Steven M. Gustafson - William H. Hsu

Abstract:

We present an alternative to standard genetic programming (GP) that applies layered learning techniques to decompose a problem. GP is applied to subproblems sequentially, where the population in the last generation of a subproblem is used as the initial population of the next subproblem. This method is applied to evolve agents to play keep-away soccer, a subproblem of robotic soccer that requires cooperation among multiple agents in a dynnamic environment. The layered learning paradigm allows GP to evolve better solutions faster than standard GP. Results show that the layered learning GP outperforms standard GP by evolving a lower fitness faster and an overall better fitness. Results indicate a wide area of future research with layered learning in GP.

Keywords:

Layered Learning, Hierarchical abstractions, Robot soccer, Robots, Multiagent systems

11 pages


Linear-Tree GP and its comparison with other GP structures

Wolfgang Kantschik - Wolfgang Banzhaf

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-tree. We describe the linear-tree-structure, as well as crossover and mutation for this new GP structure in detail. We compare linear-tree programs with linear and tree programs by analyzing their structure and results on different test problems.

Keywords:

Linear tree structure, GP representation, Crossover

11 pages


Evolving Hand-Eye Coordination for a Humanoid Robot with Machine Code Genetic Programming

W. B. Langdon - Peter Nordin

Abstract:

We evolve, using AIMGP machine code genetic programming, Discipulus, an approximation of the inverse kinematics of a real robotics arm with many degrees of freedom. Elvis is a bipedal robot with human-like geometry and motion capabilities -- a humanoid, primarily controlled by evolutionary adaptive methods. The GP system produces a useful inverse kinematic mapping, from target 3-D points (via pairs of stereo video images) to a vector of arm controller actuator set points.

Keywords:

Humanoid Robotics, Genetic Reasoning, Brain Building, Robotic Arm, Robots, Inverse Kinematics, Stereo Vision, Discipulus

12 pages


Adaption of Operator Probabilities in Genetic Programming

Jens Niehaus - Wolfgang Banzhaf

Abstract:

In this work we tried to reduce the number of free parameters within Genetic Programming without reducing the quality of the results. We developed three new methods to adapt the probabilities, different genetic operators are applied with. Using two problems from the areas of symbolic regression and classification we showed that the results in these cases were better than randomly chosen parameter sets and could compete with parameter sets chosen with empirical knowledge.

Keywords:

Adaptation, Adaption, Structure Optimisation

12 pages


Crossover in Grammatical Evolution: The Search Continues

Michael O'Neill - Conor Ryan - Maarten Keijzer - Mike Cattolico

Abstract:

Grammatical Evolution is an evolutionary automatic programming algorithm that can produce code in any language, requiring as inputs a BNF grammar definition describing the output language, and the fitness function. The utility of crossover in GP systems has been hotly debated for some time, and this debate has also arisen with respect to Grammatical Evolution. This paper serves to continue an analysis of the crossover operator in Grammatical Evolution by looking at the result of turning off crossover, and by exchanging randomly generated blocks in a headless chicken-like crossover. Results show that crossover in Grammatical Evolution is essential on the problem domains examined. The mechanism of one-point crossover in Grammatical Evolution is discussed, resulting in the discovery of some interesting properties that could yield an insight into the operator's success.

Keywords:

Grammatical Evolution, Crossover, Genotype-Phenotype Mapping, Linear Genome, Grammar

12 pages


Computational Complexity, Genetic Programming, and Implications

Bart Rylander - Terry Soule - James Fostery

Abstract:

Recent theory work has shown that a Genetic Program (GP) used to produce programs may have output that is bounded above by the GP itself [l]. This paper presents proofs that show that 1) a program that is the output of a GP or any inductive process has complexity that can be bounded by the Kolmogorov complexity of the originating program; 2) this result does not hold if the random number generator used in the evolution is a true random source; and 3) an optimization problem being solved with a GP will have a complexity that can be bounded below by the growth rate of the minimum length problem representation used for the implementation. These results are then used to provide guidance for GP implementation.

Keywords:

Computational Complexity, Quantum Computing

13 pages


Genetic Programming for Financial Time Series Prediction

Massimo Santini - Andrea Tettamanzi

Abstract:

This paper describes an application of genetic programming to forecasting financial markets that allowed the authors to rank first in a competition organized within the CEC2000 on "Dow Jones Prediction". The approach is substantially driven by the rules of that competition, and is characterized by individuals being made up of multiple GP expressions and specific genetic operators.

Keywords:

Time Series prediction, Financial markets, Multi-expression individuals, Genetic operators, Crossover

10 pages


Active Handwritten Character Recognition using Genetic Programming

A. Teredesai - J. Park - V. Govindaraju

Abstract:

This paper is intended to demonstrate the effective use of genetic programming in handwritten character recognition. When the resources utilized by the classifier increase incrementally and depend on the complexity of classification task, we term such a classifier as active. The design and implementation of active classifiers based on genetic programming principles becomes very simple and efficient. Genetic Programming has helped optimize handwritten character recognition problem in terms of feature set selection. We propose an implementation with dynamism in pre-processing and classification of handwritten digit images. This paradigm will supplement existing methods by providing better performance in terms of accuracy and processing time per image for classification. Different levels of informative detail can be present in image data and our proposed paradigm helps highlight these information rich zones. We compare our performance with passive and active handwritten digit classification schemes that are based on other pattern recognition techniques.

Keywords:

Pattern Recognition, Active Character Recognition, Digit Recognition, Handwritten digit classification

9 pages

Web site designed and maintained by Chris Osborne at EvoNet.