Part of Evo* 2019 (http://www.evostar.org)
including: EuroGP, EvoCOP, EvoMUSART and
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.