# GECCO '20: Proceedings of the 2020 Genetic and Evolutionary Computation Conference

Full Citation in the ACM Digital Library## SESSION: Evolutionary combinatorial optimization and metaheuristics

### A deep learning approach to predicting solutions in streaming optimisation domains

In the field of combinatorial optimisation, per-instance algorithm selection still
remains a challenging problem, particularly with respect to streaming problems such
as packing or scheduling. Typical approaches involve training a model to predict the
best algorithm based on features extracted from the data, which is well known to be
a difficult task and even more challenging with streaming data. We propose a radical
approach that bypasses algorithm-selection altogether by training a Deep-Learning
model using solutions obtained from a set of heuristic algorithms to directly predict
a *solution* from the instance-data. To validate the concept, we conduct experiments using a packing
problem in which items arrive in batches. Experiments conducted on six large datasets
using batches of varying size show the model is able to accurately predict solutions,
particularly with small batch sizes, and surprisingly in a small number of cases produces
better solutions than any of the algorithms used to train the model.

### Dynamic bi-objective routing of multiple vehicles

In practice, e.g. in delivery and service scenarios, Vehicle-Routing-Problems (VRPs) often imply repeated decision making on dynamic customer requests. As in classical VRPs, tours have to be planned short while the number of serviced customers has to be maximized at the same time resulting in a multi-objective problem. Beyond that, however, dynamic requests lead to the need for re-planning of not yet realized tour parts, while already realized tour parts are irreversible. In this paper we study this type of bi-objective dynamic VRP including sequential decision making and concurrent realization of decisions. We adopt a recently proposed Dynamic Evolutionary Multi-Objective Algorithm (DEMOA) for a related VRP problem and extend it to the more realistic (here considered) scenario of multiple vehicles. We empirically show that our DEMOA is competitive with a multi-vehicle offline and clairvoyant variant of the proposed DEMOA as well as with the dynamic single-vehicle approach proposed earlier.

### A robust experimental evaluation of automated multi-label classification methods

Automated Machine Learning (AutoML) has emerged to deal with the selection and configuration
of algorithms for a given learning task. With the progression of AutoML, several effective
methods were introduced, especially for traditional classification and regression
problems. Apart from the AutoML success, several issues remain open. One issue, in
particular, is the lack of ability of AutoML methods to deal with different types
of data. Based on this scenario, this paper approaches AutoML for multi-label classification
(MLC) problems. In MLC, each example can be simultaneously associated to several class
labels, unlike the standard classification task, where an example is associated to
just one class label. In this work, we provide a general comparison of five automated
multi-label classification methods - two evolutionary methods, one Bayesian optimization
method, one random search and one greedy search - on 14 datasets and three designed
search spaces. Overall, we observe that the most prominent method is the one based
on a canonical grammar-based genetic programming (GGP) search method, namely Auto-MEKA_{GGP.} Auto-MEKA_{GGP} presented the best average results in our comparison and was statistically better
than all the other methods in different search spaces and evaluated measures, except
when compared to the greedy search method.

### Do sophisticated evolutionary algorithms perform better than simple ones?

Evolutionary algorithms (EAs) come in all shapes and sizes. Theoretical investigations
focus on simple, bare-bones EAs while applications often use more sophisticated EAs
that perform well on the problem at hand. What is often unclear is whether a large
degree of algorithm sophistication is necessary, and if so, how much performance is
gained by adding complexity to an EA. We address this question by comparing the performance
of a wide range of theory-driven EAs, from bare-bones algorithms like the (1+1) EA,
a (2+1) GA and simple population-based algorithms to more sophisticated ones like
the (1+(*λ,λ*)) GA and algorithms using fast (heavy-tailed) mutation operators, against sophisticated
and highly effective EAs from specific applications. This includes a famous and highly
cited Genetic Algorithm for the Multidimensional Knapsack Problem and the Parameterless
Population Pyramid for Ising Spin Glasses and MaxSat. While for the Multidimensional
Knapsack Problem the sophisticated algorithm performs best, surprisingly, for large
Ising and MaxSat instances the simplest algorithm performs best. We also derive conclusions
about the usefulness of populations, crossover and fast mutation operators. Empirical
results are supported by statistical tests and contrasted against theoretical work
in an attempt to link theoretical and empirical results on EAs.

### Solving constrained combinatorial reverse auctions using MOEAs: a comparative study

