EvoCOP2006

6th European Conference on Evolutionary Computation in Combinatorial Optimization

Metaheuristics have often been shown to be effective for difficult combinatorial optimization problems appearing in various industrial, economical, and scientific domains. Prominent examples of metaheuristics are evolutionary algorithms, simulated annealing, tabu search, scatter search, memetic algorithms, variable neighborhood search, iterated local search, greedy randomized adaptive search procedures, estimation of distribution algorithms and ant colony optimization. Successfully solved problems include scheduling, timetabling, network design, transportation and distribution problems, vehicle routing, traveling salesperson, graph problems, satisfiability, packing problems, planning problems, and general mixed integer programming.

The EvoCOP series, started in 2001 and held annually since then, was the first event specifically dedicated to the application of evolutionary computation and related methods to combinatorial optimization problems. Following the general trend of hybrid metaheuristics and diminishing boundaries between the different classes of metaheuristics, EvoCOP has broadened its scope and now explicitly invites submissions on any kind of metaheuristic for combinatorial optimization.

The past events 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.

EvoCOP 2006 wants to bring researchers in the field of metaheuristics together once again. Each accepted paper will be presented orally at the conference and printed in the proceedings published by Springer in the LNCS series (see LNCS volumes 2037, 2279, 2611, 3004, and 3448 for the previous proceedings).

Web address: http://evonet.lri.fr//eurogp2006/?page=evocop

Topics include

Organising Committee

Program Chairs
Jens Gottlieb
jens DOT gottlieb AT sap DOT com
SAP AG, Germany
 
Günther Raidl
raidl AT ads DOT tuwien DOT ac DOT at
Vienna University of Technology
 
Local Chair
Anikó Ekárt
ekart AT sztaki DOT hu
Hungarian Academy of Sciences
 
Publicity Chair
Steven Gustafson
smg AT cs DOT nott DOT ac DOT uk
University of Nottingham, UK

Note: the e-mail addresses are masked for spam protection.

Programme Committee

Adnan Acan
Hernan Aguirre
Enrique Alba
Emin Aydin
Ruibin Bai
Jean Berger
Christian Bierwirth
Christian Blum
Peter Brucker
Edmund Burke
David Wolfe Corne
Ernesto Costa
Carlos Cotta
Peter Cowling
Bart Craenen
David Davis
Karl Doerner
Anton V. Eremeev
David B. Fogel
Bernd Freisleben
Michel Gendreau
Martin Gruber
Michael Guntsch
Walter Gutjahr
Jin-Kao Hao
Emma Hart
Richard F. Hartl
Geir Hasle
Jano van Hemert
Jörg Homberger
Bryant Arthur Julstrom
Graham Kendall
Joshua Knowles
Gary Kochenberger
Gabriele Koller
Mario Köppen
Jozef Kratica
Andrea Lodi
Arne Løkketangen
Helena Lourenco
Dirk C. Mattfeld
Helmut Mayer
Daniel Merkle
Peter Merz
Zbigniew Michalewicz
Martin Middendorf
Pablo Moscato
Christine L. Mumford
Ibrahim H. Osman
Francisco J. B. Pereira
Adam Prügel-Bennett
Jakob Puchinger
Marcus Randall
Colin Reeves
Marc Reimann
Mauricio G. C. Resende
Franz Rothlauf
Andreas Sandner
Marc Schoenauer
Christine Solnon
Eric Soubeiga
Giovanni Squillero
Thomas Stützle
Eric Taillard
El-ghazali Talbi
Edward P. Tsang
Stefan Voss
Ingo Wegener
Takeshi Yamada

Accepted Papers: titles and abstracts

Hybrid Genetic Algorithm within Branch-and-Cut for the Minimum Graph Bisection Problem
Michael Armbruster, Marzena F\"ugenschuh, Christoph Helmberg, Nikolay Jetchev, Alexander Martin

We develop a primal heuristic based on a genetic algorithm for the minimum graph bisection problem and incorporate it in a branch-and-cut framework. The problem concerns partitioning the nodes of a weighted graph into two subsets such that the total weight of each set is within some lower and upper bounds. The objective is to minimize the total cost of the edges between both subsets of the partition. We formulate the problem as an integer program. In the genetic algorithm the LP-relaxation of the IP-formulation is exploited. We present several ways of using LP information and demonstrate the computational success.


The Trade Off between Diversity and Quality for Multi-objective Workforce Scheduling
Peter Cowling, Nic Colledge, Keshav Dahal, Stephen Remde
(Nominated for Best Paper Award)

