Theory of Randomized Optimization Heuristics

In this talk, I want to discuss a recent joint work with Weijie Zheng (SUSTECH) and Yufei Liu (Polytechnique). The non-dominated sorting genetic algorithm II (NSGA-II) is the most intensively used multi-objective evolutionary algorithm (MOEA) in real-world applications. However, in contrast to several simple MOEAs analyzed also via mathematical means, no such study exists for the NSGA-II so far. In this work, we show that mathematical runtime analyses are feasible also for the NSGA-II. As particular results, we prove that with a population size larger than the Pareto front size by a constant factor, the NSGA-II with two classic mutation operators and three different ways to select the parents satisfies the same asymptotic runtime guarantees as the SEMO and GSEMO algorithms on the basic OneMinMax and LOTZ benchmark functions. However, if the population size is only equal to the size of the Pareto front, then the NSGA-II cannot efficiently compute the full Pareto front (for an exponential number of iterations, the population will always miss a constant fraction of the Pareto front). Our experiments confirm the above findings.

While the theoretical analysis of evolutionary algorithms (EAs) has made significant progress for pseudo-Boolean optimization problems in the last 25 years, only sporadic theoretical results exist on how EAs solve permutation-based problems.

To overcome the lack of permutation-based benchmark problems, we propose a general way to transfer the classic pseudo-Boolean benchmarks into benchmarks defined on sets of permutations. We then conduct a rigorous runtime analysis of the permutation-based $(1+1)$ EA proposed by Scharnow, Tinnefeld, and Wegener (2004) on the analogues of the LeadingOnes and Jump benchmarks. The latter shows that, different from bit-strings, it is not only the Hamming distance that determines how difficult it is to mutate a permutation $\sigma$ into another one $\tau$, but also the precise cycle structure of $\sigma {\tau }^{-1}$. For this reason, we also regard the more symmetric scramble mutation operator. We observe that it not only leads to simpler proofs, but also reduces the runtime on jump functions with odd jump size by a factor of $\mathrm{\Theta }(n)$. Finally, we show that heavy-tailed versions of both operators, as in the bit-string case, lead to speed-ups of order $m^{\mathrm{\Theta }(m)}$ on jump functions with jump size $m$.

Many black-box optimization techniques have a high degree of adaptiveness. But there are problems for which adaptive sampling has only negligible advantages over non-adaptive sampling, e.g., the famous 2-color Mastermind problem studied by Erdös and Renyi (1963).

In this talk I propose a black-box complexity model that allows us to study the minimal number of queries that are needed to optimize a given problem $f$, in dependency of the number of iterations $k$ that the algorithms are allowed to perform.

I will sketch the convergence proof of a minimal elitist variant of the recently proposed Hessian Estimation Evolution Strategy (HE-ES). The main difference as compared with CMA-ES is that the covariance matrix update yields monotonic convergence of the covariance matrix to the inverse Hessian. This strong stability property allows to prove that the algorithm converges at a linear rate to the minimum of a convex quadratic objective function, where the rate is independent of the problem instance. The same holds for CMA-ES, but we are lacking a proof (since 20 years). The proof works in two steps, both of which employ drift arguments. The first step is to prove convergence of the covariance matrix, which works independent of the evolution of mean and step size. The second step is to reduce the convergence proof to recent powerful results for the (1+1)-ES without CMA.

I will present the (to my knowledge) first result on the behavior of an ES facing saddle points. The (1+1)-ES overcomes even rather difficult saddle points, where it could be subjected to convergence prematurely because the success rate is smaller than 1/5, and in fact arbitrarily close to zero.

I will introduce basic problems (in particular convex quadratic functions) and algorithms (the classic (1+1)-ES and a variant with covariance matrix adaptation (CMA)). I will describe the qualitative behavior of evolution strategies with and without CMA on problems with good and bad conditioning. Some aspects of the behavior are well described by theoretical analysis, while others are open problems. I’ll then give a gist of existing analysis methodologies: Markov chains (and a recent way of proving stability), drift, and the IGO framework.

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.

From the paper: Unbalanced Mallows Models for Optimizing Expensive Black-Box Permutation Problems

Expensive black-box combinatorial optimization problems arise in practice when the objective function is evaluated by means of a simulator or a real-world experiment. Since each fitness evaluation is expensive in terms of time or resources, the number of possible evaluations is typically several orders of magnitude smaller than in non-expensive problems. Classical optimization methods are not useful in this scenario. In this talk, we propose and analyze UMM, an estimation-of-distribution (EDA) algorithm based on a Mallows probabilistic model and unbalanced rank aggregation (uBorda). UMM is based on a weighted median for permutations. The core of it is uBorda. Experimental results on black-box versions of LOP and PFSP show that UMM outperforms the solutions obtained by CEGO, a Bayesian optimization algorithm for combinatorial optimization. Nevertheless, a slight modification to CEGO, based on the different interpretations for rankings and orderings, significantly improves its performance, thus producing solutions that are slightly better than those of UMM and dramatically better than the original version. Another benefit of UMM is that its computational complexity increases linearly with both the number of function evaluations and the permutation size, which results in computation times an order of magnitude shorter than CEGO, making it specially useful when both computation time and number of evaluations are limited.

