## EvoCOP2005

### 5th European Conference on Evolutionary Computation in Combinatorial Optimization

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 26.7%). Accepted papers were published by Springer in the series Lecture Notes in Computer Science (LNCS Volumes 2037, 2279, 2611, and 3004).

EvoCOP 2005 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 include

• Applications of evolutionary algorithms and related meta-heuristics like simulated annealing, tabu search, memetic algorithms, or ant colony optimization to combinatorial optimization problems
• Representation techniques
• Evolutionary operators
• Constraint-handling techniques
• Hybrid methods and hybridization techniques
• Parallelization
• Theoretical developments
• Search space analyses
• Comparisons between different (also non-evolutionary) techniques

#### 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
Marco Tomassini
Marco.Tomassini AT hec DOT unil DOT ch
University of Lausanne, Switzerland

Publicity Chair
Jano van Hemert
jvhemert AT cwi DOT nl
Napier University, Edinburgh, Scotland, UK

#### Programme Committee

Hernan Aguirre
Enrique Alba
Emin Aydin
Jean Berger
Christian Bierwirth
Christian Blum
Edmund Burke
Ernesto Costa
Carlos Cotta
Peter Cowling
Bart Craenen
David Davis
Karl Doerner
Marco Dorigo
Anton V. Eremeev
David B. Fogel
Bernd Freisleben
Michael Guntsch
Walter Gutjahr
Jin-Kao Hao
Emma Hart
William E. Hart
Jano van Hemert
Jörg Homberger
Mikkel Thomas Jensen
Bryant Arthur Julstrom
Graham Kendall
Joshua Damian Knowles
Gabriele Koller
Mario Köppen
Jozef Kratica
Ivana Ljubic
Elena Marchiori
Dirk C. Mattfeld
Helmut Mayer
Daniel Merkle
Peter Merz
Zbigniew Michalewicz
Martin Middendorf
Pablo Moscato
Christine L. Mumford
Francisco J. B. Pereira
Jakob Puchinger
Marcus Randall
Colin Reeves
Marc Reimann
Franz Rothlauf
Andreas Sandner
Marc Schoenauer
Christine Solnon
Eric Soubeiga
Thomas Stützle
El-ghazali Talbi
Edward P. Tsang
Ingo Wegener
Xin Yao

### EvoCOP Programme

#### Wednesday, 30 March 2005

##### Session 1: Problems on Graphs I (1120-1250)
Chair: Guenther Raidl

Heuristic Colour Assignment Strategies for Merge Models in Graph Colouring
István Juhos
Attila Tóth
Jano I. van Hemert

EvoGeneS, a New Evolutionary Approach to Graph Generation
Luigi Pietro Cordella
Claudio De Stefano
Francesco Fontanella
Angelo Marcelli

Analyzing Fitness Landscapes for the Optimal Golomb Ruler Problem
Carlos Cotta
Antonio J. Fernández
(Best Paper Award Candidate)

##### Session 2: Permutation Problems (1415-1545)
Chair: Daniel Merkle

Property Analysis of Symmetric Travelling Salesman Problem Instances Acquired Through Evolution
Jano I. van Hemert
(Best Paper Award Candidate)

Scatter Search Particle Filter to Solve the Dynamic Travelling Salesman Problem
Juan José Pantrigo
Abraham Duarte
Ángel Sánchez
Raúl Cabido

Population Training Heuristics
Alexandre C. M. Oliveira
Luiz A. N. Lorena

##### Session 3: Constrained Problems (1600-1730)
Chair: Jano van Hemert

Application of the Grouping Genetic Algorithm to University Course Timetabling
Rhydian Lewis
Ben Paechter

An Agent Model for Binary Constraint Satisfaction Problems
Weicai Zhong
Jing Liu
Licheng Jiao

Choosing the Fittest Subset of Low Level Heuristics in a Hyperheuristic Framework
Konstantin Chakhlevitch
Peter Cowling

#### Thursday, 31 March 2005

##### Session 4: Problems on Graphs II (0930-1100)
Chair: Christine Solnon

