EvoWorkshops2002
5th Evolutionary Computing Workshops
3-5 April 2002
Kinsale, Ireland

Menu
Home
EvoCOP2002
Introduction
Programme
Accepted papers
Committee
EvoIASP2002
EvoSTIM2002

Joint event pages
Registration
Programme overview
All accepted papers
Local information
Accommodation
Travel

Main contacts
EvoWorkshops chair
Stefano Cagnoni
Local chair
Conor Ryan

  EvoWorkshops2002

EvoCOP2002
2nd European Workshop on Evolutionary Computation in Combinatorial Optimization


Introduction

Evolutionary algorithms have often been shown to be effective for diffcult 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.

EvoCOP2001was the first international event specifically dedicated to the application of evolutionary computation to combinatorial optimization problems. It 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 was documented by 31 submitted and 23 accepted papers, which were published by Springer in the series Lecture Notes in Computer Science (LNCS Vol. 2037).

EvoCOP2002 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.

The workshop is sponsored by EvoNet, the Network of Excellence in Evolutionary Computing. It will be part of EvoWorkshops2002 and will be held in conjunction with EuroGP2002, the European Conference on Genetic Programming.

Topics of interest include, but are not limited to:

  • applications of evolutionary algorithms and related heuristics like simulated annealing or ant systems to combinatorial optimization problems
  • representation techniques
  • evolutionary operators
  • constraint-handling techniques
  • hybrid methods
  • parallelization
  • theoretical developments
  • search space analyses
  • comparisons between different (also non-evolutionary) techniques

Programme

Draft: subject to change

See also:
Programme overview | EuroGP programme | EvoIASP programme | EvoSTIM programme

Wednesday 3 April
0830-1130 Registration
1100-1130 Coffee available
1130-1245 EuroGP Session 1:
Conference opening and invited speaker:
Prof Chrystopher L Nehaniv


Session chair: Conor Ryan
1245-1400 Lunch
1400-1545 Session 1:
Workshop opening
Graph problems

Session chair: Günther Raidl
Genetic, Iterated and Multistart Local Search for the Maximum Clique Problem
Marchiori E.
A Memetic Algorithm Guided by Quicksort for the Error-Correcting Graph Isomorphism Problem
Torres-Velázquez R., Estivill-Castro V.
A Memetic Algorithm for Vertex-Biconnectivity Augmentation
Kersting S., Raidl G. R., Ljubic I.
1530-1630 Coffee available
1630-1800 Session 2:
Exploiting statistics

Session chair: Franz Rothlauf
Exploiting Fitness Distance Correlation of Set Covering Problems
Finger M., Stützle T., Lourenço H.
Non-parametric Estimation of Properties of Combinatorial Landscapes
Eremeev A., Reeves C. R.
Evolutionary Computational Approaches to Solving the Multiple Traveling Salesman Problem using a Neighborhood Attractor Schema
Sofge D., Schultz A., De Jong K.
Thursday 4 April
0930-1030 Session 3:
Real-valued representations

Session chair: Jens Gottlieb
Evolution Strategies, Network Random Keys, and the One-Max Tree Problem
Schindler B., Rothlauf F., Pesch H.-J.
Application of Genetic Algorithms in Nanoscience: Cluster Geometry Optimization
Johnston R. L., Mortimer-Jones T. V., Roberts C., Darby S., Manby F. R.
1030-1100 Coffee available
1100-1230 Session 4:
Constrained problems

Session chair: Elena Marchiori
Comparing classical methods for solving binary constraint satisfaction problems with state of the art evolutionary computation
van Hemert J. I.
An Experimental Investigation of Iterated Local Search for Coloring Graph
Paquete L., Stützle T
Solving Car Sequencing Problems by Local Optimization
Puchta M., Gottlieb J.
1230-1345 Lunch
1345-1545 Session 5:
Ant colony optimization

Session chair: Martin Middendorf
A Population Based Approach for ACO
Guntsch M., Middendorf M.
Updating ACO pheromones using Stochastic Gradient Ascent and Cross-Entropy methods
Dorigo M., Zlochin M., Meuleau N., Birattari M.
Boosting ACO with a Preprocessing Step
Solnon C.
Savings Ants for the Vehicle Routing Problem
Doerner K., Gronalt M., Hartl R. F., Reimann M., Strauss C., Stummer M.
1545-1615 Coffee available
1615-1745 EuroGP Session 8:
Conference debate

Session chair: Julian Miller
1800 Conference social night
Friday 5 April
0930-1100 Session 6:
Scheduling problems

Session chair: Colin Reeves
Performance of Evolutionary Approaches for Parallel Task Scheduling under Different Representations
Esquivel S., Gatica C., Gallard R.
Hyperheuristics: A Tool for Rapid Prototyping in Scheduling and Optimisation
Cowling P., Kendall G., Soubeiga S.
A Performance Comparison of Alternative Heuristics for the Flow Shop Scheduling Problem
Esquivel S., Leguizamón G., Zuppa F., Gallard R.

