Evolutionary Algorithm Approach to Bilateral Negotiations
BABER V.
Abstract:
The Internet is quickly changing the way businesstoconsumer and businesstobusiness commerce is conducted. The technology has created an opportunity to get beyond singleissue negotiation by determining sellers' and buyers' preferences across multiple issues, thereby creating possible joint gains for all parties. We develop simple multiple issue algorithms and heuristics that could be used in electronic auctions and electronic markets. In this study, we show how a genetic algorithm based technique, coupled with a simple heuristic can achieve good results in business negotiations. The negotiations' outcomes are evaluated on two dimensions: joint utility and number of exchanges of offers to reach a deal. The results are promising and indicate possible use of such approaches in actual electronic commerce systems.
Session:
EuroGP Session 4: Poster session and conference reception: April 3, 17301930
Evolving classifiers to model the relationship between strategy and corporate performance using grammatical evolution
BRABAZON A.,
O'NEILL M.,
RYAN C.,
MATTHEWS R.
Abstract:
This study examines the potential of grammatical evolution to construct a linear classifier to predict whether a firm's corporate strategy will increase or decrease shareholder wealth. Shareholder wealth is measured using a relative fitness criterion, the change in a firm's marketvalueadded ranking in the SternStewart Performance 1000 list, over a four year period, 19921996. Model inputs and structure are selected by means of grammatical evolution. The best classifier correctly categorised the direction of performance ranking change in 66.38% of the firms in the training set and 65% in the outofsample validation set providing support for a hypothesis that changes in corporate strategy are linked to changes in corporate performance.
Session:
EuroGP Session 9: Grammatical evolution: April 5, 09301100
Explicit Control of Diversity and Effective Variation Distance in Linear Genetic Programming
BRAMEIER M.,
BANZHAF W.
Abstract:
We have investigated structural distance metrics for linear genetic programs. Causal connections between changes of the genotype and changes of the phenotype form a necessary condition for analyzing structural differences between genetic programs and for the two objectives of this paper: (i) The distance information between individuals is used to control structural diversity of population individuals actively by a twolevel tournament selection. (ii) Variation distance of effective code is controlled for different genetic operators  including a mutation operator that works closely with the applied distance measure. Numerous experiments have been performed for three benchmark problems.
Session:
EuroGP Session 2: Experimental & theoretical analysis: April 3, 14001605
A Puzzle to Challenge Genetic Programming
BURKE E.,
GUSTAFSON S.,
KENDALL G.
Abstract:
This report represents an initial investigation into the use of genetic programming to solve the Nprisoners puzzle. The puzzle has generated a certain level of interest among the mathematical community. We believe that this puzzle presents a significant challenge to the field of evolutionary computation and to genetic programming in particular. The overall aim is to generate a solution that encodes complex decision making. Our initial results demonstrate that genetic programming can evolve good solutions. We compare these results to engineered solutions and discuss some of the implications. One of the consequences of this study is that it has highlighted a number of research issues and directions and challenges for the evolutionary computation community.We conclude the article by presenting some of these directions which range over several areas of evolutionary computation, including multiobjective fitness, coevolution and cooperation, and problem representations.
Session:
EuroGP Session 4: Poster session and conference reception: April 3, 17301930
Automatic Generation of Control Programs for Walking Robots Using Genetic Programming
BUSCH J.,
ZIEGLER J.,
BANZHAF W.,
ROSS A.,
SAWITZKI D.,
AUE C.
Abstract:
We present the system SIGEL that combines the simulation and visualization of robots with a Genetic Programming system for the automated evolution of walking. It is designed to automatically generate control programs for arbitrary robots without depending on detailed analytical information of the robots' kinematic structure. Different fitness functions as well as a variety of parameters allow the easy and interactive configuration and adaptation of the evolution process and the simulations.
Session:
EuroGP Session 4: Poster session and conference reception: April 3, 17301930
An Analysis of Koza's Computational Effort Statistic for Genetic Programming
CHRISTENSEN S.,
OPPACHER F.
Abstract:
As research into the theory of genetic programming progresses, more effort is being placed on systematically comparing results to give an indication of the effectiveness of sundry modifications to traditional GP. The statistic that is commonly used to report the amount of computational effort to solve a particular problem with 99% probability is Koza's I(M, i, z) statistic. This paper analyzes this measure from a statistical perspective. In particular, Koza's I tends to underestimate the true computational effort, by 25% or more forcommonly used GP parameters and run sizes. The magnitude of this underestimate is nonlinearly decreasing with increasing run count, leading tothe possibility that published results based on few runs may in fact be unmatchable when replicated at higher resolution. Additional analysis shows that this statistic also underreports the generation at which optimal results are achieved.
Session:
EuroGP Session 2: Experimental & theoretical analysis: April 3, 14001605
Evolutionary Techniques for Minimizing Test Signals Application Time
Corno F.,
Sonza Reorda M.,
Squillero G.
Abstract:
Reducing productiontest application time is a key problem for modern industries. Several different hardware solutions have been proposed in the literature to ease such process. However, each hardware architecture must be coupled with an effective test signals generation algorithm. This paper propose an evolutionary approach for minimizing the application time of a test set by opportunely extending it and exploiting a new hardware architecture, named interleaved scan. The peculiarities of the problem suggest the use of a slightly modified genetic algorithm with concurrent populations. Experimental results show the effectiveness of the approach against the traditional ones.
Session:
EvoIASP Session 3: Evolvable hardware: April 3, 16001710
Hyperheuristics: A Tool for Rapid Prototyping in Scheduling and Optimisation
Cowling P.,
Kendall G.,
Soubeiga S.
Abstract:
The term hyperheuristic was introduced by the authors as a highlevel heuristic that adaptively controls several lowlevel knowledgepoor heuristics so that while using only cheap, easytoimplement lowlevel heuristics, we may achieve solution quality approaching that of an expensive knowledgerich approach. For certain classes of problems, this allows us to rapidly produce effective solutions, in a fraction of the time needed for other approaches, and using a level of expertise common among nonacademic IT professionals. Hyperheuristics have been successfully applied by the authors to a realworld problem of personnel scheduling. In this paper, the authors report another successful application of hyperheuristics to a rather different realworld problem of personnel scheduling occuring at a UK academic institution. Not only did the hyperheuristics produce results of a quality much superior to that of a manual solution but also these results were produced within a period of only three weeks due to the savings resulting from using the existing hyperheuristic software framework.
Session:
EvoCOP Session 6: Scheduling problems: April 5, 09301100
Savings Ants for the Vehicle Routing Problem
Doerner K.,
Gronalt M.,
Hartl R. F.,
Reimann M.,
Strauss C.,
Stummer M.
Abstract:
In this paper we propose a hybrid approach for solving vehicle routing problems. The main idea is to combine an Ant System (AS) with a problem specific constructive heuristic, namely the well known Savings algorithm. This differs from previous approaches, where the subordinate heuristic was the Nearest Neighbor algorithm initially proposed for the TSP. We compare our approach with some other classic, powerful metaheuristics and show that our results are competitive.
Session:
EvoCOP Session 5: Ant colony optimization: April 4, 13451545
Prediction and Modelling of the Flow of a Typical Urban Basin through Genetic Programming
Dorado J.,
Rabuńal J. R.,
Puertas J.,
Santos A.,
Rivero D.
Abstract:
Genetic Programming (GP) is an evolutionary method that creates computer programs that represent approximate or exact solutions to a problem. This paper proposes an application of GP in hydrology, namely for modelling the effect of rain on the runoff flow in a typical urban basin. The ultimate goal of this research is to design a real time alarm system to warn of floods or subsidence in various types of urban basin. Results look promising and appear to offer some improvement over stochastic methods for analysing river basin systems such as unitary radiographs.
Session:
EvoIASP Session 1: Image and signal processing and analysis: April 3, 09001100
Updating ACO pheromones using Stochastic Gradient Ascent and CrossEntropy methods
Dorigo M.,
Zlochin M.,
Meuleau N.,
Birattari M.
Abstract:
In this paper we introduce two systematic approaches, based on the stochastic gradient ascent algorithm and the crossentropy method, for deriving the pheromone update rules in the Ant Colony Optimization metaheuristic. We discuss the relationships between the two methods as well as connections to the update rules previously proposed in the literature.
Session:
EvoCOP Session 5: Ant colony optimization: April 4, 13451545
Coevolution Produces an Arms Race Among Virtual Plants
EBNER M.,
GRIGORE A.,
HEFFNER A.,
ALBERT J.
Abstract:
Creating interesting virtual worlds is a difficult task. We are using a variant of genetic programming to automatically create plants for a virtual environment. The plants are represented as contextfree Lindenmayer systems. OpenGL is used to visualize and evaluate the plants. Our plants have to collect virtual sunlight through their leaves in order to reproduce successfully. Thus we have realized an interaction between the plant and its environment. Plants are either evaluated separately or all individuals of a population at the same time. The experiments show that during coevolution plants grow much higher compared to rather bushy plants when plants are evaluated in isolation.
Session:
EuroGP Session 4: Poster session and conference reception: April 3, 17301930
Evolving Fuzzy Decision Trees with Genetic Programming and Clustering
EGGERMONT J.
Abstract:
In this paper we present a new fuzzy decision tree representation for ncategory data classification using genetic programming. The new fuzzy representation utilizes fuzzy clusters for handling continuous attributes. To make optimal use of the fuzzy classifications of this representation an extra fitness measure is used. The new fuzzy representation will be compared, using several machine learning data sets, to a similar nonfuzzy representation as well as to some other evolutionary and nonevolutionary algorithms from literature.
Session:
EuroGP Session 7: Implementation & representation issues: April 4, 13451550
Maintaining the Diversity of Genetic Programs
EKART A.,
NEMETH N.
Abstract:
An important problem of evolutionary algorithms is that throughout evolution they loose genetic diversity. Many techniques have been developed for maintaining diversity in genetic algorithms, but few investigations have been done for genetic programs. We define here a diversity measure for genetic programs based on our metric for genetic trees. We use this distance measure for studying the effects of fitness sharing. We then propose a method for adaptively maintaining the diversity of a population during evolution.
Session:
EuroGP Session 2: Experimental & theoretical analysis: April 3, 14001605
Nonparametric Estimation of Properties of Combinatorial Landscapes
Eremeev A.,
Reeves C. R.
Abstract:
Earlier papers [1,2] introduced some statistical estimation methods for measuring certain properties of landscapes induced by heuristic search methods: in particular, the number of optima. In this paper we extend this approach to nonparametric methods which allow us to relax a critical assumption of the earlier approach. Two techniques are described  the jackknife and the bootstrap  based on statistical ideas of resampling, and the results of some empirical studies are presented and analysed.
Session:
EvoCOP Session 2: Exploiting statistics: April 3, 16301800
Performance of Evolutionary Approaches for Parallel Task Scheduling under Different Representations
Esquivel S.,
Gatica C.,
Gallard R.
Abstract:
Task scheduling is known to be NPcomplete in its general form as well as in many restricted cases. Thus to find a near optimal solution in, at most, polynomial time different heuristics were proposed. The basic Graham´s task graph model [1] was extended to other listbased priority schedulers [2] where increased levels of communication overhead were included [3]. Evolutionary Algorithms (EAs) have been used in the past to implement the allocation of the components (tasks) of a parallel program to processors [4], [5]. In this paper five evolutionary algorithms are compared. All of them use the conventional Single Crossover Per Couple (SCPC) approach but they differ in what is represented by the chromosome: processor dispatching priorities, tasks priority lists, or both priority policies described in a bipartite chromosome. Chromosome structure, genetic operators, experiments and results are discussed.
Session:
EvoCOP Session 6: Scheduling problems: April 5, 09301100
A Performance Comparison of Alternative Heuristics for the Flow Shop Scheduling Problem
Esquivel S.,
Leguizamón G.,
Zuppa F.,
Gallard R.
Abstract:
Determining an optimal schedule to minimise the completion time of the last job abandoning the system (makespan) become a very difficult problem when there are more than two machines in the flow shop. Due, both to its economical impact and complexity, attention to solve this problem has been paid by many researchers. Starting with the Johnson’s exact algorithm for the twomachine makespan problem [1], over the past three decades extensive search have been done on pure mmachine flow shop problems. Many researchers faced the Flow Shop Scheduling (FSSP) by means of wellknown heuristics which, are successfully used for certain instances of the problem and providing a single acceptable solution. Current trends to solve the FSSP involve Evolutionary Computation and Ant Colony paradigms. This work shows different bioinspired heuristics for the FSSP, including hybrid versions of enhanced multirecombined evolutionary algorithms and ant colony algorithms [2], on a set of flow shop scheduling instances. A discussion on implementation details, analysis and a comparison of different approaches to the problem is shown.
Session:
EvoCOP Session 6: Scheduling problems: April 5, 09301100
Medical Image Registration Using Parallel Genetic Algorithms
Fan Y.,
Jiang T.,
Evans D. J.
Abstract:
Registration of medical image data of different modalities and multiple times is an important component of medical image analysis. A variety of robust and accurate voxelbased approaches have been proposed, and mathematically almost all of them are associated with optimization problems that are highly nonlinear and nonconvex. This article presents a parallel genetic strategy to attack mutual information based registration. The experimental results show robust registration with high speedup achieved. Furthermore, this method is readily applicable for other voxelbased registration methods.
Session:
EvoIASP Session 1: Image and signal processing and analysis: April 3, 09001100
Comparing Synchronous and Asynchronous Parallel and Distributed GP Models
FERNANDEZ F.,
GALEANO G.,
GOMEZ J. A.
Abstract:
In this paper we present a study that analyses the respective advantages and disadvantages of the synchronous and asynchronous versions of islandbased genetic programming. We also look at different measuring systems for comparing parallel genetic programming with panmitic mo del. At the same time we show an interesting relationship between the bloat phenomenon and the number of individuals we use. Finally, we study a relationship between the number of subpopulations in parallel GP and the advantages of the asynchronous model.
Session:
EuroGP Session 4: Poster session and conference reception: April 3, 17301930
Discovery of the Boolean Functions to the Best DensityClassification Rules Using Gene Expression Programming
FERREIRA C.
Abstract:
Cellular automata are idealized versions of massively parallel, decentralized computing systems capable of emergent behaviors. These complex behaviors result from the simultaneous execution of simple rules at multiple local sites. A widely studied behavior consists of correctly determining the density of an initial configuration, and both human and computerwritten rules have been found that perform with high efficiency at this task. However, the two best rules for the densityclassification task, Coevolution1 and Coevolution2, were discovered using a coevolutionary algorithm in which a genetic algorithm evolved the rules and, therefore, only the output bits of the rules are known. However, to understand why these and other rules perform so well and how the information is transmitted throughout the cellular automata, the Boolean expressions that orchestrate this behavior must be known. The results presented in this work are a contribution in that direction.
Session:
EuroGP Session 6: Applications II: April 4, 11001230
Exploiting Fitness Distance Correlation of Set Covering Problems
Finger M.,
Stützle T.,
Lourenço H.
Abstract:
The set covering problem is an NPhard combinatorial optimization problem that arises in applications ranging from crew scheduling in airlines to driver scheduling in public mass transport. In this paper we analyze search space characteristics of a widely used set of benchmark instances through an analysis of the fitnessdistance correlation. This analysis shows that there exist several classes of set covering instances that show a largely different behavior. For instances with high fitness distance correlation, we propose new ways of generating core problems and analyze the performance of algorithms exploiting these core problems.
Session:
EvoCOP Session 2: Exploiting statistics: April 3, 16301800
Using EAs for Error Prediction in Near Infrared Spectroscopy
Fonlupt C.,
Cahon S.,
Robilliard D.,
ElGhazali T.,
Duponchel L.
Abstract:
This paper presents an evolutionary approach to estimate the sugar concentration inside compound bodies based on spectroscopy measurements. New European regulation will shortly forbid the use of established chemical methods based on mercury to estimate the sugar concentration in sugar beet. Spectroscopy with a powerful regression technique called PLS (Partial Least Squares) may be used instead. We show that an evolutionary approach for selecting relevant wavelengths before applying PLS can lower the error and decrease the computation time. It is submitted that the results support the argument for replacing the PLS scheme with a GP technique.
Session:
EvoIASP Session 1: Image and signal processing and analysis: April 3, 09001100
New Results on Fuzzy Regression by Using Genetic Programming
GOLUBSKI W.
Abstract:
In this paper we continue the work on symbolic fuzzy regression problems. That means that we are interesting in finding a fuzzy function f with best matches given data pairs (xi,yi) 1<= i <= k of fuzzy numbers. We use a genetic programming approach for finding a suitable fuzzy function and will present test results about linear, quadratic and cubic fuzzy functions.
Session:
EuroGP Session 4: Poster session and conference reception: April 3, 17301930
A Population Based Approach for ACO
Guntsch M.,
Middendorf M.
Abstract:
A population based ACO (Ant Colony Optimization) algorithm is proposed where (nearly) all pheromone information corresponds to solutions that are members of the actual population. Advantages of the population based approach are that it seems promising for solving dynamic optimization problems, its finite state space and the chances it offers for designing new metaheuristics. We compare the behavior of the new approach to the standard ACO approach for several instances of the TSP and the QAP problem. The results show that the new approach is competitive.
Session:
EvoCOP Session 5: Ant colony optimization: April 4, 13451545
Some Experimental Results with Tree Adjunct Grammar Guided Genetic Programming
HOAI N. X.,
MCKAY R. I.,
ESSAM D.
Abstract:
Treeadjunct grammar guided genetic programming (TAG3P) [5] is a grammar guided genetic programming system that uses context free grammars along with treeadjunct grammars as means to set language bias for the genetic programming system. In this paper, we show the experimental results of TAG3P on two problems: symbolic regression and trigonometric identity discovery. The results show that TAG3P works well on those problems.
Session:
EuroGP Session 4: Poster session and conference reception: April 3, 17301930
The Prediction Of Journey Times On Motorways Using Genetic Programming
Howard D.,
Roberts S. C.
Abstract:
Considered is the problem of reliably predicting motorway journey times for the purpose of providing accurate information to drivers. This proof of concept experiment investigates: (a) the practicalities of using a Genetic Programming (GP) method to model/forecast motorway journey times; and (b) different ways of obtaining a journey time predictor. Predictions are compared with known times and are also judged against a collection of naive prediction formulae. A journey time formula discovered by GP is analysed to determine its structure, demonstrating that GP can indeed discover compact formulae for different traffic situations and associated insights. GP's flexibility allows it to selfdetermine the required level of modelling complexity.
Session:
EvoIASP Session 4: EC applications to traffic control: April 3, 17101800
The Boru Data Crawler for Object Detection Tasks in Machine Vision
Howard D.,
Roberts S. C.,
Ryan C.
Abstract:
A 'data crawler' is allowed to meander around an image deciding what it considers to be interesting and laying down flags in areas where its interest has been aroused. These flags can be analysed statistically as if the image was being viewed from afar to achieve object recognition. The guidance program for the crawler, the program which excites it to deposit a flag and how the flags are combined statistically, are driven by an evolutionary process which has as objective the minimisation of misses and false alarms. The crawler is represented by a treebased Genetic Programming (GP) method with fixed architecture Automatically Defined Functions (ADFs). The crawler was used as a postprocessor to the object detection obtained by a Staged GP method, and it managed to appreciably reduce the number of false alarms on a realworld application of vehicle detection in infrared imagery.
Session:
EvoIASP Session 1: Image and signal processing and analysis: April 3, 09001100
Transformation of Equational Specification by Means of Genetic Programming
IBARRA A.,
LANCHARES J.,
MENDIAS J.,
HIDALGO J. I.,
HERMIDA R.
Abstract:
High Level Synthesis (HLS) is a designing methodology aimed to the synthesis of hardware devices from behavioural specifications. One of the techniques used in HLS is formal verification. In this work we present an evolutionary algorithm in order to optimize circuit equational specifications by means of a special type of genetic operator. We have named this operator algebraic mutation, carried out with the help of the equations that Formal Verification Synthesis offers. This work can be classified within the development of an automatic tool of Formal Verification Synthesis by using genetic techniques. We have applied this technique to a simple circuit equational specification and to a much more complex algebraic equation. In the first case our algorithm simplifies the equation until the best specification is found and in the second a solution improving the former is always obtained.
Session:
EuroGP Session 4: Poster session and conference reception: April 3, 17301930
Nversion Genetic Programming via Fault Masking
IMAMURA K.,
HECKENDORN R. B.,
SOULE T.,
FOSTER J. A.
Abstract:
We introduce a new method, NVersion Genetic Programming (NVGP), for building fault tolerant software by building an ensemble of automatically generated modules in such a way as to maximize their collective fault masking ability. The ensemble itself is an example of nversion modular redundancy for fault tolerance, where the output of the ensemble is the most frequent output of n independent modules. By maximizing collective fault masking, NVGP approaches the fault tolerance expected from n version modular redundancy with independent faults in component modules. The ensemble comprises individual modules from a large pool generated with genetic programming, using operators that increase the diversity of the population. Our experimental test problem classified promoter regions in Escherichia coli DNA sequences. For this problem, NVGP reduced the number and variance of errors over single modules produced by GP, with statistical significance.
Session:
EuroGP Session 6: Applications II: April 4, 11001230
Deriving genetic programming fitness properties by static analysis
JOHNSON C.
Abstract:
The aim of this paper is to introduce the idea of using static analysis of computer programs as a way of measuring fitness in genetic programming. Such techniques extract information about the programs without explicitly running them, and in particular they infer properties which hold across the whole of the input space of a program. This can be applied to measure fitness, and has a number of advantages over measuring fitness by running members of the population on test cases. The most important advantage is that if a solution is found then it is possible to formally trust that solution to be correct across all inputs. This paper introduces these ideas, discusses various ways in which they could be applied, discusses the type of problems for which they are appropriate, and ends by giving a simple test example and some questions for future research.
Session:
EuroGP Session 4: Poster session and conference reception: April 3, 17301930
Application of Genetic Algorithms in Nanoscience: Cluster Geometry Optimization
Johnston R. L.,
MortimerJones T. V.,
Roberts C.,
Darby S.,
Manby F. R.
Abstract:
An account is presented of the design and application of Genetic Algorithms for the geometry optimization (energy minimization) of clusters and nanoparticles, where the interactions between atoms, ions or molecules are described by a variety of potential energy functions (force fields). A detailed description is presented of the Birmingham Cluster Genetic Algorithm Program, developed in our group, and two specific applications are highlighted: the use of a GA to optimize the geometry and atom distribution in mixed CuAu clusters; and the use of an energy predator in an attempt to identify the lowest six isomers of C40.
Session:
EvoCOP Session 3: Realvalued representations: April 4, 09301030
LinearGraph GP A new GP Structure
KANTSCHIK W.,
BANZHAF W.
Abstract:
In recent years different genetic programming (GP) structures have emerged. Today, the basic forms of representation for genetic programs are tree, linear and graph structures. In this contribution we introduce a new kind of GP structure which we call lineargraph, it is a further development of the linearTree structure. We describe the lineargraph structure, as well as crossover and mutation for this new GP structure in detail. We compare lineargraph programs with linear and tree programs by analyzing their structure and results on different test problems.
Session:
EuroGP Session 7: Implementation & representation issues: April 4, 13451550
Grammatical Evolution Rules: The mod and the Bucket Rule
KEIJZER M.,
O'NEILL M.,
RYAN C.,
CATTOLICO M.
Abstract:
We present an alternative mapping function called the Bucket Rule, for Grammatical Evolution, that improves upon the standard modulo rule. Grammatical Evolution is applied to a set of standard Genetic Algorithm problem domains using two alternative grammars. Applying GE to GA problems allows us to focus on a simple grammar whose effects are easily analysable.
Session:
EuroGP Session 9: Grammatical evolution: April 5, 09301100
A Memetic Algorithm for VertexBiconnectivity Augmentation
Kersting S.,
Raidl G. R.,
Ljubic I.
Abstract:
This paper considers the problem of augmenting a given graph by a cheapest possible set of additional edges in order to make the graph vertexbiconnected. A realworld instance of this problem is the enhancement of an already established computer network to become robust against single node failures. The presented memetic algorithm includes an effective preprocessing of problem data and a fast local improvement strategy which is applied during initialization, mutation, and recombination. Only feasible, locally optimal solutions are created as candidates. Empirical results indicate the superiority of the new approach over two previous heuristics and an earlier evolutionary method.
Session:
EvoCOP Session 1: Graph problems: April 3, 14001545
BruteForce Approach to Automatic Induction of Machine Code on CISC Architectures
KÜHLING F.,
WOLFF K.,
NORDIN P.
Abstract:
The usual approach to address the brittleness of machine code in evolution is to constrain mutation and crossover to ensure syntactic closure. In the novel approach presented here we use no constraints on the operators, they all work blindely on the binaries in memory, but we instead encapsulate the code and trap all resulting exceptions. The new approach presented here for machine code evolution on CISC architectures is based on the observation that modern CPUs can cope with incorrect programmes and report errors to the operating system. This way it is possible to return to very simple genetic operators with the objective of increased performance. Furthermore the instruction set used by evolved programmes is no longer limited by the genetic programming system but only by the CPU it runs on. The mapping between evolution plattform and execution plattform becomes alomst complete, ensuring correct lowlevel behaviour of all CPU functions.
Session:
EuroGP Session 4: Poster session and conference reception: April 3, 17301930
Combining Decision Trees and Neural Networks for Drug Discovery
LANGDON W. B.,
BARRETT S. J.,
BUXTON B. F.
Abstract:
Last year [Langdon and Buxton, 2001c] we presented a new system in which genetic programming (GP) automatically fuses together classifiers using the ir receiver operating characteristics (ROC) to yield superior ensembles. This year we demonstrate it combining decision trees (C4.5) and artificial neural net works (ANN) on a difficult pharmaceutical data mining (KDD) drug discovery application. Specifically predicting compound activity with a P450 enzyme. Training data came from high through put screening (HTS) runs held in GlaxoSmithKline (GSK)'s cheminformatics database. The evolved model may be used to predict behaviour of virtual (i.e. yet to be manufactured chemicals). Measures to reduce over fitting are also described.
Session:
EuroGP Session 5: Applications I: April 4, 09301030
Disruption Management for an Airline  Rescheduling of Aircraft
Love M.,
Sorensen K. R.,
Larsen J.,
Clausen J.
Abstract:
The Aircraft Recovery Problem (ARP) involves decisions concerning
aircraft to flight assignments in situations where unforeseen events
have disrupted the existing flight schedule, e.g. bad weather causing
flight delays. The aircraft recovery problem aims to recover these
flight schedules through a series of reassignments of aircraft to
flights, delaying of flights and cancellations of flights. This
article demonstrates an effective method to solve ARP. A heuristic is
implemented, which is able to generate feasible revised flight
schedules of a good quality in less than 10 seconds. This article is a
product of the DESCARTES project, a project funded by the European
Union between the Technical University of Denmark, British Airways and
Carmen.
Session:
EvoSTIM Session 1: Methods of solving scheduling problems: April 3, 09001100
Surface Profile Reconstruction From Scattered Intensity Data Using Evolutionary Strategies
Macías D.,
Olague G.,
Méndez E. R.
Abstract:
We present a study of rough surface inverse scattering problems using evolutionary strategies. The input data consists of farfield angleresolved scattered intensity data, and the objective is to reconstruct the surface profile function that produced the data. To simplify the problem, the random surface is assumed to be onedimensional and perfectly conducting. The optimum of the fitness function is searched using the evolutionary strategies (µ ?) and (µ + ?). On the assumption that some knowledge about the statistical properties of the unknown surface profile is given or can be obtained, the search space is restricted to surfaces that belong to that particular class. In our case, as the original surface, the trial surfaces constitute realizations of a stationary zeromean Gaussian random process with a Gaussian correlation function. We find that, for the conditions and parameters employed, the surface profile can be retrieved with high degree of confidence. Some aspects of the convergence and the lack of uniqueness of the solution are also discussed.
Session:
EvoIASP Session 1: Image and signal processing and analysis: April 3, 09001100
Genetic, Iterated and Multistart Local Search for the Maximum Clique Problem
Marchiori E.
Abstract:
This paper compares experimentally three heuristic algorithms for the maximum clique problem obtained as instances of an evolutionary algorithm scheme. The algorithms use three popular heuristic methods for combinatorial optimization problems, known as genetic, iterated and multistart local search, respectively.
Session:
EvoCOP Session 1: Graph problems: April 3, 14001545
A Pipelined Hardware Implementation of Genetic Programming using FPGAs and HandelC
MARTIN P.
Abstract:
A complete Genetic Programming (GP) system implemented in a single FPGA is described in this paper. The GP system is capable of solving problems that require large populations and by using parallel fitness evaluations can solve problems in a much shorter time that a conventional GP system in software. A high level language to hardware compilation system called HandelC is used for implementation.
Session:
EuroGP Session 7: Implementation & representation issues: April 4, 13451550
Ant Colony Optimization with the Relative Pheromone Evaluation Method
Merkle D.,
Middendorf M.
Abstract:
In this paper the relative pheromone evaluation method for Ant
Colony Optimization is investigated. We compare this method to the
standard pheromone method and the summation method. Moreover we
propose a new variant of the relative pheromone evaluation method.
Experiments performed for various instances of the single machine
scheduling problems with earliness costs and multiple due dates show
the potential of the relative pheromone evaluation method.
Session:
EvoSTIM Session 1: Methods of solving scheduling problems: April 3, 09001100
An investigation into the use of different search strategies with Grammatical Evolution
O'SULLIVAN J.,
RYAN C.
Abstract:
We present an investigation into the performance of Grammatical Evolution using a number of different search strategies, Simulated Annealing, Hill Climbing, Random Search and Genetic Algorithms. Comparative results on three different problems are examined. We analyse the nature of the search spaces presented by these problems and offer an explanation for the contrasting performance of each of the search strategies. Our results show that Genetic Algorithms provide a consistent level of performance across all three problems successfully coping with sensitivity of the system to discrete changes in the selection of productions from the associated grammar.
Session:
EuroGP Session 4: Poster session and conference reception: April 3, 17301930
An Experimental Investigation of Iterated Local Search for Coloring Graph
Paquete L.,
Stützle T
Abstract:
Graph coloring is a well known problem from graph theory that, when attacking it with local search algorithms, is typically treated as a series of constraint satisfaction problems: for a given number of colors k one has to find a feasible coloring; once such a coloring is found, the number of colors is decreased and the local search starts again. Here we explore the application of Iterated Local Search on the graph coloring problem. Iterated Local Search is a simple and powerful metaheuristic that has shown very good results for a variety of optimization problems. In our research we investigated several perturbation schemes and present computational results on a widely used set of benchmarks problems, a subset of those available from the DIMACS benchmark suite. Our results suggest that Iterated Local Search is particularly promising on hard, structured graphs.
Session:
EvoCOP Session 4: Constrained problems: April 4, 11001230
Allele Diffusion in Linear Genetic Programming and VariableLength Genetic Algorithms with Subtree Crossover
POLI R.,
ROWE J. E.,
STEPHENS C. R.,
WRIGHT A. H.
Abstract:
In this paper we study, theoretically, the search biases produced by GP subtree crossover when applied to linear representations, such as those used in linear GP or in variable length GAs. The study naturally leads to generalisations of Geiringer s theorem and of the notion of linkage equilibrium, which, until now, were applicable only to fixedlength representations. This indicates the presence of a diffusion process by which, even in the absence of selective pressure and mutation, the alleles in a particular individual tend not just to be swapped with those of other individuals in the population, but also to diffuse within the representation of each individual. More precisely, crossover attempts to push the population towards distributions of primitives where each primitive is equally likely to be found in any position in any individual.
Session:
EuroGP Session 4: Poster session and conference reception: April 3, 17301930
Solving Car Sequencing Problems by Local Optimization
Puchta M.,
Gottlieb J.
Abstract:
Realworld car sequencing problems deal with lots of constraints, which differ in their types and priorities. We evaluate three permutationbased local search algorithms that use different acceptance criteria for moves. The algorithms meet industrial requirements to obtain acceptable solutions in a rather short time. It is essential to employ move operators which can be evaluated quite fast. Further, using different move types enlarges the neighbourhood, thereby decreasing the total number of local optima in the search space. The comparison of the acceptance criteria shows that the greedy approach is inferior to two variants of threshold accepting that allow escaping from local optima.
Session:
EvoCOP Session 4: Constrained problems: April 4, 11001230
Detection Of Incidents On Motorways In Low Flow High Speed Conditions By Genetic Programming
Roberts S. C.,
Howard D.
Abstract:
Traditional algorithms which set a lower speed limit on a motorway to protect the traffic against collision with a queue are not successful at detecting isolated incidents late at night, in low flow high speed conditions. The Staged Genetic Programming method is used to detect an incident in this traffic regime. The evolutionary engine automatically decides the time duration for the onset of an incident. This method successfully combines traffic readings from the MIDAS system to predict a variety of late night incidents on the M25 motorway.
Session:
EvoIASP Session 4: EC applications to traffic control: April 3, 17101800
No Coercion and No Prohibition, A Position Independent Encoding Scheme for Evolutionary Algorithms  The Chorus System
RYAN C.,
AZAD A.,
SHEAHAN A.,
O'NEILL M.
Abstract:
We describe a new encoding system, Chorus, for grammar based Evolutionary Algorithms. This scheme is coarsely based on the manner in nature in which genes produce proteins that regulate the metabolic pathways of the cell. The phenotype is the behaviour of the cells metabolism, which corresponds to the development of the computer program in our case. In this procedure, the actual protein encoded by a gene is the same regardless of the position of the gene within the genome.
We show that the Chorus system has a very convenient Regular Expression  type schema notation that can be used to describe the presence of various phenotypes or phenotypic traits. This schema notation is used to demonstrate that massive areas of neutrality can exist in the search landscape, and the system is also shown to be able to dispense with large areas of the search space that are unlikely to contain useful solutions.
Session:
EuroGP Session 9: Grammatical evolution: April 5, 09301100
Genetic Algorithms Using Grammatical Evolution
RYAN C.,
NICOLAU M.,
O'NEILL M.
Abstract:
This paper describes the GAUGE system, Genetic Algorithms Using Grammatical Evolution. GAUGE is a position independent Genetic Algorithm that uses Grammatical Evolution with an attribute grammar to dictate what position a gene codes for. GAUGE suffers from neither underspecification nor overspecification, is guaranteed to produce syntactically correct individuals, and does not require any repair after the application of genetic operators. GAUGE is applied to the standard onemax problem, with results showing that its genotype to phenotype mapping and position independence nature do not affect its performance as a normal genetic algorithm. A new problem is also presented, a deceptive version of the Mastermind game, and we show that GAUGE possesses the position independence characteristics it claims, and outperforms several genetic algorithms, including the competent genetic algorithm messyGA.
Session:
EuroGP Session 4: Poster session and conference reception: April 3, 17301930
Evolution Strategies, Network Random Keys, and the OneMax Tree Problem
Schindler B.,
Rothlauf F.,
Pesch H.J.
Abstract:
Evolution strategies (ES) are efficient optimization methods for continuous problems. However, many combinatorial optimization methods can not be represented by using continuous representations. The development of the network random key representation which represents trees by using real numbers allows one to use ES for combinatorial tree problems. In this paper we apply ES to tree problems using the network random key representation. We examine whether existing recommendations regarding optimal parameter settings for ES, which were developed for the easy sphere and corridor model, are also valid for the easy onemax tree problem.
The results show that the 1/5success rule for the (1+1)ES results in low performance because the standard deviation is continuously reduced and we get early convergence. However, for the (mu+lambda)ES and the (mu,lambda)ES the recommendations from the literature are confirmed for the parameters of mutation tau1 and tau2 and the ratio mu/lambda. This paper illustrates how existing theory about ES is helpful in finding good parameter settings for new problems like the onemax tree problem.
Session:
EvoCOP Session 3: Realvalued representations: April 4, 09301030
Image Filter Design with Evolvable Hardware
Sékanina L.
Abstract:
The paper introduces a new approach to automatic design of image filters for a given type of noise. The approach employs evolvable hardware at simplified functional level and produces circuits that outperform conventional designs. If an image is available both with and without noise, the whole process of filter design can be done automatically, without influence of a designer.
Session:
EvoIASP Session 3: Evolvable hardware: April 3, 16001710
Evolutionary Computational Approaches to Solving the Multiple Traveling Salesman Problem using a Neighborhood Attractor Schema
Sofge D.,
Schultz A.,
De Jong K.
Abstract:
This paper presents a variation of the Euclidean Traveling Salesman Problem (TSP), the Multiple Traveling Salesman Problem (MTSP), and compares a variety of evolutionary computation algorithms and paradigms for solving it. Techniques implemented, analyzed, and discussed herein with regard to MTSP include use of a neighborhood attractor schema (a variation on kmeans clustering), the "shrinkwrap" algorithm for local neighborhood optimization, particle swarm optimization, MonteCarlo optimization, and a range of genetic algorithms and evolutionary strategies.
Session:
EvoCOP Session 2: Exploiting statistics: April 3, 16301800
Boosting ACO with a Preprocessing Step
Solnon C.
Abstract:
When solving a combinatorial optimization problem with the Ant Colony Optimization (ACO) metaheuristic, one usually has to find a compromise between guiding or diversifying the search. Indeed, ACO uses pheromone to attract ants. When increasing the sensibility of ants to pheromone, they converge quicker towards a solution but, as a counterpart, they usually find worse solutions. In this paper, we first study the influence of ACO parameters on the exploratory ability of ants. We then study the evolution of the impact of pheromone during the
solution process with respect to its cost's management. We finally propose to introduce a preprocessing step that actually favors a larger exploration of the search space at the beginning of
the search at low cost. We illustrate our approach on AntSolver, an ACO algorithm that has been designed to solve Constraint Satisfaction Problems, and we show on random binary problems that it allows to find better solutions more than twice quicker.
Session:
EvoCOP Session 5: Ant colony optimization: April 4, 13451545
Exons and Code Growth in Genetic Programming
SOULE T.
Abstract:
The phenomenon of code growth is well documented in genetic programming. Several well supported theories exist to explain code growth, each of which focuses on introns, sections of code that do not contribute to fitness. However, several researchers have pointed out that these theories, and code growth itself, does not seem to depend upon the presence of introns. In this paper we show for the first time that code growth can occur, albeit quite slowly, even with exons that have a significant impact on fitness.
Session:
EuroGP Session 3: Code Bloat: April 3, 16301730
Routine Duplication of Post2000 Patented Inventions by Means of Genetic Programming
STREETER M. J.,
KEANE M. A.,
KOZA J. R.
Abstract:
Previous work has demonstrated that genetic programming can automatically create analog electrical circuits, controllers, and other devices that duplicate the functionality and, in some cases, partially or completely duplicate the exact structure of inventions that were patented between 1917 and 1962. This pap er reports on a project in which we browsed patents of analog circuits issued after January 1, 2000 on the premise that recently issued patents represent current research that is considered to be of practical and scientific importance. The paper describes how we used genetic programming to automatically create circuits that duplicate the functionality or structure of five post 2000 patented inventions. This work employed four new techniques (motivated by the theory of genetic algorithms and genetic programm ing) that we believe increased the efficiency of the runs. When an automated method duplicates a previously patented human designed invention, it can be argued that the automated method satisfies a Patent Officebased variation of the Turing test.
Session:
EuroGP Session 5: Applications I: April 4, 09301030
A Dynamic Fitness Function Applied to Improve the Generalisation when Evolving a Signal Processing Hardware Architecture
Třrresen J
Abstract:
The paper introduces a new approach to automatic design of image filters for a given type of noise. The approach employs evolvable hardware at simplified functional level and produces circuits that outperform conventional designs. If an image is available both with and without noise, the whole process of filter design can be done automatically, without influence of a designer
Session:
EvoIASP Session 3: Evolvable hardware: April 3, 16001710
A Memetic Algorithm Guided by Quicksort for the ErrorCorrecting Graph Isomorphism Problem
TorresVelázquez R.,
EstivillCastro V.
Abstract:
Sorting algorithms define paths in the search space of n! permutations based on the information provided by a comparison predicate. We guide a Memetic Algorithm with a new mutation operator. Our mutation operator performs local search following the path traced by the Quicksort mechanism. The comparison predicate and the evaluation function are made to correspond and guide the evolutionary search. Our approach improves previous results for a benchmark of experiments of the ErrorCorrecting Graph Isomorphism. For this case study, our new Memetic Algorithm achieves a better quality vs effort tradeoff and remains highly effective even when the size of the problem grows.
Session:
EvoCOP Session 1: Graph problems: April 3, 14001545
Improving Street Based Routing using Building Block Mutations
Urquhart N.,
Ross P.,
Paechter B.,
Chisholm K.
Abstract:
Street based routing (SBR) is a realworld inspired routing problem
that builds routes within an urban area for mail deliveries. The
authors have previously attempted to solve this problem using an
Evolutionary Algorithm (EA). In this paper the authors examine a
heuristic mutation based on concept of building blocks. In this case a
building block is defined as a group of genes, which when placed
together within a genotype result in a useful feature within the
phenotype. After evaluation on three test data sets our experiments
conclude that the explicit use of heuristic building blocks makes a
significant improvement to the SBR algorithms results.
Session:
EvoSTIM Session 1: Methods of solving scheduling problems: April 3, 09001100
Uniform Subtree Mutation
VAN BELLE T.,
ACKLEY D
Abstract:
Genetic programming methods often suffer from `code bloat,' in which evolving solution trees rapidly become unmanageably large. To provide a measure of sensitivity to tree size in a natural way, we introduce a simple uniform subtree mutation (USM) operator that provides an approximately constant probability of mutation per tree node, rather than per tree. To help model circumstances where tree size cannot be ignored, we introduce a new notion of computational effort called size effort. Initial empirical tests show that genetic programming using only uniform subtree mutation reduces evolved tree sizes dramatically, compared to crossover, but does impact solution quality somewhat. In some cases, however, using using a combination of USM and crossover yielded both smaller trees and superior performance, as measured both by size effort and traditional metrics.
Session:
EuroGP Session 3: Code Bloat: April 3, 16301730
Comparing classical methods for solving binary constraint satisfaction problems with state of the art evolutionary computation
van Hemert J. I.
Abstract:
Constraint Satisfaction Problems form a class of problems that are generally computationally difficult and have been addressed with many complete and heuristic algorithms. We present two complete algorithms, as well as two evolutionary algorithms, and compare them on randomly generated instances of binary constraint satisfaction problems. We find that the evolutionary algorithms are less effective than the classical techniques.
Session:
EvoCOP Session 4: Constrained problems: April 4, 11001230
Efficiently Computable Fitness Functions for Binary Image Evolution
Ványi R
Abstract:
There are applications where a binary image is given and a shape is to be reconstructed from it with some kind of evolutionary algorithms. A solution for this problem usually highly depends on the fitness function. On the one hand fitness function influences the convergence speed of the EA. On the other hand, fitness computation is done many times, therefore the fitness computation itself has to be reasonably fast. This paper tries to define what ``reasonably fast'' means, by giving a definition for the efficiency. A definition alone is however not enough, therefore several fitness functions and function classes are defined, and their efficiencies are examined.
Session:
EvoIASP Session 2: Image acquisition and synthesis: April 3, 14301530
A New View on Symbolic Regression
WEINERT K.,
STAUTNER M.
Abstract:
Symbolic regression is a widely used method to reconstruct mathematical correlations. This paper presents a new graphical representation of the individuals reconstructed in this process. This new three dimensional representation allows the user to recognize certain possibilities to improve his setup of the process parameters. Furthermore this new representation allows a wider usage of the generated three dimensional objects with nearly every CAD program for further use. To show the practical usage of this new representation it was used to reconstruct mathematical descriptions of the dynamics in a machining process namely in orthogonal cutting.
Session:
EuroGP Session 7: Implementation & representation issues: April 4, 13451550
Parallel Surface Reconstruction
WEINERT K.,
SURMANN T.,
MEHNEN J.
Abstract:
The task of surface reconstruction is to find a mathematical representation of a surface which is given only by a set of discrete sampling points. The mathematical description in the computer allows to save or transfer the geometric data via internet, to manipulate (e.g. for aerodynamic or design specific reasons) or to optimize the machining of the work pieces. The reconstruction of the shape of an object is a difficult mathematical and computer scientific problem. For this reason a GP/EShybrid algorithm has been used. Due to the high complexity of the problem and in order to speed up the reconstruction process, the algorithm has been enhanced to work as a multipopulation GP/ES that runs in parallel on a network of standard PCs.
Session:
EuroGP Session 6: Applications II: April 4, 11001230
Genetic control applied to asset managements
WERNER J. C.,
FOGARTY T. C.
Abstract:
This paper address the problem of investment optimisation, with deals with obtain stock time series from data extracted of graphics available in internet, predict assets price by adaptive algorithms, optimise the portfolio with genetic algorithms and obtain a recursive model of portfolio composition onfly using genetic programming, all steps integrated to obtain an automatic management. The final result is a realtime update portfolio composition for each asset.
Session:
EuroGP Session 4: Poster session and conference reception: April 3, 17301930
Evolutionary Based Autocalibration From the Fundamental Matrix
Whitehead A,
Roth G
Abstract:
We describe a new method of achieving autocalibration that uses a stochastic optimization approach taken from the field of evolutionary computing and we perform a number of experiments on standardized data sets that show the effectiveness of the approach. The basic assumption of this method is that the internal (intrinsic) camera parameters remain constant throughout the image sequence, i.e. they are taken from the same camera without varying the focal length. We show that for the autocalibration of focal length and aspect ratio, the evolutionary method achieves comparable results without the implementation complexity of other methods. Autocalibrating from the fundamental matrix is simply transformed into a global minimization problem utilizing a cost function based on the properties of the fundamental matrix and the essential matrix.
Session:
EvoIASP Session 2: Image acquisition and synthesis: April 3, 14301530
Needles in Haystacks Are Not Hard to Find with Neutrality
YU T.,
MILLER J.
Abstract:
We propose building neutral networks in needleinhaystack fitness landscapes to assist an evolutionary algorithm to perform search. The experimental results on four different problems show that this approach improves the search success rates in most cases. In situations where neutral networks do not give performance improvement, no impairment occurs either. We also tested a hypothesis proposed in our previous work. The results support the hypothesis: when the ratio of adaptive/neutral mutations during neutral walk is close to that of fitness improvement step, the evolutionary search has a high success rate. Moreover, the ratio magnitudes indicate that more neutral mutations (than adaptive mutations) are required for the algorithms to find a solution in this type of search space.
Session:
EuroGP Session 2: Experimental & theoretical analysis: April 3, 14001605