On the Application of Evolutionary Algorithms to the Consensus Tree Problem
Carlos Cotta
(Best Paper Award Candidate)

An Adaptive Genetic Algorithm for the Minimal Switching Graph Problem
Maolin Tang

Making the Edge-Set Encoding Fly by Controlling the Bias of its Crossover Operator
Franz Rothlauf
Carsten Tzschoppe

##### Session 5: Assignment and Packing Problems (1120-1250)
Chair: Jens Gottlieb

Multiobjective Quadratic Assignment Problem Solved by an Explicit Building Block Search Algorithm -- MOMGA-IIa
Richard Day
Gary Lamont

An Attribute Grammar Decoder for the 0-1 MultiConstrained Knapsack Problem
Robert Cleary
Michael O'Neill

Self-Adapting Evolutionary Parameters: Encoding Aspects for Combinatorial Optimization Problems
Marcos H. Maruo
Heitor S. Lopes

##### Session 6: Specific Applications (1415-1545)
Chair: Elena Marchiori

Immune Algorithms with Aging Operators for the String Folding Problem and the Protein Folding Problem
Vincenzo Cutello
Giuseppe Morelli
Giuseppe Nicosia
Mario Pavone

A Novel Application of Evolutionary Computing in Process Systems Engineering
Jessica Andrea Carballido
Ignacio Ponzoni
Nelida Beatriz Brignole

An Improved Simulated Annealing Method for the Combinatorial Sub-Problem of the Profit-Based Unit Commitment Problem
T. Aruldoss Albert Victoire
A. Ebenezer

##### Session 7: Lot sizing and scheduling (1600-1730)
Chair: Carlos Cotta

The Use of Meta-Heuristics To Solve Economic Lot Scheduling Problem
Syed Asif Raza
Ali Akgunduz

Lot-Sizing in a Foundry Using Genetic Algorithm and Repair Functions
Jerzy Duda

A New Hybrid GA/SA Algorithm for the Job Shop Scheduling Problem
Chaoyong Zhang
Peigen Li
Yunqing Rao
Shuxia Li

#### Friday, 1 April 2005

##### Session 8: Estimation of Distribution Algorithms (0930-1100)

Chair: Franz Rothlauf

An External Partial Permutations Memory for Ant Colony Optimization
(Best Paper Award Candidate)

Estimation of Distribution Algorithms with Mutation
Hisashi Handa

Ant Algorithm for the Graph Matching Problem
Olfa Sammoud
Christine Solnon
Khaled Ghédira

### EvoCOP: Titles and abstracts accepted papers

#### An External Partial Permutations Memory for Ant Colony Optimization

(Best Paper Award Candidate)

A novel external memory implementation based on the use of partially complete sequences of solution components from above-average quality individuals over a number of previous iterations is introduced. Elements of such variable-size partial permutation sequences are taken from randomly selected positions of parental individuals and stored in an external memory called the partial permutation memory. Partial permutation sequences are associated with lifetimes together with their parent solutions' fitness values that are used in retrieving and updating the contents of the memory. When a solution is to be constructed, a partial permutation sequence is retrieved from the memory based on its age and associated fitness value, and the remaining components of the partial solution is completed with an ant colony optimization algorithm. Resulting solutions are also used to update some elements within the memory. The implemented algorithm is used for the solution of a difficult combinatorial optimization problem, namely the quadratic assignment problem, for which significant performance achievements are provided in terms of convergence speed and solution quality.

Jessica Andrea Carballido
Ignacio Ponzoni
Nelida Beatriz Brignole

#### A Novel Application of Evolutionary Computing in Process Systems Engineering