Workshop close


Accepted papers

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 high-level heuristic that adaptively controls several low-level knowledge-poor heuristics so that while using only cheap, easy-to-implement low-level heuristics, we may achieve solution quality approaching that of an expensive knowledge-rich 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 non-academic IT professionals. Hyperheuristics have been successfully applied by the authors to a real-world problem of personnel scheduling. In this paper, the authors report another successful application of hyperheuristics to a rather different real-world 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, 0930-1100


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 meta-heuristics and show that our results are competitive.

Session:
EvoCOP Session 5: Ant colony optimization: April 4, 1345-1545


Updating ACO pheromones using Stochastic Gradient Ascent and Cross-Entropy 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 cross-entropy 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, 1345-1545


Non-parametric 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 non-parametric 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, 1630-1800


Performance of Evolutionary Approaches for Parallel Task Scheduling under Different Representations
Esquivel S., Gatica C., Gallard R.

Abstract:
Task scheduling is known to be NP-complete 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 list-based 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, 0930-1100


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 two-machine makespan problem [1], over the past three decades extensive search have been done on pure m-machine flow shop problems. Many researchers faced the Flow Shop Scheduling (FSSP) by means of well-known 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 bio-inspired 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, 0930-1100


Exploiting Fitness Distance Correlation of Set Covering Problems
Finger M., Stützle T., Lourenço H.

Abstract:
The set covering problem is an NP-hard 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 fitness-distance 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, 1630-1800


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, 1345-1545


Application of Genetic Algorithms in Nanoscience: Cluster Geometry Optimization
Johnston R. L., Mortimer-Jones 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 Cu-Au clusters; and the use of an energy predator in an attempt to identify the lowest six isomers of C40.

Session:
EvoCOP Session 3: Real-valued representations: April 4, 0930-1030


A Memetic Algorithm for Vertex-Biconnectivity 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 vertex-biconnected. A real-world 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, 1400-1545


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, 1400-1545


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 sub-set 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, 1100-1230


Solving Car Sequencing Problems by Local Optimization
Puchta M., Gottlieb J.

Abstract:
Real-world car sequencing problems deal with lots of constraints, which differ in their types and priorities. We evaluate three permutation-based 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, 1100-1230


Evolution Strategies, Network Random Keys, and the One-Max 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 one-max tree problem. The results show that the 1/5-success 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 one-max tree problem.

Session:
EvoCOP Session 3: Real-valued representations: April 4, 0930-1030


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 k-means clustering), the "shrink-wrap" algorithm for local neighborhood optimization, particle swarm optimization, Monte-Carlo optimization, and a range of genetic algorithms and evolutionary strategies.

Session:
EvoCOP Session 2: Exploiting statistics: April 3, 1630-1800


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 Ant-Solver, 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, 1345-1545


A Memetic Algorithm Guided by Quicksort for the Error-Correcting Graph Isomorphism Problem
Torres-Velázquez R., Estivill-Castro 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 Error-Correcting Graph Isomorphism. For this case study, our new Memetic Algorithm achieves a better quality vs effort trade-off and remains highly effective even when the size of the problem grows.

Session:
EvoCOP Session 1: Graph problems: April 3, 1400-1545


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, 1100-1230


Committee

EvoCOP Chairs:

Jens Gottlieb
SAP AG
Neurottstr. 16
69190 Walldorf, Germany
jens.gottlieb@sap.com
tel: +49(6227)7-49356
fax: +49(6227)78-32766

Günther Raidl
Institute of Computer Graphics and Algorithms
Vienna University of Technology
Favoritenstr. 9-11/186
1040 Vienna, Austria
raidl@ads.tuwien.ac.at
http://www.ads.tuwien.ac.at/people/Raidl.html
tel: +43(1)58801-18616
fax: +43(1)58801-18699

EvoCOP program Committee:

Edmund Burke (UK)
Jie Cheng (USA)
David Corne (UK)
Carlos Cotta-Porras (Spain)
Peter Cowling (UK)
Marco Dorigo (Belgium)
Gusz Eiben (The Netherlands)
David Fogel (USA)
Jin-Kao Hao (France)
Michiel de Jong (The Netherlands)
Bryant Julstrom (USA)
Dimitri Knjazew (Germany)
Joshua Knowles (UK)
Gabriele Kodydek (Austria)
Mario Köppen (Germany)
Jozef Kratica (Yugoslavia)
Yu Li (France)
Ivana Ljubic (Austria)
Elena Marchiori (The Netherlands)
Dirk Mattfeld (Germany)
Georgios Papadimitriou (Greece)
Colin Reeves (UK)
Marc Reimann (Austria)
Claudio Rossi (Italy)
Franz Rothlauf (Germany)
Marc Schoenauer (France)
Thomas Stützle (Germany)
El-ghazali Talbi (France)
Christine Valenzuela (UK)