Part of Evo* 2017 (http://www.evostar.org)
including: EuroGP, EvoCOP, EvoMUSART and
EvoApplications
The 17th 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 2017 conference will be held in the city of Amsterdam, The Netherlands. 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:
Title: A Computational Study of Neighborhood Operators for Job-shop Scheduling Problems with Regular Objectives
Authors: Hayfa Hammami and Thomas Stützle
Abstract: Job-shop scheduling problems have received a considerable attention in the literature. While the most tackled objective in this area is makespan, job-shop scheduling problems with other objectives such as the minimization of the weighted or unweighted tardiness, the number of late jobs, or the sum of the jobs' completion times have been considered. However, the problems under the latter objectives have been generally less studied than makespan. In this paper, we study job-shop scheduling under various objectives. In particular, we examine the impact various neighborhood operators have on the performance of iterative improvement algorithms, the composition of variable neighborhood descent algorithms, and the performance of metaheuristics such as iterated local search in dependence of the type of local search algorithm used.
Title: A Genetic Algorithm for Multi-Component Optimization Problems: the Case of the Travelling Thief Problem
Authors: Daniel K. S. Vieira, Gustavo L. Soares, João A. Vasconcelos, and Marcus H. S. Mendes
Abstract: Real-world problems are often composed of multiple interdependent components. In this case, benchmark problems that do not represent that interdependence are not a good choice to assess algorithm performance. In recent literature, a benchmark problem called Travelling Thief Problem (TTP) was proposed to better represent real-world multi-component problems. TTP is a combination of two well-known problems: 0-1 Knapsack Problem (KP) and the Travelling Salesman Problem (TSP). This paper presents a genetic algorithm-based optimization approach called Multi-Component Genetic Algorithm (MCGA) for solving TTP. It aims to solve the overall problem instead of each sub-component separately. Starting from a solution for the TSP component, obtained by the Chained Lin-Kernighan heuristic, the MCGA applies the evolutionary process (evaluation, selection, crossover, and mutation) iteratively using different basic operators for KP and TSP components. The MCGA was tested on some representative instances of TTP available in the literature. The comparisons show that MCGA obtains competitive solutions in 20 of the 24 TTP instances with 195 and 783 cities.
Title: A Hybrid Feature Selection Algorithm Based on Large Neighborhood Search
Authors: Gelareh Taghizadeh and Nysret Musliu
Abstract: Feature selection aims at choosing a small number of relevant features of samples in a data set to achieve similar or even better classification accuracy than using all features. This paper presents the first study on Large Neighborhood Search (LNS) algorithm for the feature selection problem. We propose a novel hybrid Wrapper and Filter feature selection method using LNS algorithm (WFLNS). In LNS, an initial solution is gradually improved by alternately destroying and repairing the solution. We introduce the idea of using filter ranking method in the process of destroying and repairing to accelerate the search in identifying the core feature subsets. Particularly, WFLNS either adds or removes a feature from a candidate solution based on the correlation based feature ranking method. The proposed algorithm has been tested on twelve benchmark data sets and the results have been compared with ten most recent wrapper methods where WFLNS outperforms over methods in most of the data sets.
Title: A Memetic Algorithm to Maximise the Employee Substitutability in Personnel Shift Scheduling
Authors: Jonas Ingels and Broos Maenhout
Abstract: Personnel rosters are typically constructed for a medium-term period under the assumption of a deterministic operating environment. However, organisations usually operate in a stochastic environment and are confronted with unexpected events in the short term. These unexpected events affect the workability of the personnel roster and need to be resolved efficiently and effectively. To facilitate this short-term recovery, it is important to consider robustness by adopting proactive scheduling strategies during the roster construction. In this paper, we discuss a proactive strategy that maximises the employee substitutability value in a personnel shift scheduling context. We propose a problem-specific population-based approach with local and evolutionary search heuristics to solve the resulting non-linear personnel shift scheduling problem and construct a medium-term personnel shift roster with a maximised employee substitutability value. Detailed computational experiments are presented to validate the design of our heuristic procedure and the selection of the heuristic operators.
Title: Construct, Merge, Solve and Adapt versus Large Neighborhood Search for Solving the Multi-Dimensional Knapsack Problem: Which One Works Better When?
Authors: Evelia Lizárraga, María J. Blesa, and Christian Blum
Abstract: Both, Construct, Merge Solve and Adapt (CMSA) and Large Neighborhood Search (LNS), are hybrid algorithms that are based on iteratively solving sub-instances of the original problem instances, if possible, to optimality. This is done by reducing the search space of the tackled problem instance in algorithm-specific ways which differ from one technique to the other. In this paper we provide first experimental evidence for the intuition that, conditioned by the way in which the search space is reduced, LNS should generally work better than CMSA in the context of problems in which solutions are rather large, and the opposite is the case for problems in which solutions are rather small. The size of a solution is hereby measured by the number of components of which the solution is composed, in comparison to the total number of solution components. Experiments are conducted in the context of the multi-dimensional knapsack problem.
Title: Decomposing SAT Instances with Pseudo Backbones
Authors: Wenxiang Chen and Darrell Whitley
Abstract: Two major search paradigms have been proposed for SAT solving: Systematic Search (SS) and Stochastic Local Search (SLS). In SAT competitions, while SLS solvers are effective on uniform random instances, SS solvers dominate SLS solvers on application instances with internal structures. One important structural property is decomposability. SS solvers have long been exploited the decomposability of application instances with success. We conjecture that SLS solvers can be improved by exploiting decomposability of application instances, and propose the first step toward exploiting decomposability with SLS solvers using pseudo backbones. We then propose two SAT-specific optimizations that lead to better decomposition than on general pseudo Boolean optimization problems. Our empirical study suggests that pseudo backbones can vastly simplify SAT instances, which further results in decomposing the instances into thousands of connected components. This decomposition serves as a key stepping stone for applying the powerful recombination operator, partition crossover, to the SAT domain. Moreover, we establish a priori analysis for identifying problem instances with potential decomposability using visualization of MAXSAT instances and treewidth.
Title: Efficient Consideration of Soft Time Windows in a Large Neighborhood Search for the Districting and Routing Problem for Security Control
Authors: Bong-Min Kim, Christian Kloimüllner, and Günther R. Raidl
Abstract: For many companies it is important to protect their physical and intellectual property in an efficient and economically viable manner. Thus, specialized security companies are delegated to guard private and public property. These companies have to control a typically large number of buildings, which is usually done by teams of security guards patrolling different sets of buildings. Each building has to be visited several times within given time windows and tours to patrol these buildings are planned over a certain number of periods (days). This problem is regarded as the Districting and Routing Problem for Security Control. Investigations have shown that small time window violations do not really matter much in practice but can drastically improve solution quality. When softening time windows of the original problem, a new subproblem arises where the minimum time window penalty for a given set of districts has to be found for each considered candidate route: What are optimal times for the individual visits of objects that minimize the overall penalty for time window violations? We call this Optimal Arrival Time Problem. In this paper, we investigate this subproblem in particular and first give an exact solution approach based on linear programming. As this method is quite time-consuming we further propose a heuristic approach based on greedy methods in combination with dynamic programming. The whole mechanism is embedded in a large neighborhood search (LNS) to seek for solutions having minimum time window violations. Results show that using the proposed heuristic method for determining almost optimal starting times is much faster, allowing substantially more LNS iterations yielding in the end better overall solutions.
Title: Estimation of Distribution Algorithms for the Firefighter Problem
Authors: Krzysztof Michalak
Abstract: The firefighter problem is a graph-based optimization problem in which the goal is to effectively prevent the spread of a threat in a graph using a limited supply of resources. Recently, metaheuristic approaches to this problem have been proposed, including ant colony optimization and evolutionary algorithms. In this paper Estimation of Distribution Algorithms (EDAs) are used to solve the FFP. A new EDA is proposed in this paper, based on a model that represents the relationship between the state of the graph and positions that become defended during the simulation of the fire spreading. Another method that is tested in this paper, named EH-PBIL, uses an edge histogram matrix model with the learning mechanism used in the Population-based Incremental Learning (PBIL) algorithm with some modifications introduced in order to make it work better with the FFP. Apart from these two EDAs the paper presents results obtained using two versions of the Mallows model, which is a probabilistic model often used for permutation-based problems. For comparison, results obtained on the same test instances using an Ant Colony Optimization (ACO) algorithm, an Evolutionary Algorithm (EA) and a Variable Neighbourhood Search (VNS) are presented. The state-position model proposed in this paper works best for graphs with 1000 vertices and more, outperforming the comparison methods. For smaller graphs (with less than 1000 vertices) the VNS works best.
Title: LCS-Based Selective Route Exchange Crossover for the Pickup and Delivery Problem with Time Windows
Authors: Miroslaw Blocho and Jakub Nalepa
Abstract: The pickup and delivery with time windows (PDPTW) is an NP-hard discrete optimization problem of serving transportation requests using a fleet of homogeneous trucks. Its main objective is to minimize the number of vehicles, and the secondary objective is to minimize the distance traveled during the service. In this paper, we propose the longest common subsequence based selective route exchange crossover (LCS-SREX), and apply this operator in the memetic algorithm (MA) for the PDPTW. Also, we suggest the new solution representation which helps handle the crossover efficiently. Extensive experimental study performed on the benchmark set showed that using LCS-SREX leads to very high-quality feasible solutions. The analysis is backed with the statistical tests to verify the importance of the elaborated results. Finally, we report one new world's best routing schedule found using a parallel version of the MA exploiting LCS-SREX.
Title: Multi-rendezvous Spacecraft Trajectory Optimization with Beam P-ACO
Authors: Luís F. Simões, Dario Izzo, Evert Haasdijk, and A. E. Eiben
Abstract: The design of spacecraft trajectories for missions visiting multiple celestial bodies is here framed as a multi-objective bilevel optimization problem. A comparative study is performed to assess the performance of different Beam Search algorithms at tackling the combinatorial problem of finding the ideal sequence of bodies. Special focus is placed on the development of a new hybridization between Beam Search and the Population-based Ant Colony Optimization algorithm. An experimental evaluation shows all algorithms achieving exceptional performance on a hard benchmark problem. It is found that a properly tuned deterministic Beam Search always outperforms the remaining variants. Beam P-ACO, however, demonstrates lower parameter sensitivity, while offering superior worst-case performance. Being an anytime algorithm, it is then found to be the preferable choice for certain practical applications.
Title: Optimizing Charging Station Locations for Electric Car-Sharing Systems
Authors: Benjamin Biesinger, Bin Hu, Martin Stubenschrott, Ulrike Ritzinger, and Matthias Prandtstetter
Abstract: This paper is about strategic decisions required for running an urban station-based electric car-sharing system. In such a system, users can rent and return publicly available electric cars from charging stations. We approach the problem of deciding on the location and size of these stations and on the total number of cars in such a system using a bi-level model. The first level of the model identifies the number of rental stations, the number of slots at each station, and the total number of cars to be acquired. Then, such a generated solution is evaluated by computing which trips can be accepted by the system using a path-based heuristic on a time-expanded location network. This path-based heuristic iteratively finds paths for the cars through this network. We compare three different pathfinder methods, which are all based on the concept of tree search using a greedy criterion. The algorithm is evaluated on a set of benchmark instances which are based on real-world data from Vienna, Austria using a demand model derived from taxi data of about 3500 taxis operating in Vienna. Computational tests show that for smaller instances the algorithm is able to find near optimal solutions and that it scales well for larger instances.
Title: Selection of Auxiliary Objectives Using Landscape Features and Offline Learned Classifier
Authors: Anton Bassin and Arina Buzdalova
Abstract: In order to increase the performance of an evolutionary algorithm, additional auxiliary optimization objectives may be added. It is hard to predict which auxiliary objectives will be the most efficient at different stages of optimization. Thus, the problem of dynamic selection between auxiliary objectives appears. This paper proposes a new method for efficient selection of auxiliary objectives, which uses fitness landscape information and problem meta-features. An offline learned meta-classifier is used to dynamically predict the most efficient auxiliary objective during the main optimization run performed by an evolutionary algorithm. An empirical evaluation on two benchmark combinatorial optimization problems (Traveling Salesman and Job Shop Scheduling problems) shows that the proposed approach outperforms similar known methods of auxiliary objective selection.
Title: Sparse, Continuous Policy Representations for Uniform Online Bin Packing via Regression of Interpolants
Authors: John H. Drake, Jerry Swan, Geoff Neumann and Ender Özcan
Abstract: Online bin packing is a classic optimisation problem, widely tackled by heuristic methods. In addition to human-designed heuristic packing policies (e.g. first- or best- fit), there has been interest over the last decade in the automatic generation of policies. One of the main limitations of some previously-used policy representations is the trade-off between locality and granularity in the associated search space. In this article, we adopt an interpolation-based representation which has the jointly-desirable properties of being sparse and continuous (i.e. exhibits good genotype-to-phenotype locality). In contrast to previous approaches, the policy space is searchable via real-valued optimization methods. Packing policies using five different interpolation methods are comprehensively compared against a range of existing methods from the literature, and it is determined that the proposed method scales to larger instances than those in the literature.
Title: The Weighted Independent Domination Problem: ILP Model and Algorithmic Approaches
Authors: Pedro Pinacho Davidson, Christian Blum, and José A. Lozano
Abstract: This work deals with the so-called weighted independent domination problem, which is an NP-hard combinatorial optimization problem in graphs. In contrast to previous theoretical work from the literature, this paper considers the problem from an algorithmic perspective. The first contribution consists in the development of an integer linear programming model and a heuristic that makes use of this model. Second, two greedy heuristics are proposed. Finally, the last contribution is a population-based iterated greedy algorithm that takes profit from the better one of the two developed greedy heuristics. The results of the compared algorithmic approaches show that small problem instances based on random graphs are best solved by an efficient integer linear programming solver such as CPLEX. Larger problem instances are best tackled by the population-based iterated greedy algorithm. The experimental evaluation considers random graphs of different sizes, densities, and ways of generating the node and edge weights.
Title: Towards Landscape-Aware Automatic Algorithm Configuration: Preliminary Experiments on Neutral and Rugged Landscapes
Authors: Arnaud Liefooghe, Bilel Derbel, Sébastien Verel, Hernán Aguirre, and Kiyoshi Tanaka
Abstract: The proper setting of algorithm parameters is a well-known issue that gave rise to recent research investigations from the (offline) automatic algorithm configuration perspective. Besides, the characteristics of the target optimization problem is also a key aspect to elicit the behavior of a dedicated algorithm, and as often considered from a landscape analysis perspective. In this paper, we show that fitness landscape analysis can open a whole set of new research opportunities for increasing the effectiveness of existing automatic algorithm configuration methods. Specifically, we show that using landscape features in iterated racing both (i) at the training phase, to compute multiple elite configurations explicitly mapped with different feature values, and (ii) at the production phase, to decide which configuration to use on a feature basis, provides significantly better results compared against the standard landscape-oblivious approach. Our first experimental investigations on NK-landscapes, considered as a benchmark family having controllable features in terms of ruggedness and neutrality, and tackled using a memetic algorithm with tunable population size and variation operators, show that a landscape-aware approach is a viable alternative to handle the heterogeneity of (black-box) combinatorial optimization problems.
Title: Understanding Phase Transitions with Local Optima Networks: Number Partitioning as a Case Study
Authors: Gabriela Ochoa, Nadarajen Veerapen, Fabio Daolio, and Marco Tomassini
Abstract: Phase transitions play an important role in understanding search difficulty in combinatorial optimisation. However, previous attempts have not revealed a clear link between fitness landscape properties and the phase transition. We explore whether the global landscape structure of the number partitioning problem changes with the phase transition. Using the local optima network model, we analyse a number of instances before, during, and after the phase transition. We compute relevant network and neutrality metrics; and importantly, identify and visualise the funnel structure with an approach (monotonic sequences) inspired by theoretical chemistry. While most metrics remain oblivious to the phase transition, our results reveal that the funnel structure clearly changes. Easy instances feature a single or a small number of dominant funnels leading to global optima; hard instances have a large number of suboptimal funnels attracting the search. Our study brings new insights and tools to the study of phase transitions in combinatorial optimisation.
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: https://myreview.saclay.inria.fr/evocop17/