The EvoCOP series started in 2001 and has been annually since then, being the first event specifically dedicated to the application of evolutionary computation and related methods to combinatorial optimization problems. The events have given 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 the EvoCOP series is documented by a steadily growing number of submissions from all continents and a strong reviewing process. Each accepted paper will be presented orally at the conference and published by Springer as part of the Lecture Notes in Computer Science series. Previous EvoCOP papers are availbable in LNCS Volumes 2037, 2279 and 2611.

LNCS 3004, the proceedings for EvoCOP2004, is now available online

EvoCOP PROGRAMME DETAILS

CONFERENCE PAPERS:

Mutation Multiplicity in a Panmictic Two-Strategy Genetic Algorithm
Adnan Acan

Abstract:
Fitness based selection procedures leave majority of population individuals idle, that is, they don't take place in any recombination operation although some of them have above average fitness values. Based on this observation, a two-phase two-strategy genetic algorithm using a conventional strategy with multiple mutation operators in the first phase is proposed. In the second phase, those individuals that are not sufficiently recombined in the first phase are reconsidered within a second strategy and recombined using multiple mutation operators only. In the second strategy, mutation operator probabilities are adaptively determined based on the cumulative fitness-gain achieved by each mutation operator over a number of generations. The proposed genetic algorithm paradigm is used for the solution of hard numerical and combinatorial optimization problems. The results demonstrate that the proposed approach performs much better than the conventional implementations in terms of solution quality and the convergence speed.

Solving the Vehicle Routing Problem by Using Cellular Genetic Algorithms
Enrique Alba, Bernabé Dorronsoro

Abstract:
Cellular Genetic Algorithms (cGAs) are a subclass of Genetic Algorithms (GAs) in which the populationdiversity and exploration are enhanced thanks to the existence of small overlapped neighborhoods. Such a kind of structured algorithms is specially well suited for complex problems. In this paper we propose the utilization of some cGAs with and without including local search techniques for solving the vehicle routing problem (VRP). A study on the behavior of these algorithms has been performed in terms of the quality of the solutions found, execution time, and number of function evaluations (effort). We have selected the benchmark of Christofides, Mingozzi and Toth for testing the proposed cGAs, and compare them with some other heuristics in the literature. Our conclusions are that cGAs with an added local search operator are able of always locating the optimum of the problem at low times and reasonable effort for thetested instances.

Landscape Regularity and Random Walks for the Job-Shop Scheduling Problem
Christian Bierwirth, Dirk Christian Mattfeld, Jean-Paul Watson

Abstract:
We perform a novel analysis of the fitness landscape of the job-shop scheduling problem (JSP). In contrast to other well-known combinatorial optimization problems, we show that the landscape of the JSP is non-regular, in that the connectivity of solutions is variable. As a consequence, we argue that random walks performed on such a landscape will be biased. We conjecture that such a bias should affect both random walks and local search algorithms, and may provide a partial explanation for the remarkable success of the latter in solving the JSP.

A Comparison of Adaptive Operator Scheduling Methods on the Traveling Salesman Problem
Wouter Boomsma

Abstract:
The implementation of an evolutionary algorithm necessarily involves the selection of an appropriate set of genetic operators. For many real-world problem domains, an increasing number of such operators is available. The usefulness of these operators varies for different problem instances and can change during the course of the evolutionary process. This motivates the use of adaptive operator scheduling (AOS) to automate the selection of efficient operators. However, little research has been done on the question of which scheduling method to use. This paper compares different operator scheduling methods on the Traveling Salesman Problem. Several new AOS techniques are introduced and comparisons are made to two non-adaptive alternatives. The results show that most of the introduced algorithms perform as well as Davis' algorithm while being significantly less cumbersome to implement. Overall, the use of AOS is shown to give significant performance improvements - both in quality of result and convergence time

Ant Packing - An Ant Colony Optimization Approach for the One-dimensional Bin Packing Problem
Boris Brugger, Karl F. Doerner, Richard F. Hartl, Marc Reimann

Abstract:
This paper deals with the one-dimensional bin packing problem and presents a metaheuristic solution approach based on Ant Colony Optimization. Some novel algorithm design features are proposed and the comprehensive computational study performed, shows both the contribution of using these features as well as the overall quality of the approach as compared to state of the art competing metaheuristics.

