# Evostar 2018

The Leading European Event on Bio-Inspired Computation. Parma, Italy. 4-6 April 2018.

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

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

The 18th European Conference on Evolutionary Computation in Combinatorial Optimisation is a multidisciplinary conference that brings together researchers working on evolutionary computation methods and other metaheuristics for solving difficult combinatorial optimisation problems appearing in various industrial, economic, and scientific domains. Prominent examples of metaheuristics include: evolutionary algorithms, estimation of distribution algorithms, swarm intelligence methods such as ant colony and particle swarm optimisation, local search methods such as simulated annealing, tabu search, variable neighbourhood search, iterated local search, scatter search and path relinking, and their hybridisation, such as memetic algorithms. Automatic algorithm configuration and design, meta-optimisation, model-based methods, and hyperheuristics are also topics of interest. Successfully solved problems include, but are not limited to, multi-objective, uncertain, dynamic and stochastic problems in the context of scheduling, timetabling, network design, transportation and distribution, vehicle routing, graph problems, satisfiability, energy optimisation, cutting, packing, and planning problems.

The EvoCOP 2018 conference will be held in the city of Parma, Italy. It will be held in conjunction with EuroGP (the 21st European Conference on Genetic Programming), EvoMUSART (7th European conference on evolutionary and biologically inspired music, sound, art and design) and EvoApplications (the 21st European Conference on the Applications of Evolutionary Computation), in a joint event collectively known as EvoStar (Evo*).

Areas of Interest and Contributions

Topics of interest include, but are not limited to:

• Applications of metaheuristics to combinatorial optimisation problems
• Representation techniques
• Practical solution of NP-hard problems
• Neighbourhoods and efficient algorithms for searching them
• Variation operators for stochastic search methods
• Theoretical developments
• Constraint-handling techniques
• Parallelisation and grid computing
• Search space and landscape analyses
• Comparisons between different (also exact) methods
• Heuristics
• Genetic programming and Genetic algorithms
• Tabu search, iterated local search and variable neighbourhood search
• Ant colony optimisation
• Artificial immune systems
• Scatter search
• Particle swarm optimisation
• Memetic algorithms
• Hybrid methods and hybridisation techniques
• Matheuristics (hybrids of exact and heuristic methods)
• Hyper-heuristics and autonomous search
• Automatic algorithm configuration and design
• Metaheuristics and machine learning
• Surrogate-model-based methods
• Estimation of distribution algorithms
• String processing
• Scheduling and timetabling
• Network design
• Vehicle routing
• Graph problems
• Satisfiability
• Packing and cutting problems
• Energy optimisation problems
• Multi-objective optimisation
• Search-based software engineering

### EvoCOP Programme Chairs

• Arnaud Liefooghe, University of Lille, France, arnaud.liefooghe (at) univ-lille1.fr
• Manuel López-Ibáñez, University of Manchester, UK, manuel.lopez-ibanez (at) manchester.ac.uk

### Programme Committee

