Theory of Randomized Optimization Heuristics

This talk provides an introduction to optimization with multiple objective functions. The concepts of Pareto dominance and solution efficiency are presented, and a number of alternative problem formulations are introduced and discussed. While the set of efficient solutions, and the corresponding non-dominated set, expose the tradeoffs between the different objectives, selecting an overall best solution requires additional preference information to be provided by a Decision Maker, and ultimately changes the problem to be solved. Preference modelling via utility functions and outranking methods is outlined and related to scalarization approaches and population-based methods, respectively, as two important families of multiobjective optimization methods. Finally, some of the challenges posed by the experimental evaluation of such methods are identified, and some additional research topics are highlighted.

In the context of constrained optimization problems, we might face constraints, which yield a boolean (feasible or infeasible). We tackle this issue by building a surrogate model to find an approximation of the constraint boundary. The model is used within the Augmented Lagrangian CMA-ES (AL-CMA-ES) algorithm, which is a competitive algorithm for constrained black-box optimization. In this talk we discuss the achievements as well as the challenges of our approach.

In this talk, I will present the overview of a recent convergence proof of the algorithm CMA-ES (Covariance Matrix Adaptation – Evolution Strategies). More precisely, for a certain class of function called scaling-invariant, the normalization of the states of CMA-ES defines a homogeneous Markov chain, that we prove to be irreducible. When the objective function is ellipsoid (i.e., with ellipsoid level sets) we are able to establish a drift condition and the geometric ergodicity of this Markov chain. We deduce the linear convergence from a law of large numbers.

In this short introductory talk I introduce the main challenges and questions of interest for the analysis of evolutionary algorithms in continuous domains. One major distinction is between evolution strategies with versus without covariance matrix adaptation. While the latter class is well analyzed, the former poses significant challenges. Designing appropriate drift functions reflecting the complex dynamics of online adaptation rules for step size and covariance matrix is an open problem.

Set-quality indicators, which map a point set into a scalar value, are a convenient way to assess (the image of) solution sets in multiobjective optimization. Such indicators may comprise in this scalar value the proximity of the set of points to the Pareto front, as well as information regarding the distribution of points in the set. Performance assessment through quality indicators can be viewed as a transformation of the multiobjective optimization problem into a single-objective one, where the goal is to find a point set, frequently bounded in size, that maximizes the quality indicator. Consequently, each indicator is biased towards some point sets. The study of the theoretical properties of quality indicators allows to characterize the indicator-optimal subsets and, therefore, to understand such biases and their implications in performance assessment and in indicator-based evolutionary multiobjective optimization algorithms. Such theoretical aspects will be discussed in this talk.

Designing a suitable potential function is one of the crucial steps when performing drift analysis. In the context of evolution strategies, it has to capture the complex adaptation mechanism of the algorithm. Especially for evolution strategies with covariance matrix adaptation, the design of such a function imposes a significant challenge. In this flash talk, I will present a novel approach to numerically compute a suitable potential function, that provides a constant drift across a grid of parameter values.

Constraint handling techniques can often be interpreted as (partial) scalarizations of associated multiobjective optimization problems: In a first step, constraints are relaxed and re-interpreted as additional objective functions, and in a second step appropriate scalarizations are used to obtain one (or a series of ) unconstrained problems. This naturally leads to the questions whether constraint handling techniques could be chosen to reflect decision maker preferences, and/or to provide additional trade-off information at little extra cost. A prominent example is the relaxation of constraints in a Lagrangian relaxation framework that corresponds to weighted sum scalarizations of associated multiobjective problems. An interesting alternative are hypervolume scalarizations that have non-linear level curves and can thus generate solution in non-convex parts of the outcome set / the Pareto front, respectively.

In studying randomized search heuristics, a frequent quantity of interest is the first time a (real-valued) stochastic process obtains (or passes) a certain value. Commonly, the processes under investigation show a bias towards this goal, the stochastic drift. Turning an iteration-wise expected bias into a first time of obtaining a value is the main result of drift theorems. This thesis gives an introduction into the theory of stochastic drift, providing examples and reviewing the main drift theorems available. Furthermore, the thesis explains how these methods can be applied in a variety of contexts, including those where drift theorems seem a counter intuitive choice. Later sections examine related methods and approaches.

