EvoCOP2003
3rd European Workshop on Evolutionary Computation in Combinatorial Optimization
Previous editions:
Lake Como, Italy, 2001
Kinsale, Ireland, 2002
Introduction
Evolutionary algorithms have often been shown to be effective
for difficult combinatorial optimization problems appearing in
various industrial, economical, and scientific domains. Prominent
examples of such problems are transportation problems, vehicle routing,
traveling salesperson, satisfiability, packing, network design,
or general mixed integer programming.
The first two EvoCOP workshops were the first international
events specifically dedicated to the application of evolutionary
computation to combinatorial optimization problems.
They gave researchers a good opportunity to present their latest
research and to discuss current developments and applications,
besides stimulating closer future interaction between members of this
scientific community.
The success of EvoCOP2001 and EvoCOP2002 was documented by 31 (32)
submitted and 23 (18) accepted
papers, which were published by Springer in the series Lecture
Notes in Computer Science (LNCS Volume 2037
and Volume 2279).
EvoCOP2003 wants to bring researchers in the field together once again.
Each accepted paper will be presented orally at the workshop and
printed in the proceedings published by Springer in the LNCS series.
A special issue of the Journal of Mathematical Modelling and
Algorithms on Evolutionary Computation in Combinatorial
Optimization (see http://www.ads.tuwien.ac.at/ecco_jmma)
will be published. Authors of selected EvoCOP papers will be invited to
submit an extended version for consideration in this special issue.
Topics of interest include, but are not limited to:
 Applications and case studies of evolutionary algorithms and related
metaheuristics like simulated annealing, tabu search or ant systems to
combinatorial optimization problems
 Representation techniques
 Evolutionary operators
 Constrainthandling techniques
 Hybrid methods
 Parallelization
 Theoretical developments, search space analysis
 Comparisons between different (also nonevolutionary) techniques
Programme
Draft: subject to change
See also: Programme overview
Monday 14 April 
09001000 
Registration

10001115 
EuroGP Session 1: Conference opening and invited speaker: David Goldberg
Session chair: Terry Soule

11151130 
Coffee break

13001400 
Lunch

14001515 
Session 1: New directions
Session chair: Jens Gottlieb
Guiding SingleObjective Optimization using MultiObjective Methods
Jensen M
Combinations of Local Search and Exact Algorithms
Dumitrescu I,
Stützle T

15301600 
Tea break

16001800 
Session 2: Satisfiability and selection problems
Session chair: Colin Reeves
A Genetic Algorithm for the Index Selection Problem
Kratica J,
Ljubic I,
Tosic D
Experimental Comparison of Two Evolutionary Algorithms for Independent Set Problem
Borisovsky P,
Zavolovskaya M
Multilevel Heuristic Algorithm for Graph Partitioning
Banos R,
Gil C,
Ortega J,
Montoya F
Evolutionary Computing for the Satisfiability Problem
Hao J,
Lardeux F,
Saubion F

17301930 
EuroGP Session 5: Posters
Session chair: James Foster
Assembling Strategies in Extrinsic Evolvable Hardware with Bidirectional Incremental Evolution
Baradavkaigor I,
Kalganova T
Neutral Variations Cause Bloat in Linear GP
Brameier M,
Banzhaf W
Experimental design based multiparent crossover operator
Chan K,
Fogarty T
An Enhanced Framework for Microprocessor
Corno F,
Squillero G
The Effect of Plagues in Genetic Programming: A Study of VariableSize Populations
Fernandez F,
Vanneschi L,
Tomassini M
Multi Niche Parallel GP with a Junkcode Migration Model
Garcia S,
Levine J,
Gonzalez F
Tree Adjoining Grammars, Language Bias, and Genetic Programming
Xuan N,
McKay R,
Abbass H
Artificial Immune System Programming for Symbolic Regression
Johnson C
Grammatical Evolution with Bidirectional Representation
Kubalik J,
Koutni J,
Rothkrantz L
Introducing a Perl Genetic Programming System: and Can Metaevolution Solve the Bloat Problem?
MacCallum R
Evolutionary Optimized Mold Temperature Control Strategies using a MultiPolyline Approach
Mehnen J,
Michelitsch T,
Weinert K
Genetic Programming for Attribute Construction in Data Mining
Otero F,
Silva M,
Freitas A,
Nievola J
Sensible Initialisation in Chorus
Ryan C,
Atif R
An Analysis of Diversity of Constants of Genetic Programming
Ryan C,
Keijzer M
Research of a cellular automaton simulating logic gates by evolutionary algorithms
Sapin E,
Bailleux O,
Chabrier J
From Implementations to a General Concept of Evolvable Machines
Sekanina L
Cooperative Evolution on the Intertwined Spirals Problem
Soule T
The Root Causes of Code Growth in Genetic Programming
Streeter M
Fitness Distance Correlation in Structural Mutation Genetic Programming
Vanneschi L,
Tomassini M,
Collard P,
Clergue M
Disease modeling using Evolved Discriminate Function
Werner J,
Kalganova T
No Free Lunch, Program Induction and Combinatorial Problems
Woodward J,
Neil J

Tuesday 15 April 
11001120 
Coffee break

11201250 
Session 3: Ant colony optimisation 1
Session chair: Martin Middendorf
Searching for Maximum Cliques with Ant Colony Optimization
Fenet S,
Solnon C
Ant Algorithms for the University Course Timetabling Problem with Regard to the StateoftheArt
Socha K,
Sampels M,
Manfrin M
A Study of Greedy, Local Search and Ant Colony Optimization Approaches for Car Sequencing Problems
Gottlieb J,
Puchta M,
Solnon C

12501345 
Lunch

13451515 
Session 4: Miscellaneous
Session chair: Marc Reimann
Genetic algorithms on NKlandscapes: Effects of Selection, Drift, Mutation, and Recombination
Aguirre H,
Tanaka K
A Template Approach to Producing Incremental Objective Cost Functions for Local Search Metaheuristics
Randall M
Adapting to Complexity During Search in Combinatorial Landscapes
Riopka T

15151530 
Tea break

15301630 
Session 5: Mobile cellular networks
Session chair: David Corne
An Experimental Comparison of Two Different Encoding Schemes for the Location of Base Stations in Cellular Networks
Brizuela C,
Gutierrez E
Constrained Coverage Optimization for Mobile Cellular Networks
Du L,
Bigham J

16301730 
EuroGP Session 10: Conference debate
Session chair: James Foster

1800 
Conference dinner: Tudor banquet

Wednesday 16 April 
10001100 
Session 6: Ant colony optimisation 2
Session chair: Christine Solnon
Analyzing a Unified Ant System for the VRP and Some of its Variants
Reimann M,
Doerner K,
Hartl R
New Ideas for Applying Ant Colony Optimization to the Probabilistic TSP
Branke J,
Guntsch M

11001120 
Coffee break

11201250 
Session 7: Search space analysis
Session chair: Guenther Raidl
Landscape State Machines: Tools for Evolutionary Algorithm Performance Analyses and Landscape/Algorithm Mapping
Corne D,
Oates M,
Kell D
On Confidence Intervals for the Number of Local Optima
Eremeev A,
Reeves C
Search Space Analysis of the Linear Ordering Problem
Schiavinotto T,
Stützle T
Workshop close


Accepted papers
The EvoWorkshops2003 proceedings will be published by Spinger as part of their Lecture Notes in Computer Science series.
A Genetic Algorithm for the Index Selection Problem
Kratica J,
Ljubic I,
Tosic D
This paper considers the problem of minimizing the response time for a given database workload by a proper choice of indexes. This problem is NPhard and known in the literature as the Index Selection Problem (ISP). We propose a genetic algorithm (GA) for solving the ISP. Computational results of the GA on standard ISP instances are compared to branchandcut method and its initialisation heuristics and two state of the art MIP solvers: CPLEX and OSL. These results indicate good performance, reliability and efficiency of the proposed approach.
EvoCOP Session 2: Satisfiability and selection problems: April 14, 16001800
A Study of Greedy, Local Search and Ant Colony Optimization Approaches for Car Sequencing Problems
Gottlieb J,
Puchta M,
Solnon C
This paper describes and compares several heuristic approaches for the car sequencing problem. We first study greedy heuristics, and show that dynamic ones clearly outperform their static counterparts. We then describe local search and ant colony optimization (ACO) approaches, that both integrate greedy heuristics, and experimentally compare them on benchmark instances. ACO yields the best solution quality for smaller time limits, and it is comparable to local search for larger limits. Our best algorithms proved one instance being feasible, for which it was formerly unknown whether it is satisfiable or not.
EvoCOP Session 3: Ant colony optimisation 1: April 15, 11201250
A Template Approach to Producing Incremental Objective Cost Functions for Local Search Metaheuristics
Randall M
Metaheuristic search techniques based on local search operators have proven to be very eective at solving combinatorial optimisation problems. A characteristic of local search operators is that they usually only make a small change to the solution state when applied. As a result, it is often unnecessary to reevaluate the entire objective function once a transition is made but to use an incremental cost function. For example in the travelling salesman problem, the position of two cities within a tour, may be interchanged. Using an incremental cost function, this equates to an O(1) operation as opposed to an O(n) operation (where n is the number of cities). In this paper, a new approach based on the use of templates is developed for the generic linked list modelling system [4]. It demonstrates that incremental objective cost functions can be automatically generated for given problems using dierent local search operators.
EvoCOP Session 4: Miscellaneous: April 15, 13451515
Adapting to Complexity During Search in Combinatorial Landscapes
Riopka T
Fitness landscape complexity in the context of evolutionary algorithms can be considered to be a relative term due to the complex interaction between search strategy, problem difficulty and problem representation. A new paradigm for genetic search referred to as the Collective Learning Genetic Algorithm (CLGA) has been demonstrated for combinatorial optimization problems which utilizes genotypic learning to do recombination based on a cooperative exchange of knowledge (instead of symbols) between interacting chromosomes. There is evidence to suggest that the CLGA is able to modify its recombinative behavior based on the consistency of the information in its environment, specifically, the observed fitness landscape. By analyzing the structure of the evolving individuals, a landscapecomplexity measure is extracted a posteriori and then plotted for various types of example problems. This paper presents preliminary results that show that the CLGA appears to adapt its search strategy to the fitness landscape induced by the CLGA itself, and hence relative to the landscape being searched.
EvoCOP Session 4: Miscellaneous: April 15, 13451515
An Experimental Comparison of Two Different Encoding Schemes for the Location of Base Stations in Cellular Networks
Brizuela C,
Gutierrez E
This paper presents preliminary results on the comparison of binary and integer based representations for the Base Stations Location (BSL) problem. The simplest model of this problem, which is already NPcomplete, is dealt with to compare also dierent crossover operators. Experimental results support the hypothesis that the integer based representation with a specific crossover operator outperforms the more traditional binary one for a very specific set of instances.
EvoCOP Session 5: Mobile cellular networks: April 15, 15301630
Analyzing a Unified Ant System for the VRP and Some of its Variants
Reimann M,
Doerner K,
Hartl R
In this paper we analyze the application of an Ant System to dierent vehicle routing problems. More specifically, we study the robustness of our Unified Ant System by evaluating its performance on four dierent problem classes within the domain of vehicle routing.
EvoCOP Session 6: Ant colony optimisation 2: April 16, 10001100
Ant Algorithms for the University Course Timetabling Problem with Regard to the StateoftheArt
Socha K,
Sampels M,
Manfrin M
Two ant algorithms solving a simplified version of a typical university course timetabling problem are presented Ant Colony System and MAXMIN Ant System. The algorithms are tested over a set of instances from three classes of the problem. Results are compared with recent results obtained with several metaheuristics using the same local search routine (or neighborhood definition), and a reference random restart local search algorithm. Further, both ant algorithms are compared on an additional set of instances. Conclusions are drawn about the performance of ant algorithms on timetabling problems in comparison to other metaheuristics. Also the design, implementation, and parameters of ant algorithms solving the university course timetabling problem are discussed. It is shown that the particular implementation of an ant algorithm has significant influence on the observed algorithm performance.
EvoCOP Session 3: Ant colony optimisation 1: April 15, 11201250
Combinations of Local Search and Exact Algorithms
Dumitrescu I,
Stützle T
In this paper we describe the advantadges and disadvantages of local search and exact methods of solving NPhard problems and see why combining the two approaches is highly desirable. We review some of the papers existent in the literature that create new algorithms from such combinations. In this paper we focus on local search approaches that are strengthened by the use of exact algorithms.
EvoCOP Session 1: New directions: April 14, 14001515
Constrained Coverage Optimization for Mobile Cellular Networks
Du L,
Bigham J
This paper explores the use of evolutionary algorithms to optimise cellular coverage so as to balance the trac load over the whole mobile cellular network. A transformation of the problem space is used to remove the principal power constraint. A problem with the intuitive transformation is shown and a revised transformation with much better performance is presented. This highlights a problem with transformationbased methods in evolutionary algorithms. While the aim of transformation is to speed convergence, a bad transformation can be counterproductive. A criterion that is necessary for successful transformations is explained. Using penalty functions to manage the constraints was investigated but gave poor results. The techniques described can be used as constrainthandling method for a wide range of constrained optimisations.
EvoCOP Session 5: Mobile cellular networks: April 15, 15301630
Evolutionary Computing for the Satisfiability Problem
Hao J,
Lardeux F,
Saubion F
This paper presents GASAT, a hybrid evolutionary algorithm for the satisfiability problem (SAT). A specific crossover operator generates new solutions, that are improved by a tabu search procedure. The performance of GASAT is assessed using a set of wellknown benchmarks. Comparisons with stateoftheart SAT algorithms show that GASAT gives very competitive results. These experiments also allow us to introduce a new SAT benchmark from a coloring problem.
EvoCOP Session 2: Satisfiability and selection problems: April 14, 16001800
Experimental Comparison of Two Evolutionary Algorithms for Independent Set Problem
Borisovsky P,
Zavolovskaya M
This work presents an experimental comparison of the steadystate genetic algorithm to the (1+1)evolutionary algorithm applied to the maximum vertex independent set problem. The penalty approach is used for both algorithms and tuning of the penalty function is considered in the first part of the paper. In the second part we give some reasons why one could expect the competitive performance of the (1+1)EA. The results of computational experiment are presented.
EvoCOP Session 2: Satisfiability and selection problems: April 14, 16001800
Genetic algorithms on NKlandscapes: Effects of Selection, Drift, Mutation, and Recombination
Aguirre H,
Tanaka K
Empirical studies have shown that the overall performance of random bit climbers on NKLandscapes is superior to the performance of some simple and enhanced GAs. Analytical studies have also lead to suggest that NKLandscapes may not be appropriate for testing the performance of GAs. In this work we study the effect of selection, drift, mutation, and recombination on NKLandscapes for N = 96. We take a model of generational parallel varying mutation GA (GASRM) and switch on and off its major components to emphasize each of the four processes mentioned above. We observe that using an appropriate selection pressure and postponing drift make GAs quite robust on NKLandscapes; different to previous studies, even simple GAs with these two features perform better than a random bit climber (RBC+) for a broad range of classes of problems (K>=4). We also observe that the interaction of parallel varying mutation with crossover improves further the reliability of the GA, especially for 32 > K > 12. Contrary to intuition, we find that for small K a mutation only EA is very effective and crossover may be omitted; but the relative importance of crossover interacting with varying mutation increases with K performing better than mutation alone (K > 12). We conclude that NKLandscapes are useful for testing the GA s overall behavior and performance and also for testing each one of the major processes involved in a GA.
EvoCOP Session 4: Miscellaneous: April 15, 13451515
Guiding SingleObjective Optimization using MultiObjective Methods
Jensen M
This paper investigates the possibility of using multiobjective methods to guide the search when solving singleobjective optimization problems with genetic algorithms. Using the job shop scheduling problem as an example, experiments demonstrate that by using helperobjectives (additional objectives guiding the search), the average performance of a standard GA can be significantly improved. The helperobjectives guide the search towards solutions containing good building blocks and helps the algorithm avoid local optima. The experiments reveal that the approach only works if the number of helperobjectives used simultaneously is low. However, a high number of helperobjectives can be used in the same run by changing the helperobjectives dynamically.
EvoCOP Session 1: New directions: April 14, 14001515
Landscape State Machines: Tools for Evolutionary Algorithm Performance Analyses and Landscape/Algorithm Mapping
Corne D,
Oates M,
Kell D
Many evolutionary algorithm applications involve either fitness functions with high time complexity or large dimensionality (hence very many fitness evaluations will typically be needed) or both. In such circumstances, there is a dire need to tune various features of the algorithm well so that performance and time savings are optimized. However, these are precisely the circumstances in which prior tuning is very costly in time and resources. There is hence a need for methods which enable fast prior tuning in such cases. We describe a candidate technique for this purpose, in which we model a landscape as a finite state machine, inferred from preliminary sampling runs. In prior algorithmtuning trials, we can replace the 'real' landscape with the model, enabling extremely fast tuning, saving far more time than was required to infer the model. Preliminary results indicate much promise, though much work needs to be done to establish various aspects of the conditions under which it can be most beneficially used. A main limitation of the method as described here is a restriction to mutationonly algorithms, but there are various ways to address this and other limitations.
EvoCOP Session 7: Search space analysis: April 16, 11201250
Multilevel Heuristic Algorithm for Graph Partitioning
Banos R,
Gil C,
Ortega J,
Montoya F
Many real applications involve optimisation problems where more than one objective has to be optimised at the same time. One of these kinds of problems is graph partitioning, that appears in ap plications such as VLSI design, datamining, e cient disc storage of databases, etc. The problem of graph partitioning consists of dividing a graph into a given number of balanced and nonoverlapping partitions while the cuts are minimised. Although di erent algorithms to solve this problem have been proposed, since this is an NPcomplete problem, to get more e cient algorithms for increasing complex graphs still remains as an open question. In this paper, we present a new multilevel algorithm including a hybrid heuristic that is applied along the searching process. We also provide experimental results to demonstrate the e ciency of the new algorithm and compare our approach with other previously proposed e cient algorithms.
EvoCOP Session 2: Satisfiability and selection problems: April 14, 16001800
New Ideas for Applying Ant Colony Optimization to the Probabilistic TSP
Branke J,
Guntsch M
The Probabilistic Traveling Salesperson Problem (PTSP) is a stochastic variant of the Traveling Salesperson Problem (TSP); each customer has to be serviced only with a given probability. The goal is to find an a priori tour with shortest expected tourlength, with the customers being served in the specified order and customers not requiring service being skipped. In this paper, we use the Ant Colony Optimization (ACO) metaheuristic to construct solutions for PTSP. We propose two new heuristic guidance schemes for this problem, and examine the idea of using approximations to calculate the expected tour length. This allows to find better solutions or use less time than the standard ACO approach.
EvoCOP Session 6: Ant colony optimisation 2: April 16, 10001100
On Confidence Intervals for the Number of Local Optima
Eremeev A,
Reeves C
The number of local optima is an important indicator of optimization problem diculty for local search algorithms. Here we will discuss some methods of finding the confidence intervals for this parameter in problems where the large cardinality of the search space does not allow exhaustive investigation of solutions. First results are reported that were obtained by using these methods for NK landscapes, and for the low autocorrelation binary sequence and vertex cover problems.
EvoCOP Session 7: Search space analysis: April 16, 11201250
Search Space Analysis of the Linear Ordering Problem
Schiavinotto T,
Stützle T
The Linear Ordering Problem (LOP) is an NPhard combinatorial optimization problem that arises in a variety of applications and several algorithmic approaches to its solution have been proposed. However, few details are known about the search space characteristics of LOP instances. In this article we develop a detailed study of the LOP search space. The results indicate that, in general, LOP instances show high fitnessdistance correlations and large autocorrelation length but also that there exist significant differences between reallife and randomly generated LOP instances. Because of the limited size of realworld instances, we propose new, randomly generated large reallife like LOP instances which appear to be much harder than other randomly generated instances. Additionally, we propose a rather straightforward Iterated Local Search algorithm, which shows better performance than several stateoftheart heuristics.
EvoCOP Session 7: Search space analysis: April 16, 11201250
Searching for Maximum Cliques with Ant Colony Optimization
Fenet S,
Solnon C
In this paper, we investigate the capabilities of Ant Colony Optimization (ACO) for solving the maximum clique problem. We describe AntClique, an algorithm that successively generates maximal cliques through the repeated addition of vertices into partial cliques. ACO is used to choose, at each step, the vertex to add. We illustrate the behaviour of this algorithm on two representative benchmark instances and we study the impact of pheromone on the solution process. We also experimentally compare AntClique with GLS, a Genetic Local Search approach, and we show that AntClique finds larger cliques, on average, on a majority of DIMACS benchmark instances, even though it does not reach the best known results on some instances.
EvoCOP Session 3: Ant colony optimisation 1: April 15, 11201250
Chairs
Jens Gottlieb
SAP AG
Neurottstr. 16
69190 Walldorf, Germany
jens.gottlieb@sap.com
phone: +49(6227)749356
fax: +49(6227)7832766
Günther Raidl
Institute of Computer Graphics and Algorithms Vienna University of Technology
Favoritenstr. 911/186
1040 Vienna, Austria
raidl@ads.tuwien.ac.at
www.ads.tuwien.ac.at/people/Raidl.html
phone: +43(1)5880118616
fax: +43(1)5880118699
Programme committee
 Emile Aarts (NL)
 Edmund Burke (UK)
 David Corne (UK)
 Carlos CottaPorras (Spain)
 Peter Cowling (UK)
 David Davis (USA)
 Karl Doerner (Austria)
 Marco Dorigo (Belgium)
 Gusz Eiben (NL)
 Anton Eremeev (Russia)
 David Fogel (USA)
 JinKao Hao (France)
 Jano van Hemert (NL)
 Nick Jakobi (UK)
 Bryant Julstrom (USA)
 Dimitri Knjazew (Germany)
 Joshua Knowles (Belgium)
 Gabriele Kodydek (Austria)
 Mario Köppen (Germany)
 Jozef Kratica (Yugoslavia)
 Ivana Ljubic (Austria)
 Elena Marchiori (NL)
 Dirk Mattfeld (Germany)
 Helmut Mayer (Austria)
 Zbigniew Michalewicz (USA)
 Martin Middendorf (Germany)
 Francisco Pereira (Portugal)
 Marcus Randall (Australia)
 Colin Reeves (UK)
 Marc Reimann (Austria)
 Claudio Rossi (Spain)
 Franz Rothlauf (Germany)
 Marc Schoenauer (France)
 Christine Solnon (France)
 Thomas Stützle (Germany)
 Elghazali Talbi (France)
 Edward Tsang (UK)
 Christine Valenzuela (UK)
 Xin Yao (UK)
