Evostar 2016

• EuroGP
  
• EvoCOP
  
• EvoMUSART
  
• EvoApplications
  
  
  • EvoBAFIN
  • EvoBIO
  • EvoCOMNET
  • EvoCOMPLEX
  • EvoENERGY
  • EvoGAMES
  • EvoIASP
  • EvoINDUSTRY
  • EvoNUM
  • EvoPAR
  • EvoRISK
  • EvoROBOT
  • EvoSTOC
  EvoStar Best Paper Candidates
  EvoStar Best Paper Awards 2016
  

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

Download flyer

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 Mat­heuristic Algorithm for The Heterogeneous Vehicle Routing Problem with Simultaneous Pick­up 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 Pick­up 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 small­size problems. Therefore we propose a hybrid mat­heuristic approach based on the formulation and Local Search to solve medium and large­size HVRPSPDs. A series of experiments is performed to evaluate the performance of proposed algorithm. Computational results show that hybrid mat­heuristic is computationally efficient to find good quality of initial solutions.

A Property Preserving Method for Extending a Single­objective 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 multi­objective optimization problem instances from a corresponding single­objective 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 single­objective 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 multi­objective 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
Real­World problems usually consist of several different small sub­problems 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 sub­problems 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 Repetition­Free 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 repetition­free longest common subsequence problem. The applied algorithm, which is labelled CONSTRUCT, MERGE, SOLVE & ADAPT, generates sub­instances based on merging the solution components found in randomly constructed solutions. These sub­instances are subsequently solved by means of an exact solver. Moreover, the considered sub­instances 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 repetition­free 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 de­construct 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 sub­valleys 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 Multi­Objective Pseudo­Boolean 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 stand­alone 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 k­bounded 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 pseudo­Boolean 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
Meta­heuristics 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 state­of­the­art meta­heuristics.

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 NP­hard 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 NP­hard but relatively fast exponential­time 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 Hyper­heuristics
Fawaz Alanazi and Per Kristian Lehre
Learning mechanisms in selection hyper­heuristics 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 well­known combinatorial optimisation problems, bin­packing and flow­shop, 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 Time­steps 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 time­step t can be modified into a colouring for a similar graph at time­step t+1 in some beneficial manner.

Particle Swarm Optimisation with Sequence­Like 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 graph­based 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 Multi­Objective 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 4­bit 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 multi­objective 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 weighted­sum fitness function (WSPSO) and the other with dominance­based fitness function. Concretely, it uses the fast Non­dominate Sorting scheme, and thus is called NSPSO. The experimental results showed that both PSO variants performed better than NSGA­II, which is the one of the most commonly used multi­objective 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 dominance­based fitness function in solving multi­objective Web service location allocation problem.

Sim­EDA: A Multipopulation Estimation of Distribution Algorithm Based on Problem Similarity
Krzysztof Michalak
In this paper a new estimation of distribution algorithm Sim­EDA 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 Sim­EDA algorithm is a general framework which can be used with various EDAs. The presented algorithm has been tested on several instances of the Max­Cut 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 real­life 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.