# Evostar 2016

The Leading European Event on Bio-Inspired Computation.

Porto, Portugal, 30 March - 1 April 2016

## Call for papers:

## EvoCOP

## The 16th European Conference on Evolutionary Computation in Combinatorial Optimisation

- Accepted paper abstracts
- Download Programme (Note: programmes are provisional and subject to change until the final version is posted).

Part of Evo* 2016 (http://www.evostar.org)
including: EuroGP, EvoCOP, EvoMUSART and
EvoApplications

The 16th European Conference on Evolutionary Computation in Combinatorial Optimisation is a multidisciplinary conference that brings together researchers working on metaheuristics for solving difficult combinatorial optimisation problems appearing in various industrial, economic, and scientific domains. Prominent examples of metaheuristics include: evolutionary algorithms, simulated annealing, tabu search, scatter search and path relinking, memetic algorithms, ant colony and bee colony optimisation, particle swarm optimisation, variable neighbourhood search, iterated local search, greedy randomized adaptive search procedures, estimation of distribution algorithms, and hyperheuristics. Successfully solved problems include scheduling, timetabling, network design, transportation and distribution problems, vehicle routing, travelling salesman, graph problems, satisfiability, energy optimisation problems, packing problems, and planning problems.

The EvoCOP 2016 conference will be held in the city of Porto, Portugal. It will be held in conjunction with EuroGP (the 19th European Conference on Genetic Programming), EvoMUSART (5th European conference on evolutionary and biologically inspired music, sound, art and design) and EvoApplications (specialist events on a range of evolutionary computation topics and applications), in a joint event collectively known as Evo*.

**Areas of Interest and Contributions**

Topics of interest include, but are not limited to:

- Applications of metaheuristics to combinatorial optimisation problems
- Novel application domains for metaheuristic optimisation methods
- Representation techniques
- Neighbourhoods and efficient algorithms for searching them
- Variation operators for stochastic search methods
- Constraint-handling techniques
- Hybrid methods and hybridization techniques
- Parallelization
- Theoretical developments
- Search space and landscape analyses
- Comparisons between different (also exact) techniques
- Metaheuristics and machine learning
- Ant colony optimisation
- Artificial immune systems
- Genetic programming and Genetic algorithms
- (Meta-)heuristics
- Scatter search
- Particle swarm optimisation
- Tabu search, iterated local search and variable neighbourhood search
- Memetic algorithms
- Hyper-heuristics and autonomous search
- Estimation of distribution algorithms
- String processing
- Scheduling and timetabling
- Network design
- Vehicle routing
- Graph problems
- Satisfiability
- Packing and cutting problems
- Energy optimisation problems
- Practical solving of NP-hard problems
- Mixed integer programming
- Multi-objective optimisation
- Grid computing
- Combinatorial optimisation
- Nature and Bio-inspired methods
- Quantum computing and quantum annealing
- Optimisation in Cloud computing
- Search-based software engineering

**Publication Details**

All accepted papers 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, 3448, 3906, 4446, 4972, 5482, 6022, 6622, 7245, 7832, 8600 and 9026 for the previous proceedings).

**Submission Details**

Submissions must be original and not published elsewhere. The submissions will be peer reviewed by members of the program committee. 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. At least one author of each accepted work has to register for the conference, attend the conference and present the work.

The reviewing process will be double-blind, please omit information about the authors in the submitted paper. Submit your manuscript in Springer LNCS format.

Page limit: **16 pages**

**Submission link**: http://myreview.csregistry.org/evocop16/

### Special Issue

Selected papers published in the conference will be invited to be extended for a Special Issue on “Metaheuristics for Combinatorial Optimization” in the Journal of Heuristics, guest-edited by Bin Hu and Francisco Chicano.### EvoCOP Programme Chairs

**Francisco Chicano**University of Malaga, Spain

chicano(at)lcc.uma.es

**Bin Hu**

Austrian Institute of Technology, Austria

*bin.hu(at)ait.ac.at*

### Programme Committee

