EvoWorkshops2003
6th European Evolutionary Computing Workshops
14-16 April 2003

Menu
Home
EvoBIO
EvoCOP
EvoIASP
EvoMUSART
EvoROB
EvoSTIM

Post conference pages
2004 announcement
Awards
Photos
Feature articles
Proceedings

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

Main contacts
EvoWorkshops chair
Günther Raidl
Local co-chairs
Edward Tsang
Riccardo Poli

EuroGP2003

EvoCOP2003
3rd European Workshop on Evolutionary Computation in Combinatorial Optimization

The 18 papers accepted for last year's EvoCOP workshop are available in Springer's LNCS series, volume 2279.

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 meta-heuristics like simulated annealing, tabu search or ant systems to combinatorial optimization problems
Representation techniques
Evolutionary operators
Constraint-handling techniques
Hybrid methods
Parallelization
Theoretical developments, search space analysis
Comparisons between different (also non-evolutionary) techniques

Programme

Draft: subject to change

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 NP-hard and known in the literature as the Index Selection Problem (ISP). We propose a genetic algorithm (GA) for solving the ISP. Computational results of the GA on standard ISP instances are compared to branch-and-cut method and its initialisation heuristics and two state of the art MIP solvers: CPLEX and OSL. These results indicate good performance, reliability and efficiency of the proposed approach.
EvoCOP Session 2: Satisfiability and selection problems: April 14, 1600-1800

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Chairs

Jens Gottlieb
SAP AG
Neurottstr. 16
69190 Walldorf, Germany
jens.gottlieb@sap.com
phone: +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
www.ads.tuwien.ac.at/people/Raidl.html
phone: +43(1)58801-18616
fax: +43(1)58801-18699

Programme committee