Recently, the field of quantum computing (QC) has seen impressive results. Since quantum devices require meticulous tuning, a lot of research efforts are guided towards automating these tasks and the field is in some cases moving towards evolution. In this talk, I present some of the background of quantum devices and present some of the tuning problems that arise and how they are challenging the current state of the art in evolutionary algorithms. The two main points i discuss will be: a) as observations are often indirect, fitness evaluations are often based on model fits, that take a lot of time and can introduce systematic errors. b) Due to the underlying discrete state space of digital quantum computers, objective function landscapes are often a series of plateaus with the interesting physics lying on their intersections. I am happy to also host a breakout session to discuss some of these points.

A fundamental question in theory of evolutionary computation is to understand structural properties of fitness landscapes that make them easy or hard for given classes of evolutionary algorithms. This talk introduces the so-called SLO hierarchy which provides a classification of all pseudo-Boolean functions according to the sparsity of local optima and density of fitness valleys. The hardest sub-classes of the hierarchy include problems covered by the No Free Lunch Theorem. A smaller class include problems with exponential unrestricted black-box complexity. An even smaller class cover problems with exponential elitist black box complexity. We also show a positive result, where appropriately tuned non-elitist EAs have polynomial expected runtime.

The Jump_k benchmark was the first problem for which crossover was proven to give a speedup over mutation-only evolutionary algorithms. Jansen and Wegener (2002) proved an upper bound of $O(\text{poly}(n)+4^k/p_c)$ for the ($\mu$+1) Genetic Algorithm (($\mu$+1) GA), but only for unrealistically small crossover probabilities $p_c$. To this date, it remains an open problem to prove similar upper bounds for realistic $p_c$; the best known runtime bound for $p_c=\mathrm{\Omega }(1)$ is $O({(n/\chi )}^{k-1})$, $\chi$ a positive constant.

Using recently developed techniques, we analyse the evolution of the population diversity, measured as sum of pairwise Hamming distances, for a variant of the ($\mu$+1) GA on Jump_k. We show that population diversity converges to an equilibrium of near-perfect diversity. This yields an improved and tight time bound of $O(\mu n\log (k)+4^k/p_c)$ for a range of $k$ under the mild assumptions $p_c=O(1/k)$ and $\mu \in \mathrm{\Omega }(kn)$. For all constant $k$ the restriction is satisfied for some $p_c=\mathrm{\Omega }(1)$. Our work partially solves a problem that has been open for more than 20 years.

If you are playing the coupon collector game, but don’t know how many distinct coupons there are, how do you know when to stop playing? This problem can be seen as a model of deciding termination criteria for randomised heuristic algorithms – a subject that has received very little theoretical treatment to date.

In the balanced allocation problem we wish to allocate m balls (jobs) into n bins (servers) by allowing each ball to choose from some bins sampled uniformly at random. The goal is to maintain a small gap between the maximum load and average load. For the one-choice protocol, where each ball is allocated to a random bin, the gap diverges for large m. However, for the two-choice protocol, where each ball samples two bins and is placed in the least loaded of the two, it was shown that gap is only O(log log n) for all m. This dramatic improvement is widely known as “power of two choices”, and similar effects have been observed in hashing and routing.

In this talk, we will first give some intuition why two-choice maintains such a good balance in practice and theory. Then we will present our recent results in settings where the load information is subject to some noise. For example, the queried load information of bins might be (i) outdated, (ii) subject to some adversarial or random perturbation or (iii) only retrievable by binary queries. We prove that, roughly speaking, if the noise is not too strong, then performance is not affected and the O(log log n) gap bound of two-choice still holds.

Estimation of Distribution Algorithms replace genetic search operators with a constructed probability distribution. In this work, I compare stochastic hill-climber with a Markov Random Field model. The former has a polynomial runtime, but the later is exponential.