- Adnan Acan , Eastern Mediterranean University , Turkey
- Enrique Alba , University of Malaga , Spain
- Mehmet-Emin Aydin , University of Bedfordshire , UK
- Matthieu Basseur , University of Angers , France
- Maria J. Blesa , Universitat Politècnica de Catalunya - BarcelonaTech , Spain
- Christian Blum , IKERBASQUE - Basque Foundation for Science , Spain
- Sandy Brownlee , University of Stirling , Scotland UK
- Thomas Bartz-Beielstein , Cologne University of Applied Sciences , Germany
- Pedro Castillo , Universidad de Granada , Spain
- Francisco Chicano , Universidad de Malaga , Spain
- Carlos Coello-Coello , CINVESTAV-IPN , Mexico
- Peter Cowling , University of York , UK
- Karl Doerner , University of Vienna , Austria
- Benjamin Doerr , LIX-Ecole Polytechnique , France
- Bernd Freisleben , University of Marburg , Germany
- Adrien Goeffon , University of Angers , France
- Jens Gottlieb , SAP , Germany
- Walter Gutjahr , University of Vienna , Austria
- Jin-Kao Hao , University of Angers , France
- Emma Hart , Edinburgh Napier University , Scotland UK
- Richard Hartl , University of Vienna , Austria
- Geir Hasle , SINTEF Applied Mathematics , Norway
- Bin Hu , Austrian Institute of Technology , Austria
- Istvan Juhos , University of Szeged , Hungary
- Graham Kendall , University of Nottingham , UK
- Joshua Knowles , University of Manchester , UK
- Mario Koeppen , Kyushu Institute of Technology , Japan
- Frederic Lardeux , University of Angers , France
- Rhyd Lewis , Cardiff University , UK
- Arnaud Liefooghe , University Lille 1 , France
- Jose Antonio Lozano , University of the Basque Country , Spain
- Gabriel Luque , University of Malaga , Spain
- Penousal Machado , University of Coimbra , Portugal
- Jorge Maturana , Universidad Austral de Chile , Chile
- David Meignan , University of Osnabruck , Germany
- Martin Middendorf , University of Leipzig , Germany
- Julian Molina , University of Malaga , Spain
- Eric Monfroy , University of Nantes , France
- Christine L. Mumford , Cardiff University , UK
- Nysret Musliu , Vienna University of Technology , Austria
- Gabriela Ochoa , University of Stirling , Scotland UK
- Beatrice Ombuki-Berman , Brock University , Canada
- Mario Pavone , University of Catania , Italy
- Francisco J. Pereira , Universidade de Coimbra , Portugal
- Matthias Prandtstetter , Austrian Institute of Technology , Austria
- Jakob Puchinger , Austrian Institute of Technology , Austria
- Rong Qu , University of Nottingham , UK
- Günther Raidl , Vienna University of Technology , Austria
- Marcus Randall , Bond University , Australia
- Eduardo Rodriguez-Tello , Civerstav - Tamaulipas , Mexico
- Peter Ross , Edinburgh Napier University , UK
- Frederic Saubion , University of Angers , France
- Marc Schoenauer , INRIA , France
- Patrick Siarry , University of Paris 12 , France
- Kevin Sim , Edinburgh Napier University , UK
- Jim Smith , University of the West of England , UK
- Giovanni Squillero , Politecnico di Torino , Italy
- Thomas Stuetzle , Universite Libre de Bruxelles , Belgium
- Andrew M. Sutton , Friedrich-Schiller-University Jena , Germany
- El-ghazali Talbi , Universite des Sciences et Technologies de Lille , France
- Renato Tinós , University of Sao Paulo , Brasil
- Nadarajen Veerapen , University of Stirling , Scotland UK
- Sebastien Verel , Universite du Littoral Cote d'Opale , France
- Takeshi Yamada , NTT Communication Science Laboratories , Kyoto-Japan
- Shengxiang Yang , De Montfort University , UK

### EvoCOP abstracts

**A Hybrid Constructive Matheuristic Algorithm for The Heterogeneous Vehicle Routing Problem with
Simultaneous Pickup and Delivery
***Baris Kececi, Fulya Altiparmak and Imdat Kara
*

In this paper, a variant of Vehicle Routing Problem, called Heterogeneous Vehicle Routing Problem
with Simultaneous Pickup and Delivery (HVRPSPD), is considered. The HVRPSPD can be defined as
determining the routes and vehicle types on each route in such a way that the pickup and delivery demands of
each customer must be performed with same vehicle, while minimizing the total cost. We propose a
mathematical model for the problem and some valid inequalities for the model. Since the HVRPSPD is an NP-
hard problem, the proposed mathematical model can be used to find the optimal solution for the smallsize
problems. Therefore we propose a hybrid matheuristic approach based on the formulation and Local Search
to solve medium and largesize HVRPSPDs. A series of experiments is performed to evaluate the
performance of proposed algorithm. Computational results show that hybrid matheuristic is computationally
efficient to find good quality of initial solutions.

**A Property Preserving Method for Extending a Singleobjective Problem Instance to Multiple Objectives
with Specific Correlations
***Ruby L. V. Moritz, Enrico Reich, Matthias Bernt and Martin Middendorf
*