In this paper we investigate and compare multi-objective and weighted single objective approaches to a real world workforce scheduling problem. For this difficult problem we consider the trade off in solution quality versus population diversity, for different sets of fixed objective weights. Our real-world workforce scheduling problem consists of assigning resources with the appropriate skills to geographically dispersed task locations while satisfying time window constraints. The problem is NP-Hard and contains the Resource Constrained Project Scheduling Problem (RCPSP) as a sub problem. We investigate a genetic algorithm and serial schedule generation scheme together with various multi-objective approaches. We show that multi-objective genetic algorithms can create solutions whose fitness is within 2% of genetic algorithms using weighted sum objectives even though the multi-objective approaches know nothing of the weights. The result is highly significant for complex real-world problems where objective weights are seldom known in advance since it suggests that a multi-objective approach can generate a solution close to the user preferred one without having knowledge of user preferences.


Evolving the Structure of the Particle Swarm Optimization Algorithms
Laura Dio\c{s}an, Mihai Oltean

A new model for evolving the structure of a Particle Swarm Optimization (PSO) algorithm is proposed in this paper. The model is a hybrid technique that combines a Genetic Algorithm (GA) and a PSO algorithm. Each GA chromosome is an array encoding a meaning for updating the particles of the PSO algorithm. The evolved PSO algorithm is compared to a human-designed PSO algorithm by using ten artificially constructed functions and one real-world problem. Numerical experiments show that the evolved PSO algorithm performs similarly and sometimes even better than standard approaches for the considered problems.


A Tabu Search Algorithm for Optimization of Gas Distribution Networks
Herbert de M\'elo Duarte, Elizabeth Gouv\^{e}a Goldbarg, Marco C\'esar Goldbarg

In this paper a tabu search algorithm is proposed for the optimization of constrained gas distribution networks. The problem consists in finding the least cost combination of diameters, from a discrete set of commercially available ones, for the pipes of a given gas network, satisfying the constraints related to minimum pressure requirements and upstream pipe conditions. Since this is a nonlinear mixed integer problem, metaheuristic approaches seem to be more suitable and to provide better results than classical optimization methods. In this work, a tabu search heuristics is applied to the problem and the results of the proposed algorithm are compared with the results of a genetic algorithm and two other versions of tabu search algorithms. The results are very promising, regarding both quality of solutions and computational time.


Design of a Retail Chain Stocking up Policy with a Hybrid Evolutionary Algorithm
Anna I Esparcia-Alc\'azar, Lidia Lluch-Revert, Manuel Card\'os, Ken Sharman, Carlos Andr\'es-Romano

In this paper we address the joint problem of minimising both the transport and inventory costs of a retail chain that is supplied from a central warehouse. We propose a hybrid evolutionary algorithm where the delivery patterns are evolved for each shop, while the delivery routes are obtained employing the multistart sweep algorithm. The experiments performed show that this method can obtain acceptable results consistently and within a reasonable timescale. The results are also of a lower cost than those obtained by other strategies employed in previous research. Furthermore, they confirm the interest of addressing the optimisation problem jointly, rather than minimising separately inventory and transport.


Parametrized GRASP Heuristics for Three-Index Assignment
Armin F\"ugenschuh, Benjamin H\"ofler

Constructive greedy heuristics are algorithms that try to iteratively construct feasible solutions for combinatorial optimization problems from the scratch. For this they make use of a greedy scoring function, which evaluates the myopic impact of each possible element with respect to the solution under construction. Although fast, effective, and even exact for some problem classes, greedy heuristics might construct poor solution when applied to difficult (NP-hard) problems. To avoid such pitfalls we suggest the approach of parametrizing the scoring function by including several different myopic aspects at once, which are weighted against each other. This so-called pgreedy approach can be embedded into the metaheuristic concept of GRASP. The hybrid metaheuristic of GRASP with a parametrized scoring function is called parametrized GRASP heuristic (PGRASP). We present a PGRASP algorithm for the axial three index assignment problem (AP3) and computational results comparing PGRASP with the classical GRASP strategy.


A Memetic Algorithm with Bucket Elimination for the Still Life Problem
Jos\'e E. Gallardo, Carlos Cotta, Antonio J. Fern\'andez

Bucket elimination (BE) is an exact technique based on variable elimination, commonly used for solving constraint satisfaction problems. We consider the hybridization of BE with evolutionary algorithms endowed with tabu search. The resulting memetic algorithm (MA) uses BE as a mechanism for recombining solutions, providing the best possible child from the parental set. This MA is applied to the maximum density still life problem. Experimental tests indicate that the MA provides optimal or near-optimal results at an acceptable computational cost.