In this article we present a Multi-Objective Genetic Algorithm for Initialization (MOGAI) that finds a starting sensor configuration for Observability Analysis (OA), this study being a crucial stage in the design and revamp of process-plant instrumentation. The MOGAI is a binary-coded genetic algorithm with a three-objective fitness function based on cost, reliability and observability metrics. MOGAI?s special features are: dynamic adaptive bit-flip mutation and guided generation of the initial population, both giving a special treatment to non-feasible individuals, and an adaptive genotypic convergence criterion to stop the algorithm. The algorithmic behavior was evaluated through the analysis of the mathematical model that represents an ammonia synthesis plant. Its efficacy was assessed by comparing the performance of the OA algorithm with and without MOGAI initialization. The genetic algorithm proved to be advantageous because it led to a significant reduction in the number of itera-tions required by the OA algorithm.

Konstantin Chakhlevitch
Peter Cowling

#### Choosing the Fittest Subset of Low Level Heuristics in a Hyperheuristic Framework

A hyperheuristic is a high level procedure which searches over a space of low level heuristics rather than directly over the space of problem solutions. The sequence of low level heuristics, applied in an order which is intelligently determined by the hyperheuristic, form a solution method for the problem. In this paper, we consider a hyperheuristic-based methodology where a large set of low level heuristics is constructed by combining simple selection rules. Given sufficient time, this approach is able to achieve high quality results for a real-world personnel scheduling problem. However, some low level heuristics in the set do not make valuable contributions to the search and only slow down the solution process. We introduce learning strategies into hyperheuristics in order to select a fit subset of low level heuristics tailored to a particular problem instance. We compare a range of selection approaches applied to a varied collection of real-world personnel scheduling problem instances.

Robert Cleary
Michael O'Neill

#### An Attribute Grammar Decoder for the 01 MultiConstrained Knapsack Problem

We describe how the standard genotype-phenotype mapping process of Grammatical Evolution (GE) can be enhanced with an attribute grammar to allow GE to operate as a decoder-based Evolutionary Algorithm (EA). Use of an attribute grammar allows GE to maintain context-sensitive and semantic information pertinent to the capacity constraints of the 01 Multiconstrained Knapsack Problem (MKP). An attribute grammar specification is used to perform decoding similar to a first-fit heuristic. The results presented are encouraging, demonstrating that GE in conjunction with attribute grammars can provide an improvement over the standard context-free mapping process for problems in this domain.

Luigi Pietro Cordella
Claudio De Stefano
Francesco Fontanella
Angelo Marcelli

#### EvoGeneS, a New Evolutionary Approach to Graph Generation

Graphs are powerful and versatile data structures, useful to represent complex and structured information of interest in various fields of science and engineering. We present a system, called EvoGeneS, based on an evolutionary approach, for generating undirected graphs whose number of nodes is not a priori known. The method is based on a special data structure, called multilist, which encodes undirected attributed relational graphs. Two novel crossover and mutation operators are defined in order to evolve such structure. The developed system has been tested on a wireless network configuration and the results compared with those obtained by a genetic programming based approach recently proposed in the literature.

Carlos Cotta
Antonio J. Fernández

#### Analyzing Fitness Landscapes for the Optimal Golomb Ruler Problem

(Best Paper Award Candidate)

We focus on the Golomb ruler problem, a hard constrained combinatorial optimization problem. Two alternative encodings are considered, one based on the direct representation of solutions, and one based on the use of an auxiliary decoder. The properties of the corresponding fitness landscapes are analyzed. It turns out that the landscape for the direct encoding is highly irregular, causing drift to low-fitness regions. On the contrary, the landscape for the indirect representation is regular, and exhibits comparable fitness-distance correlation to that of the former landscape. These findings are validated in the context of variable neighborhood search.

Carlos Cotta

#### On the Application of Evolutionary Algorithms to the Consensus Tree Problem

(Best Paper Award Candidate)

Computing consensus trees amounts to finding a single tree that summarizes a collection of trees. Three evolutionary algorithms are defined for this problem, featuring characteristics of genetic programming (GP), evolution strategies (ES) and evolutionary programming (EP) respectively. These algorithms are evaluated on a benchmark composed of phylogenetic trees computed from genomic data. The GP-like algorithm is shown to provide better results than the other evolutionary algorithms, and than two greedy heuristics defined ad hoc for this problem.