• Adnan Acan, Eastern Mediterranean University, Turkey
• Hernán Aguirre, Shinshu University, France
• Enrique Alba, Universidad de Málaga, Spain
• Richard Allmendinger, University of Manchester, UK
• Thomas Bartz-Beielstein, Cologne University of Applied Sciences, Germany
• Benjamin Biesinger, Austrian Institute of Technology, Austria
• Christian Blum, Artificial Intelligence Research Institute (IIIA-CSIC), Bellaterra, Spain
• Sandy Brownlee, University of Stirling, UK
• Pedro Castillo, Universidad de Granada, Spain
• Francisco Chicano, Universidad de Malaga, Spain
• Carlos Coello Coello, CINVESTAV-IPN, Mexico
• Bilel Derbel, University of Lille, France
• Luca Di Gaspero, University of Udine, Italy
• Karl Doerner, Johannes Kepler University Linz, Austria
• Benjamin Doerr, LIX-Ecole Polytechnique, France
• Carola Doerr, Université Pierre et Marie Curie, France
• Paola Festa, Universitá di Napoli Federico II, Italy
• Bernd Freisleben, University of Marburg, Germany
• Carlos Garcia-Martinez, University of Córdoba, Spain
• Adrien Goeffon, University of Angers, France
• Jens Gottlieb, SAP, Germany
• Walter Gutjahr, University of Vienna, Austria
• Said Hanafi, University of Valenciennes, France
• Jin-Kao Hao, University of Angers, France
• Emma Hart, Edinburgh Napier University, UK
• Geir Hasle, SINTEF Applied Mathematics, Norway
• Bin Hu, Austrian Institute of Technology, Austria
• Andrzej Jaszkiewicz, Poznan University of Technology, Poland
• Istvan Juhos, University of Szeged, Hungary
• Graham Kendall, University of Nottingham, UK
• Ahmed Kheiri, Lancaster University, UK
• Mario Koeppen, Kyushu Institute of Technology, Japan
• Timo Kötzing, Hasso Plattner Institute, Germany
• Frederic Lardeux, University of Angers, France
• Rhyd Lewis, Cardiff University, UK
• Arnaud Liefooghe, University of Lille, France
• Manuel López-Ibáñez, University of Manchester, UK
• Jose Antonio Lozano, University of the Basque Country, Spain
• Gabriel Luque, University of Malaga, Spain
• David Meignan, University of Osnabruck, Germany
• Juan Julian Merelo, University of Granada, Spain
• Krzysztof Michalak, University of Economics, Wroclaw, Poland
• Martin Middendorf, University of Leipzig, Germany
• Christine L. Mumford, Cardiff University, UK
• Nysret Musliu, Vienna University of Technology, Austria
• Gabriela Ochoa, University of Stirling, UK
• Beatrice Ombuki-Berman, Brock University, Canada
• Luis Paquete, University of Coimbra, Portugal
• Mario Pavone, University of Catania, Italy
• Paola Pellegrini, French institute of science and technology for transport, France
• Francisco J. Pereira, Universidade de Coimbra, Portugal
• Matthias Prandtstetter, Austrian Institute of Technology, Austria
• Jakob Puchinger, SystemX-Centrale Supélec, France
• Günther Raidl, Vienna University of Technology, Austria
• Maria Cristina Riff, Universidad Técnica Federico Santa María, Chile
• Eduardo Rodriguez-Tello, CINVESTAV – Tamaulipas, Mexico
• Andrea Roli, Università di Bologna, Italy
• Peter Ross, Edinburgh Napier University, UK
• Frederic Saubion, University of Angers, 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, Université Libre de Bruxelles, Belgium
• El-ghazali Talbi, University of Lille, France
• Sara Tari, University of Angers, France
• Renato Tinós, University of Sao Paulo, Brasil
• Nadarajen Veerapen, University of Stirling, UK
• Sébastien Verel, Université du Littoral Cote d'Opale, France
• Bing Xue, Victoria University of Wellington, New Zealand
• Takeshi Yamada, NTT Communication Science Laboratories, Japan

Publication Details

Regular 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, 9026, 9595 and 10197 for the previous proceedings).

Late-breaking abstracts (LBAs) summarising ongoing research, recent studies and applications of evolutionary computation and other meta-heuristics to real-world or academic combinatorial optimisation problems. LBAs will be presented as posters during the conference.

Submission Details

Regular paper 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 (Regular papers): 16 pages
• Page limit (LBAs): 1 page

Submission link (Regular papers): https://myreview.saclay.inria.fr/evocop18/

Submission link (LBAs): https://myreview.saclay.inria.fr/evocop18_lba/

Important Dates

• Submission deadline (Regular papers): November 1, 2017
• EXTENDED Submission deadline (Regular papers): November 10, 2017
• Notification (Regular papers): 3 January 2018
• Camera-ready (Regular papers): 15 January 2018
• Submission deadline (Late-breaking abstracts): January 15, 2018
• Notification (Late-breaking abstracts): 1 February 2017
• Camera-ready (Late-breaking abstracts): 15 February 2017
• Mandatory registration per paper: 9 February 2017
• Early registration discount: TBA
• Registration deadline: TBA
• EvoStar dates: 4-6 April 2018