A method is proposed to generate multiobjective optimization problem instances from a
corresponding singleobjective instance. The user of the method can specify the correlations between the
generated the objectives. Different from existing instance generation methods the new method allows to keep
certain properties of the original singleobjective instance. In particular, we consider optimization problems
where the objective is defined by a matrix, e.g., a distance matrix for the Traveling Salesperson problem (TSP)
or a flow matrix for the Quadratic Assignment problem. It is shown that the method creates new distance
matrices with specific correlations between each other and also have the same average distance and variance
of distances as the distance matrix of the original instance. This property is important, e.g., when the influence
of correlations between the objectives on the behavior of metaheuristics for the multiobjective TSP are
investigated. Some properties of the new method are shown theoretically. In an empirical analysis the new
method is compared with instance generation methods from the literature.

**An Evolutionary Approach to the Full Optimization of the Traveling Thief Problem
***Nuno Lourenço, Francisco B. Pereira and Ernesto Costa
*

RealWorld problems usually consist of several different small subproblems interacting with each
other. These interactions promote a relation of interdependence, where the quality of a solution to one sub-
problem influences the quality of another partial solution. The Traveling Thief Problem (TTP) is a recent
benchmark that results from the combination of the Traveling Salesman Problem (TSP) and the Knapsack
Problem (KP). Thus far, existing approaches solve the TTP by fixing one of the components, usually the TSP,
and then tackling the KP. We follow in a different direction and propose an Evolutionary Algorithm that
addresses both subproblems at the same time. Experimental results show that solving the TTP as whole
creates conditions for discovering solutions with enhanced quality, and that fixing one of the components might
compromise the overall results.

**Construct, Merge, Solve & Adapt: Application to the RepetitionFree Longest Common Subsequence
Problem
***Christian Blum and Maria J. Blesa
*

In this paper we present the application of a recently proposed, general, algorithm for combinatorial
optimization to the repetitionfree longest common subsequence problem. The applied algorithm, which is
labelled CONSTRUCT, MERGE, SOLVE & ADAPT, generates subinstances based on merging the solution
components found in randomly constructed solutions. These subinstances are subsequently solved by means
of an exact solver. Moreover, the considered subinstances are dynamically changing due to adding new
solution components at each iteration, and removing existing solution components on the basis of indicators
about their usefulness. The results of applying this algorithm to the repetitionfree longest common
subsequence problem show that the algorithm generally outperforms competing approaches from the
literature. Moreover, they show that the algorithm is competitive with CPLEX for small and medium size
problem instances, whereas it outperforms CPLEX for larger problem instances.

**Deconstructing the Big Valley Search Space Hypothesis
***Gabriela Ochoa and Nadarajen Veerapen
*

The big valley hypothesis suggests that, in combinatorial optimisation, local optima of good quality
are clustered and surround the global optimum. We show here that the idea of a single valley does not always
hold. Instead the big valley seems to deconstruct into several valleys, also called ‘funnels’ in theoretical
chemistry. We use the local optima networks model and propose an effective procedure for extracting the
network data. We conduct a detailed study on four selected TSP instances of moderate size and observe that
the big valley decomposes into a number of subvalleys of different sizes and fitness distributions. Sometimes
the global optimum is located in the largest valley, which suggests an easy to search landscape, but this is not
generally the case. The global optimum might be located in a small valley, which offers a clear and visual
explanation of the increased search difficulty in these cases. Our study opens up new possibilities for
analysing and visualising combinatorial landscapes as complex networks.

**Determining the Difficulty of Landscapes by PageRank Centrality in Local Optima Networks
***Sebastian Herrmann
*

The contribution of this study is twofold: First, we show that we can predict the performance of
Iterated Local Search (ILS) in different landscapes with the help of Local Optima Networks (LONs) with escape
edges. As a predictor, we use the PageRank Centrality of the global optimum. Escape edges can be extracted
with lower effort than the edges used in a previous study. Second, we show that the PageRank vector of a
LON can be used to predict the solution quality (average fitness) that can be achieved by ILS in different
landscapes.

**Efficient Hill Climber for MultiObjective PseudoBoolean Optimization
***Francisco Chicano, Darrell Whitley and Renato Tinós
*

Local search algorithms and iterated local search algorithms are a basic technique. Local search can
be a standalone search method, but it can also be hybridized with evolutionary algorithms. Recently, it has
been shown that it is possible to identify improving moves in Hamming neighborhoods for kbounded pseudo-
Boolean optimization problems in constant time. This means that local search does not need to enumerate
neighborhoods to find improving moves. It also means that evolutionary algorithms do not need to use random
mutation as a operator, except perhaps as a way to escape local optima. In this paper, we show how
improving moves can be identified in constant time for multiobjective problems that are expressed as k-
bounded pseudoBoolean functions. In particular, multiobjective forms of NK Landscapes and Mk Landscapes
are considered.

