Seminars Spring 2021

These seminars were organised by Benjamin Doerr (École Polytechnique) and Per Kristian Lehre (University of Birmingham).

Representing fitness landscapes by valued constraints to understand open-ended evolution

Artem Kaznatcheev (Pennsylvania/Oxford) July 1st 2021, (7pm BST, 20:00 CEST, 2pm EDT) (NB! Note the unusual time.)

Experiments show that evolutionary fitness landscapes can have a rich combinatorial structure due to epistasis. For some landscapes, this structure can produce a computational constraint that prevents evolution from finding local fitness optima thus overturning the traditional assumption that local fitness peaks can always be reached quickly if no other evolutionary forces challenge natural selection. This creates a distinction between easy landscapes where local fitness peaks can be found quickly, and the hard landscapes of open-ended evolution where finding local optima is infeasible (PLS-complete). To understand what separates easy landscape from hard landscapes, we represent landscapes using valued constraints.

First, we show that for fitness landscapes representable by binary Boolean valued constraints there is a minimal necessary constraint graph that can be easily computed. Second, we consider landscapes as equivalent if they allow the same (improving) local search moves; we show that a minimal constraint graph still exists, but is NP-hard to compute.

We then develop several techniques to bound the length of any sequence of improving local search moves. We show that a level-based analysis bound can be obtained from the numerical values of the constraints in the representation, and show how this bound may be tightened by considering equivalent representations. This level-based analysis gives a quadratic bound on the number of improving moves made by any local search for a degree 2 constraint graph. But to extend the quadratic bound to any tree-structured constraint graph requires us to introduce a new encouragement-path analysis instead of the level-based analysis.

Finally, we build two families of examples to show that the conditions in our tractability results are essential. With domain size three, even just a path of binary constraints can model a landscape with an exponentially long sequence of improving moves. With a treewidth-two constraint graph, even with a maximum degree of three, binary Boolean constraints can model a landscape with an exponentially long sequence of improving moves.

This talk is based on joint work with Dave Cohen and Peter Jeavons:

Kaznatcheev, A. (2019). Computational complexity as an ultimate constraint on evolution. Genetics, 212(1), 245-265.

Kaznatcheev, A., Cohen, D., & Jeavons, P. (2020). Representing fitness landscapes by valued constraints to understand the complexity of local search. Journal of Artificial Intelligence Research, 69, 1077-1102.

Provably Good Solutions to the Knapsack Problem via Neural Networks of Bounded Size

Christoph Hertrich (TU Berlin, Germany) June 24 2021, (1pm BST, 14:00 CEST, 8am EDT)

The development of a satisfying and rigorous mathematical understanding of the performance of neural networks is a major challenge in computer science. Against this background, we study the expressive power of neural networks through the example of the classical NP-hard Knapsack Problem. Our main contribution is a class of recurrent neural networks (RNNs) with rectified linear units that are iteratively applied to each item of a Knapsack instance and thereby compute optimal or provably good solution values. We show that an RNN of depth four and width depending quadratically on the profit of an optimum Knapsack solution is sufficient to find optimum Knapsack solutions. We also prove the following tradeoff between the size of an RNN and the quality of the computed Knapsack solution: for Knapsack instances consisting of \(n\) items, an RNN of depth five and width \(w\) computes a solution of value at least \( 1 - O( n^2 / \sqrt{w} )\) times the optimum solution value. Our results build upon a classical dynamic programming formulation of the Knapsack Problem as well as a careful rounding of profit values that are also at the core of the well-known fully polynomial-time approximation scheme for the Knapsack Problem. A carefully conducted computational study qualitatively supports our theoretical size bounds. Finally, we point out that our results can be generalized to many other combinatorial optimization problems that admit dynamic programming solution methods, such as various Shortest Path Problems, the Longest Common Subsequence Problem, and the Travelling Salesperson Problem.

Lazy Parameter Tuning and Control: Choosing All Parameters Randomly From a Power-Law Distribution