Scatter Search and Memetic Approaches to the Error Correcting Code Problem
Carlos Cotta

Abstract:
We consider the problem of designing error correcting codes (ECC), a hard combinatorial optimization problem of relevance in the field of telecommunications. This problem is tackled here with two related techniques, scatter search and memetic algorithms. The instantiation of these techniques for ECC design will be discussed. Specifically, the design of the local improvement strategy and the combination method will be treated. The empirical evaluation will show that these techniques can dramatically outperform previous approaches to this problem. Among other aspects, the influence of the update method, or the use of path relinking is also analyzed on increasingly large problem instances.

A Hybrid Evolutionary Algorithm for Solving the Register Allocation Problem
Betul Demiroz, Haluk Topcuoglu, Mahmut Kandemir

Abstract:
One of the strong impacts on runtime performance of a given code is the register allocation phase of compilation. It is crucial to provide aggressive and sophisticated register allocators for the embedded devices, where the excessive compilation time is tolerated because of its off-line nature. In this paper, we present a hybrid evolutionary algorithm for register allocation problem that combines genetic algorithms with a local search technique. Our algorithm exploits a novel, highly-specialized crossover operator that considers domain-specific information. Computational experiments performed on various synthetic benchmarks prove that our method significantly outperform the state-of-the-art algorithms with respect to all given comparison metrics on solution quality.

Parallel Ant Systems for the Capacitated Vehicle Routing Problem
Karl F. Doerner, Richard F. Hartl, Guenter Kiechle, Maria Lucka, Marc Reimann

Abstract:
In this paper we first provide a thorough performance comparison of the three main Ant Colony Optimization (ACO) paradigms for the Vehicle Routing Problem (VRP), namely the Rank based Ant System, the Max-Min Ant System and the Ant Colony System. Based on the results of this comparison we then implement a parallelization strategy to increase computational efficiency and study the effects of increasing the number of processors.

A Hierarchical Social Metaheuristic for the Max-Cut Problem
Abraham Duarte, Felipe Fernández, Angel Sánchez, Antonio Sanz

Abstract:
This paper introduces a new social metaheuristic for the Max-Cut problem applied to a weighted undirected graph. This problem consists in finding a partition of the nodes into two subsets, such that the sum of the weights of the edges having endpoints in different subsets is maximized. This NP-hard problem for non planar graphs has several application areas such as VLSI and ASICs CAD. The hierarchical social (HS) metaheuristic here proposed for solving the referred problem is tested and compared with other two metaheuristics: a greedy randomized adaptive search procedure (GRASP) and an hybrid memetic heuristic that combines a genetic algo-rithm (GA) and a local search. The computational results on a set of standard test problems show the suitability of the approach.

On the Structure of Sequential Search: Beyond "No Free Lunch"
Thomas English

Abstract:
Novel results are obtained by investigating the search algorithms predicated in "no free lunch" (NFL) theorems rather than NFL itself. Finite functions are represented as strings of values. The set of functions is partitioned into maximal blocks of functions that are permutations of one another. A search algorithm effectively maps each test function to a permutation of the function. This mapping is partitioned into one-to-one correspondences on blocks. A distribution on the functions is referred to as block uniform if each function has the same probability as all its permutations. For any search algorithm, the distributions of test functions and permuted test functions have identical Kullback-Leibler distance to the nearest block uniform distribution. That is, divergence from block uniformity is conserved by search. There is NFL in the special case of no divergence, i.e., the distributions are block uniform.

Dealing with Solution Diversity in an EA for Multiple Objective Decision Support - A Case Study
Alvaro Gomes, Carlos Henggeler Antunes, Antonio Gomes Martins

Abstract:
The characteristics of the search space (its size and shape as well as solution density) are key issues in the application of evolutionary algorithms to real-world problems. Often some regions are crowded and other regions are almost empty. Therefore, some techniques must be used to avoid solutions too close (which the decision maker is indifferent to) and to allow all the regions of interest to be adequately represented in the population. In this paper the concept of delta-non-dominance is introduced which is based on indifference thresholds. Experiments dealing with the use of this technique in the framework of an evolutionary approach are reported to provide decision support in the identification and selection of electric load control strategies