Randomized optimization heuristics (ROHs) are algorithms applied to optimization problems where the objective function is only indirectly accessible, that is, it can only be accessed by evaluating solution candidates. Guided by the quality of such candidates, ROHs aim to iteratively generate solutions of better quality. This raises natural questions such as how quickly an ROH improves its solutions, whether it is capable of finding optimal solutions, or if there are any approaches that generate better solutions more quickly. Theoretical analyzes aim to answer these questions and more.

In this talk, we provide an introduction to theoretical analyzes on ROHs in the discrete domain. We introduce the setting that ROHs are applied in, the so-called black-box setting, and we discuss how theoretical results aim to answer questions about the real-world application of ROHs. To this end, we introduce common theory benchmark functions, ROHs, as well as the mathematical tools used for their analyses. We conclude by deriving a standard run time result, illustrating how problems in this domain are typically approached.

I will discuss several seemingly easy situations in which evolutionary and genetic algorithms can fail. Some of them are rather surprising, since the hardest regions are not always close to the optimum. In particular, I will mention the detrimental effects of large mutation rates or of large population size for optimizing monotone functions, introduce a simple dynamic setting, and discuss how the self-adapting $(1,\lambda )$-EA can fail on OneMax.

In Genetic Programming, it is customary to have population sizes in the order of $\mu =100-1000$. For the next generation, $\lambda =2\mu$ parents are independently selected. In order to select a parent, lexicase selection first removes duplicates in performance space, i.e., individuals which show the same performance on all test cases. Then it picks one test case at random, and removes all candidates which fail on this test case (unless all candidates fail, in which case the test is skipped). This is iterated until only one candidate remains. My two co-authors report that lexicase selection is regarded critically in their community due to its very bad worst-case runtime, but that the runtime in practice is much faster. We investigated why the runtime is fast and found a measure for population diversity such that i) empirically population diversity is large, and ii) a large population diversity guarantees theoretically fast runtimes.

In this flash talk, a gray-box operator tailored for combinatorial optimization problems is presented. The operator is called balanced flip EA, which the mutation operator has been introduced to the specific problem so that the algorithm is extended for better behavior. By applying runtime analysis of both the (1+1) EA and the balanced EA, a tighter upper bound is provided for balanced flip EA as $𝒪({\backslash }^{\ni })$ while the (1+1) EA is as $𝒪({\backslash }^{△})$. Other than the introduction of analysis strategy, the experimental evidence for long bad path to support the partial proof of the lower bound as well as the probability bound for complete bipartite graph has also been discussed. As a result, the flash talk presented the key point that the benefits of gray-box operator should be considered. Especially when it comes to solve the specific problem like combinatorial optimization.

We identify a class of nonconvex functions for which we can show that perturbed gradient descent converges to a global minimum, in contrast to gradient descent without noise that can get stuck in local minima far from a global solution.

We give a brief overview of the used techniques, such as convergence analysis of (stochastic) gradient methods, biased gradients, and randomized smoothing.

Based on joint work with A. Ajalloeian [1] and H. Vardhan [2].

Evolutionary algorithms make countless random decisions during selection, mutation and crossover operations. These random decisions require a steady stream of random numbers, however generating good quality randomness is non-trivial.

We consider the expected number of random bits used throughout a run of an evolutionary algorithm and refer to this as the cost of randomness. We give general bounds on the cost of randomness for mutation-based evolutionary algorithms using 1-bit flips or standard bit mutations using either a naive or a common, more efficient implementation that uses Theta(log n) random bits per mutation. Uniform crossover is a potentially wasteful operator as the number of random bits used equals the Hamming distance of the two parents, which can be up to n. However, we show for a (2+1) GA that optimizes OneMax in expected Theta(n log n) evaluations that the total cost of randomness during all crossover operations on OneMax is only Theta(n).

We hope to show that the cost of randomness may be useful as an additional performance measure, to give new insights into search dynamics and to aid in the design of operators that use randomness more carefully.