Vincenzo Cutello
Giuseppe Morelli
Giuseppe Nicosia
Mario Pavone

#### Immune Algorithms with Aging Operators for the String Folding Problem and the Protein Folding Problem

We present an Immune Algorithm (IA) based on clonal selection principle and which uses memory B cells, to face the protein structure prediction problem (PSP) a particular example of the String Folding Problem in 2D and 3D lattice. Memory B cells with a longer life span are used to partition the funnel landscape of PSP, so to properly explore the search space. The designed IA shows its ability to tackle standard benchmarks instances substantially better than other IA's. In particular, for the 3D HP model the IA allowed us to find energy minima not found by other evolutionary algorithms described in literature.

Richard Day
Gary Lamont

#### Multiobjective Quadratic Assignment Problem Solved by an Explicit Building Block Search Algorithm -- MOMGA-IIa

The multi-objective quadratic assignment problem (mQAP) is an non-deterministic polynomial-time complete (NPC) problem with many real-world applications. The application addressed in this paper is the minimization of communication flows in a heterogenous mix of Organic Air Vehicles (OAV). A multi-objective approach to solving the general mQAP for this OAV application is developed. The combinatoric nature of this problem calls for a stochastic search algorithm; moreover, two linkage learning algorithms, the multi-objective fast messy genetic algorithm (MOMGA-II) and MOMGA-IIa, are compared. Twenty-three different problem instances having three different sizes (10, 20, and 30) plus two and three objectives are solved. Results indicate that the MOMGA-IIa resolves all pareto optimal points for problem instances <20.

Jerzy Duda

#### Lot-Sizing in a Foundry Using Genetic Algorithm and Repair Functions

The paper presents a study of genetic algorithms applied to a lot-sizing problem, which has been formulated for an operational production planning in a foundry. Three variants of genetic algorithm are considered, each of them using special crossover and mutation operators as well as repair functions. The real size test problems, based on the data taken from the production control system, are presented for assessment of the proposed algorithms. The obtained results show that the genetic algorithm with two repair functions can generate good suboptimal solutions in the time, which can be acceptable from the deci-sion maker point of view.

Hisashi Handa

#### Estimation of Distribution Algorithms with Mutation

The Estimation of Distribution Algorithms are a class of evolutionary algorithms which adopt probabilistic models to reproduce the genetic information of the next generation, instead of conventional crossover and mutation operations. In this paper, we propose new EDAs which incorporate mutation operator to conventional EDAs in order to keep the diversities in EDA populations. Empirical experiments carried out this paper confirm us the effectiveness of the proposed methods.

Jano I. van Hemert

#### Property Analysis of Symmetric Travelling Salesman Problem Instances Acquired Through Evolution

(Best Paper Award Candidate)

We show how an evolutionary algorithm can successfully be used to evolve a set of difficult to solve symmetric travelling salesman problem instances for two variants of the Lin-Kernighan algorithm. Then we analyse the instances in those sets to guide us towards deferring general knowledge about the efficiency of the two variants in relation to structural properties of the symmetric travelling salesman problem.

István Juhos
Attila Tóth
Jano I. van Hemert

#### Heuristic Colour Assignment Strategies for Merge Models in Graph Colouring

In this paper, we combine a powerful representation for graph colouring problems with different heuristic strategies for colour assignment. Our novel strategies employ heuristics that exploit information about the partial colouring in an aim to improve performance. An evolutionary algorithm is used to drive the search. We compare the different strategies to each other on several very hard benchmarks and on generated problem instances, and show where the novel strategies improve the efficiency.

Rhydian Lewis
Ben Paechter

#### Application of the Grouping Genetic Algorithm to University Course Timetabling

University Course Timetabling-Problems (UCTPs) involve the allocation of resources (such as rooms and timeslots) to all the events of a university, satisfying a set of hard-constraints and, as much as possible, some soft constraints. Here we work with a well-known version of the problem where there seems a strong case for considering these two goals as separate sub-problems. In particular we note that the satisfaction of hard constraints fits the standard definition of a grouping problem. As a result, a grouping genetic algorithm for finding feasible timetables for hard problem instances has been developed, with promising results.