A Study into Ant Colony Optimisation, Evolutionary Computation and Constraint Programming on Binary Constraint Satisfaction Problems
Jano I. van Hemert, Christine Solnon

Abstract:
We compare two heuristic approaches, evolutionary computation and ant colony optimisation, and a complete tree-search approach, constraint programming, for solving binary constraint satisfaction problems. We experimentally show that, if evolutionary computation is far from being able to compete with the two other approaches, ant colony optimisation nearly always succeeds in finding a solution, so that it can actually compete with constraint programming. The resampling ratio is used to provide insight into heuristic algorithms performances. Regarding efficiency, we show that if constraint programming is the fastest when instances have a low number of variables, ant colony optimisation becomes faster when increasing the number of variables.

Binary Merge Model Representation of the Graph Colouring Problem
István Juhos, Attila Tóth, Jano I. van Hemert

Abstract:
This paper describes a novel representation and ordering model that, aided by an evolutionary algorithm, is used in solving the graph k-colouring problem. Its strength lies in reducing the number of neighbors that need to be checked for validity. An empirical comparison is made with two other algorithms on a popular selection of problem instances and on a suite of instances in the phase transition. The new representation in combination with a heuristic mutation operator shows promising results.

Hardness Prediction for the University Course Timetabling Problem
Philipp Kostuch, Krzysztof Socha

Abstract:
This paper presents an attempt to find a statistical model that predicts the hardness of the University Course Timetabling Problem by analyzing instance properties. The model may later be used for better understanding what makes a particular instance hard. It may also be used for tuning the algorithm actually solving that problem instance. The paper introduces the definition of hardness, explains the statistical approach used for modeling instance hardness, as well as presents results obtained and possible ways of exploiting them.

Hybrid Estimation of Distribution Algorithm for Multiobjective Knapsack Problem
Hui Li, Qingfu Zhang, Edward Tsang, John Ford

Abstract:
We propose a hybrid estimation of distribution algorithm (MOHEDA) for solving the multiobjective 0/1 knapsack problem (MOKP). Local search based on weighted sum method is proposed, and random repair method (RRM) is used to handle the constraints. Moreover, for the purpose of diversity preservation, a new and fast clustering method, called stochastic clustering method (SCM), is also introduced for mixture-based modelling. The experimental results indicate that MOHEDA outperforms several other state-of-the-art algorithms.

On the Use of Path Relinking for the p-Hub Median Problem
Melquiades Perez, Francisco Almeida Rodriguez, J. Marcos Moreno Vega

Abstract:
The p-hub median problem is an NP hard location allocation problem, which consists of finding p points to establish facilities and the as- signment of the users to these points. A new evolutionary approach that has been very effective for solving optimisation problems is Path Relinking, an ex- tension of Scatter Search that links solutions over neighborhood spaces. Path Relinking gives a framework for combining solutions that goes beyond the crossover mechanism of genetic algorithms, and introduces new fundamental principles, such as the use of systematic strategies instead of random strategies. In this paper, we present an application of Path Relinking to solve the p-hub median problem and compare its effectiveness with other classical techniques. This procedure provides high quality solutions in reasonable execution times and yields a significant improvement in the size of the problems that can be solved.

Solving a Real-World Glass Cutting Problem
Jakob Puchinger, Günther R. Raidl, Gabriele Koller

Abstract:
We consider the problem of finding two-dimensional cutting patterns for glass sheets in order to produce rectangular elements requested by customers. The number of needed sheets, and therefore the waste, is to be minimized. The cutting facility requires three-staged guillotineable cutting patterns, and in addition, a plan for loading produced elements on transportation wagons. The availability of only three loading docks for wagons imposes additional constraints on the feasibility of cutting patterns. We describe a greedy first fit heuristic, two branch-and-bound based heuristics, and different variants of an evolutionary algorithm for the problem, and compare them on a set of real-world instances. The evolutionary algorithm is based on an order representation, specific recombination and mutation operators, and a decoding heuristic. In one variant, branch-and-bound is occasionally applied to locally optimize parts of a solution during decoding.

Designing Reliable Communication Networks with a Genetic Algorithm Using a Repair Heuristic
Dirk Reichelt, Franz Rothlauf, Peter Gmilkowsky