**Evaluating hyperheuristics and local search operators for periodic routing problems
***Yujie Chen, Philip Mourdjis, Fiona Polack, Peter Cowling and Stephen Remde
*

Metaheuristics and hybrid heuristic approaches have been successfully applied to Periodic Vehicle
Routing Problems (PVRPs). However, to be competitive, these methods require careful design of specific
search strategies for each problem. By contrast, hyperheuristics use the performance of low level heuristics to
automatically select and tailor search strategies. Hyperheuristics have been successfully applied to problem
domains such as timetabling and production scheduling. In this study, we present a comprehensive analysis of
hyperheuristic approaches to solving PVRPs. The performance of hyperheuristics is compared to published
performance of stateoftheart metaheuristics.

**Evolutionary Algorithms for Finding Short Addition Chains: Going the Distance
***Stjepan Picek, Carlos A. Coello Coello, Domagoj Jakobovic and Nele Mentens
*

The problem of finding the shortest addition chain for a given exponent is of great relevance in
cryptography, but is also very difficult to solve since it is an NPhard problem. In this paper, we propose a
genetic algorithm with a novel representation of solutions and new crossover and mutation operators to
minimize the length of the addition chains corresponding to a given exponent. We also develop a repair
strategy that significantly enhances the performance of our approach. The results are compared with respect
to those generated by other metaheuristics for instances of moderate size, but we also investigate values up to
127
3. For those instances, we were unable to find any results produced by other metaheuristics for
2
comparison, and three additional strategies were adopted in this case to serve as benchmarks. Our results
indicate that the proposed approach is a very promising alternative to deal with this problem.

**Experimental Evaluation of Two Approaches to Optimal Recombination for Permutation Problems
***Anton Eremeev and Julia Kovalenko
*

We consider two approaches to formulation and solving of optimal recombination problems arising as
supplementary problems in genetic algorithms for the Asymmetric Travelling Salesman Problem and the
Makespan Minimization Problem on a Single Machine. All four optimal recombination problems under
consideration are NPhard but relatively fast exponentialtime algorithms are known for solving them. The
experimental evaluation carried out in this paper shows that the two approaches to optimal recombination are
competitive with each other.

**Hyperplane Elimination for Quickly Enumerating Local Optima
***Brian Goldman and William Punch
*

Examining the properties of local optima is a common method for understanding combinatorial-
problem landscapes. Unfortunately, exhaustive algorithms for finding local optima are limited to very small
problem sizes. We propose a method for exploiting problem structure to skip hyperplanes that cannot contain
local optima, allowing runtime to scale with the number of local optima instead of with the landscape size. We
prove optimality for linear functions and Concatenated Traps, and we provide empirical evidence of optimality
on NKq Landscapes and Ising Spin Glasses. We further refine this method to find solutions that cannot be
improved by flipping r or fewer bits, which counterintuitively can reduce total runtime. While previous methods
were limited to landscapes with at most 2
problems with 2

**Limits to Learning in Reinforcement Learning Hyperheuristics
***Fawaz Alanazi and Per Kristian Lehre
*

Learning mechanisms in selection hyperheuristics are used to identify the most appropriate subset
of heuristics when solving a given problem. Several experimental studies have used additive reinforcement
learning mechanisms, however, these are inconclusive with regard to the performance of selection hyper-
heuristics with these learning mechanisms. This paper points out limitations to learning with additive
reinforcement learning mechanisms. Our theoretical results show that if the probability of improving the
candidate solution in each point of the search process is less than 1/2 which is a mild assumption, then
additive reinforcement learning mechanisms perform asymptotically similar to the simple random mechanism
which chooses heuristics uniformly at random. In addition, frequently used adaptation schemes can affect the
memory of reinforcement learning mechanisms negatively. We also conducted experiments on two wellknown
combinatorial optimisation problems, binpacking and flowshop, and the obtained results confirm the
theoretical findings. This study suggests that alternatives to the additive updates in reinforcement learning
mechanisms should be considered.

**Modifying Colourings between Timesteps to Tackle Changes in Dynamic Random Graphs
***Bradley Hardy, Rhyd Lewis and Jonathan Thompson
*