This talk presents an ongoing work that aims to develop an analytical study of the Differential Evolution (DE) algorithm behavior. Analytical formulae for the probability of enhancement of and individual in populations of the DE/rand/1/bin and DE/rand/1/exp algorithm versions are developed for the sphere objective function. It is shown that those formulae can be adapted for the study of the algorithm behavior in the optimization of quadratic functions with different relations between the minimal and maximal eigenvalues. In the case of large differences of eigenvalue magnitudes, it is shown that the convergence occurs in different scales, and the formulae approximately hold for the corresponding scale dimension. The known effect of performance degradation as the problem dimension increases is partly explained by the decrease in the probability of enhancement of individuals, as indicated in the formulae. Experimental results show that DE/best algorithm versions, as expected, are able to solve problems of higher dimensions. Further research will be performed in order to examine the convergence dependency with the algorithm parameters.

Dominance move (DoM), a binary quality indicator, can be used in multi-objective and many-objective optimization to compare two solution sets. DoM is very intuitive but hard to calculate due to its combinatorial nature. Different mathematical models are presented and analyzed. A computationally fast approximate approach is also discussed. Computational results are promising and an upper bound analysis for the approximation ratio would be useful.

Problem modelling is often overlooked as the crucial step preceding the practical application of randomised optimisation heuristics (ROHs). In order to make ROHs more accessible in the real world, there is a need to specify how optimisation algorithms interface with the problem instances of interest. In addition, guidance should be provided to practitioners on how problem-specific information can be exposed to the algorithms through such an interface. In other words, such an interface definition should support an associated problem modelling methodology.

From a different perspective, such an interface specification must also support the development of practical algorithms that can be applied directly to any given problem implementing that interface. A brief presentation of two Application Programming Interfaces (APIs) for combinatorial optimisation under development, and of the design principles behind them, was the starting point for a discussion on the potential of such an approach and how theory-friendly it might be.

As a minimal example, we went through IGO framework and NES algorithm, using 1D example $f(x)=x^2$ and Gaussians. We discussed the quantile rescaling technique in detail, and whether it may or may not be understood as a static fitness transformation. We also discussed the role of rescaling the gradient with the Fisher information matrix for achieving linear convergence. We identified potential connections to variance-reduced gradient descent techniques, as well as to the sampling literature. The general impression was that the natural SGD setting with quantile rescaling is too far from the standard analysis of SGD to allow for a straightforward transfer of proof techniques.

We started with a “naive” potential, which is a straightforward extension of the (1+1)-ES potential. We then focused on Armand’s problem and understood that it is a model of the initial phase of optimizing the discus problem. We tried to fix the $log(\Vert m\Vert )$ term to achieve additive drift in this situation, without much success. Therefore, we shifted the discussion to how a multi-stage drift for that situation may work.

We started gathering examples of problems on which comma selection performs differently to plus selection, focusing on theoretically proven examples. Although the topic was originally set to deal with noise, we considered deterministic problems for the most part.

It is known that comma selection in a ($\mu$,$\lambda$) EA does not perform better than plus selection on Jump functions, and this holds for arbitrary population sizes $\mu$ and $\lambda$. On the Cliff function, comma strategies perform well, enabling a (1,$\lambda$) EA to jump down the cliff if all offspring are down the cliff and the algorithm moves towards the global optimum without jumping back up the cliff. For optimal fixed $\lambda$, the best known expected runtime is essentially $n^{3.97\mathrm{\dots }}$ (up to sub-polynomial factors). Self-adjusting $\lambda$ can reduce this to $O(n\log n)$ if a reset mechanism is used that resets $\lambda$ to 1 if it exceeds a given threshold. The effect is similar to using hyperheuristics or ageing where occasionally non-elitist steps are accepted. The structure of the function is quite benign as the gradient past the cliff points towards the global optimum.

It is also known that for large values of $\lambda$, a comma strategy will behave like a plus strategy because there is a high probability of cloning the parent. If $\lambda$ is too small, $\lambda \le (1-\epsilon ){\log }_{\frac{e}{e-1}}n$, optimising any fitness function with a unique optimum takes exponential time. So there is a narrow region for values of $\lambda$ where one can see an advantage of comma selection over plus selection.

We also discussed elitist versus non-elitist algorithms more generally (e.g. tournament selection, self-adaptation and island models). For all algorithms discussed, the crucial issue came down to balancing exploration and exploitation: being able to escape from local optima while also being able to climb hills.

We came to the conclusion that there is a gap between theory and practice as we’re lacking convincing examples (apart from Cliff) where comma selection provably helps, whereas in practice comma strategies seem to be quite popular to escape from local optima. Part of this gap might be caused by theory traditionally aiming to find the exact global optimum, whereas in practice one is usually content with a good approximation of the optimal fitness. Using a fixed-target perspective for less ambitious targets might give a different picture as much smaller values of $\lambda$ might be sufficient.