Abstract:
This paper investigates GA approaches for solving the reliable communication network design problem. For solving this problem a network with minimum cost must be found that satisfies a given network reliability constraint. To consider the additional reliability constraint different approaches are possible. We show that existing approaches using penalty functions can result in invalid solutions and are therefore not appropriate for solving this problem. To overcome these problems we present a repair heuristic, which is based on the number of spanning trees in a network. This heuristic always generates a valid solution, which when compared to a greedy cheapest repair heuristic shows that the new approach finds better solutions with less computational effort.

Improving Vehicle Routing Using a Customer Waiting Time Colony
Samer Sa'adah, Peter Ross, Ben Paechter

Abstract:
In the vehicle routing problem with time windows (VRPTW), there are two main objectives. The primary objective is to reduce the number of vehicles, the secondary one is to minimise the total distance travelled by all vehicles. This paper describes some experiments with multiple ant colony systems, in particular a Triple Ant Colony System TACS, in which one colony (VMIN) tries to minimise the number of vehicles, one (DMIN) tries to minimise the total distance and a third (CWTsMAX) tries to maximise customer waiting time. The inclusion of this third colony improves the results very significantly, compared to not using it and to a range of other options. Experiments are conducted on Solomon's 56 benchmark problems. The results are comparable to those obtained by other state-of-the-art approaches.

New Benchmark Instances for the QAP and the Experimental Analysis of Algorithms
Thomas Stüutzle, Susana Fernandes

Abstract:
The quadratic assignment problem arises in a variety of practical settings. It is known to be among the hardest combinatorial problems for exact algorithms. Therefore, a large number of heuristic approaches have been proposed for its solution. In this article we introduce a new, large set of QAP instances that is intended to allow the systematic study of the performance of metaheuristics in dependence of QAP instance characteristics. Additionally, we give computational results with several high performing algorithms known from literature and give exemplary results on the influence of instance characteristics on the performance of these algorithms.

Improving Edge Recombination through Alternate Inheritance and Greedy Manner
Chuan-Kang Ting

Abstract:
Genetic Algorithms (GAs) are well-known heuristic algorithms and have been widely applied to solve combinatorial problems. Edge recombination is one of the famous crossovers designed for GAs to solve combinatorial prob- lems. The essence of edge recombination is to achieve maximal inheritance from parental edges. This paper presents two strategies to improve edge recom- bination. First, we encourage alternation of parents in edge inheritance. Second, a greedy method is used to handle the failures occurred in edge recombination. A modified edge recombination, called edge recombination with tabu (Edge-T), is proposed according to these two strategies. The traveling salesman problem is used as a benchmark to demonstrate the effectiveness of the proposed method. Experimental results indicate that Edge-T can achieve better perform- ance than the conventional edge recombination Edge-3 in terms of both solution quality and convergence speed.

Clustering Nominal and Numerical Data: A New Distance Concept for a Hybrid Genetic Algorithm
Laetitia Vermeulen-Jourdan, Clarisse Dhaenens, El-Ghazali Talbi

Abstract:
As intrinsic structures, like the number of clusters, is, for real data, a major issue of the clustering problem, we propose, in this paper, CHyGA (Clustering Hybrid Genetic Algorithm) an hybrid genetic algorithm for clustering. CHyGA treats the clustering problem as an optimization problem and searches for an optimal number of clusters characterized by an optimal distribution of instances into the clusters. CHyGA introduces a new representation of solutions and uses dedicated operators, such as one iteration of K-means as a mutation operator. In order to deal with nominal data, we propose a new definition of the cluster center concept and demonstrate its properties. Experimental results on classical benchmarks are given.

On Search Space Symmetry in Partitioning Problems
Benjamin Weinberg, El-Ghazali Talbi

Abstract:
Many problems consist in splitting a set of objects so that each part verifies some properties. In practice, a partitioning is often encoded by an array mapping each object to its group numbering. In fact, the group number of a object does not really matter, and one can simply rename each part to obtain a new encoding. That is what we call the symmetry of the search space in a partitioning problem. This property may be prejudicial for methods such as evolutionary algorithms (EA) which require some diversity during their executions. This article aims at providing a theoretical framework for breaking this symmetry. We define an equivalence relation on the encoding space. This leads us to define a non-trivial search space which eliminates symmetry. We define polynomially computable tools such as equality test, a neighborhood operator and a metric applied on the set of partitioning.