Effects of Scale-Free and Small-World Topologies on Binary Coded Self-Adaptive CEA
Mario Giacobini, Mike Preuss, Marco Tomassini

In this paper we investigate the properties of CEAs with populations structured as Watts-Strogatz small-world graphs and Albert-Barabasi scale-free graphs as problem solvers, using several standard discrete optimization problems as a benchmark. The EA variants employed include self-adaptation of mutation rates. Results are compared with the corresponding classical panmictic EA showing that topology together with self-adaptation drastically influences the search.


Particle Swarm for the Traveling Salesman Problem
Elizabeth Gouv\^{e}a Goldbarg, Givanaldo R.\ de Souza, Marco C\'esar Goldbarg

Abstract. This paper presents a competitive Particle Swarm Optimization algorithm for the Traveling Salesman Problem, where the velocity operator is based upon local search and path-relinking procedures. The paper proposes two versions of the algorithm, each of them utilizing a distinct local search method. The proposed heuristics are compared with other Particle Swarm Optimization algorithms presented previously for the same problem. The results are also compared with three effective algorithms for the TSP. A computational experiment with benchmark instances is reported. The results show that the method proposed in this paper finds high quality solutions and is comparable with the effective approaches presented for the TSP.


Hierarchical Cellular Genetic Algorithm
Stefan Janson, Enrique Alba, Bernab\'e Dorronsoro, Martin Middendorf

Cellular Genetic Algorithms (cGA) are spatially distributed Genetic Algorithms that, because of their high level of diversity, are superior to regular GAs on several optimization functions. Also, since these distributed algorithms only require communication between few closely arranged individuals, they are very suitable for a parallel implementation. We propose a new kind of cGA, called hierarchical cGA (H-cGA), where the population structure is augmented with a hierarchy according to the current fitness of the individuals. Better individuals are moved towards the center of the grid, so that high quality solutions are exploited quickly, while at the same time new solutions are provided by individuals at the outside that keep exploring the search space. This algorithmic variant is expected to increase the convergence speed of the cGA algorithm and maintain the diversity given by the distributed layout. We examine the effect of the introduced hierarchy by observing the variable takeover rates at different hierarchy levels and we compare the H-cGA to the cGA algorithm on a set of benchmark problems and show that the new approach performs promising.


Improving Graph Colouring Algorithms and Heuristics Using a Novel Representation
Istv\'an Juhos, Jano van Hemert

We introduce a novel representation for the graph colouring problem, called the Integer Merge Model, which aims to reduce the time complexity of an algorithm. Moreover, our model provides useful information for guiding heuristics as well as a compact description for algorithms. To verify the potential of the model, we use it in DSATUR, in an evolutionary algorithm, and in the same evolutionary algorithm extended with heuristics. An empiricial investigation is performed to show an increase in efficiency on two problem suites , a set of practical problem instances and a set of hard problem instances from the phase transition.


Minimizing makespan on a single batch processing machine with nonidentical job sizes: a hybrid genetic approach
Ali Husseinzadeh Kashan, Behrooz Karimi, Fariborz Jolai

This paper addresses minimizing makespan by genetic algorithm (GA) for scheduling jobs with non-identical sizes on a single batch processing machine. We propose two different genetic algorithms based on different encoding schemes. The first one is a sequence based GA (SGA) that generates random sequences of jobs and applies the batch first fit (BFF) heuristic to group the jobs. The second one is a batch based hybrid GA (BHGA) that generates random batches of jobs and ensures feasibility through using knowledge of the problem. A pairwise swapping heuristic based on the problem characteristics is hybridized with BHGA that has the ability of steering efficiently the search toward the optimal or near optimal schedules. Computational results show that BHGA performs considerably well compared with a modified lower bound and significantly outperforms the SGA and a simulated annealing (SA) approach addressed in literature. In comparison with a constructive heuristic named FFLPT, BHGA also shows its superiority.


A Relation-Algebraic View on Evolutionary Algorithms for Some Graph Problems
Britta Kehden, Frank Neumann
(Nominated for Best Paper Award)

We take a relation-algebraic view on the formulation of evolutionary algorithms in discrete search spaces. First, we show how individuals and populations can be represented as relations and formulate some standard mutation and crossover operators for this representation using relation-algebra. Evaluating a population with respect to their constraints seems to be the most costly step in one generation for many important problems. We show that the evaluation process for a given population can be sped up by using relation-algebraic expressions in the process. This is done by examining the evaluation of possible solutions for three of the best-known NP-hard combinatorial optimization problems on graphs, namely the vertex cover problem, the computation of maximum cliques, and the determination of a maximum independent set. Extending the evaluation process for a given population to the evaluation of the whole search space we get exact methods for the considered problems, which allow to evaluate the quality of solutions obtained by evolutionary algorithms.


