Part of Evo* 2019 (http://www.evostar.org)
including: EuroGP, EvoCOP, EvoMUSART and
EvoApplications
The 19th 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 2019 conference will be held in the city of Leipzig, Germany, together with EuroGP (the 22nd European Conference on Genetic Programming), EvoMUSART (the 8th European conference on evolutionary and biologically inspired music, sound, art and design) and EvoApplications (the 22nd 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:
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, 10197 and 10782 for the previous proceedings).
The best regular paper presented at EvoCOP 2019 will be distinguished with a *Best Paper Award*. Authors of the best regular papers will be invited for fast track publication in the *Evolutionary Computation Journal*. The invited submissions must significantly extend the conference paper and will undergo peer review.
Reproducibility studies are concise and rigorous experimental studies that replicate published experiments, and that substantially shift the confidence in the main results of the original study. We strongly encourage the authors to discuss the reasons for the new findings, such as, e.g., input data not considered in the original work or different implementation details. A reproducibility study should follow the usual reproducibility standards, that is, it should provide complete details about the implementation, compiler options, input data description, algorithmic parameters, operating system and hardware specification. Moreover, the code should be available in a public repository immediately after the submission to EvoCOP and should remain available after publication in the proceedings. Statistical analysis, if applicable, should provide details about the statistical assumptions and statistical testing procedures. Although it is expected that textual similarity between the reproducibility study and the original work may arise, the usual plagiarism standards will be taken into account. Reproducibility studies will take the form of short papers presented orally at the conference and published in the Springer LNCS proceedings.
Late-breaking abstracts (LBAs) summarise 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 short talks during the conference.
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.
A Unifying View on Recombination Spaces and Abstract Convex Evolutionary Search
Marcos Diez Garcia, Alberto Moraglio
Previous work proposed to unify an algebraic theory of fitness
landscapes and a geometric framework of evolutionary algorithms (EAs).
The aim behind this unification is to develop an analytical method
that verifies if a problem's landscape belongs to certain abstract
convex landscape classes, where certain recombination-based EAs
(without mutation) have polynomial runtime performance. This paper
advances such unification by showing that: (a) crossovers can be
formally classified according to geometric or algebraic axiomatic
properties; and (b) a class of crossovers admits both a geometric and
algebraic understanding of the population-behaviour induced by them in
a recombination-based EA. These results make a significant
contribution for the basis of an integrated geometric-algebraic
framework with which analyse recombination spaces and
recombination-based EAs.
A New Representation in Genetic Programming for Evolving Dispatching Rules for Dynamic Flexible Job Shop Scheduling
Fangfang Zhang, Yi Mei, Mengjie Zhang
Dynamic flexible job shop scheduling (DFJSS) is a very important
problem with a wide range of real-world applications such as cloud
computing and manufacturing. In DFJSS, it is critical to make two
kinds of real-time decisions (i.e. the routing decision that assigns
machine to each job and the sequencing decision that prioritises the
jobs in a machine queue) effectively in the dynamic environment with
unpredicted events such as new job arrivals and machine breakdowns.
Dispatching rule is an ideal technique for this purpose. In DFJSS, one
has to design a routing rule and a sequencing rule for making the two
kinds of decisions. Manually designing these rules is time consuming
and requires human expertise which is not always available. Genetic
programming (GP) has been applied to automatically evolve more
effective rules than the manually designed ones. In GP for DFJSS,
different features in the terminal set have different contributions to
the decision making. However, the current GP approaches cannot
perfectly find proper combinations between the features in accordance
with their contributions. In this paper, we propose a new
representation for GP that better considers the different
contributions of different features and combines them in a
sophisticated way, thus to evolve more effective rules. The results
show that the proposed GP approach can achieve significantly better
performance than the baseline GP in a range of job shop scenarios.
Clarifying the Differences in Local Optima Network Sampling Algorithms
Sarah L. Thomson, Gabriela Ochoa, Sébastien Verel
We conduct the first ever statistical comparison between two Local
Optima Network (LON) sampling algorithms. These methodologies attempt
to capture the connectivity in the local optima space of a fitness
landscape. One sampling algorithm is based on a random-walk
snowballing procedure, while the other is centered around multiple
traced runs of an Iterated Local Search. Both of these are proposed
for the Quadratic Assignment Problem (QAP), making this the focus of
our study. It is important to note the sampling algorithm frameworks
could easily be modified for other domains. In our study descriptive
statistics for the obtained search space samples are contrasted and
commented on. The LON features are also used in linear mixed models
and random forest regression for predicting heuristic optimisation
performance of two prominent heuristics for the QAP on the underlying
combinatorial problems. The model results are then used to make
deductions about the sampling algorithms' utility. We also propose a
specific set of LON metrics for use in future predictive models
alongside previously-proposed network metrics, demonstrating the
payoff in doing so.
Route Planning for a Fleet of Electric Vehicles with Waiting Times at Charging Stations
Baoxiang Li, Shashi Jha, Hoong Chuin Lau
Electric Vehicles (EVs) are the next wave of technology in the
transportation industry. EVs are increasingly becoming common for
personal transport and pushing the boundaries to become the mainstream
mode of transportation. Use of such EVs in logistic fleets for
delivering customer goods is not far from becoming reality. However,
managing such fleet of EVs bring new challenges in terms of battery
capacities and charging infrastructure for efficient route planning.
Researchers have addressed such issues considering different aspects
of the EVs such as linear battery charging/discharging rate, fixed
travel times, etc. In this paper, we address the issue of waiting
times due to limited charging capacity at the charging stations while
planning the routes of EVs for providing pickup/delivery services. We
provide an exact mathematical model of the problem considering waiting
times of vehicle based on their arrival at the charging stations. We
further develop a genetic algorithm approach that embeds Constraint
Programming to solve the problem. We test our approach on a set of
benchmark Solomon instances.
An Iterated Local Search Algorithm for the Two-Machine Flow Shop Problem with Buffers and Constant Processing Times on One Machine
Hoang Thanh Le, Philine Geser, Martin Middendorf
This paper considers a special case of two-machine flow shop
scheduling problems with buffers, namely, the case that all processing
times on one of the two machines are equal. This case is interesting
because it occurs in various applications, e.g., when one machine is a
packing machine. For the buffers we consider two types of buffers that
have been studied in the literature for flow shops. It is shown that
all considered buffered flow shop problems remain NP-hard for the
makespan criterion and permutation schedules even with the restriction
of equal processing times on one machine. Two specific heuristics for
solving the problems are proposed: i) a modification of the commonly
used NEH heuristic (mNEH) and ii) an Iterated Local Search heuristic
(2BF-ILS) that uses the mNEH heuristic for computing its initial
solution. It is shown experimentally that the proposed 2BF-ILS
heuristic obtains better results than two state-of-the-art algorithms
for buffered flow shop problems from the literature and an Ant Colony
Optimization algorithm. In addition, it is shown experimentally that
2BF-ILS can obtain the same solution quality as the standard NEH
heuristic with a smaller number of function evaluations.
Program Trace Optimization with Constructive Heuristics for Combinatorial Problems
James McDermott, Alberto Moraglio
Program Trace Optimisation (PTO), a recent and highly general
optimisation framework, is applied to a range of combinatorial
optimisation (COP) problems. It effectively combines ``smart''
problem-specific constructive heuristics and problem-agnostic
metaheuristic search, automatically and implicitly designing
problem-appropriate search operators. A weakness is identified in
PTO's operators when applied in conjunction with smart heuristics on
COP problems, and an improved method is introduced to address this. To
facilitate the comparison of this new method with the original, across
problems, a common format for PTO generators is demonstrated, similar
to that of GRASP. This also facilitates comparison of the degree of
greediness (the GRASP alpha parameter) in the heuristics. Experiments
across several problems show that the novel operators consistently
outperform the original without any loss of generality or cost in CPU
time; hill-climbing is a sufficient metaheuristic; and intermediate
levels of greediness are usually best.
A Cooperative Optimization Approach for Distributing Service Points in Mobility Applications
Thomas Jatschka, Tobias Rodemann, Günther Raidl
We investigate a variant of the facility location problem concerning
the optimal distribution of service points with incomplete information
within a certain geographical area. The application scenario is
generic in principle, but we have the setup of charging stations for
electric vehicles or rental stations for bicycles or cars in mind.
When planning such systems, estimating under which conditions which
customer demand can be fulfilled is fundamental in order to evaluate
and optimize possible solutions. In this paper we present a
cooperative optimization approach for distributing service points that
incorporates potential customers not only in the data acquisition but
also during the optimization process. A surrogate objective function
is used to evaluate intermediate solutions during the optimization.
The quality of this surrogate objective function is iteratively
improved by learning from the feedback of potential users given to
candidate solutions. For the actual optimization we consider a
population based iterated greedy algorithm. Experiments on artificial
benchmark scenarios with idealized simulated user behavior show the
learning capabilities of the surrogate objective function and the
effectiveness of the optimization.
Multiple periods vehicle routing problems: a case study
Bilal Messaoudi, Ammar Oulamara, Nastaran Rahmani
In this paper, we consider a challenging problem faced by an hygiene
services company. The problem consists of planning and routing a set
of customers over a 3-months horizon period where multiple frequencies
of visits can be required simultaneously by each single customer. The
objective is then threefold: (1) balancing workload between vehicles
(agents) (2) minimizing number of visits to the same customer (3)
minimizing total routing costs. In this context, a routing plan must
be prepared for the whole horizon, taking into account all constraints
of the problem. We model the problem using a decomposition approach of
planning horizon, namely, weeks planning and days planning
optimization. We propose an adaptive large neighborhood search with
several operators for routing phase of solving approach. To evaluate
the performance of the solving approach we solve an industrial
instance with more than 6000 customers and 69951 requests of visits.
The results show an excellent performance of the solving approach in
terms of solution quality comparing with the existing plan used by the
hygiene services company.
Rigorous Performance Analysis of State-of-the-art TSP Heuristic Solvers
Paul McMenemy, Nadarajen Veerapen, Jason Adair, Gabriela Ochoa
Understanding why some problems are better solved by one algorithm
rather than another is still an open problem, and the symmetric
Travelling Salesperson Problem (TSP) is no exception. We apply three
state-of-the-art heuristic solvers to a large set of TSP instances of
varying structure and size to identify which heuristics solve specific
instances to optimality faster than others. The first two solvers
considered are variants of the multi-trial Helsgaun's Lin-Kernighan
Heuristic (a form of iterated local search), each using a different
form of Partition Crossover; the third solver is a genetic algorithm
(GA) using Edge Assembly Crossover. Our results show that the GA with
Edge Assembly Crossover is the best solver, shown to significantly
outperform the other algorithms in 73% of the instances analysed. A
comprehensive set of features for all instances are also extracted,
and decision trees are used to identify features which could best
inform algorithm selection. The most prominent features identified a
high proportion of instances where the GA with Edge Assembly Crossover
performed significantly better at solving to optimality.
Insights into the Feature Selection Problem using Local Optima Networks
Werner Mostert, Katherine Malan, Gabriela Ochoa, Andries Engelbrecht
The binary feature selection problem is investigated in this paper.
Feature selection fitness landscape analysis is done, which allows for
a better understanding of the behaviour of feature selection
algorithms. Local optima networks are employed as a tool to visualise
and characterise the fitness landscapes of the feature selection
problem in the context of classification. An analysis of the fitness
landscape global structure is provided, based on seven real-world
datasets with up to 17 features. Formation of neutral global optima
plateaus are shown to indicate the existence of irrelevant features in
the datasets. Removal of irrelevant features resulted in a reduction
of neutrality and the ratio of local optima to the size of the search
space, resulting in improved performance of genetic algorithm search
in finding the global optimum.
A Binary Algebraic Differential Evolution for the multidimensional two-way number partitioning problem
Marco Baioletti, Gabriele Di Bari, Alfredo Milani, Valentino Santucci
This paper introduces MADEB, a Memetic Algebraic Differential
Evolution algorithm for the Binary search space. MADEB has been
applied to the Multidimensional Two-Way Number Partitioning Problem
(MDTWNPP) and its main components are the binary differential mutation
operator and a variable neighborhood descent procedure. The binary
differential mutation is a concrete application of the abstract
algebraic framework for the binary search space. The variable
neighborhood descent is a local search procedure specifically designed
for MDTWNPP. Experiments have been held on a widely accepted benchmark
suite and MADEB is experimentally compared with respect to the current
state-of-the-art algorithms for MDTWNPP. The experimental results
clearly show that MADEB is the new state-of-the-art algorithm in the
problem here investigated.
Runtime Analysis of Discrete Particle Swarm Optimization Applied to Shortest Paths Computation
Alexander Rass, Jonas Schreiner, Rolf Wanka
We mathematically analyze a discrete particle swarm optimization (PSO)
algorithm solving the single-source shortest path (SSSP) problem. Key
features are an improved and extended study on Markov chains expanding
the adaptability of this technique and its application on the
ubiquitous SSSP problem. The results are upper and lower bounds on the
expected optimization time. For upper bounds, we combine return times
within a Markov model with the well known fitness level method which
is appropriate even for the non-elitist PSO algorithm. For lower
bounds we prove that the recently introduced property of
indistinguishability applies in this setting and we also combine it
with a further Markov chain analysis.
Quasi-Optimal Recombination Operator
Francisco Chicano, Gabriela Ochoa, Darrell Whitley, Renato Tinós
The output of an optimal recombination operator for two parent
solutions is a solution with the best possible value for the objective
function among all the solutions fulfilling the gene transmission
property (the value of any variable in the offspring is taken from one
of the parents). This set of solutions coincides with the largest
dynastic potential for the two parent solutions of any recombination
operator with the gene transmission property. In general, exploring
the full dynastic potential is computationally costly, but if the
variables of the objective function have a low number of non-linear
interactions among them, the exploration can be done in $O(n^2+m)$
time, for problems with $n$ variables and $m$ subfunctions. In this
paper, we propose a quasi-optimal recombination operator, called
Dynastic Potential Crossover (DPX), that runs in $O(n^2+m)$ time in
any case and is able to explore the full dynastic potential. We
compare this operator, both theoretically and experimentally, with two
recently defined operators using concepts of gray box optimization:
Partition Crossover (PX) and Articulation Points Partition Crossover
(APX). The empirical comparison uses NKQ Landscapes and MAX-SAT
instances.