### Accepted paper abstracts

Title: On the Fractal Nature of Local Optima Networks
Author: Sarah L. Thomson, Sébastien Verel, Gabriela Ochoa, Nadarajen Veerapen, Paul McMenemy
Abstract: A Local Optima Network represents fitness landscape connectivity within the space of local optima as a mathematical graph. In certain other complex networks or graphs there have been recent observations made about inherent self-similarity. An object is said to be self-similar if it shows the same patterns when measured at different scales; another word used to convey self-similarity is fractal. The fractal dimension of an object captures how the detail observed changes with the scale at which it is measured, with a high fractal dimension being associated with complexity. We conduct a detailed study on the fractal nature of the local optima networks of a benchmark combinatorial optimisation problem (NK Landscapes). The results draw connections between fractal characteristics and performance by three prominent metaheuristics: Iterated Local Search, Simulated Annealing, and Tabu Search.

Title: An Evolutionary Algorithm with Practitioner's-Knowledge-Based Operators for the Inventory Routing Problem
Author: Piotr Lipinski, Krzysztof Michalak
Abstract: This paper concerns the Inventory Routing Problem (IRP) which is an optimization problem addressing the optimization of transportation routes and the inventory levels at the same time. The IRP is notable for its difficulty - even finding feasible initial solutions poses a~significant problem. In this paper an evolutionary algorithm is proposed that uses approaches to solution construction and modification utilized by practitioners in the field. The population for the EA is initialized starting from a~base solution which in this paper is generated by a~heuristic, but can as well be a~solution provided by a~domain expert. Subsequently, feasibility-preserving moves are used to generate the initial population. In the paper dedicated recombination and mutation operators are proposed which aim at generating new solutions without lofeasibility. In order to reduce the search space, solutions in the presented EA are encoded as lists of routes with the quantities to be delivered determined by a~supplying policy. The presented work is a~step towards utilizing domain knowledge in evolutionary computation. The EA presented in this paper employs mechanisms of solution initialization capable of generating a set of feasible initial solutions of the IRP in a reasonable time. Presented operators generate new feasible solutions effectively without requiring a repair mechanism.

Title: How Perturbation Strength Shapes the Global Structure of TSP Fitness Landscapes
Author: Paul McMenemy, Gabriela Ochoa, Nadarajen Veerapen
Abstract: Local optima networks are a valuable tool used to analyse and visualise the global structure of combinatorial search spaces; in particular, the existence and distribution of multiple funnels in the landscape. We extract and analyse the networks induced by Chained-LK, a powerful iterated local search for the TSP, on a large set of randomly generated (Uniform and Clustered) instances. Results indicate that increasing the perturbation strength employed by Chained-LK modifies the landscape's global structure, with the effect being markedly different for the two classes of instances. Our quantitative analysis shows that several funnel metrics have stronger correlations with Chained-LK success rate than the number of local optima, indicating that global structure clearly impacts search performance.

Title: An Ant Colony Approach for the Winner Determination Problem
Author: Abhishek Ray, Mario Ventresca
Abstract: Combinatorial auctions are those where bidders can bid on bundles of items. These auctions can lead to more economically efficient allocations, but determining the winners is an NP-complete problem. In this paper, we propose an ant colony technique for approximating solutions to hard instances of this problem. Hard instances are those that are unsolvable within 1$seconds by CPLEX and have more than 1000 bids on 500 or more unique items. Such instances occur in real world applications such as 4th Party Logistics auctions, online resource time sharing auctions and the sale of spectrum licenses by the Federal Communications Commission. We perform experiments on 10 such instances to show and compare the performance of the proposed approach to CPLEX (Branch-and-Bound), stochastic greedy search, random walk and memetic algorithm. Results indicate that in a given runtime, CPLEX results lie within the third quartile of the values generated using our approach for 3 of 10 of the instances. In addition, CPLEX results are on average {BODY}.24\%$ lower than best values reported using our approach for 5 of 10 instances. Further, our approach performs statistically significantly better than other heuristics on all instances.