New Computational Results for the Nurse Scheduling Problem: a Scatter Search Algorithm
Broos Maenhout, Mario Vanhoucke

In this paper, we present a scatter search algorithm for the well-known nurse scheduling problem (NSP). This problem aims at the construction of roster schedules for nurses taking both hard and soft constraints into account. The objective is to minimize the total preference cost of the nurses and the total penalty cost from violations of the soft constraints. The problem is known to be NP-hard. The contribution of this paper is threefold. First, we are, to the best of our knowledge, the first to present a scatter search algorithm for the NSP. Second, we investigate two different types of solution combination methods in the scatter search framework, based on four different cost elements. Last, we present detailed computational experiments on a benchmark dataset presented recently, and solve these problem instances under different assumptions. We show that our procedure performs consistently well under many different circumstances, and hence, can be considered as robust against case-specific constraints.


Fast EAX Algorithm Considering Population Diversity for Traveling Salesman Problems
Yuichi Nagata

This paper proposes an evolutionary algorithm (EA) that is applied to the traveling salesman problem (TSP). Existing approximation methods to address the TSP known to be state-of-the-art heuristics almost exclusively utilize Lin-Kernighan local search (LKLS) and its variants. We propose an EA that does not use LKLS, and demonstrate that it is comparable with these heuristics even though it does not use them. The proposed EA uses edge assembly crossover (EAX) that is known to be an efficient and effective crossover for solving TSPs. We first propose a modified EAX algorithm that can be executed more efficiently than the original, which is 2--7 times faster. We then propose a selection model that can efficiently maintain population diversity at negligible computational cost. The edge entropy measure is used as an indicator of population diversity. The proposed method called EAX-1AB(ENT) is applied to TSP benchmarks up to instances of 13509 cities. Experimental results reveal that EAX-1AB(ENT) with a population of 200 can almost always find optimal solutions effectively in most TSP benchmarks up to instances of 5915 cities. In the experiments, a previously proposed EAs using EAX can find an optimal solution of usa13509 with reasonable computational cost due to the fast EAX algorithm proposed in this paper. We also demonstrate that EAX-1AB(ENT) is comparable to well-known LKLS methods when relatively small populations such as 30 are used.


A Memetic Algorithm with Population Management (MA|PM) for the Capacitated Location-Routing Problem
Christian Prins, Caroline Prodhon, Roberto Wolfler~Calvo

As shown in recent researches, in a distribution system, ignoring routes when locating depots may overestimate the overall system cost. The Location Routing Problem (LRP) overcomes this drawback dealing simultaneously with location and routing decisions. This paper presents a memetic algorithm with population management (MA|PM) to solve the LRP with capacitated routes and depots. MA|PM is a very recent form of memetic algorithm in which the diversity of a small population of solutions is controlled by accepting a new solution if its distance to the population exceeds a given threshold. The method is evaluated on three sets of instances, and compared to other heuristics and a lower bound. The preliminary results are quite promising since the MA|PM already finds the best results on several instances.


The Core Concept for the Multidimensional Knapsack Problem
Jakob Puchinger, G\"unther R. Raidl, Ulrich Pferschy

We present the newly developed core concept for the Multidimensional Knapsack Problem (MKP) which is an extension of the classical concept for the one-dimensional case. The core for the multidimensional problem is defined in dependence of a chosen efficiency function of the items, since no single obvious efficiency measure is available for MKP. An empirical study on the cores of widely-used benchmark instances is presented, as well as experiments with different approximate core sizes. Furthermore we describe a memetic algorithm and a relaxation guided variable neighborhood search for the MKP, which are applied to the original and to the core problems. The experimental results show that given a fixed run-time, the different metaheuristics as well as a general purpose integer linear programming solver yield better solution when applied to approximate core problems of fixed size.


Multiobjective Scheduling of Jobs with Incompatible Families on Parallel Batch Machines
Dirk Reichelt, Lars M\"onch

We consider scheduling heuristics for batching machines from semiconductor manufacturing. A batch is a collection of jobs that are processed at the same time on the same machine. The processing time of a batch is given by the identical processing time of the jobs within one incompatible family. We are interested in minimizing total weighted tardiness and makespan at the same time. In order to solve this problem, i.e. generate a Pareto-front, we suggest a multiobjective genetic algorithm. We present results from computational experiments on stochastically generated test instances that show the good solution quality of the suggested approach.