Denis Antipov (ITMO University, Saint Petersburg, Russia) June 17 2021, (1pm BST, 14:00 CEST, 8am EDT)

Most evolutionary algorithms have multiple parameters and their values drastically affect the performance. Due to the often complicated interplay of the parameters, setting these values right for a particular problem is a challenging task. This task becomes even more complicated when the optimal parameter values change significantly during the run of the algorithm since then a dynamic parameter choice is necessary.

In this work, we propose a lazy but effective solution, namely choosing all parameter values in each iteration randomly from a suitably scaled power-law distribution. We demonstrate the effectiveness of this approach via runtime analyses of the \((1 + (\lambda, \lambda))\) genetic algorithm with all three parameters chosen in this manner. We show that this algorithm on the one hand can imitate simple hill-climbers like the (1+1) EA, giving the same asymptotic runtime on some simple problems. On the other hand, this algorithm is also very efficient on jump functions, where the best static parameters are very different from those necessary to optimize simple problems. We prove a performance guarantee that is comparable to, and sometimes even better than, the best performance known for static parameters. We complement our theoretical results with a rigorous empirical study confirming what the asymptotic runtime results suggest.

(Joint work with Benjamin Doerr (Laboratoire d’Informatique (LIX), CNRS, cole Polytechnique, Palaiseau, France) and Maxim Buzdalov (ITMO University, Saint Petersburg, Russia))

Populations in Dynamic Optimization

Johannes Lengler (ETH, Switzerland) June 10 2021, (1pm BST, 14:00 CEST, 8am EDT)

I will talk about optimization in an environment where the fitness function changes in every round. While we cannot expect reasonable behaviour in the general case, I will discuss two benchmarks, Dynamic Binary Value and Dynamic Linear Functions, in which we can hope that an optimization heuristic may find the global optimum. We understand the case of the (1+1)-EA very well. However, when we increase the population size and go to the (\(\mu\)+1)-EA, some quite unexpected population dynamics happen. In some cases, a larger population size makes it much easier to find the optimum. In other cases, a larger population size makes it much harder, and practically infeasible to find the opimum. Even for \(\mu=2\), the population dynamics has quite counter-intuitive effects.

Our understanding is good enough to know that the population dynamics must have some strong and counterintuitive effect. But we do not understand the dynamics, and we don’t even have an intuitive explanation where these effects might come from. I will give an overview of the known results, and particularly about the unsolved questions in this setting.

Generalized Jump Functions

Henry Bambury and Antoine Bultel (Ecole Polytechnique, France) June 3 2021, (1pm BST, 14:00 CEST, 8am EDT)

Jump functions are the most studied non-unimodal benchmark in the theory of randomized search heuristics, in particular, evolutionary algorithms (EAs). They have significantly improved our understanding of how EAs escape from local optima. However, their particular structure – to leave the local optimum one can only jump directly to the global optimum – raises the question of how representative such results are.

For this reason, we propose an extended class \(\text{Jump}_{k,\delta}\) of jump functions that contain a valley of low fitness of width \(\delta\) starting at distance \(k\) from the global optimum. We prove that several previous results extend to this more general class: for all \(k = o(n^{1/3})\) and \(\delta < k\), the optimal mutation rate for the (1+1) EA is \(\frac{\delta}{n}\), and the fast (1+1) EA runs faster than the classical (1+1) EA by a factor super-exponential in \(\delta\). However, we also observe that some known results do not generalize: the randomized local search algorithm with stagnation detection, which is faster than the fast (1+1) EA by a factor polynomial in \(k\) on \(\text{Jump}_k\), is slower by a factor polynomial in \(n\) on some \(\text{Jump}_{k,\delta}\) instances.

Computationally, the new class allows experiments with wider fitness valleys, especially when they lie further away from the global optimum.

(Joint work with Benjamin Doerr)

When Move Acceptance Selection Hyper-Heuristics Outperform Metropolis and Elitist Evolutionary Algorithms and When Not

John Alasdair Warwicker (Karlsruhe Institute of Technology, Germany) May 27th 2021, (1pm BST, 14:00 CEST, 8am EDT)