Title: Automatic grammar-based design of heuristic algorithms for unconstrained binary quadratic programming
Author: Marcelo de Souza, Marcus Ritt
Abstract: Automatic methods have been applied to find good heuristic algorithms to combinatorial optimization problems. These methods aim at reducing human efforts in the trial-and-error search for promising heuristic strategies. We propose a grammar-based approach to the automatic design of heuristics and apply it to binary quadratic programming. The grammar represents the search space of algorithms and parameter values. A solution is represented as a sequence of categorical choices, which encode the decisions taken in the grammar to generate a complete algorithm. We use an iterated F-race to evolve solutions and tune parameter values. Experiments show that our approach can find algorithms which perform better than or comparable to state-of-the-art methods, and can even find new best solutions for some instances of standard benchmark sets.

Title: Data Clustering Using Grouping Hyper-heuristics
Author: Anas Elhag, Ender Ozcan
Abstract: Grouping problems represent a class of computationally hard to solve problems requiring optimal partitioning of a given set of items with respect to multiple criteria varying dependent on the domain. A recent work proposed a general-purpose selection hyper-heuristic search framework with reusable components, designed for rapid development of grouping hyper-heuristics to solve grouping problems. The framework was tested only on the graph colouring problem domain. Extending the previous work, this study compares the performance of selection hyper-heuristics implemented using the framework, pairing up various heuristic/operator selection and move acceptance methods for data clustering. The selection hyper-heuristic performs the search processing a single solution at any decision point and controls a fixed set of generic low level heuristics specifically designed for the grouping problems based on a bi-objective formulation. An archive of high quality solutions, capturing the trade-off between the number of clusters and overall error of clustering, is maintained during the search process. The empirical results verify the effectiveness of a successful selection hyper-heuristic, winner of a recent hyper-heuristic challenge for data clustering on a set of benchmark problem instances.

Title: Automatic Algorithm Configuration for the Permutation Flow Shop Scheduling Problem Minimizing Total Completion Time
Author: Artur Brum, Marcus Ritt
Abstract: Automatic algorithm configuration aims to automate the often time-consuming task of designing and evaluating search methods. We address the permutation flow shop scheduling problem minimizing total completion time with a context-free grammar that defines how algorithmic components can be combined to form a full heuristic search method. We implement components from various works from the literature, including several local search procedures. The search space defined by the grammar is explored with a racing-based strategy and the algorithms obtained are compared to the state of the art.

Title: Reference Point Adaption Method for Genetic Programming Hyper-heuristic in Many-Objective Job Shop Scheduling
Author: Atiya Masood, Gang Chen, Yi Mei, Mengjie Zhang
Abstract: Job Shop Scheduling (JSS) is considered to be one of the most significant combinatorial optimization problems in practice. It is widely evidenced in the literature that JSS usually contains many (four or more) potentially conflicting objectives. One of the promising and successful approaches to solve the JSS problem is Genetic Programming Hyper-Heuristic (GP-HH). This approach automatically evolves dispatching rules for solving JSS problems. This paper aims to evolve a set of effective dispatching rules for many-objective JSS with genetic programming and NSGA-III. NSGA-III originally defines uniformly distributed reference points in the objective space. Thus, there will be few reference points with no Pareto optimal solutions associated with them; especially, in the cases with discrete and non-uniform Pareto front, resulting in many useless reference points during evolution. In other words, these useless reference points adversely affect the performance of NSGA-III and genetic programming. To address the above issue, in this paper a new reference point adaptation mechanism is proposed based on the distribution of the candidate solutions. We evaluated the performance of the proposed mechanism on many-objective benchmark JSS instances. Our results clearly show that the proposed strategy is promising in adapting reference points and outperforms the existing state-of-the-art algorithms for many-objective JSS