Traditional Combinatorial Reverse Auctions (CRAs) (multiple items and single or multiple attributes) have been effectively adopted in several real-world applications. However, looking for the best solution (a set of winning sellers) is difficult to solve due to CRAs complexity. The use of exact algorithms is quite unsuitable in some real-life auctions due to the exponential time cost of these algorithms. Hence, we have opted for multi-objective evolutionary optimization methods (MOEAs) to find the best compromising solutions. This paper makes a comparative study between different MOEAs to solve the Problem of Determination of Winners (WDP) in a Multi Attribute Combinatorial Reverse Auctions (MACRA) of several items with several attributes, establishing a model inspired by a WDP found in the literature. Six real problems of purchasing electronic products of different complexities are considered. The algorithms were assessed according to MOEA evaluation metrics and according to the best auction solution.

### Journey to the center of the linear ordering problem

A number of local search based algorithms have been designed to escape from the local optima, such as, iterated local search or variable neighborhood search. The neighborhood chosen for the local search as well as the escape technique play a key role in the performance of these algorithms. Of course, a specific strategy has a different effect on distinct problems or instances. In this paper, we focus on a permutation-based combinatorial optimization problem: the linear ordering problem. We provide a theoretical landscape analysis for the adjacent swap, the swap and the insert neighborhoods. By making connections to other different problems found in the Combinatorics field, we prove that there are some moves in the local optima that will necessarily return a worse or equal solution. The number of these non-better solutions that could be avoided by the escape techniques is considerably large with respect to the number of neighbors. This is a valuable information that can be included in any of those algorithms designed to escape from the local optima, increasing their efficiency.

### Solving the single row facility layout problem by differential evolution

Differential evolution is an efficient evolutionary optimization paradigm that has shown a good ability to solve a variety of practical problems, including combinatorial optimization ones. Single row facility layout problem is an NP-hard permutation problem often found in facility design, factory construction, production optimization, and other areas. Real-world problems can be cast as large single row facility location problem instances with different high-level properties and efficient algorithms that can solve them efficiently are needed. In this work, the differential evolution is used to solve the single row facility location problem and the ability of three different variants of the algorithm to evolve solutions to various problem instances is studied.

### Multi-layer local optima networks for the analysis of advanced local search-based algorithms

A Local Optima Network (LON) is a graph model that compresses the fitness landscape of a particular combinatorial optimization problem based on a specific neighborhood operator and a local search algorithm. Determining which and how landscape features affect the effectiveness of search algorithms is relevant for both predicting their performance and improving the design process. This paper proposes the concept of multi-layer LONs as well as a methodology to explore these models aiming at extracting metrics for fitness landscape analysis. Constructing such models, extracting and analyzing their metrics are the preliminary steps into the direction of extending the study on single neighborhood operator heuristics to more sophisticated ones that use multiple operators. Therefore, in the present paper we investigate a two-layer LON obtained from instances of a combinatorial problem using bit-flip and swap operators. First, we enumerate instances of NK-landscape model and use the hill climbing heuristic to build the corresponding LONs. Then, using LON metrics, we analyze how efficiently the search might be when combining both strategies. The experiments show promising results and demonstrate the ability of multi-layer LONs to provide useful information that could be used for in metaheuristics based on multiple operators such as Variable Neighborhood Search.

### Just-in-time batch scheduling subject to batch size

This paper considers single-machine just-in-time scheduling of jobs that may be grouped into batches subject to a constraint on batches' weights. A job has a weight, due date, and earliness and tardiness penalties per unit time. A batch's processing time is determined by its jobs. Each job inherits its batch's completion time. The objective is to minimize the weighted sum of earliness and tardiness penalties of all jobs. This problem is challenging: Jobs-to-batch assignment changes the batch's processing time; thus, affects the structure of the entire solution and most importantly of its cost components. This problem is an excellent benchmark for testing linkage learning techniques, which exploit a problem's structure. We propose a matheuristic LTGA, which integrates evolutionary algorithms with mixed-integer programming (MIP). It builds a linkage tree that extracts the dependency among decision variables of MIP solutions. We compare its performance to a state of the art matheuristic CMSA, which combines the learning component of an ant colony system (ACS) with MIP within a construct, solve, merge, and adapt framework. It uses knowledge extracted from ACS' ants to construct a restricted MIP, solves it efficiently, and feeds it back to ACS. Computational tests indicate that LTGA outperforms MIP solvers and CMSA.

### Advanced statistical analysis of empirical performance scaling

