EuroGP2003
EvoWorkshops2003
14-16 April 2003

Home

Post conference pages
2004 announcement
Awards
Photos
Feature articles
Proceedings

Joint event pages
Registration
Travel bursaries
Information for authors
Travel information
Where to stay
Local information
Programme overview
All accepted papers

EuroGP2003/EvoWorkshops

All accepted papers

Springer Lecture Notes in Computer Science series The EuroGP2003 & EvoWorkshops2003 proceedings will be
published by Spinger as part of their
Lecture Notes in Computer Science series.


A Genetic Algorithm for the Index Selection Problem
Kratica J, Ljubic I, Tosic D
This paper considers the problem of minimizing the response time for a given database workload by a proper choice of indexes. This problem is NP-hard and known in the literature as the Index Selection Problem (ISP). We propose a genetic algorithm (GA) for solving the ISP. Computational results of the GA on standard ISP instances are compared to branch-and-cut method and its initialisation heuristics and two state of the art MIP solvers: CPLEX and OSL. These results indicate good performance, reliability and efficiency of the proposed approach.
EvoCOP Session 2: Satisfiability and selection problems: April 14, 1600-1800

A Simple but Theoretically-motivated Method to Control Bloat in Genetic Programming
Poli R
This paper presents a simple method to control bloat which is based on the idea of strategically and dynamically creating fitness {``holes{'' in the fitness landscape which repel the population. In particular we create holes by zeroing the fitness of a certain proportion of the offspring that have above average length. Unlike other methods where all individuals are penalised when length constraints are violated, here we randomly penalise only a fixed proportion of all the constraint-violating offspring. The paper describes the theoretical foundation for this method and reports the results of its empirical validation with two relatively hard test problems, which has confirmed the effectiveness of the approach.
EuroGP Session 7: Meta-search, compiler optimisation and bloat: April 15, 1120-1250

A Study of Greedy, Local Search and Ant Colony Optimization Approaches for Car Sequencing Problems
Gottlieb J, Puchta M, Solnon C
This paper describes and compares several heuristic approaches for the car sequencing problem. We first study greedy heuristics, and show that dynamic ones clearly outperform their static counterparts. We then describe local search and ant colony optimization (ACO) approaches, that both integrate greedy heuristics, and experimentally compare them on benchmark instances. ACO yields the best solution quality for smaller time limits, and it is comparable to local search for larger limits. Our best algorithms proved one instance being feasible, for which it was formerly unknown whether it is satisfiable or not.
EvoCOP Session 3: Ant colony optimisation 1: April 15, 1120-1250

A Template Approach to Producing Incremental Objective Cost Functions for Local Search Meta-heuristics
Randall M
Meta-heuristic search techniques based on local search operators have proven to be very eective at solving combinatorial optimisation problems. A characteristic of local search operators is that they usually only make a small change to the solution state when applied. As a result, it is often unnecessary to re-evaluate the entire objective function once a transition is made but to use an incremental cost function. For example in the travelling salesman problem, the position of two cities within a tour, may be interchanged. Using an incremental cost function, this equates to an O(1) operation as opposed to an O(n) operation (where n is the number of cities). In this paper, a new approach based on the use of templates is developed for the generic linked list modelling system [4]. It demonstrates that incremental objective cost functions can be automatically generated for given problems using dierent local search operators.
EvoCOP Session 4: Miscellaneous: April 15, 1345-1515

Accurate L-corner Measurement using USEF Functions and Evolutionary Algorithms
Olague G, n Hernandez B, Dunn E
Corner feature extraction is studied in this paper as a global optimization problem. We propose a new parametric corner modeling based on a Unit Step Edge Function (USEF) that defines a straight line edge. This USEF function is a distribution function, which models the optical and physical characteristics present in digital photogrammetric systems. We search model parameters characterizing completely single gray-value structures by means of least squares fit of the model to the observed image intensities. As the identification results relies on the initial parameter values and as usual with non-linear cost functions in general we cannot guarantee to find the global minimum. Hence, we introduce an evolutionary algorithm using an affine transformation in order to estimate the model parameters. This transformation encapsulates within a single algebraic form the two main operations, mutation and crossover, of an evolutionary algorithm. Experimental results show the superiority of our L-corner model applying several levels of noise with respect to simplex and simulated annealing.
EvoIASP Session 1: Computer Vision: April 14, 1130-1300

Adapting to Complexity During Search in Combinatorial Landscapes
Riopka T
Fitness landscape complexity in the context of evolutionary algorithms can be considered to be a relative term due to the complex interaction between search strategy, problem difficulty and problem representation. A new paradigm for genetic search referred to as the Collective Learning Genetic Algorithm (CLGA) has been demonstrated for combinatorial optimization problems which utilizes genotypic learning to do recombination based on a cooperative exchange of knowledge (instead of symbols) between interacting chromosomes. There is evidence to suggest that the CLGA is able to modify its recombinative behavior based on the consistency of the information in its environment, specifically, the observed fitness landscape. By analyzing the structure of the evolving individuals, a landscape-complexity measure is extracted a posteriori and then plotted for various types of example problems. This paper presents preliminary results that show that the CLGA appears to adapt its search strategy to the fitness landscape induced by the CLGA itself, and hence relative to the landscape being searched.
EvoCOP Session 4: Miscellaneous: April 15, 1345-1515

Algorithms for identification key generation and optimization.
Reynolds A, Rayward-Smith V, de la Iglesia B, Wesselink J, Robert V, Boekhout T
Algorithms for the automated creation of low cost identification keys are described and theoretical and empirical justifications are provided. The algorithms are shown to handle differing test costs, prior probabilities for each potential diagnosis and tests that produce uncertain results. The approach is then extended to cover situations where more than one measure of cost is of importance, by allowing tests to be performed in batches. Experiments are performed on a real-world case study involving the identification of yeasts.
EvoBIO Session 5: Optimisation in Bioinformatics: April 15, 1120-1250

An Analysis of Diversity of Constants of Genetic Programming
Ryan C, Keijzer M
This paper conducts an investigation into the manner in which constants evolve during the course of GP run. It starts by describing an intuitive Gaussian type mutation for constants and showing that its ability to produce small changes in individuals leads to a high performance. It then demonstrates the surprising result that, in a selection of real world problems, simple random mutation performs better. The paper then finishes with an analysis of the diversity of constants in the population, and the manner in which this changes over time.
EuroGP Session 5: Posters: April 14, 1730-1930

An Enhanced Framework for Microprocessor
Corno F, Squillero G
Test programs are fragment of code, but, unlike ordinary application programs, they are not intended to solve a problem, nor to calculate a function. Instead, they are supposed to give information about the machine that actually executes them. Today, the need for effective test programs is increasing, and, due to the inexorable increase in the number of transistor that can be integrated onto a single silicon die, devising effective test programs is getting more problematical. This paper presentsGP, an efficient and versatile approach to test-program generation based on an evolutionary algorithm. The proposed methodology is highly versatile and improves previous approaches, allowing the test-program generator generating complex assembly programs that include subroutines calls.
EuroGP Session 5: Posters: April 14, 1730-1930

An Experimental Comparison of Two Different Encoding Schemes for the Location of Base Stations in Cellular Networks
Brizuela C, Gutierrez E
This paper presents preliminary results on the comparison of binary and integer based representations for the Base Stations Location (BSL) problem. The simplest model of this problem, which is already NP-complete, is dealt with to compare also dierent crossover operators. Experimental results support the hypothesis that the integer based representation with a specific crossover operator outperforms the more traditional binary one for a very specific set of instances.
EvoCOP Session 5: Mobile cellular networks: April 15, 1530-1630

An innovative application of a constrained-syntax genetic programming system to the problem ofpredicting survival of patients
Bojarczuk C, Lopes H, Freitas A
This paper proposes a constrained-syntax genetic programming (GP) algorithm for discovering classification rules in medical data sets. The proposed GP contains several syntactic constraints to be enforced by the system using a disjunctive normal form representation, so that individuals represent valid rule sets that are easy to interpret. The GP is compared with C4.5 in a real-world medical data set. This data set represents a difficult classification problem, and a new preprocessing method was devised for mining the data.
EuroGP Session 3: Medical applications: April 14, 1400-1530

Analysis of a Digit Concatenation Approach to Constant Creation
O'Neill M, Dempsey I, Brabazon A, Ryan C
This study examines the utility of employing digit concatenation, as distinct from the traditional expression based approach, for the purpose of evolving constants in Grammatical Evolution. Digit concatenation involves creating constants (either whole or real numbers) by concatenating digits to form a single value. The two methods are compared using three different problems, which are finding a static real constant, finding dynamic real constants, and a quadratic map, which on iteration generates a chaotic time-series. The results indicate that the digit concatenation approach results in a significant improvement in the best fitness obtained across all problems analysed here.
EuroGP Session 2: Linear GP, crossover and constants: April 14, 1130-1300

Analyzing a Unified Ant System for the VRP and Some of its Variants
Reimann M, Doerner K, Hartl R
In this paper we analyze the application of an Ant System to dierent vehicle routing problems. More specifically, we study the robustness of our Unified Ant System by evaluating its performance on four dierent problem classes within the domain of vehicle routing.
EvoCOP Session 6: Ant colony optimisation 2: April 16, 1000-1100

Ant Algorithms for the University Course Timetabling Problem with Regard to the State-of-the-Art
Socha K, Sampels M, Manfrin M
Two ant algorithms solving a simplified version of a typical university course timetabling problem are presented Ant Colony System and MAX-MIN Ant System. The algorithms are tested over a set of instances from three classes of the problem. Results are compared with recent results obtained with several metaheuristics using the same local search routine (or neighborhood definition), and a reference random restart local search algorithm. Further, both ant algorithms are compared on an additional set of instances. Conclusions are drawn about the performance of ant algorithms on timetabling problems in comparison to other metaheuristics. Also the design, implementation, and parameters of ant algorithms solving the university course timetabling problem are discussed. It is shown that the particular implementation of an ant algorithm has significant influence on the observed algorithm performance.
EvoCOP Session 3: Ant colony optimisation 1: April 15, 1120-1250

Anticipating Bankruptcy Reorganisation from Raw Financial Data using Grammatical Evolution
Brabazon A, O'Neill M
This study using Grammatical Evolution, constructs a series of models for the prediction of bankruptcy, employing information drawn from financial statements. Unlike prior studies in this domain, the raw financial information is not preprocessed into pre-determined financial ratios. Instead, the ratios to be incorporated into the predictive rule are evolved from the raw financial data. This allows the creation and subsequent evolution of alternative ratio-based representations of the financial data. A sample of 178 publically quoted, US firms, drawn from the period 1991 to 2000 are used to train and test the model. The best evolved model in each time period correctly classified 78 (70)% of the firms in the out-of-sample validation set, one (three) year(s) prior to failure. The utility of a number of different Grammars for the problem domain is also examined.
EvoIASP Session 3: Miscellanea: April 14, 1600-1800

Applying Memetic Algorithms to the Analysis of Microarray Data
Cotta C, Mendes A, Garcia V, Franca P, Moscato P
This work deals with the application of Memetic Algorithms to the Microarray Gene Ordering problem, a NP-hard problem with strong implications in Medicine and Biology. It consists in ordering a set of genes, grouping together the ones with similar behavior. We propose a MA, and evaluate the influence of several features, such as the intensity of local searches and the utilization of multiple populations, in the performance of the MA. We also analyze the impact of different objective functions on the general aspect of the solutions. The instances used for experimentation are extracted from the literature and represent real biological systems.
EvoBIO Session 1: Microarray analysis 1: April 14, 1145-1300

ArtiE-Fract: The Artist’s Viewpoints.
Lutton E, Cayla E, Chapuis J
ArtiE-Fract is an interactive evolutionary system designed for artistic exploration of the space of fractal 2D shapes. We report in this paper an experiment performed with an artist, the painter Emmanuel Cayla. The benefit of such a collaboration was twofold: first of all, the system itself has evolved in order to better fit the needs of non-computer-scientist users, and second, it as initiated an artistic approach and open up the way to new possible design outputs.
EvoMUSART Session 2: Evolutionary Computation Systems in Visual Arts, performances and Installations: April 14, 1400-1530

Artificial Immune System for Classification of Cancer
Ando S, Hitoshi I
This paper presents a method for cancer type classification based on microarray-monitored data. The method is based on artificial immune system(AIS), which utilizes immunological recognition for classification. The system evolutionarily selects important genes; optimize their weights to derive classification rules. This system was applied to gene expression data of acute leukemia patients to classify their cancer class. The primary result found few classification rules which correctly classified all the test samples and gave some interesting implications for feature selection principles.
EvoBIO Session 2: Microarray analysis 2: April 14, 1400-1530

Artificial Immune System Programming for Symbolic Regression
Johnson C
Artificial Immune Systems are computational algorithms which take their inspiration from the way in which natural immune systems learn to respond to attacks on an organism. This paper discusses how such a system can be used as an alternative to genetic algorithms as a way of exploring program-space in a system similar to genetic programming. Some experimental results are given for a symbolic regression problem. The paper ends with a discussion of future directions for the use of artificial immune systems in program induction.
EuroGP Session 5: Posters: April 14, 1730-1930

Assembling Strategies in Extrinsic Evolvable Hardware with Bidirectional Incremental Evolution
Baradavkaigor I, Kalganova T
Bidirectional incremental evolution (BIE) has been proposed as a technique to overcome the "stalling" effect in evolvable hardware applications. However preliminary results show perceptible dependence of performance of BIE and quality of evaluated circuit on assembling strategy applied during reverse stage of incremental evolution. The purpose of this paper is to develop assembling strategy that will assist BIE to produce relatively optimal solution with minimal computational effort (e.g. the minimal number of generations).
EuroGP Session 5: Posters: April 14, 1730-1930

Behavioral plasticity in autonomous agents: a comparison between two types of controller
Tuci E, Quinn M
Blynel et al. recently compared two types of recurrent neural network, Continuous Time Recurrent Neural Networks (CTRNNs) and Plastic Neural Networks (PNNs), on their ability to control the behaviour of a robot in a simple learning task; they found little difference between the two. However, this may have been due to the simplicity of their task. Our comparison on a slightly more complex task yielded very different results: 70% runs with CTRNNs produced successful learning networks; runs with PNNs failed to produce a single success.
EvoROB Session 3: : April 15, 1345-1515

Chromosomal breakpoint detection in Human Cancer
Jong K, Marchiori E, van der Vaart A, Ylstra B, Weiss M, Meijer G
Chromosomal aberrations are differences in DNA sequence copy number of chromosome regions \footnote{Aberrations can occur without change of copy number, but these aberrations are not the subject of this paper.}. These differences may be crucial genetic events in the development and progression of human cancers. Array Comparative Genomic Hybridization is a laboratory method used in cancer research for the measurement of chromosomal aberrations in tumor genomes. A recurrent aberration at a particular genome location may indicate the presence of a tumor suppressor gene or an oncogene. The goal of the analysis of this type of data includes detection of locations of copy number changes, called breakpoints, and estimate of the values of the copy number value before and after a change. Knowing the exact locations of a breakpoint is import ant to identify possibly damaged genes. This paper introduces genetic local search algorithms to perform this task.
EvoBIO Session 2: Microarray analysis 2: April 14, 1400-1530

Combinations of Local Search and Exact Algorithms
Dumitrescu I, Stützle T
In this paper we describe the advantadges and disadvantages of local search and exact methods of solving NP-hard problems and see why combining the two approaches is highly desirable. We review some of the papers existent in the literature that create new algorithms from such combinations. In this paper we focus on local search approaches that are strengthened by the use of exact algorithms.
EvoCOP Session 1: New directions: April 14, 1400-1515

Comparison of AdaBoost and Genetic Programming for combining Neural Networks for Drug Discovery.
Langdon W, Barrett S, Buxton B
Genetic programming (GP) based data fusion and AdaBoost can both improve {\em in vitro} prediction of Cytochrome P450 activity by combining artificial neural networks (ANN). Pharmaceutical drug design data provided by high throughput screening (HTS) is used to train many base ANN classifiers. In data mining (KDD) we must avoid over fitting. The ensembles do extrapolate from the training data to other unseen molecules. I.e.\ they predict inhibition of a P450 enzyme by compounds unlike the chemicals used to train them. Thus the models might provide {\em in silico} screens of virtual chemicals as well as physical ones from Glaxo\allowbreak SmithKline (GSK)'s cheminformatics database. The receiver operating characteristics (ROC) of boosted and evolved ensemble are given.
EvoBIO Session 5: Optimisation in Bioinformatics: April 15, 1120-1250

Competitive Co-Evolution of Predator and Prey Sensory-Motor Systems
Buason G, Ziemke T
A recent trend in evolutionary robotics research is to maximize selforganization in the design of robotic systems in order to reduce the human designer bias. This article presents simulation experiments that extend Nolfi and Floreano’s work on competitive co-evolution of neural robot controllers in a predator-prey scenario and integrate it with ideas from work on the ‘coevolution’ of robot morphology and control systems. The aim of the twenty-one experiments summarized here has been to systematically investigate the tradeoffs and interdependencies between morphological parameters and behavioral strategies through a series of predator-prey experiments in which increasingly many aspects are subject to self-organization through competitive co-evolution. The results illustrate that competitive co-evolution has great potential as a method for the automatic design of robotic systems.
EvoROB Session 2: : April 15, 1120-1250

Constrained Coverage Optimization for Mobile Cellular Networks
Du L, Bigham J
This paper explores the use of evolutionary algorithms to optimise cellular coverage so as to balance the trac load over the whole mobile cellular network. A transformation of the problem space is used to remove the principal power constraint. A problem with the intuitive transformation is shown and a revised transformation with much better performance is presented. This highlights a problem with transformationbased methods in evolutionary algorithms. While the aim of transformation is to speed convergence, a bad transformation can be counterproductive. A criterion that is necessary for successful transformations is explained. Using penalty functions to manage the constraints was investigated but gave poor results. The techniques described can be used as constraint-handling method for a wide range of constrained optimisations.
EvoCOP Session 5: Mobile cellular networks: April 15, 1530-1630

Cooperative Evolution on the Intertwined Spirals Problem
Soule T
This paper examines the evolution cooperation on the intertwined spirals problem.Multiple cooperation mechanisms are tested. Cooperation evolves fairly easily for each of the cooperation mechanisms, producing compact, successful team based solutions. Importantly, the team members' fitness is relatively poor.
EuroGP Session 5: Posters: April 14, 1730-1930

Cross validation consistency for the assessment of genetic programming results in microarray studies
Moore J
DNA microarray technology has made it possible to measure the expression levels of thousands of genes simultaneously in a particular cell or tissue. The challenge for computational biologists and bioinformaticists will be to develop methods that are able to identify subsets of gene expression variables and features that classify cells and tissues into meaningful biological and clinical groups. Genetic programming (GP) has emerged as a machine learning tool for variable and feature selection in microarray data analysis. However, a limitation of GP is a lack of cross validation strategies for the assessment of GP results. This is partly due to the inherent complexity of GP due to its stochastic properties. Here, we introduce and review cross validation consistency (CVC) as a new modeling strategy for use with GP. We review the application of CVC to symbolic discriminant analysis (SDA), a GP-based analytical strategy for mining gene expression patterns in DNA microarray data.
EvoBIO Session 3: Methodology: April 14, 1600-1700

Decreasing the Number of Evaluations in Evolutionary Algorithms by using a Meta-Model of the Fitness Function
Ziegler J, Banzhaf W
In this paper a method is presented that decreases the necessary number of evaluations in Evolutionary Algorithms. A classifier with confidence information is evolved to replace time consuming evaluations during tournament selection. Experimental analysis of a mathematical example and the application of the method to the problem of evolving walking patterns for quadruped robots show the potential of the presented approach.
EuroGP Session 4: Meta-fitness and alternative computational structures: April 14, 1600-1730

Discovering haplotypes in lynkage disequilibrium mapping with an adaptive genetic algorithm.
Jourdan L, Dhaenens C, Talbi G
In this paper, we present an evolutionary approach to discover candidate haploty pes in a linkage disequilibrium study. This work takes place into the study of f actors involved in multi-factorial diseases such as diabetes and obesity. A firs t study on the linkage disequilibrium problem structure led us to use a genetic algorithm to solve it. Due to the particular, but classical, evaluation function given by the biologists, we design our genetic algorithm with several populatio ns. This model lead us to implement different cooperative operators such as muta tion and crossover. Probabilities of application of those mechanisms are set ada ptively. In order to introduce some diversity, we also implement a random immigr ant strategy and to cover up the cost of the evaluation computation we paralleli ze it in a master / slave model. Different combinations of the presented mechani sms are tested on real data and compared in term of robustness and computation c ost. We show that the most complete strategy is able to find the best solutions and is the most robust.
EvoBIO Session 5: Optimisation in Bioinformatics: April 15, 1120-1250

Disease modeling using Evolved Discriminate Function
Werner J, Kalganova T
Precocious diagnosis increases the survival time and patient quality of life. It is a binary classification, exhaustively studied in the literature. This paper innovates proposing the application of genetic programming to obtain a discriminate function. This function contains the disease dynamics used to classify the patients with as little false negative diagnosis as possible. If its value is greater than zero then it means that the patient is ill, otherwise healthy. A graphical representation is proposed to show the influence of each dataset attribute in the discriminate function. The experiment deals with Breast Cancer and Thrombosis and Collagen diseases diagnosis. The main conclusion is that the discriminate function is able to classify the patient using numerical clinical data, and the graphical representation displays patterns that allow understanding of the model.
EuroGP Session 5: Posters: April 14, 1730-1930

Divide and Conquer: Genetic Programming Based on Multiple Branches Encoding
Rodriguez K, Oliver-Morales C
This paper describes an alternative genetic programming encoding, which is based on a rooted-node with fixed-content. This rooted node combines partial results of a set of multiple branches. Hence, this approach is named Multiple Branches Genetic Programming. It is tested on a symbolic regression problem and used on a Boolean domain to solve the even-n parity problem.
EuroGP Session 9: Multi-program integration: April 15, 1530-1630

DNA based algorithms for some scheduling problems
Blazewicz J, Formanowicz P, Urbaniak R
RNA computing is an alternative approach to performing computations. In general it is possible to design a series of biochemical experiments involving DNA molecules which is equivalent to making transformations of information. In classical computing devices electronic logical gates are elements which allow for storing and transforming information. Designing of an appropriate sequence or a net of ''store'' and ''transform'' operations (in a sense of building a device or writing a program) is equivalent to preparing some computations. In DNA computing the situation is analogous, and the main difference is that instead of electronic gates DNA molecules are used for storing and transforming information. From this follows that the set of basic operations is different in comparison to electronic devices but the results of using them may be similar. In this paper DNA based algorithms for solving some single machine with limited availability scheduling problems are presented. To our best knowledge it is the first attempt to solve scheduling problems by molecular algorithms.
EvoSTIM Session 1: : April 14, 1130-1300

Ensemble techniques for Parallel Genetic Programming based Classifiers
Folino G, Pizzuti C, Spezzano G
An extension of Cellular Genetic Programming for data classification to induce an ensemble of predictors is presented. Each classifier is trained on a different subset of the overall data, then they are combined to classify new tuples by applying a simple majority voting algorithm, like bagging. Preliminary results on a large data set show that the ensemble of classifiers trained on a sample of the data obtains higher accuracy than a single classifier that uses the entire data set at a much lower computational cost.
EuroGP Session 9: Multi-program integration: April 15, 1530-1630

Evolution of Collective Behavior in a Team of Physically Linked Robots
Baldassarre G, Nolfi S, Parisi D
In this paper we address the problem of how a group of four assembled simulated robots forming a linear structure can co-ordinate and move as straight and as fast as possible. This problem is solved in a rather simple and effective way by providing the robots with a sensor that detects the direction and intensity of the traction that the turret exerts on the chassis of each robot and by evolving their neural controllers. We also show how the evolved robots are able to generalize their ability in rather different circumstance by: (a) producing coordinated movements in teams with varying size, topology, and type of links; (b) displaying individual or collective obstacle avoidance behaviors when placed in an environment with obstacles; (c) displaying object pushing/pulling behavior when connected to or around a given object.
EvoROB Session 1: : April 15, 1000-1100

Evolutionary approach to discovery of classification rules from remote sensing images
Korczak J, Quirin A
In this article a new method for classification of remote sensing images is described. For most applications, these images contain voluminous, complex, and sometimes noisy data. For the approach presented herein, image classification rules are discovered by an evolution-based process, rather than by applying an a priori chosen classification algorithm. During the evolution process, classification rules are created using raw remote sensing images, the expertise encoded in classified zones of images, and statistics about related thematic objects. The resultant set of evolved classification rules are simple to interpret, efficient, robust and noise resistant. This evolution-based approach is detailed and validated based on remote sensing images covering not only urban zones of Strasbourg, France, but also vegetation zones of the lagoon of Venice.
EvoIASP Session 3: Miscellanea: April 14, 1600-1800

Evolutionary Computing for the Satisfiability Problem
Hao J, Lardeux F, Saubion F
This paper presents GASAT, a hybrid evolutionary algorithm for the satisfiability problem (SAT). A specific crossover operator generates new solutions, that are improved by a tabu search procedure. The performance of GASAT is assessed using a set of well-known benchmarks. Comparisons with state-of-the-art SAT algorithms show that GASAT gives very competitive results. These experiments also allow us to introduce a new SAT benchmark from a coloring problem.
EvoCOP Session 2: Satisfiability and selection problems: April 14, 1600-1800

Evolutionary Design of Objects Using Scene Graphs
Ebner M
One of the main issues in evolutionary design is how to create three-dimensional shape. The representation needs to be general enough such that all possible shapes can be created, yet it has to be evolvable. That is, parent and offspring must be related. Small changes to the genotype should lead to small changes of the fitness of an individual. We have explored the use of scene graphs to evolve three-dimensional shapes. Two different scene graph representations are analyzed, the scene graph representation used by OpenInventor and the scene graph representation used by VRML. Both representations use internal floating point variables to specify three-dimensional vectors, rotation axes and rotation angles. The internal parameters are initially chosen at random, then remain fixed during the run. We also experimented with an evolution strategy to adapt the internal variables. Experimental results are presented for the evolution of a wind turbine. The VRML representation produced better results.
EuroGP Session 11: Alternative representations and 3-D shape design: April 16, 1000-1100

Evolutionary Music and the Zipf-Mandelbrot Law: Progress towards Developing Fitness Functions for Pleasant Music.
Manaris W, Vaughan D, Wagner C, Romero J, Davis R
A study on a 220-piece corpus (baroque, classical, romantic, 12-tone, jazz, rock, DNA strings, and random music) reveals that aesthetically pleasing music may be describable under the Zipf-Mandelbrot law. Various Zipf-based metrics have been developed and evaluated. Some focus on music-theoretic at-tributes such as pitch, pitch and duration, melodic intervals, and harmonic inter-vals. Others focus on higher-order attributes and fractal aspects of musical bal-ance. Zipf distributions across certain dimensions appear to be a necessary, but not sufficient condition for pleasant music. Statistical analyses suggest that com-binations of Zipf-based metrics might be used to identify genre and/or composer. This is supported by a preliminary experiment with a neural network classifier. We describe an evolutionary music framework under development, which utilizes Zipf-based metrics as fitness functions.
EvoMUSART Session 1: Evolutionary Computation in Music and Sound Creation: April 14, 1130-1300

Evolutionary Optimized Mold Temperature Control Strategies using a Multi-Polyline Approach
Mehnen J, Michelitsch T, Weinert K
During the machining process the tools for pressure and injection molding have to keep an optimal working temperature. This temperature depends on the workpiece material and allows a safe, efficient and precise machining process. The compact and very expensive steel molds are penetrated with deep hole drilling bores that are combined to form mold temperature control circuits. Today the structure of these circuits are designed manually. Here, a new automatic layout system for mold temperature control strategies is introduced which uses a multiobjective fitness function. The circuits are encoded via a polyline approach. The complex optimization problem is solved using a variation of the evolution strategy. The evolutionary approach as well as first results of the system will be discussed.
EuroGP Session 5: Posters: April 14, 1730-1930

Evolving Cellular Automata to Grow Microstructures
Basanta D, Bentley P, Miodownik M, Holm E
The properties of engineering structures such as cars, cell phones or bridges rely on materials and on the properties of these materials. The study of these properties, which are determined by the internal architecture of the material or microstructure, has significant importance for material scientists. One of the things needed for this study is a tool that can create microstructural patterns. In this paper we explore the use of a genetic algorithm to evolve the rules of an effector automata to recreate these microstructural patterns.
EuroGP Session 4: Meta-fitness and alternative computational structures: April 14, 1600-1730

Evolving Finite State Transducers: Some Initial Explorations
Lucas S
Finite state transducers (FSTs) are finite state machines that map strings in a source domain into strings in a target domain. While there are many reports in the literature of evolving general finite state machines, there has been much less work on evolving FSTs.In particular, the fitness functions required for evolving FSTs are generally different to those used for FSMs.This paper considers three string-distance based fitness functions.We compute their fitness distance correlations, and present results on using two of these (Strict and Hamming) to evolve FSTs. We can control the difficulty of the problem by the presence of short strings in the training set, which make the learning problem easier.In the case of the harder problem, the Hamming measure performs best, while the Strict measure performs best on the easier problem.
EuroGP Session 4: Meta-fitness and alternative computational structures: April 14, 1600-1730

Evolving Hierarchical and RecursiveTeleo-Reactive Programs through Genetic Programming
Kochenderfer M
Teleo-reactive programs and the triple tower architecture have been proposed as a framework for linking perception and action in agents. The triple tower architecture continually updates the agent's knowledge of the world and evokes actions according to teleo-reactive control structures. This paper uses block stacking problems to demonstrate how genetic programming may be used to evolve hierarchical and recursive teleo-reactive programs.
EuroGP Session 8: Feature construction and modularity and hierarchies in GP: April 15, 1345-1515

Evolving Motion of Robots with Muscles
Mahdavi S, Bentley P
The objective of this work is to investigate how effective smart materials are for generating the motion of a robot. Because of the unique method of locomotion, an evolutionary algorithm is used to evolve the best combination of smart wire activations to move most efficiently. For this purpose, a robot snake was built that uses Nitinol wire as muscles in order to move. The most successful method of locomotion that was evolved, closely resembled the undulating motion of the cobra snake. During experimentation, one of the four Nitinol wires snapped, and the algorithm then enabled adaptive behaviour by the robot by evolving another sequence of muscle activations that more closely resembled the undulations exhibited by the earthworm.
EvoROB Session 3: : April 15, 1345-1515

Evolving Neural Networks for the Control of a Lenticular Blimp
Doncieux S, Meyer J
We used evolution to shape a neural controller for keeping a blimp at a given altitude, and as horizontal as possible, despite disturbing winds. The blimp has a lenticular shape whose aerodynamic properties make it quite different from a classical cigar-shaped airship. Evolution has exploited these features to generate a neural network that proved to be more efficient than a hand-designed PID-based controller that independently controlled the blimp's three degrees of freedom.
EvoROB Session 3: : April 15, 1345-1515

Evolving Spiking Neuron Controllers for Phototaxis and Phonotaxis
Damper R, French R
Our long-term goal is to evolve neural controllers which reproduce in behaving robots the kind of phonotaxis behaviour seen in real animals, such as crickets. We have previously studied the evolution of neural circuitry which, when implanted in a Braitenberg type~2b vehicle, promoted phototaxis behaviour in the form of movement towards flashing lights of different frequencies. (It was simpler to study light-driven than acoustic-driven behaviour.)\ \ Since this is not truly sequential behaviour, we now describe new work to discriminate between particular mark-space ratio patterns of the same basic (flash or on-off) frequency. The next step will be to integrate the two behaviours so that robot taxis is driven by a signal with temporal structure closer to that of the cricket `song'.
EvoROB Session 2: : April 15, 1120-1250

Evolving Symbolic Controllers
Godzik N, Schoenauer M, Sebag M
The idea of symbolic controllers tries to bridge the gap between the top-down manual design of the controller architecture, as advocated in Brooks' subsumption architecture, and the bottom-up designer-free approach that is now standard within the Evolutionary Robotics community. The designer provides a set of elementary behavior, and evolution is given the goal of assembling them to solve complex tasks. Two experiments are presented, demonstrating the efficiency and showing the recursiveness of this approach. In particular, the sensitivity with respect to the proposed elementary behaviors, and the robustness w.r.t. generalization of the resulting controllers are studied in detail.
EvoROB Session 2: : April 15, 1120-1250

Experimental Comparison of Two Evolutionary Algorithms for Independent Set Problem
Borisovsky P, Zavolovskaya M
This work presents an experimental comparison of the steady-state genetic algorithm to the (1+1)-evolutionary algorithm applied to the maximum vertex independent set problem. The penalty approach is used for both algorithms and tuning of the penalty function is considered in the first part of the paper. In the second part we give some reasons why one could expect the competitive performance of the (1+1)-EA. The results of computational experiment are presented.
EvoCOP Session 2: Satisfiability and selection problems: April 14, 1600-1800

Experimental design based multi-parent crossover operator
Chan K, Fogarty T
Recently, the methodologies of multi-parent crossover have been developed by performing the crossover operation with multi-parent. Some studies have indicated the high performance of multi-parent cros\-sover on some numerical optimization problems. Here a new crossover operator has been proposed by integrating multi-parent crossover with the approach of experimental design. It is based on experimental design method in exploring the solution space that compensates the random search as in traditional genetic algorithm. By replacing the inbuilt randomness of crossover operator with a more systematical method, the proposed method outperforms the classical GA strategy on several GA benchmark problems.
EuroGP Session 5: Posters: April 14, 1730-1930

Exploring the T-Maze: Evolving Learning-Like Robot Behaviors using CTRNNs
Blynel J, Floreano D
This paper explores the capabilities of continuous time recurrent neural networks (CTRNNs) to display reinforcement learning-like abilities on a set of T-Maze and double T-Maze navigation tasks, where the robot has to locate and “remember” the position of a reward-zone. The “learning” comes about without modifications of synapse strengths, but simply from internal network dynamics, as proposed by [12]. Neural controllers are evolved in simulation and in the simple case evaluated on a real robot. The evolved controllers are analyzed and the results obtained are discussed.
EvoROB Session 1: : April 15, 1000-1100

Feature Construction and Selection using Genetic Programming and a Genetic Algorithm
Smith M, Bull L
The use of machine learning techniques to automatically analyse data for information is becoming increasingly widespread. In this paper we examine the use of Genetic Programming and a Genetic Algorithm to pre-process data before it is classified using the C4.5 decision tree learning algorithm. The Genetic Programming is used to construct new features from those available in the data, a potentially significant process for data mining since it gives consideration to hidden relationships between features. The Genetic Algorithm is used to determine which such features are the most predictive. Using ten well-known datasets we show that our approach, in comparison to C4.5 alone, provides marked improvement in a number of cases.
EuroGP Session 8: Feature construction and modularity and hierarchies in GP: April 15, 1345-1515

Fitness Distance Correlation in Structural Mutation Genetic Programming
Vanneschi L, Tomassini M, Collard P, Clergue M
A new kind of mutation for genetic programming based on the structural distance operators for trees is presented in this paper. We firstly describe a new genetic programming process based on these operators (we call it structural mutation genetic programming). Then we use structural distance to calculate the fitness distance correlation coefficient and we show that this coefficient is a reasonable measure to express problem difficulty for structural mutation genetic programming for the considered set of problems, i.e. unimodal trap functions, royal trees and MAX problem.
EuroGP Session 5: Posters: April 14, 1730-1930

From Implementations to a General Concept of Evolvable Machines
Sekanina L
This paper introduces a little bit different view on evolvable computational machines than it is usually presented. Evolvable machines are considered as mathematical machines. Traditional tools of theoretical computer science are then employed in order to obtain qualitatively new understanding the evolvable machines. In particular the questions related to formal definition and computational power are discussed. The concept is proposed in framework of traditional software and hardware implementations of evolvable machines.
EuroGP Session 5: Posters: April 14, 1730-1930

GAME-HDL: Implementation of Evolutionary Algorithms using Hardware Description Languages
Drechsler R, Drechsler N
Evolutionary Algorithms (EAs) have been proposed as a very powerful heuristic optimization technique to solve complex problems. Many case studies have shown that they work very efficient on a large set of problems, but in general the high qualities can only be obtained by high run time costs. In the past several approaches based on parallel implementations have been studied to speed up EAs. In this paper we present a technique for the implementation of EAs in hardware based on a the concept of reusable modules. These modules are described in a Hardware Description Language (HDL). The resulting ``hardware EA'' can be directly synthesized and mapped to Application Specific Integrated Circuits (ASICs) or Field Programmable Gate Arrays (FPGAs). This approach finds direct application in signal processing, where hardware implementations are often needed to meet the run time requirements of a real­time system. In our prototype implementation we used VHDL and synthesized an EA for solving the OneMax problem. Simulation results show the feasibility of the approach. Due to the use of a standard HDL, the components can be reused in the form of a library.
EvoIASP Session 3: Miscellanea: April 14, 1600-1800

Generalisation and model selection in supervised learning with evolutionary computation
Rowland J
EC-based supervised learning has been demonstrated to be an effective approach to forming predictive models in genomics, spectral interpretation, and other problems in modern biology. Longer-established methods such as PLS and ANN are also often successful. In supervised learning, overtraining is always a potential problem. The literature reports numerous methods of validating predictive models in order to avoid overtraining. Some of these approaches can be applied to EC-based methods of supervised learning, though the characteristics of EC learning are different from those obtained with PLS and ANN and selecting a suitably general model can be more difficult. This paper reviews the issues and various approaches, illustrating salient points with examples taken from applications in bioinformatics.
EvoBIO Session 3: Methodology: April 14, 1600-1700

Genetic algorithms for gene expression analysis
Keedwell E, Narayanan A
The major problem for current gene expression analysis techniques is how to identify the handful of genes which contribute to a disease from the thousands of genes measured on gene chips (microarrays). The use of a novel neural-genetic hybrid algorithm for gene expression analysis is described here. The genetic algorithm identifies possible gene combinations for classification and then uses the output from a neural network to determine the fitness of these combinations. Normal mutation and crossover operations are used to find increasingly fit combinations. Experiments on artificial and real-world gene expression databases are reported. The results from the algorithm are also explored for biological plausibility and confirm that the algorithm is a powerful alternative to standard data mining techniques in this domain.
EvoBIO Session 2: Microarray analysis 2: April 14, 1400-1530

Genetic Algorithms for the Generation of Models with Micropopulations.
Saez Y, Sanjuan O, Segovia J, Isasi P
The present article puts forward a method for an interactive model generation through the use of Genetic Algorithms applied to small populations. Micropopulations actually worsen the problem of the premature convergence of the algorithm, since genetic diversity is very limited. In addition, some key factors, which modify the changing likelihood of alleles, cause the likelihood of premature convergence to decrease. The present technique has been applied to the design of 3D models, starting from generic and standard pieces, using objective searches and searches with no defined objective.
EvoMUSART Session 2: Evolutionary Computation Systems in Visual Arts, performances and Installations: April 14, 1400-1530

Genetic algorithms on NK-landscapes: Effects of Selection, Drift, Mutation, and Recombination
Aguirre H, Tanaka K
Empirical studies have shown that the overall performance of random bit climbers on NK-Landscapes is superior to the performance of some simple and enhanced GAs. Analytical studies have also lead to suggest that NK-Landscapes may not be appropriate for testing the performance of GAs. In this work we study the effect of selection, drift, mutation, and recombination on NK-Landscapes for N = 96. We take a model of generational parallel varying mutation GA (GA-SRM) and switch on and off its major components to emphasize each of the four processes mentioned above. We observe that using an appropriate selection pressure and postponing drift make GAs quite robust on NK-Landscapes; different to previous studies, even simple GAs with these two features perform better than a random bit climber (RBC+) for a broad range of classes of problems (K>=4). We also observe that the interaction of parallel varying mutation with crossover improves further the reliability of the GA, especially for 32 > K > 12. Contrary to intuition, we find that for small K a mutation only EA is very effective and crossover may be omitted; but the relative importance of crossover interacting with varying mutation increases with K performing better than mutation alone (K > 12). We conclude that NK-Landscapes are useful for testing the GA s overall behavior and performance and also for testing each one of the major processes involved in a GA.
EvoCOP Session 4: Miscellaneous: April 15, 1345-1515

Genetic Improvisation Model, a framework for real-time performance environments.
Neminovsky P, Watson R
This paper presents the current state in an ongoing development of the Genetic Improvisation Model (GIM): a framework for the design of real-time improvi-sational systems. The aesthetic rationale for the model is presented, followed by a discussion of its general principles. A discussion of the Emonic Environment, a networked system for audiovisual creation built on GIM’s principles, follows.
EvoMUSART Session 1: Evolutionary Computation in Music and Sound Creation: April 14, 1130-1300

Genetic Programming Applied to Compiler Heuristic Optimization
Stephenson M, O'Reilly U, Martin M, Amarasinghe S
Genetic programming (GP) has a natural niche in the optimization of small but high payoff software heuristics.We use GP to optimize the priority functions associated with two well known compiler heuristics: predicated hyperblock formation, and register allocation.Our system achieves impressive speedups over a standard baseline for both problems.For hyperblock selection, application-specific heuristics obtain an average speedup of 23% (up to 73%) for the applications in our suite. By evolving the compiler's heuristic over several benchmarks, the best general-purpose heuristic our system found improves the predication algorithm by an average of 25% on our training set, and 9% on a completely unrelated test set.We also improve a well-studied register allocation heuristic.On average, our system obtains a 6% speedup when it specializes the register allocation algorithm for individual applications.The general-purpose heuristic for register allocation achieves a 3% improvement.
EuroGP Session 7: Meta-search, compiler optimisation and bloat: April 15, 1120-1250

Genetic Programming for Attribute Construction in Data Mining
Otero F, Silva M, Freitas A, Nievola J
For a given data set, its set of attributes defines its data space representation. The quality of a data space representation is one of the most important factors influencing the performance of a data mining algorithm. The attributes defining the data space can be inadequate, making it difficult to discover high-quality knowledge. In order to solve this problem, this paper proposes a Genetic Programming algorithm developed for attribute construction. This algorithm constructs new attributes out of the original attributes of the data set, performing an important preprocessing step for the subsequent application of a data mining algorithm.
EuroGP Session 5: Posters: April 14, 1730-1930

Genetic Programming with Boosting for Ambiguities in Regression Problems
Paris G, Robilliard D, Fonlupt C
Facing ambiguities in regression problems is a challenge.There exists many powerful evolutionary schemes to deal with regression, however, these techniques do not usually take into account ambiguities {i.e. the existence of 2 or more solutions for some or all points in the domain).Nonetheless ambiguities are present in some real world inverse problems, and it is interesting in such cases to provide the user with a choice of possible solutions. We propose in this article an approach based on boosted genetic programming in order to propose several solutions when ambiguities are detected.
EuroGP Session 12: Symbolic regression: April 16, 1120-1250

Genetic Programming With Meta-Search: Searching For a Successful Population Within The Classification Domain
Loveard T
The genetic programming (GP) search method can often vary greatly in the quality of solution derived from one run to the next. As a result, it is often the case that a number of runs must be performed to ensure that an effective solution is found. This paper introduces several methods which attempt to better utilise the computational resources spent on performing a number of independent GP runs. Termed meta-search strategies, these methods seek to search the space of evolving GP populations in an attempt to focus computational resources on those populations which are most likely to yield competitive solutions. Two meta-search strategies are introduced and evaluated over a set of classification problems. The meta-search strategies are termed a pyramid search strategy and a population beam search strategy. Additional to these methods, a combined approach using properties of both the pyramid and population beam search methods is evaluated. Over a set of five classification problems, results show that meta-search strategies can substantially improve the accuracy of solutions over those derived by a set of independent GP runs. In particular the combined approach is demonstrated to give more accurate classification performance whilst requiring less time to train than a set of independent GP runs, making this method a promising approach for problems for which multiple GP runs must be performed to ensure a quality solution.
EuroGP Session 7: Meta-search, compiler optimisation and bloat: April 15, 1120-1250

Genophone: Evolving Sounds and Integral Performance Parameter Mappings.
Mandelis J
This project explores the application of evolutionary techniques to the design of novel sounds and their characteristics during performance. It is based on the “selective breeding” paradigm and as such dispensing with the need for detailed knowledge of the Sound Synthesis Techniques involved, in order to design sounds that are novel and of musical interest. This approach has been used successfully on several SSTs therefore validating it as an Adaptive Sound Meta-synthesis Technique. Additionally, mappings between the control and the parametric space are evolved as part of the sound setup. These mappings are used during performance.
EvoMUSART Session 1: Evolutionary Computation in Music and Sound Creation: April 14, 1130-1300

Grammatical Evolution with Bidirectional Representation
Kubalik J, Koutni J, Rothkrantz L
Grammatical evolution is an evolutionary algorithm designed to evolve programs in any language. Grammatical evolution operates on binary strings and the mapping of the genotype onto the phenotype (the tree representation of the programs) is provided through the grammar described in the form of production rules. The program trees are constructed in a pre-order fashion, which means that as the genome is traversed first the left most branch of the tree is completed then the second from the left one etc. Once two individuals are crossed over by means of simple one-point crossover the tail parts of the chromosomes (originally encoding the structures on the right side of the program tree) may map on different program structures within the new context. Here we present a {\it bidirectional representation which helps to equalize the survival rate of both the program structures appearing on the left and right side of the program parse tree.
EuroGP Session 5: Posters: April 14, 1730-1930

Guiding Single-Objective Optimization using Multi-Objective Methods
Jensen M
This paper investigates the possibility of using multi-objective methods to guide the search when solving single-objective optimization problems with genetic algorithms. Using the job shop scheduling problem as an example, experiments demonstrate that by using helper-objectives (additional objectives guiding the search), the average performance of a standard GA can be significantly improved. The helper-objectives guide the search towards solutions containing good building blocks and helps the algorithm avoid local optima. The experiments reveal that the approach only works if the number of helper-objectives used simultaneously is low. However, a high number of helper-objectives can be used in the same run by changing the helper-objectives dynamically.
EvoCOP Session 1: New directions: April 14, 1400-1515

How functional dependency adapts to salience hierarchy in the GAuGE system
Nicolau M, Ryan C
GAuGE is a position independent genetic algorithm that suffers from neither under nor over-specification, and uses a genotype to phenotype mapping process. By specifying both the position and the value of each gene, it has the potential to group important data together in the genotype string, to prevent it from being broken up and disrupted during the evolution process. To test this ability, GAuGE was applied to a set of problems with exponentially scaled salience. The results obtained demonstrate that GAuGE is indeed moving the more salient genes to the start of the genotype strings, creating robust individuals that are built in a progressive fashion from the left to the right side of the genotype.
EuroGP Session 11: Alternative representations and 3-D shape design: April 16, 1000-1100

Hybrid Evolution Strategy-Downhill Simplex Algorithm for Inverse Light Scattering Problems
Macias D, Olague G, Mendez
The rough surface inverse scattering problem is approached with a combination of evolutionary strategies and the simplex method. The surface, assumed one-dimensional and perfectly conducting, is represented using spline curves. Starting from rigorously calculated far-field angle-resolved scattered intensity data, we search for the optimum profile using the evolutionary strategies (μ/ρ,+λ). After a fixed number of iterations, the best surface is finally recovered with the downhill simplex method. Aspects of the convergence and lack of uniqueness of the solution are discussed.
EvoIASP Session 3: Miscellanea: April 14, 1600-1800

Improving Symbolic Regression with Interval Arithmetic and Linear Scaling
Keijzer M
The use of protected operators and squared error measures are standard approaches in symbolic regression. It will be shown that two relatively minor modifications of a symbolic regression system can result in greatly improved predictive performance and reliability of the induced expressions. To achieve this, interval arithmetic and linear scaling are used. An experimental section demonstrates the improvements on 15 symbolic regression problems.
EuroGP Session 12: Symbolic regression: April 16, 1120-1250

Inferring Gene Networks from Microarray Data using a Hybrid GA
Levine J, Cumiskey M, Armstrong D
With the first draft completion of multiple organism genome sequencing programmes the emphasis is now moving toward a functional understanding of these genes and their network interactions. Microarray technology allows for large-scale gene experimentation. Using this technology it is possible to find the expression levels of genes across different conditions. The use of a genetic algorithm with a backpropagation local searching mechanism to reconstruct gene networks was investigated. This study demonstrates that the distributed genetic algorithm approach shows promise in that the method can infer gene networks that fit test data closely. Evaluating the biological accuracy of predicted networks from currently available test data is not possible. The best that can be achieved is to produce a set of possible networks to pass to a biologist for experimental verification.
EvoBIO Session 1: Microarray analysis 1: April 14, 1145-1300

Interactive GP for Data Retrieval in Medical Databases
Landrin-Schweitzer Y, Collet P, Lutton E
We present in this paper the design of ELISE, an interactive GP system for document retrieval tasks in very large medical databases. The components of ELISE have been tailored in order to produce a system that is capable of suggesting documents related to the query that may be of interest to the user, thanks to evolved profiling information. Tests on the "Cystic Fibrosis Database" benchmark show that, while suggesting original documents by adaptation of its internal rules to the context of the user, ELISE is able to improve its recall rate.
EuroGP Session 3: Medical applications: April 14, 1400-1530

Introducing a Perl Genetic Programming System: and Can Meta-evolution Solve the Bloat Problem?
MacCallum R
An open source Perl package for genetic programming, called PerlGP, is presented.The supplied algorithm is strongly typed tree-based GP with homologous crossover.User-defined grammars allow any valid Perl to be evolved, including object oriented code and parameters of the PerlGP system itself.Time trials indicate that PerlGP is around 10 times slower than a C based system on a numerical problem, but this is compensated by the speed and ease of implementing new problems, particularly string-based ones.The effect of per-node, fixed and self-adapting crossover and mutation rates on code growth and fitness is studied.On a pi estimation problem, self-adapting rates give both optimal and compact solutions.The source code and manual can be found at http://perlgp.org
EuroGP Session 5: Posters: April 14, 1730-1930

Landscape State Machines: Tools for Evolutionary Algorithm Performance Analyses and Landscape/Algorithm Mapping
Corne D, Oates M, Kell D
Many evolutionary algorithm applications involve either fitness functions with high time complexity or large dimensionality (hence very many fitness evaluations will typically be needed) or both. In such circumstances, there is a dire need to tune various features of the algorithm well so that performance and time savings are optimized. However, these are precisely the circumstances in which prior tuning is very costly in time and resources. There is hence a need for methods which enable fast prior tuning in such cases. We describe a candidate technique for this purpose, in which we model a landscape as a finite state machine, inferred from preliminary sampling runs. In prior algorithm-tuning trials, we can replace the 'real' landscape with the model, enabling extremely fast tuning, saving far more time than was required to infer the model. Preliminary results indicate much promise, though much work needs to be done to establish various aspects of the conditions under which it can be most beneficially used. A main limitation of the method as described here is a restriction to mutationonly algorithms, but there are various ways to address this and other limitations.
EvoCOP Session 7: Search space analysis: April 16, 1120-1250

Learning Action Strategies for Planning Domains using Genetic Programming
Levine J, Humphreys D
There are many different approaches to solving planning problems, one of which is the use of domain specific control knowledge to help guide a domain independent search algorithm. This paper presents L2Plan which represents this control knowledge as an ordered set of control rules, called a {\it policy}, and learns using genetic programming. The genetic program's crossover and mutation operators are augmented by a simple local search. L2Plan was tested on both the blocks world and briefcase domains. In both domains, L2Plan was able to produce policies that solved all the test problems and which outperformed the hand-coded policies written by the authors.
EvoSTIM Session 1: : April 14, 1130-1300

Maximum Homologous Crossover for Linear Genetic Programming
Platel M, Clergue M, Collard P
We introduce a new recombination operator, the Maximum Homologous Crossover for Linear Genetic Programming. In contrast to standard crossover, it attempts to preserve similar structures from parents, by aligning them according to their homology, thanks to an algorithm used in Bio-Informatics. To highlight disruptive effects of crossover operators, we introduce the Royal Road landscapes and the Homology Driven Fitness problem, for Linear Genetic Programming. Two variants of the new crossover operator are described and tested on this landscapes. Results show a reduction in the bloat phenomenon and in the frequency of deleterious crossovers.
EuroGP Session 2: Linear GP, crossover and constants: April 14, 1130-1300

Mobile Robot Sensor Fusion Using Flies
Boumaza A, Louchet J
The "Fly algorithm" is a fast artificial evolution-based image processing technique. Previous work has shown how to process stereo image sequences and use the evolving population of "flies" as a continuously updated representation of the scene for obstacle avoidance in a mobile robot. In this paper, we show that it is possible to use several sensors providing independent information sources on the surrounding scene and the robot's position, and fuse them through the introduction of corresponding additional terms into the fitness function. This sensor fusion technique keeps the main properties of the fly algorithm: asynchronous processing, no low-level image pre-processing or costly image segmentation, fast reaction to new events in the scene. Simulation test results are presented.
EvoIASP Session 1: Computer Vision: April 14, 1130-1300

Modularity in Genetic Programming
Woodward J
Genetic Programming uses a tree based representation to express solutions to problems. Trees are constructed from a primitive set which consists of a function set and a terminal set. An extension to GP is the ability to define modules, which are in turn tree based representations defined in terms of the primitives. The most well known of these methods is Koza's Automatically Defined Functions. In this paper it is proved that for a given problem, the minimum number of nodes in the main tree plus the nodes in any modules is independent of the primitive set (up to an additive constant) and depends only on the function being expressed. This reduces the number of user defined parameters in the run and makes the inclusion of a hypothesis in the search space independent of the primitive set.
EuroGP Session 8: Feature construction and modularity and hierarchies in GP: April 15, 1345-1515

More on Computational Effort Statistics for Genetic Programming
Niehaus J, Banzhaf W
In this contribution we take a look at the computational effort statistics as described by Koza. We transfer the notion from generational genetic programming to tournament-selection (steady-state) GP and show why, in both cases, the measured value of the effort often differs from its theoretical counterpart. It is discussed how systematic estimation errors are introduced by a low number of experiments. Two reasons examined are the number of unsuccessful experiments and the variation in the number of fitness evaluations necessary to find a solution among the successful experiments.
EuroGP Session 6: Population size and performance measures: April 15, 1000-1100

Multi Niche Parallel GP with a Junk-code Migration Model
Garcia S, Levine J, Gonzalez F
We describe in this paper a parallelimplementation of Multi Niche Genetic Programming that we use to test the performance ofa modified migration model. Evolutive introns is a technique developed to accelerate the convergence of GP in classification andsymbolic regression problems. Here, we will copy into a differentiatedsubpopulation the individuals that dueto theevolution processcontain longer Evolutive Introns.Additionally, the multi island model is parallelised in order to speed up convergence. These results are also analysed. Our results prove that the multi island model achieves faster convergence in the three different symbolic regression problems tested, and that the junk-coded subpopulation is not significantly worse than the others, which reinforces our belief in that the important thing is notonly fitness but keepinggood genetic diversityalong all the evolution process. The overhead introduced in the process by the existence of various island, and the migration model is reduced using a multi-thread approach.
EuroGP Session 5: Posters: April 14, 1730-1930

Multilevel Heuristic Algorithm for Graph Partitioning
Banos R, Gil C, Ortega J, Montoya F
Many real applications involve optimisation problems where more than one objective has to be optimised at the same time. One of these kinds of problems is graph partitioning, that appears in ap- plications such as VLSI design, data-mining, e cient disc storage of databases, etc. The problem of graph partitioning consists of dividing a graph into a given number of balanced and non-overlapping partitions while the cuts are minimised. Although di erent algorithms to solve this problem have been proposed, since this is an NP-complete problem, to get more e cient algorithms for increasing complex graphs still remains as an open question. In this paper, we present a new multilevel algorithm including a hybrid heuristic that is applied along the searching process. We also provide experimental results to demonstrate the e ciency of the new algorithm and compare our approach with other previously proposed e cient algorithms.
EvoCOP Session 2: Satisfiability and selection problems: April 14, 1600-1800

Multiple Genetic Snakes for Bone Segmentation
Ballerini L, Bocchi L
Clinical assessment of skeletal age is a frequent, but yet difficult and time-consuming task. Automatic methods which estimate the skeletal age from a hand radiogram are currently being studied. This work presents a method to segment each bone complex in the radiogram, using a modified active contour approach. Each bone is modelled by an independent contour, while neighbouring contours are coupled by an elastic force. The optimization of the contour is done using a genetic algorithm. Experimental results, carried out on a portion of the whole radiogram, show that coupling of deformable contours with genetic optimization allows to obtain an accurate segmentation.
EvoIASP Session 1: Computer Vision: April 14, 1130-1300

MusicBlox: a Real-time Algorithmic Composition System Incorporating a Distributed Interactive Genetic Algorithm
Gartland-Jones A
This paper discusses the motivation, design and construction of a generative music system, 'MusicBlox', (by the author) that utilises a domain specific, knowledge rich Genetic Algorithm (GA). The paper begins by de-scribing the functionality and musical aims of the project, and goes on to detail the implementation of a GA as part of the project's compositional sub-system, including a discussion of the suitability of using a GA for compositional tasks. The paper concludes that the developed GA is able to produce musically suc-cessful results, but that significant additional work still needs to be undertaken before it achieves all the aims outlined.
EvoMUSART Session 1: Evolutionary Computation in Music and Sound Creation: April 14, 1130-1300

Neutral Variations Cause Bloat in Linear GP
Brameier M, Banzhaf W
In this contribution we investigate the influence of different variation effects on the growth of code. A mutation-based variant of linear GP is applied that operates with minimum structural step sizes. Results show that neutral variations are a direct cause for (and not only a result of) the emergence and the growth of intron code. The influence of non-neutral variations has been found to be considerably smaller. Neutral variations turned out to be beneficial by solving two classification problems more successfully.
EuroGP Session 5: Posters: April 14, 1730-1930

New Factorial Design Theoretic Crossover Operator for Parametrical Problem
Chan K, Aydin M, Fogarty T
Recent research shows that factorial design methods improve the performance of the crossover operator in evolutionary computation. However the methods employed so far ignore the effects of interaction between genes on fitness, i.e. "epistasis". Here we propose the application of a systematic method for interaction effect analysis to enhance the performance of the crossover operator. It is shown empirically that the proposed method significantly outperforms existing crossover operators on benchmark problems with high interaction between the variables.
EuroGP Session 2: Linear GP, crossover and constants: April 14, 1130-1300

New Ideas for Applying Ant Colony Optimization to the Probabilistic TSP
Branke J, Guntsch M
The Probabilistic Traveling Salesperson Problem (PTSP) is a stochastic variant of the Traveling Salesperson Problem (TSP); each customer has to be serviced only with a given probability. The goal is to find an a priori tour with shortest expected tour-length, with the customers being served in the specified order and customers not requiring service being skipped. In this paper, we use the Ant Colony Optimization (ACO) metaheuristic to construct solutions for PTSP. We propose two new heuristic guidance schemes for this problem, and examine the idea of using approximations to calculate the expected tour length. This allows to find better solutions or use less time than the standard ACO approach.
EvoCOP Session 6: Ant colony optimisation 2: April 16, 1000-1100

No Free Lunch, Program Induction and Combinatorial Problems
Woodward J, Neil J
This paper has three aims. Firstly, to clarify the poorly understood No Free Lunch Theorem (NFL) which states all search algorithms perform equally. Secondly, search algorithms are often applied to program induction and it is suggested that NFL does not hold due to the universal nature of the mapping between program space and functionality space. Finally, NFL and combinatorial problems are examined. When evaluating a candidate solution, it can be discarded without being fully examined. A stronger version of NFL is established for this class of problems where the goal is to minimize a quantity.
EuroGP Session 5: Posters: April 14, 1730-1930

On Two Approaches to Image Processing Algorithm Design for Binary Images using GP
Quintana M, Poli R, Claridge E
In this paper we describe and compare two different approaches to design image processing algorithms for binary images using Genetic Programming (GP). The first approach is based on the use of mathematical morphology primitives. The second is based on Sub-Machine-Code GP, a technique to speed up and extend GP based on the idea of exploiting the internal parallelism of sequential CPUs. In both cases the objective is to find programs which can transform binary images of a certain kind into other binary images containing just a particular characteristic of interest. In particular, here we focus on the extraction of three different features in music sheets.
EvoIASP Session 2: Genetic Programming: April 14, 1400-1530

On Confidence Intervals for the Number of Local Optima
Eremeev A, Reeves C
The number of local optima is an important indicator of optimization problem diculty for local search algorithms. Here we will discuss some methods of finding the confidence intervals for this parameter in problems where the large cardinality of the search space does not allow exhaustive investigation of solutions. First results are reported that were obtained by using these methods for NK landscapes, and for the low autocorrelation binary sequence and vertex cover problems.
EvoCOP Session 7: Search space analysis: April 16, 1120-1250

On the development of critics in evolutionary computation artists.
Romero J, Machado P, Santos A, Cardoso A
One of the problems in the use of evolutionary computer systems in artistic tasks is the lack of artificial models of human critics. In this paper, based on the state of the art and on our previous related work, we propose a general architecture for an artificial art critic, and a strategy for the validation of this type of system. The architecture includes two modules: the analyser, which does a pre-processing of the artwork, extracting several measurements and characteristics; and the evaluator, which, based on the output of the analyser, classifies the artwork according to a certain criteria. The validation procedure consists of several stages, ranging from author and style discrimination to the integration of critic in a dynamic environment together with humans.
EvoMUSART Session 3: The Past, Present and Future of EC in Art and Music: April 14, 1600-1730

Overfitting or Poor Learning: A Critique of Current Financial Applications of GP
Chen S, Kuo T
Motivated by a measure of predictability, this paper uses the extracted signal ratio as a measure of the degree of overfitting.With this measure, we examine the performance of one type of overfitting-avoidance design frequently used in financial applications of GP.Based on the simulation results run with the software Simple GP, we find that this design is not effective in avoiding overfitting. Furthermore, within the range of search intensity typically considered by these applications, we find that underfitting, instead of overfitting, is the more prevalent problem.This problem becomes more serious when the data is generated by a process that has a high degree of algorithmic complexity.This paper, therefore, casts doubt on the conclusions made by those early applications regarding the poor performance of GP, and recommends that changes be made to ensure progress.
EuroGP Session 3: Medical applications: April 14, 1400-1530

Parallel Programs are More Evolvable than Sequential Programs
Leung K, Lee K, Cheang S
This paper presents a novel phenomenon of the Genetic Parallel Programming (GPP) paradigm - the GPP accelerating phenomenon. GPP is a novel Linear Genetic Programming representation for evolving parallel programs running on a Multi-ALU Processor (MAP).We carried out a series of experiments on GPP with different number of ALUs. We observed that parallel programs are more evolvable than sequential programs. For example, in the Fibonacci sequence regression experiment, evolving a 1-ALU sequential program requires 51 times on average of the computational effort of an 8-ALU parallel program.This paper presents three benchmark problems to show that the GPP can accelerate evolution of parallel programs. Due to the accelerating evolution phenomenon of GPP over sequential program evolution, we could increase the normal GP's evolution efficiency by evolving a parallel program by GPP and if there is a need, the evolved parallel program can be translated into a sequential program so that it can run on conventional hardware.
EuroGP Session 11: Alternative representations and 3-D shape design: April 16, 1000-1100

Pattern Search in Molecules with FANS: Preliminary Results
Blanco A, Pelta D, Verdegay J
We show here how \FANS, a fuzzy sets-based heuristic, is applied to a particular case of the Molecular Structure Matching problem: given two molecules $A$ (the pattern) and $B$ (the target) we want to find a subset of points of $B$ whose set of intra-atomic distances is the most similar to that of $A$. This is a hard combinatorial problem because, first we have to determine a subset of atoms of $B$ and then some order for them has to be established. We analyze how the size of the pattern affects the performance of the heuristic, thus obtaining guidelines to approach the solution of real problems in the near future.
EvoBIO Session 4: Pattern discovery: April 15, 1000-1100

Pixel Statistics and False Alarm Area in Genetic Programming for Object Detection
Zhang M, Andreae P, Pritchard M
This paper describes a domain independent approach to the use of genetic programming for object detection problems. Rather than using raw pixels or high level domain specific features, this approach uses domain independent statistical features as terminals in genetic programming. Besides position invariant statistics such as mean and standard deviation, this approach also uses position dependent pixel statistics such as moments and local region statistics as terminals. Based on an existing fitness function which uses linear combination of detection rate and false alarm rate, we introduce a new measure called "false alarm area" to the fitness function. In addition to the standard arithmetic operators, this approach also uses a conditional operator 'if' in the function set. This approach is tested on two object detection problems. The experiments suggest that position dependent pixel statistics computed from local (central) regions and nonlinear condition functions are effective to object detection problems. Fitness functions with false alarm area can reflect the smoothness of evolved genetic programs. This approach works well for detecting small regular multiple class objects on a relatively uncluttered background.
EvoIASP Session 2: Genetic Programming: April 14, 1400-1530

Promoter recognition with a GP-automaton
Howard D, Benson K
A GP-automaton evolves motif sequences for its states; it moves the point of motif application at transition time using an integer that is stored and evolved in the transition; and it combines motif matches via logical functions that it also stores and evolves in each transition. This scheme learns to predict promoters in human genome. The experiments reported use 5-fold cross validation.
EvoBIO Session 4: Pattern discovery: April 15, 1000-1100

Reducing Population Size While Maintaining Diversity
Monsieurs P, Flerackerseddy E
This paper presents a technique to drastically reduce the size of a population, while still maintaining sufficient diversity for evolution. An advantage of a reduced population size is the reduced number of fitness evaluations necessary. In domains where calculation of fitness values is expensive, this results in a huge speedup of the search. Additionally, in the experiments performed, smaller populations also resulted in a faster convergence speed towards an optimal solution.
EuroGP Session 6: Population size and performance measures: April 15, 1000-1100

Research of a cellular automaton simulating logic gates by evolutionary algorithms
Sapin E, Bailleux O, Chabrier J
This paper presents a method of using genetic programming to seek new cellular automata that perform computational tasks. Two genetic algorithms are used : the first one discovers a rule supporting gliders and the second one modifies this rule in such a way that some components appear allowing it to simulate logic gates. The results show that the genetic programming is a promising tool for the search of cellular automata with specific behaviors, and thus can prove to be decisive for discovering new automata supporting universal computation.
EuroGP Session 5: Posters: April 14, 1730-1930

Restoration of Old Documents with Genetic Algorithms
Rivero D, Vidal R, Dorado J, Rabunal J, Pazos A
Image recognition is a problem present in many real­world applications. In this paper we present an application of genetic algorithms (GAs) to solve one of those problems: the recovery of a deteriorated old document from the damages caused by centuries. This problem is particularly hard because these documents are affected by many aggressive agents, mainly by the humidity caused by a wrong storage during many years. This makes this problem unaffordable by other image processing techniques, but results show how GAs can successfully solve this problem.
EvoIASP Session 3: Miscellanea: April 14, 1600-1800

Routing using Evolutionary Agents and Proactive Transactions
Urquhart N, Ross P, Paechter B, Chisholm K
The authors have previously introduced the concept of building a delivery networ k using an agent-based system. The delivery networks are built in response to a real-world problem that involves delivering post to a large number of households within an urban area. The initial agent based system worked to primarily resolv e hard constraint violations. To further improve the solution obtained by the ag ents, we propose to allow agents to negotiate exchanges of work. We demonstrate the solution obtained may be further improved by allowing such negotiated transa ctions.
EvoSTIM Session 1: : April 14, 1130-1300

Search Space Analysis of the Linear Ordering Problem
Schiavinotto T, Stützle T
The Linear Ordering Problem (LOP) is an NP-hard combinatorial optimization problem that arises in a variety of applications and several algorithmic approaches to its solution have been proposed. However, few details are known about the search space characteristics of LOP instances. In this article we develop a detailed study of the LOP search space. The results indicate that, in general, LOP instances show high fitness-distance correlations and large autocorrelation length but also that there exist significant differences between real-life and randomly generated LOP instances. Because of the limited size of real-world instances, we propose new, randomly generated large real-life like LOP instances which appear to be much harder than other randomly generated instances. Additionally, we propose a rather straightforward Iterated Local Search algorithm, which shows better performance than several state-of-the-art heuristics.
EvoCOP Session 7: Search space analysis: April 16, 1120-1250

Searching for Maximum Cliques with Ant Colony Optimization
Fenet S, Solnon C
In this paper, we investigate the capabilities of Ant Colony Optimization (ACO) for solving the maximum clique problem. We describe Ant-Clique, an algorithm that successively generates maximal cliques through the repeated addition of vertices into partial cliques. ACO is used to choose, at each step, the vertex to add. We illustrate the behaviour of this algorithm on two representative benchmark instances and we study the impact of pheromone on the solution process. We also experimentally compare Ant-Clique with GLS, a Genetic Local Search approach, and we show that Ant-Clique finds larger cliques, on average, on a majority of DIMACS benchmark instances, even though it does not reach the best known results on some instances.
EvoCOP Session 3: Ant colony optimisation 1: April 15, 1120-1250

Sensible Initialisation in Chorus
Ryan C, Atif R
One of the key characteristics of Evolutionary Algorithms is the manner in which solutions are evolved from a primordial soup. The way this soup, or initial generation, is created can have major implications for the eventual quality of the search, as, if there is not enough diversity, the population may become stuck on a local optimum. This paper reports an initial investigation using a position independent evolutionary algorithm, {\em Chorus, where the usual random initialisation has been compared to an approach modelled on the GP ramped half and half method. Three standard benchmark problems have been chosen from the GP literature for this study. It is shown that the new initialisation method, termed sensible initialisation maintains populations with higher average fitness especially earlier on in evolution than with random initialisation. Only one of the benchmarks fails to show an improvement in a probability of success measure, and we demonstrate that this is more likely a symptom of issues with that benchmark than with the idea of sensible initialisation. Performance seems to be unaffected by the different derivation tree depths used, and having a wider pool of individuals, regardless of their average size, seems enough to improve the performance of the system.
EuroGP Session 5: Posters: April 14, 1730-1930

Tabula Rasa: A Case Study in Evolutionary Curation.
Bird J, Webster A, Faith J
This paper describes a novel use of evolutionary techniques to curate a main stream art show,Tabula Rasa .Thisallowedanopen- ended approach to curation that was entirely in keeping with the artistic motivations behind the project.We detail a major dificulty with this approach that will be faced by any future automatic curation systems.
EvoMUSART Session 2: Evolutionary Computation Systems in Visual Arts, performances and Installations: April 14, 1400-1530

The Effect of Plagues in Genetic Programming: A Study of Variable-Size Populations
Fernandez F, Vanneschi L, Tomassini M
A study on the effect of variable size populations in genetic programming is presented in this work. We apply the idea of plague (high desease of individuals). We show that although plagues are generally considered as negative events, they can help populations to save computing time and at the same time surviving individuals can reach high peaks in the fitness landscape.
EuroGP Session 5: Posters: April 14, 1730-1930

The Effectiveness of Cost Based Subtree Caching Mechanisms in Typed Genetic Programming for Image Segmentation
Roberts M
Genetic programming (GP) has long been known as a computationally expensive optimisation technique. When evolving imaging operations, the processing time increases dramatically. This work describes a system using a caching mechanism which reduces the number of evaluations needed by up to 66 percent, counteracting the effects of increasing tree size. This results in a decrease in elapsed time of up to 52 percent. A cost threshold is introduced which can guarantee a speed increase. This caching technique allows GP to be feasibly applied to problems in computer vision and image processing. The trade-offs involved in caching are analysed, and the use of the technique on a previously time consuming medical segmentation problem is shown.
EvoIASP Session 2: Genetic Programming: April 14, 1400-1530

The emergence of Social Learning in Artificial Societies.
Annunziato M
The most recent advances of artificial life research are opening up a new frontier: the creation of simulated life environments populated by autonomous agents. In several cases a new paradigm for learning is emerging: social learning as a form of self-organization of many individual learning. In this paper two different approaches are presented and discussed: genetic competition and partial emulation. Finally an example of application of these concepts.
EvoMUSART Session 2: Evolutionary Computation Systems in Visual Arts, performances and Installations: April 14, 1400-1530

The Root Causes of Code Growth in Genetic Programming
Streeter M
This paper discusses the underlying pressures responsible for code growth in genetic programming, and shows how an understanding of these pressures can be used to use to eliminate code growth while simultaneously improving performance.We begin with a discussion of two distinct components of code growth and the extent to which each component is relevant in practice.We then define the concept of resilience in GP trees, and show that the buildup of resilience is essential for code growth. We present simple modifications to the selection procedures used by GP that eliminate bloat without hurting performance.Finally, we show that eliminating bloat can improve the performance of genetic programming by a factor that increases as the problem is scaled in difficulty.
EuroGP Session 5: Posters: April 14, 1730-1930

Towards a prehistory of evolutionary and adaptive computation in music.
Johnson C
A number of systems have been created which apply genetic algorithms, cellular automata, artificial life, agents, and other evolutionary and adaptive computation ideas in the creation of music. The aim of this paper is to examine the context in which such systems arose by looking for features of experimental music which prefigure the ideas used in such systems. A number of ideas are explored: the use of randomness in music, the view of compositions as parameterized systems, the idea of emergent structure in music and the idea of musicians performing the role of reactive agents.
EvoMUSART Session 3: The Past, Present and Future of EC in Art and Music: April 14, 1600-1730

Tree Adjoining Grammars, Language Bias, and Genetic Programming
Xuan N, McKay R, Abbass H
In this paper, we introduce a new grammar guided genetic programming system called tree-adjoining grammar guided genetic programming (TAG3P+), where tree-adjoining grammars (TAGs) are used as means to set language bias for genetic programming. We show that the capability of TAGs in handling context-sensitive information and categories can be useful to set a language bias that cannot be specified in grammar guided genetic programming. Moreover, we bias the genetic operators to preserve the language bias during the evolutionary process. The results pace the way towards a better understanding of the importance of bias in genetic programming.
EuroGP Session 5: Posters: April 14, 1730-1930