Selection hyper-heuristics (HHs) are automated algorithm selection methodologies that choose between different heuristics during the optimisation process. Recently Selection HHs have been shown to optimise standard unimodal benchmark functions from evolutionary computation in the optimal expected runtime achievable with the available low-level heuristics. In this talk, we extend our understanding of the performance of HHs to the domain of multimodal optimisation by considering a Move Acceptance HH (MAHH) from the literature that can switch between elitist and non-elitist heuristics during the run.

We first identify the range of parameters that allow MAHH to hillclimb efficiently. Afterwards, we use standard multimodal benchmark functions to highlight function characteristics where MAHH is efficient by quickly escaping local optima and ones where it is not. We then design a more general benchmark function class where the size and the gradient of the slopes leading to and away from the local optima can be tuned. This function class also allows us to highlight natural examples of when the use of non-elitism makes a difference between small polynomial expected runtimes versus the exponential runtime required by elitist search heuristics. We complete the picture by providing an example function where the sensitivity of Metropolis to differences in fitness values is crucial, allowing us to illustrate when it is able to significantly outperform the HH.

Since the MAHH is essentially a non-elitist random local search heuristic, the talk is of independent interest to researchers in the fields of artificial intelligence and randomised search heuristics.

(Joint work with Pietro Oliveto and Andrei Lissovoi.)

Non-elitist Evolutionary Algorithms Excel in Fitness Landscapes with Sparse Deceptive Regions and Dense Valleys

Per Kristian Lehre (University of Birmingham, UK) May 6th 2021, (1pm BST, 14:00 CEST, 8am EDT)

It is largely unknown how the runtime of evolutionary algorithms (EAs) depends on fitness landscape characteristics for broad classes of problems. Runtime guarantees for complex and multi-modal problems where EAs are typically applied are rarely available.

We present a parameterised problem class SparseLocalOpt\(_{\alpha,\varepsilon}\), where the class with parameters \(\alpha,\varepsilon\in[0,1]\) contains all fitness landscapes with deceptive regions of sparsity \(\varepsilon\) and fitness valleys of density \(\alpha\). We study how the runtime of EAs depends on these fitness landscape parameters.

We find that for any constant density and sparsity \(\alpha,\varepsilon\in(0,1)\), SparseLocalOpt\(_{\alpha,\varepsilon}\) has exponential elitist (\(\mu\)+\(\lambda\)) black-box complexity, implying that a wide range of elitist EAs fail even for mildly deceptive and multi-modal landscapes. In contrast, we derive a set of sufficient conditions for non-elitist EAs to optimise any problem in SparseLocalOpt\(_{\alpha,\varepsilon}\) in expected polynomial time for broad values of \(\alpha\) and \(\varepsilon\). These conditions can be satisfied for tournament selection and linear ranking selection, but not for (\(\mu\),\(\lambda\))-selection.

(Joint work with Duc-Cuong Dang and Anton Eremeev.)

Analysis of Evolutionary Algorithms on Fitness Function with Time-linkage Property

Weijie Zheng (Southern University of Science and Technology) April 22nd 2021, (1pm BST, 14:00 CEST, 8am EDT)

In real-world applications, many optimization problems have the time-linkage property, that is, the objective function value relies on the current solution as well as the historical solutions. Although the rigorous theoretical analysis on evolutionary algorithms has rapidly developed in recent two decades, it remains an open problem to theoretically understand the behaviors of evolutionary algorithms on time-linkage problems. This paper takes the first step to rigorously analyze evolutionary algorithms for time-linkage functions. Based on the basic OneMax function, we propose a time-linkage function where the first bit value of the last time step is integrated but has a different preference from the current first bit. We prove that with probability \( 1-o(1) \), randomized local search and (1+1) EA cannot find the optimum, and with probability \( 1 -o(1)\), (\(\mu\) + 1) EA is able to reach the optimum.

(Joint work with Huanhuan Chen and Xin Yao).

Tight Bounds on the Expected Runtime of a Standard Steady State Genetic Algorithm