In this talk I gave a high-level overview on theory of evolutionary computation on discrete search spaces. The talk reviewed common scenarios in runtime analysis and introduced common evolutionary algorithm designs for discrete search spaces. It described recent hot topics including diversity optimisation, runtime analyses of state-of-the art multi-objective evolutionary algorithms, smart ideas for designing efficient evolutionary algorithms and analyses of complex evolutionary dynamics.

In the field of combinatorial optimization, parameterized complexity theory can offer tools for understanding the influence of problem structure on hardness for evolutionary algorithms by isolating the source of problem complexity to a parameter of the input (distinct from the problem size). It can also offer insight into designing problem-class tailored operators that yield runtime guarantees in some situations. I present some recent ideas on a population-based evolutionary algorithm for solving constrained graph problems that maintains a population of feasible solutions to induced subgraphs and leverages crossover to build up feasible solutions to larger induced subgraphs. This involves two problem-specific steps during evolution: generating a special “template” parent for multi-parent uniform crossover, and an efficient constraint-repair technique inspired by the method of iterative compression from parameterized complexity theory.

A central challenge in solving real-world optimisation problems is the lack of a systematic process. Existing approaches largely either adjust the problem representation to match a specific algorithm (e.g., by discretising) or customise an algorithm to fit the problem. However, their results tend to remain problem-or even instance-specific. The point of this talk was to start an open discussion on the challenges in abstracting real-world applications enough to conduct (theoretical) research while maintaining practical meaningfulness, based on my own experiences in empirical/industry research.

This talk is a self-introduction talk. It introduces my research in four aspects (algorithm choosing, parameter setting, practical problem, and practical algorithms), aiming for efficient and practical evolutionary algorithms with theoretical guarantees.

Co-evolutionary algorithms have been studied empirically for a long time in Evolutionary Computation. Practitioners often report pathological behaviour, such as cycling, disengagement, and forgetting. A survey by Popovici, Bucci, Wiegand and de Jong (2012) identified runtime analysis of co-evolution as an important open problem.

The EC theory group in Birmingham has an ongoing effort in developing runtime analysis for competitive co-evolutionary algorithms. The first results include upper bounds on the runtime of the Pairwise-Dominance Co-Evolutionary Algorithm (PDCoEA) to find an $\epsilon$-approximation to the maximin-solution of some instances of a bilinear problem (Lehre, GECCO2022, Algorithmica2024). Later analyses of bilinear games considered the algorithms RLS-PD (Fajardo, Lehre, Lin, GECCO2023), $(\mu ,\lambda )$ CoEA (Fajardo & Lehre, GECCO2023), and RankDivCoEA (Fajardo & Lehre, PPSN2024). Other games have been considered, including Diagonal (a game with binary payoffs) (Lehre & Lin, PPSN 2024), as well as more complex class of symmetric zero-sum games (Benford & Lehre, GECCO 2024). Some general conclusions from this work include:

• $\mathrm{■}$

  Classical drift analysis and occupation-time bounds can be used to derive runtime. Also, a co-evolutionary level-based theorem is now available, providing upper bounds on the expected runtime of population-based CoEAs (Lehre, 2022GECCO).

• $\mathrm{■}$

  A sufficiently large population or archives can be essential. (1+1) CoEA-type algorithms forget their state (i.e., showing cycling behaviour) on several benchmark problems.

• $\mathrm{■}$

  Population diversity is often important, such as in “Games of Skill” (Benford & Lehre, GECCO24). RankDivCoEA uses a diversity mechanism which promotes unique rankings of opponents.

• $\mathrm{■}$

  Mutation rates can be critical. CoEAs have “error thresholds” (performance breaks down above critical mutation rate) similar to non-elitist EAs. However, mutation rates can be adapted automatically via self-adaptation (Fajardo et al, GECCO24).

• $\mathrm{■}$

  Traditional CoEAs do not always perform well, and it is non-trivial to design new ones. PDCoEA and RankDivCoEA have polynomial expected runtime on Bilinear, and also show excellent empirical performance on several benchmark problems.

The breakout session noted that early influential work, such as Hillis’ co-evolution of sorting networks, provided inadequate details to allow easy replication.