Marcos H. Maruo
Heitor S. Lopes

#### Self-Adapting Evolutionary Parameters: Encoding Aspects for Combinatorial Optimization Problems

Evolutionary algorithms are powerful tools in search and optimization tasks with several applications in complex engineering problems. However, setting all associated parameters is not an easy task and the adaptation seems to be an interesting alternative. This paper aims to analyze the effect of self-adaptation of some evolutionary parameters of genetic algorithms (GAs). Here we intend to propose a flexible GA-based algorithm where only few parameters have to be defined by the user. Benchmark problems of combinatorial optimization were used to test the performance of the proposed approach.

Alexandre C. M. Oliveira
Luiz A. N. Lorena

#### Population Training Heuristics

This work describes a new way of employing problem-specific heuristics to improve evolutionary algorithms: the Population Training Heuristic (PTH). The PTH employs heuristics in fitness definition, guiding the population to settle down in search areas where the individuals can not be improved by such heuristics. Some new theoretical improvements not present in early algorithms are now introduced. An application for pattern sequencing problems is examined with new improved computational results. The method is also compared against other approaches, using benchmark instances taken from the literature.

Juan José Pantrigo
Abraham Duarte
Ángel Sánchez
Raúl Cabido

#### Scatter Search Particle Filter to Solve the Dynamic Travelling Salesman Problem

This paper presents the Scatter Search Particle Filter (SSPF) algorithm and its application to the Dynamic Travelling Salesman Problem (DTSP). SSPF combines sequential estimation and combinatorial optimization methods to improve the execution time in dynamic optimization problems. It allows obtaining new high quality solutions in subsequent iterations using solutions found in previous time steps. The hybrid SSPF approach increases the performance of general Scatter Search (SS) metaheuristic in dynamic optimization problems. We have applied the SSPF algorithm to different DTSP instances. Experimental results have shown that SSPF performance is significantly better than classical DTSP approaches, where new solutions of derived problems are obtained without taking advantage of previous solutions corresponding to similar problems. Our proposal reduces execution time appreciably without affecting the quality of the estimated solution.

Syed Asif Raza
Ali Akgunduz

#### The Use of Meta-Heuristics To Solve Economic Lot Scheduling Problem

Economic lot scheduling problem has been an important topic in production planning and scheduling research for more than four decades. The problem is known to be NP-hard due to it's combinatorial nature. In this paper, two meta-heuristics algorithms - Tabu Search and Simulated Annealing - are proposed. To investigate the effect of control parameters to the performance of tabu search and simulated annealing algorithms, a general factorial design of experiment study is used. Two Neighborhood Search heuristics that differ in rounding off scheme of the production frequencies are also tested. Experimental study shows that both tabu search and simulated annealing algorithms outperform two best known solution methods - Dobson's Heuristic and Hybrid Genetic Algorithm.

Franz Rothlauf
Carsten Tzschoppe

#### Making the Edge-Set Encoding Fly by Controlling the Bias of its Crossover Operator

Edge-sets encode spanning trees directly by listing their edges. Evolutionary operators for edge-sets may be heuristic, considering the weights of edges they include in offspring, or naive, including edges without regard to their weights. Crossover operators that heuristically prefer shorter edges are strongly biased towards minimum spanning trees (MST); EAs that apply heuristic crossover generally perform poorly on spanning tree problems whose optimum solutions are not very similar to MSTs. For the edge-set encoding, a modified heuristic crossover called $\gamma$-TX implements variable bias towards low-weight edges and thus towards MSTs. The bias can be set arbitrarily between the strong bias of the heuristic crossover operator, or being unbiased. An investigation into the performance of EAs using the $\gamma$-TX for randomly created OCST problems of different types and OCST test instances from the literature present good results when setting the crossover-specific parameter $\gamma$ properly. The presented results suggest that the original heuristic crossover operator of the edge-sets should be substituted by the modified $\gamma$-TX operator that allows us to control the bias towards the MST.