Many real world operational research problems can be formulated as graph colouring problems.
Algorithms for this problem usually operate under the assumption that the size and constraints of a problem
are fixed, allowing us to model the problem using a static graph. For many problems however, this is not the
case and it would be more appropriate to model such problems using dynamic graphs. In this paper we will
explore whether feasible colourings for one graph at timestep t can be modified into a colouring for a similar
graph at timestep t+1 in some beneficial manner.

**Particle Swarm Optimisation with SequenceLike Indirect Representation for Web Service Composition
***Alexandre Sawczuk da Silva, Yi Mei, Hui Ma and Mengjie Zhang
*

Automated Web service composition, which refers to the creation of a complex application from pre-
existing building blocks (Web services), has been an active research topic in the past years. The advantage of
having an automated composition system is that it allows users to create new applications simply by providing
the required parameters, instead of having to manually assemble the services. Existing approaches to
automated composition rely on planning techniques or evolutionary computing (EC) to modify and optimise
composition solutions directly in their tree/graph form, a complex process that requires several constraints to
be considered before each alteration. To improve the search efficiency and simplify the checking of
constraints, this work proposes an indirect Particle Swarm Optimisation (PSO)based approach. The key idea
of the indirect approach is to optimise a service queue which is then decoded into a composition solution by
using a planning algorithm. This approach is compared to a previously proposed graphbased direct
representation method, and experiment results show that the indirect representation can lead to a greater (or
equivalent) quality while requiring a lower execution time. The analysis conducted shows that this is due to the
design of the algorithms used for building and evaluating the fitness of solutions.

**Particle Swarm Optimization for MultiObjective Web Service Location Allocation
***Boxiong Tan, Yi Mei, Hui Ma and Mengjie Zhang
*

Web service location allocation problem is an important problem in the modern IT industry. In this
34 binary strings, hyperplane elimination can enumerate the same
77 binary strings, and find all 4bit local optima of problems with 2
paper, the two major objectives, i.e. deployment cost and network latency, are considered simultaneously. In
order to solve this new multiobjective problem effectively, we adopted the framework of binary Particle Swarm
Optimization (PSO) due to its efficacy that has been demonstrated in many optimization problems.
Specifically, we developed two PSO variants, one with weightedsum fitness function (WSPSO) and the other
with dominancebased fitness function. Concretely, it uses the fast Nondominate Sorting scheme, and thus is
called NSPSO. The experimental results showed that both PSO variants performed better than NSGAII,
which is the one of the most commonly used multiobjective genetic algorithms. Furthermore, we have found
that NSPSO achieved a more diverse set of solutions than WSPSO, and thus covers the Pareto front better.
This demonstrates the efficacy of using the dominancebased fitness function in solving multiobjective Web
service location allocation problem.

**SimEDA: A Multipopulation Estimation of Distribution Algorithm Based on Problem Similarity
***Krzysztof Michalak
*

In this paper a new estimation of distribution algorithm SimEDA is presented. This algorithm
combines a multipopulation approach with distribution modelling. The proposed approach is to tackle several
similar instances of the same optimization problem at once. Each subpopulation is assigned to a different
instance and a migration mechanism is used for transferring information between the subpopulations. The
migration process can be performed using one of the proposed strategies: two based on similarity between
problem instances and one which migrates specimens between subpopulations with uniform probability.
Similarity of problem instances is expressed numerically and the value of the similarity function is used for
determining how likely a specimen is to migrate between two populations. The SimEDA algorithm is a general
framework which can be used with various EDAs. The presented algorithm has been tested on several
instances of the MaxCut and TSP problems using three different migration strategies and without migration.
The results obtained in the experiments confirm, that the performance of the algorithm is improved when
information is transferred between subpopulations assigned to similar instances of the problem. The migration
strategy which transfers specimens between the most similar problem instances consistently produces better
results than the algorithm without migration.

**Solving the Quadratic Assignment Problem with Cooperative Parallel Extremal Optimization
***Danny Munera, Daniel Diaz and Salvador Abreu
*

Several reallife applications can be stated in terms of the Quadratic Assignment Problem. Finding
an optimal assignment is computationally very difficult, for many useful instances. We address this problem
using a local search technique, based on Extremal Optimization and present experimental evidence that this
approach is competitive. Moreover, cooperative parallel versions of our solver improve performance so much
that large and hard instances can be solved quickly.

### Important dates:

**Submission Deadline:**

**EXTENDED DEADLINE:**11 November 2015

*(site remains open for final changes until 15 Nov)*

**Notification:**4 January 2016

**Camera-ready:**18 January 2016

**Mandatory registration per paper:**15 February

**Student bursary deadline:**20 February

**Early registration discount:**25 February 2016

**Registration deadline:**24 March

**EvoStar dates:**30 March - 1 April 2016