Dirk Sudholt (University of Passau) April 15th 2021, (1pm BST, 14:00 CEST, 8am EDT)

Recent progress in the runtime analysis of evolutionary algorithms (EAs) has allowed the derivation of upper bounds on the expected runtime of standard steady-state Genetic Algorithms (GAs). These upper bounds have shown speed-ups of the GAs using crossover and mutation over the same algorithms that only use mutation operators (i.e., steady-state EAs) both for standard unimodal (i.e., OneMax) and multimodal (i.e., Jump) benchmark functions. The bounds suggest that populations are beneficial to the GA as well as higher mutation rates than the default \(1/n\) rate. However, making rigorous claims was not possible because matching lower bounds were not available. Proving lower bounds on crossover-based EAs is a notoriously difficult task as it is hard to capture the progress that a diverse population can make. We use a potential function approach to prove a tight lower bound on the expected runtime of the (2+1) GA for OneMax for all mutation rates \( c/n \) with \( c < 1.422 \). This provides the last piece of the puzzle that completes the proof that larger population sizes improve the performance of the standard steady-state GA for OneMax for various mutation rates, and it proves that the optimal mutation rate for the (2+1) GA on OneMax is \( (\sqrt{97}-5)/(4n) \approx 1.2122/n \).

Evolutionary Minimization of Traffic Congestion

Martin Krejca (Sorbonne University) April 8th 2021, (1pm BST, 14:00 CEST, 8am EDT)

Traffic congestion is a major issue that can be solved by suggesting drivers alternative routes they are willing to take. This concept has been formalized as a strategic routing problem in which a single alternative route is suggested to an existing one. In this talk, we extend this formalization and introduce the Multiple-Routes problem, which is given a start and a destination and then aims at finding up to \( n \) different routes that the drivers strategically disperse over, minimizing the overall travel time of the system. Due to the NP-hard nature of the problem, we introduce the Multiple-Routes evolutionary algorithm (MREA) as a heuristic solver. We study several mutation and crossover operators and evaluate them on real-world data of the city of Berlin, Germany.

Please note that this work is empirical. However, the formalization of the objective function stems from game theory, with some proven guarantees. Thus, there might be the possibility of approaching our setting also from a theoretical perspective.

slides

Pareto Optimization for Subset Selection with Dynamic Partition Matroid Constraints

Viet Anh Do (University of Adelaide) April 1st 2021, (1pm BST, 14:00 CEST, 8am EDT)

In this talk, we consider the subset selection problems with submodular or monotone discrete objective functions under partition matroid constraints. We focus on POMC, a simple Pareto optimization approach that has been shown to be effective on such problems. Our analysis departs from singular constraint problems and extends to problems with multiple constraints. We add to the existing results of POMC’s worst-case performance with parameters related to the partition matroid constraints. Additionally, we show that when the constraint thresholds change dynamically, the algorithm is able to maintain the approximation guarantees w.r.t. the new constraints and optima in polynomial time. Lastly, we highlight the difficulties in worst-case analyses in the presence of multiple constraints.

Result Diversification by Multi-objective Evolutionary Algorithms

Chao Qian (Nanjing University) March 25th 2021, (1pm GMT, 14:00 CET, 9am EDT)

Given a ground set of items, result diversification aims to select a subset with high ``quality" and ``diversity" while satisfying some constraints. It arises in various real-world applications, such as web-based search, document summarization, feature selection and facility location, just to name a few. The quality can often be characterized by a monotone submodular function, and the diversity is usually measured by the sum of distances between the selected items. In this talk, we will introduce how to apply multi-objective evolutionary algorithms (MOEAs) to solve the result diversification problem. We will show that MOEAs can achieve the (asymptotically) optimal polynomial-time approximation ratio for the problem with cardinality constraints as well as the more general matroid constraints. Furthermore, we will show that when the quality or distance changes dynamically, MOEAs can maintain the optimal approximation ratio in polynomial running time, which addresses the open question proposed by [Borodin et al. TALG'17].