Title: MOEA/DEP: An Algebraic Decomposition-based Evolutionary Algorithm for the Multi-objective Permutation Flowshop Scheduling Problem
Author: Marco Baioletti, Alfredo Milani, Valentino Santucci
Abstract: Algebraic evolutionary algorithms are an emerging class of meta-heuristics for combinatorial optimization based on strong mathematical foundations. In this paper we introduce a decomposition-based algebraic evolutionary algorithm, namely MOEA/DEP, in order to deal with multiobjective permutation-based optimization problems. As a case of study, MOEA/DEP has been experimentally validated on a multiobjective permutation flowshop scheduling problem (MoPFSP). In particular, the makespan and total flowtime objectives have been investigated. Experiments have been held on a widely used benchmark suite, and the obtained results have been compared with respect to the state-of-the-art Pareto fronts for MoPFSP. The experimental results have been analyzed by means of two commonly used performance metrics for multiobjective optimization. The analysis clearly shows that MOEA/DEP reaches new state-of-the-art results for the considered benchmark.

Title: Better Runtime Guarantees Via Stochastic Domination
Author: Benjamin Doerr
Abstract: Apart from few exceptions, the mathematical runtime analysis of evolutionary algorithms is mostly concerned with expected runtimes. In this work, we argue that stochastic domination is a notion that should be used more frequently in this area. Stochastic domination allows to formulate much more informative performance guarantees than the expectation alone, it allows to decouple the algorithm analysis into the true algorithmic part of detecting a domination statement and probability theoretic part of deriving the desired probabilistic guarantees from this statement, and it allows simpler and more natural proofs. As particular results, we prove a fitness level theorem which shows that the runtime is dominated by a sum of independent geometric random variables, we prove tail bounds for several classic problems, and we give a short and natural proof for Witt's result that the runtime of any $(\mu,p)$ mutation-based algorithm on any function with unique optimum is subdominated by the runtime of a variant of the (1+1) EA on the \onemax function.

Title: Worst improvement based iterated local search
Author: Sara Tari, Matthieu Basseur, Adrien Goëffon
Abstract: To solve combinatorial optimization problems, many metaheuristics use first or best improvement hill-climbing as intensification mechanism in order to find local optima. In particular, first improvement offers a good tradeoff between computation cost and quality of reached local optima. In this paper, we investigate a worst improvement-based moving strategy, never considered in the literature. Such a strategy is able to reach good local optima despite requiring a significant additional computation cost. Here, we investigate if such a pivoting rule can be efficient when considered within metaheuristics, and especially within iterated local search (ILS). In our experiments, we compare an ILS using a first improvement pivoting rule to an ILS using an approximated version of worst improvement pivoting rule. Both methods are launched with the same number of evaluations on bit-string based fitness landscapes. Results are analyzed using some landscapes' features in order to determine if the worst improvement principle should be considered as a moving strategy in some cases.

Title: A multistart alternating tabu search for commercial districting
Author: Alex Gliesch, Marcus Ritt, Mayron C.O. Moreira
Abstract: In this paper we address a class of commercial districting problems that arises in the context of the distribution of goods. The problem aims at partitioning an area of distribution, which is modeled as an embedded planar graph, into connected components, called districts. Districts are required to be mutually balanced with respect to node attributes, such as number of customers, expected demand, and service cost, and as geometrically-compact as possible, by minimizing their Euclidean diameters. To solve this problem, we propose a multistart algorithm that repeatedly constructs solutions greedily and improves them by two alternating tabu searches, one aiming at achieving feasibility through balancing and the other at maximizing district compactness. Computational experiments confirm the effectiveness of the different components of our method and show that it significantly outperforms the current state of the art, improving known upper bounds in almost all instances.

### Important dates:

Submission Deadline: 1 November 2017
EXTENDED SUBMISSION DEADLINE: 10 November 2017
Notification: 3 January 2018
Camera-ready: 15 January 2018
Mandatory registration per paper: 9 February 2018
Early registration discount: 28 February
Registration deadline: 28 March
EvoStar dates: 4-6 April 2018