Theoretical running time complexity analysis is a widely adopted method for studying
the scaling behaviour of algorithms. However, theoretical analysis remains intractable
for many high-performance, heuristic algorithms. Recent advances in statistical methods
for empirical running time scaling analysis have shown that many state-of-the-art
algorithms can achieve significantly better scaling in practice than expected. However,
current techniques have only been successfully applied to study algorithms on randomly
generated instance sets, since they require instances that can be grouped into "bins",
where each instance in a bin has the same size. In practice, real-world instance sets
with this property are rarely available. We introduce a novel method that overcomes
this limitation. We apply our method to a broad range of scenarios and demonstrate
its effectiveness by revealing new insights into the scaling of several prominent
algorithms; *e.g.*, the SAT solver lingeling often appears to achieve *sub-polynomial* scaling on prominent bounded model checking instances, and the training times of
scikit-learn's implementation of SVMs scale as a lower-degree polynomial than expected
(≈ 1.51 instead of 2).

### Golden parameter search: exploiting structure to quickly configure parameters in parallel

Automated algorithm configuration procedures such as SMAC, GGA++ and irace can often
find parameter configurations that substantially improve the performance of state-of-the-art
algorithms for difficult problems - *e.g.*, a three-fold speedup in the running time required by EAX, a genetic algorithm, to
find optimal solutions to a set of widely studied TSP instances. However, it is usually
recommended to provide these methods with running time budgets of one or two days
of wall-clock time as well as dozens of CPU cores. Most general-purpose algorithm
configuration methods are based on powerful meta-heuristics that are designed for
challenging and complex search landscapes; however, recent work has shown that many
algorithms appear to have parameter configuration landscapes with a relatively simple
structure. We introduce the golden parameter search (GPS) algorithm, an automatic
configuration procedure designed to exploit this structure while optimizing each parameter
semi-independently in parallel. We compare GPS to several state-of-the-art algorithm
configurators and show that it often finds similar or better parameter configurations
using a fraction of the computing time budget across a broad range of scenarios spanning
TSP, SAT and MIP.

### Why many travelling salesman problem instances are easier than you think

While there are many inexact heuristics for generating high quality solutions to the Travelling Salesman Problem, our understanding of why these methods are effective and efficient is still limited. This paper looks at two population based heuristics: the EAX algorithm and the Mixing GA using partition crossover. We show that the local optima used to construct the initial population are also sampling edges found in the global optimum at an extremely high rate: in the majority of TSP instances, the number of global edges in the initial population is more than 73%. Next, we look at how recombination operators increase the representation of edges from the global optimum in the population, or increase the number of global edges in the best solutions in the population. We also look at TSP instances that are more difficult to solve, and again we find that edge frequency information can help to explain algorithm performance. Finally we use these result to suggest new strategies for generating high quality solutions for Travelling Salesman Problems.

### Automatic decomposition of mixed integer programs for lagrangian relaxation using a multiobjective approach

This paper presents a new method to automatically decompose general Mixed Integer Programs (MIPs). To do so, we represent the constraint matrix for a general MIP problem as a hypergraph and relax constraints by removing hyperedges from the hypergraph. A Breadth First Search algorithm is used to identify the individual partitions that now exist and the resulting decomposed problem. We propose that good decompositions have both a small number of constraints relaxed and small subproblems in terms of the number of variables they contain. We use the multiobjective Nondominated Sorting Genetic Algorithm II (NSGA-II) to create decompositions which minimize both the size of the subproblems and the number of constraints relaxed. We show through our experiments the types of decompositions our approach generates and test empirically the effectiveness of these decompositions in producing bounds when used in a Lagrangian Relaxation framework. The results demonstrate that the bounds generated by our decompositions are significantly better than those attained by solving the Linear Programming relaxation, as well as the bounds found via random and greedy constraint relaxation and decomposition generation.

### Specific single- and multi-objective evolutionary algorithms for the chance-constrained knapsack problem

The chance-constrained knapsack problem is a variant of the classical knapsack problem
where each item has a weight distribution instead of a deterministic weight. The objective
is to maximize the total profit of the selected items under the condition that the
weight of the selected items only exceeds the given weight bound with a small probability
of *α.* In this paper, we consider problem-specific single-objective and multi-objective
approaches for the problem. We examine the use of heavy-tail mutations and introduce
a problem-specific crossover operator to deal with the chance-constrained knapsack
problem. Empirical results for single-objective evolutionary algorithms show the effectiveness
of our operators compared to the use of classical operators. Moreover, we introduce
a new effective multi-objective model for the chance-constrained knapsack problem.
We use this model in combination with the problem-specific crossover operator in multi-objective
evolutionary algorithms to solve the problem. Our experimental results show that this
leads to significant performance improvements when using the approach in evolutionary
multi-objective algorithms such as GSEMO and NSGA-II.