Accepted papers
The EuroGP2003 proceedings will be published by Spinger as part of their Lecture Notes in Computer Science series.
Oral presentations
A Simple but Theoreticallymotivated 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 constraintviolating 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: Metasearch, compiler optimisation and bloat: April 15, 11201250
An innovative application of a constrainedsyntax genetic programming system to the problem ofpredicting survival of patients
Bojarczuk C,
Lopes H,
Freitas A
This paper proposes a constrainedsyntax 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 realworld 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, 14001530
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 timeseries.
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, 11301300
Decreasing the Number of Evaluations in Evolutionary Algorithms by using a MetaModel 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: Metafitness and alternative computational structures: April 14, 16001730
Divide and Conquer: Genetic Programming Based on Multiple Branches Encoding
Rodriguez K,
OliverMorales C
This paper describes an alternative genetic programming encoding,
which is based on a rootednode with fixedcontent. 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 evenn parity problem.
EuroGP Session 9: Multiprogram integration: April 15, 15301630
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: Multiprogram integration: April 15, 15301630
Evolutionary Design of Objects Using Scene Graphs
Ebner M
One of the main issues in evolutionary design is how to create
threedimensional 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 threedimensional 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 threedimensional 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 3D shape design: April 16, 10001100
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: Metafitness and alternative computational structures: April 14, 16001730
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 stringdistance 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: Metafitness and alternative computational structures: April 14, 16001730
Evolving Hierarchical and RecursiveTeleoReactive Programs through Genetic Programming
Kochenderfer M
Teleoreactive 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
teleoreactive control structures. This paper uses block stacking
problems to demonstrate how genetic programming may be used to
evolve hierarchical and recursive teleoreactive programs.
EuroGP Session 8: Feature construction and modularity and hierarchies in GP: April 15, 13451515
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 preprocess 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 wellknown 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, 13451515
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,
applicationspecific 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
generalpurpose 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
wellstudied register allocation heuristic.On average, our
system obtains a 6% speedup when it specializes the register
allocation algorithm for individual applications.The
generalpurpose
heuristic for register allocation achieves a 3% improvement.
EuroGP Session 7: Metasearch, compiler optimisation and bloat: April 15, 11201250
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, 11201250
Genetic Programming With MetaSearch: 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 metasearch
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 metasearch strategies are introduced and evaluated over a set
of classification problems. The metasearch 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 metasearch
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: Metasearch, compiler optimisation and bloat: April 15, 11201250
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 overspecification, 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 3D shape design: April 16, 10001100
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, 11201250
Interactive GP for Data Retrieval in Medical Databases
LandrinSchweitzer 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, 14001530
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 BioInformatics. 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, 11301300
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, 13451515
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 tournamentselection
(steadystate) 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, 10001100
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, 11301300
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 overfittingavoidance
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, 14001530
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 MultiALU 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 1ALU
sequential program requires 51 times on average of the computational effort
of an 8ALU 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 3D shape design: April 16, 10001100
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, 10001100
Poster presentations
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, 17301930
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
testprogram generation based on an evolutionary algorithm. The proposed
methodology is highly versatile and improves previous approaches, allowing
the testprogram generator generating complex assembly programs that include subroutines calls.
EuroGP Session 5: Posters: April 14, 17301930
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 programspace 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, 17301930
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, 17301930
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, 17301930
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, 17301930
Evolutionary Optimized Mold Temperature Control Strategies using a MultiPolyline 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, 17301930
Experimental design based multiparent crossover operator
Chan K,
Fogarty T
Recently, the methodologies of multiparent crossover have been
developed by performing the crossover operation with multiparent.
Some studies have indicated the high performance of multiparent
cros\sover on some numerical optimization problems. Here a new
crossover operator has been proposed by integrating multiparent
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, 17301930
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, 17301930
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, 17301930
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 highquality 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, 17301930
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 preorder
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 onepoint 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, 17301930
Introducing a Perl Genetic Programming System: and Can Metaevolution Solve the Bloat Problem?
MacCallum R
An open source Perl package for genetic programming, called
PerlGP, is presented.The supplied algorithm is strongly typed
treebased GP with homologous crossover.Userdefined 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 stringbased ones.The
effect of pernode, fixed and selfadapting crossover and mutation
rates on code growth and fitness is studied.On a pi estimation
problem, selfadapting 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, 17301930
Multi Niche Parallel GP with a Junkcode 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 junkcoded 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 multithread approach.
EuroGP Session 5: Posters: April 14, 17301930
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 mutationbased 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 nonneutral 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, 17301930
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, 17301930
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, 17301930
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, 17301930
The Effect of Plagues in Genetic Programming: A Study of VariableSize 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, 17301930
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, 17301930
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 treeadjoining grammar guided genetic programming (TAG3P+), where
treeadjoining grammars (TAGs) are used as means to set language bias for genetic
programming. We show that the capability of TAGs in handling contextsensitive
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, 17301930