Co-chair: Jens Gottlieb, SAP AG <jens.gottlieb@sap.com>
Co-chair: Günther Raidl, Vienna University of Technology, <raidl@ads.tuwien.ac.at>
Local Chair: Ernesto Costa, University of Coimbra <ernesto@dei.uc.pt>
Jarmo Alander (Finland)
Hernan Aguirre (Japan)
Emin Aydin (UK)
Jean Berger (Canada)
Jürgen Branke (Germany)
Edmund Burke (UK)
David Corne (UK)
Ernesto Costa (Portugal)
Carlos Cotta (Spain)
Peter Cowling (UK)
Bart Craenen (NL)
David Davis (USA)
Marco Dorigo (Belgium)
Karl Dörner (Austria)
Anton Eremeev (Russia)
David Fogel (USA)
Bernd Freisleben (Germany)
Jens Gottlieb (Germany)
Michael Guntsch (Germany)
Jin-Kao Hao (France)
Emma Hart (UK)
Jano van Hemert (NL)
Jörg Homberger (Germany)
Li Hui (UK)
Mikkel Jensen (Denmark)
Bryant Julstrom (USA)
Graham Kendall (UK)
Dimitri Knjazew (Germany)
Joshua Knowles (UK)
Gabriele Koller (Austria)
Mario Köppen (Germany)
Jozef Kratica (Yugoslavia)
Ivana Ljubic (Austria)
Elena Marchiori (NL)
Dirk Mattfeld (Germany)
Helmut Mayer (Austria)
Daniel Merkle (Germany)
Peter Merz (Germany)
Martin Middendorf (Germany)
Christine Mumford (UK)
Francisco Pereira (Portugal)
Adam Prügel-Bennett (UK)
Jakob Puchinger (Austria)
Günther Raidl (Austria)
Marcus Randall (Australia)
Colin Reeves (UK)
Marc Reimann (Austria)
Claudio Rossi (Spain)
Franz Rothlauf (Germany)
Andreas Sandner (Germany)
Marc Schoenauer (France)
Christine Solnon (France)
Giovanni Squillero (Italy)
Thomas Stützle (Germany)
El-ghazali Talbi (France)
Ingo Wegener (Germany)
Darrell Whitley (USA)
Yong Xu (UK)
Takeshi Yamada (Japan)

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 scheduling, timetabling, network design, transportation and distribution problems, vehicle routing, traveling salesperson, other 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. The 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. The success of the EvoCOP series is documented by a steadily growing number of submissions from all continents and a strong reviewing process (the last EvoCOP's acceptance ratio was 48.7%). Accepted papers were published by Springer in the series Lecture Notes in Computer Science (LNCS Volumes 2037, 2279 and 2611).

EvoCOP 2004 wants to bring researchers in the field together once again. Each accepted paper will be presented orally at the conference and printed in own proceedings published by Springer in the LNCS series.

Topics of interest include, but are not limited to:

• Applications of evolutionary algorithms and related meta-heuristics like simulated annealing, tabu search, memetic algorithms, or ant systems to combinatorial optimization problems;
• representation techniques;
• evolutionary operators;
• constraint-handling techniques;
• hybrid methods and hybridization techniques;
• parallelisation;
• theoretical developments;
• search space analyses;
• comparisons between different (also non-evolutionary) techniques.

Send your manuscript (PDF or postscript, max. 10 A4 pages) by email to evocop2004@ads.tuwien.ac.at no later than 21 November (extended deadline) 2003. Please see http://www.springer.de/comp/lncs/authors.html for the formatting instructions. IMPORTANT: The reviewing process will be double-blind, so please omit information about the authors in the submitted paper. The submissions will be peer reviewed by at least three members of the program committee. Authors will be notified on the results of the review by 19 December 2003.

The authors of accepted papers will have to improve their paper on the basis of the reviewers' comments and will be asked to send a camera ready version of their manuscripts by 16 January 2004.

The EvoCOP2004 proceedings will be
published by Spinger as part of their
Lecture Notes in Computer Science series.