A Memetic Algorithm for the Biobjective Minimum Spanning Tree Problem
Daniel A. M. Rocha, Elizabeth Gouv\^{e}a, Marco C\'esar Goldbarg
(Nominated for Best Paper Award)

Combinatorial optimization problems with multiple objectives are, in general, more realistic representations of practical situations than their counterparts with a single-objective. The bi-objective minimum spanning tree problem is a NP-hard problem with applications in network design. In this paper a memetic algorithm is presented to solve this problem. A computational experiment compares the proposed approach with AESSEA, a known algorithm of the literature. The comparison of the algorithms is done with basis on the binary additive ?-indicator. The results show that the proposed algorithm consistently produces better solutions than the other method.


A Comparative Study of Ant Colony Optimization and Reactive Search for Graph Matching Problems
Olfa Sammoud, S\'ebastien Sorlin, Christine Solnon, Khaled Gh\'edira

Many applications involve matching two graphs in order to identify their common features and compute their similarity. In this paper, we address the problem of computing a graph similarity measure based on a multivalent graph matching and which is generic in the sense that other well known graph similarity measures can be viewed as special cases of it. We propose and compare two different kinds of algorithms: an Ant Colony Optimization based algorithm and a Reactive Search. We compare the efficiency of these two algorithms on two different kinds of difficult graph matching problems and we show that they obtain complementary results.


Divide-and-Evolve: a New Memetic Scheme for Domain-Independent Temporal Planning
Marc Schoenauer, Pierre Sav\'eant, Vincent Vidal

An original approach, termed \DAE is proposed to hybridize Evolutionary Algorithms (EAs) with Operational Research (OR) methods in the domain of Temporal Planning Problems (TPPs). Whereas standard Memetic Algorithms use local search methods to improve the evolutionary solutions, and thus fail when the local method stops working on the complete problem, the \DAE approach splits the problem at hand into several, hopefully easier, sub-problems, and can thus solve globally problems that are intractable when directly fed into deterministic OR algorithms. But the most prominent advantage of the \DAE approach is that it immediately opens up an avenue for multi-objective optimization, even though the OR method that is used is single-objective. Proof of concept approach on the standard (single-objective) Zeno transportation benchmark is given, and a small original multi-objective benchmark is proposed in the same Zeno framework to assess the multi-objective capabilities of the proposed methodology, a breakthrough in Temporal Planning.


A Variable Neighbourhood Search Algorithm for Job Shop Scheduling Problems
Mehmet Sevkli, M. Emin Aydin

Variable Neighbourhood Search (VNS) is one of the most recent metaheuristics used for solving combinatorial optimization problems in which a systematic change of neighbourhood within a local search is carried out. In this paper, a variable neighbourhood search algorithm is proposed for Job Shop Scheduling (JSS) problem with makespan criterion. The results gained by VNS algorithm are presented and compared with the best known results in literature. It is concluded that the VNS implementation is better than many recently published works with respect to the quality of the solution.


An efficient hybrid search algorithm for various optimization problems
Mario Vanhoucke

This paper describes a detailed study of a recursive search algorithm for different optimization problems. Although the algorithm has been originally developed for a project scheduling problem with financial objectives, we show that it can be extended to many other application areas and therefore, can serve as a sub-procedure for various optimization problems. The contribution of the paper is threefold. First, we present a hybrid recursive search procedure for the project scheduling problem with net present value maximization and compare it with state-of-the-art procedures by means of computational tests. Second, we show how the procedure can be adapted to two other application areas: project scheduling with work continuity minimization and the open pit mining problem. Last, we highlight some future research areas where this hybrid procedure might bring a promising contribution.


A Hybrid VNS/Tabu Search Algorithm for Apportioning the European Parliament
Gabriel Villa, Sebasti\'an Lozano, Jes\'us Racero, David Canca

In a Proportional Representation (PR) electoral system it is assumed that seats are apportioned to the different electoral districts/states according to the corresponding voters distribution. In a previous paper we proposed a MILP (Mixed Integer Linear Programming) model to apportion the seats in the Euro- pean Parliament (EP). Since the exact solution to the problem is not computa- tionally efficient, we have designed a hybrid metaheuristic algorithm based on Variable Neighborhood Search (VNS) and Tabu Search (TS). The proposed approach takes into account the existing situation, guaranteeing a minimum number of seats, independently of the population size of each member. The model is illustrated with actual data and its results are compared with the pre- sent apportionment. The results show that the proposed approach can signifi- cantly improve the proportionality of the present apportionment.