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:
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.
Submission link (Regular papers): https://myreview.saclay.inria.fr/evocop18/
Submission link (LBAs): https://myreview.saclay.inria.fr/evocop18_lba/
Important Dates
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.