Olfa Sammoud
Christine Solnon
Khaled Ghédira

#### Ant Algorithm for the Graph Matching Problem

This paper describes a new Ant Colony Optimization (ACO) algorithm for solving Graph Matching Problems, the goal of which is to find the best matching between vertices of multi-labeled graphs. This new ACO algorithm is experimentally compared with greedy and reactive tabu approaches on subgraph isomorphism problems and on multivalent graph matching problems.

Maolin Tang

#### An Adaptive Genetic Algorithm for the Minimal Switching Graph Problem

Minimal Switching Graph (MSG) is a graph-theoretic representation of the constrained via minimization problem -- a combinatorial optimization problem in integrated circuit design automation. From a computational point of view, the problem is NP-complete. Hence, a genetic algorithm (GA) was proposed to tackle the problem, and the experiments showed that the GA was efficient for solving large-scale via minimization problems. However, it is observed that the GA is sensitive to the permutation of the genes in the encoding scheme. For an MSG problem, if different permutations of the genes are used the performances of the GA are quite different. In this paper, we present a new GA for MSG problem. Different from the original GA, this new GA has a self-adaptive encoding mechanism that can adapt the permutation of the genes in the encoding scheme to the underlying MSG problem. Experimental results show that this adaptive GA outperforms the original GA.

T. Aruldoss Albert Victoire
A. Ebenezer Jeyakumar

#### An Improved Simulated Annealing Method for the Combinatorial Sub-Problem of the Profit-Based Unit Commitment Problem

Here is presented an improved simulated annealing (SA) method for solving the combinatorial sub-problem of profit-based unit commitment (UC) problem in electric power and energy systems. The UC problem is divided into a combinatorial sub-problem in unit status variables and a non-linear programming sub-problem in unit power output variables. The simulated annealing method with an improved random perturbation of current solution scheme is proposed to solve the combinatorial sub-problem. A simple scheme for generating initial feasible commitment schedule for the SA method to solve the combinatorial problem is also proposed. The non-linear programming sub-problem is solved using the sequential quadratic programming (SQP) technique. Several example systems are solved to validate the robustness and effectiveness of the proposed technique for the profit-based UC problem.

Chaoyong Zhang
Peigen Li
Yunqing Rao
Shuxia Li

#### A New Hybrid GA/SA Algorithm for the Job Shop Scheduling Problem

Among the modern heuristic methods, simulated annealing (SA) and genetic algorithms (GA) represent powerful combinatorial optimization methods with complementary strengths and weaknesses. Borrowing from the respective advantages of the two paradigms, an effective combination of GA and SA, called Genetic Simulated Algorithm (GASA), is developed to solve the job shop scheduling problem (JSP). This new algorithm incorporates metropolis acceptance criterion into crossover operator, which could maintain the good characteristics of the previous generation and reduce the disruptive effects of genetic operators. Furthermore, we present two novel features for this algorithm to solve JSP. Firstly, a new full active schedule (FAS) based on the operation-based representation is presented to construct schedule, which can further reduce the search space. Secondly, we propose a new crossover operator, named Precedence Operation Crossover (POX), for the operation-based representation. The approach is tested on a set of standard instances and compared with other approaches. The Simulation results validate the effectiveness of the proposed algorithm.

Weicai Zhong
Jing Liu
Licheng Jiao

#### An Agent Model for Binary Constraint Satisfaction Problems

With the intrinsic properties of constraint satisfaction problems (CSPs) in mind, several behaviors are designed for agents by making use of the ability of agents to sense and act on the environment. These behaviors are controlled by means of evolution, so that multiagent evolutionary algorithm for constraint satisfaction problems (MAEA-CSPs) results. To overcome the disadvantages of the general encoding methods, the minimum conflict encoding is also proposed. The experiments use 250 benchmark CSPs to test the performance of MAEA-CSPs, and compare it with four well-defined algorithms. The results show that MAEA-CSPs outperforms the other methods. In addition, the effect of the parameters is analyzed systematically.