The cost of a coevolutionary algorithm (CoEA) can be prohibitively expensive if every pairwise combination of individuals is evaluated when selecting parents. Many CoEAs mitigate this cost by employing tournament selection, where each parent is selected based on the outcome of a small tournament of randomly sampled individuals. It has been proven that classical evolutionary algorithms using tournaments even of size 2 efficiently optimise a wide range of objective functions, including those that decompose into reasonable fitness levels. It is therefore surprising that we prove that this robustness does not always extend to CoEAs, showing that there exist games with payoff landscapes that have analogous decompositions for which optimal play is unlikely to be discovered within eΩ(λ/k2) payoff evaluations by a CoEA using population size λ and tournament size k.

Extending the black-box complexity framework, we consider multistage stochastic optimisation problems under recourse. Such problems ask for a solution to an optimisation problem under uncertainty, where once the uncertainty is (partially) observed, in one or more stages, a stage-by-stage set of 'recourse' actions may be applied to repair the solution. These problems have been studied in the optimisation literature for decades, and applications include multistage portfolio investment, routing under uncertainty, and (dynamic) rescheduling. To facilitate rigorous complexity analysis of these problems in a black-box setting, we develop a precise, broad framework enabling us to describe what information is exchanged between the black-box and the optimisation algorithm, and what solution concept is used. To illustrate the power of the technique, we develop runtime bounds for evolutionary algorithms applied to stochastic optimisation problems with recourse. The theoretical results are complemented by experiments.

Due to their complex dynamics, combinatorial games are a key test case and application for algorithms that train game playing agents. Among those algorithms that train using self-play are coevolutionary algorithms (CoEAs). However, the successful application of CoEAs for game playing is difficult due to pathological behaviours such as cycling, an issue especially critical for games with intransitive payoff landscapes. Insight into how to design CoEAs to avoid such behaviours can be provided by runtime analysis. In this paper, we push the scope of runtime analysis for CoEAs to combinatorial games, proving a general upper bound for the number of simulated games needed for a simple estimation of distribution algorithm to discover (with high probability) an optimal strategy. This result applies to any impartial combinatorial game, and for many games the implied bound is polynomial or quasipolynomial as a function of the number of game positions. After proving the main result, we provide several applications to simple well-known games: Nim, Chomp, Silver Dollar, and Turning Turtles. As the first runtime analysis for CoEAs on combinatorial games, this result is a critical step towards a comprehensive theoretical framework for coevolution.

While some common fitness landscape characteristics are critical when determining the runtime of evolutionary algorithms (EAs), the relationship between fitness landscape structure and the runtime of EAs is poorly understood. Recently, Dang, Eremeev, and Lehre introduced a classification of pseudo-Boolean problems showing that "sparsity" of local optima and the "density" of fitness valleys can be crucial characteristics when determining the runtime of EAs Dang et al. (in Proceedings of the Genetic and Evolutionary Computation Conference. Association for Computing Machinery, New York, NY, USA, GECCO'21, pp 1133-1141, 10.1145/3449639.3459398, 2021c). However, their approach could only classify some classes of pseudo-Boolean functions and thus defined an incomplete hierarchy. We generalise the previous work to a complete hierarchy for all pseudo-Boolean functions, denoted Slo[Formula: see text]. The hierarchy is consistent with existing results for the runtime of EAs. The easiest problems are in Slo[Formula: see text] for [Formula: see text] and [Formula: see text]. As we increase [Formula: see text] and decrease [Formula: see text], the function class contains more interesting functions, including instances of hard combinatorial optimisation problems and problems perturbed by static noise. For [Formula: see text] and [Formula: see text] the problem class contains every problem, including problems closed under permutation (No Free Lunch). Problem classes where local optima sparsity exceed fitness valley density are shown to have exponential black-box complexity. We also study how random perturbations of a function can change its classification. E.g., randomly perturbing search points in OneMax with constant probability leads to a problem class that can still be optimised efficiently with appropriately tuned non-elitist EAs.

The maximin optimisation problem, inspired by Von Neumann’s work (von Neumann 1928) and widely applied in adversarial optimisation, has become a key research area in machine learning. Gradient Descent Ascent (GDA) is a common method for solving these problems but requires the pay-off function to be differentiable, making it unsuitable for discrete or binary functions that often occur in game-theoretical scenarios. Co-evolutionary algorithms (CoEAs), which are derivative-free, offer an alternative to these problems. However, the theoretical understanding of CoEAs is still limited. This paper provides the first rigorous runtime analysis of CoEAs with pairwise dominance on binary two-player zero-sum games (or maximin problems), specifically focusing on the DIAGONAL game. The mathematical analysis rigorously shows that the PDCoEA can efficiently find the optimum in polynomial runtime with high probability under low mutation rates and large population sizes. Empirical evidence also identifies an error threshold where higher mutation rates lead to inefficiency. In contrast, single-pair-individual algorithms, i.e., RLS-PD and (1+1)-CoEAs, fail to find the optimum in polynomial time. These findings highlight the usefulness of pairwise dominance, low mutation rates, and large populations in maintaining a “co-evolutionary arms race”.

Coevolutionary algorithms are a family of black-box optimisation algorithms with many applications in game theory. We study a coevolutionary algorithm on an important class of games in game theory: potential games. In these games, a real-valued function defined over the entire strategy space encapsulates the strategic choices of all players collectively. We present the first theoretical analysis of a coevolutionary algorithm on potential games, showing a runtime guarantee that holds for all exact potential games, some weighted and ordinal potential games, and certain non-potential games. Using this result, we show a polynomial runtime on singleton congestion games. Furthermore, we show that there exist games for which coevolutionary algorithms find Nash equilibria exponentially faster than best or better response dynamics, and games for which coevolutionary algorithms find better Nash equilibria as well. Finally, we conduct experimental evaluations showing that our algorithm can outperform widely used algorithms, such as better response on random instances of singleton congestion games, as well as fictitious play, counterfactual regret minimisation (CFR), and external sampling CFR on dynamic routing games.

Most methods for finding a Nash equilibrium rely on procedures that operate over the entire action space, making them infeasible for settings with too many actions to be searched exhaustively. Randomised search heuristics such as coevolutionary algorithms offer benefits in such settings, however they lack many of the theoretical guarantees established for exhaustive methods such as zero-regret learning. We address this by developing a method for proving necessary and sufficient conditions for a coevolutionary algorithm to be stable, in the sense that it reliably retains a Nash equilibrium following discovery. As the method provides bounds that are adapted to both application and algorithm instance, it can be used as a practical tool for parameter configuration. We additionally show how bounds on regret may be deduced from our results and undertake corresponding empirical analysis.

Competitive coevolutionary algorithms (CoEAs) have a natural application to problems that are adversarial or feature strategic interaction. However, there is currently limited theoretical insight into how to avoid pathological behaviour associated with CoEAs. In this paper we use impartial combinatorial games as a challenging domain for CoEAs and provide a corresponding runtime analysis. By analysing how individuals capitalise on the mistakes of their opponents, we prove that the Univariate Marginal Distribution Algorithm finds (with high probability) an optimal strategy for a game called Reciprocal LeadingOnes within $O(n^2\log^3{n})$ game evaluations, a significant improvement over the best known bound of $O(n^5\log^2{n})$. Critical to the analysis is the introduction of a novel stabilising operator, the impact of which we study both theoretically and empirically.

Abstract Competitive co-evolutionary algorithms (CoEAs) do not rely solely on an external function to assign fitness values to sampled solutions. Instead, they use the aggregation of outcomes from interactions between competing solutions allowing to rank solutions and make selection decisions. This makes CoEAs a useful tool for optimisation problems that have intrinsically interactive domains. Over the past decades, many ways to aggregate the outcomes of interactions have been considered. At the moment, it is unclear which of these is the best choice. Previous research is fragmented and most of the fitness aggregation methods (fitness measures) proposed have only been studied empirically. We argue that a proper understanding of the dynamics of CoEAs and their fitness measures can only be achieved through rigorous analysis of their behaviour. In this work we make a step towards this goal by using runtime analysis to study two commonly used fitness measures. We show a dichotomy in the behaviour of a $$(1, \lambda )$$ ( 1 , λ ) CoEA when optimising a Bilinear problem. The algorithm finds a solution near the Nash equilibrium in polynomial time with high probability if the worst interaction is used as a fitness measure but is inefficient if the average of all interactions is used instead.

Abstract The usual approach in runtime analysis is to derive estimates on the number of fitness function evaluations required by a method until a suitable element of the search space is found. One justification for this is that in real applications, fitness evaluation often contributes the most computational effort. A tacit assumption in this approach is that this effort is uniform and static across the search space. However, this assumption often does not hold in practice: some candidates may be far more expensive to evaluate than others. This might occur, for example, when fitness evaluation requires running a simulation or training a machine learning model. Despite the availability of a wide range of benchmark functions coupled with various runtime performance guarantees, the runtime analysis community currently lacks a solid perspective of handling variable fitness cost. Our goal with this paper is to argue for incorporating this perspective into our theoretical toolbox. We introduce two models of handling variable cost: a simple non-adaptive model together with a more general adaptive model. We prove cost bounds in these scenarios and discuss the implications for taking into account costly regions in the search space.

A common aim in real-world optimisation problems is to seek a solution offering highest performance on expected scenarios, but at the same time guaranteeing an at least acceptable performance on worst-case scenarios. Competitive coevolution evolves a population of solutions alongside a population of difficult scenarios in order to find so-called robust solutions. However, solutions with maximal worst-case performance often exhibit poor performance on more typical scenarios. Existing coevolutionary approaches generally favour such solutions over ones which sacrifice only a small amount of average performance for an almost as large gain in worst-case performance, despite the latter being favourable in most practical applications. We present a new coevolutionary algorithm which treats average performance and worst-case performance as two objectives of a bicriteria optimisation problem and seeks the corresponding Pareto front. Such an algorithm enables the discovery of solutions with strong performance in both of these metrics, which would otherwise be rejected if optimising for only one. Our algorithm constitutes the first coevolutionary approach to this solution concept. We also provide experimental results on the performance of this algorithm on the design of smart controllers for the management of energy flow between buildings, renewable energy sources, and electric vehicles.

A standard aim in game theory is to find a pure or mixed Nash equilibrium. For strategy spaces too large for a Nash equilibrium to be computed classically, this can instead be approached using a co-evolutionary algorithm. How to design coevolutionary algorithms which avoid pathological behaviours (such as cycling or forgetting) on challenging games is then a crucial open problem.

While some common fitness landscape characteristics are critical when determining the runtime of evolutionary algorithms (EAs), the relationship between fitness landscape structure and the runtime of EAs is poorly understood. Recently, Dang et al. (2021) introduced a classification of pseudo-Boolean problems showing that "sparsity" of local optima and the "density" of fitness valleys can be crucial characteristics when determining the runtime of EAs. However, their approach could only classify some classes of pseudo-Boolean functions and thus defined an incomplete hierarchy.

Coevolutionary algorithms are helpful computational abstractions of adversarial behavior and they demonstrate multiple ways that populations of competing adversaries influence one another. We introduce the ability for each competitor's mutation rate to evolve through self-adaptation. Because dynamic environments are frequently addressed with self-adaptation, we set up dynamic problem environments to investigate the impact of this ability. For a simple bilinear problem, a sensitivity analysis of the adaptive method's parameters reveals that it is robust over a range of multiplicative rate factors, when the rate is changed up or down with equal probability. An empirical study determines that each population's mutation rates converge to values close to the error threshold. Mutation rate dynamics are complex when both populations adapt their rates. Large scale empirical self-adaptation results reveal that both reasonable solutions and rates can be found. This addresses the challenge of selecting ideal static mutation rates in coevolutionary algorithms. The algorithm's payoffs are also robust. They are rarely poor and frequently they are as high as the payoff of the static rate to which they converge. On rare runs, they are higher.

Black-box optimisation is one of the important areas in optimisation. The original No Free Lunch (NFL) theorems highlight the limitations of traditional black-box optimisation and learning algorithms, serving as a theoretical foundation for traditional optimisation. No Free Lunch Analysis in adversarial (also called maximin) optimisation is a long-standing problem [45 , 46]. This paper first rigorously proves a (NFL) Theorem for general black-box adversarial optimisation when considering Pure Strategy Nash Equilibrium (NE) as the solution concept. We emphasise the solution concept (i.e. define the optimality in adversarial optimisation) as the key in our NFL theorem. In particular, if Nash Equilibrium is considered as the solution concept and the cost of the algorithm is measured in terms of the number of columns and rows queried in the payoff matrix, then the average performance of all black-box adversarial optimisation algorithms is the same. Moreover, we first introduce black-box complexity to analyse the black-box adversarial optimisation algorithm. We employ Yao’s Principle and our new NFL Theorem to provide general lower bounds for the query complexity of finding a Nash Equilibrium in adversarial optimisation. Finally, we illustrate the practical ramifications of our results on simple two-player zero-sum games. More specifically, no black-box optimisation algorithm for finding the unique Nash equilibrium in two-player zero-sum games can exceed logarithmic complexity relative to search space size. Meanwhile, no black-box algorithm can solve any bimatrix game with unique NE with fewer than a linear number of queries in the size of the payoff matrix.

Abstract Co-evolutionary algorithms have a wide range of applications, such as in hardware design, evolution of strategies for board games, and patching software bugs. However, these algorithms are poorly understood and applications are often limited by pathological behaviour, such as loss of gradient, relative over-generalisation, and mediocre objective stasis. It is an open challenge to develop a theory that can predict when co-evolutionary algorithms find solutions efficiently and reliable. This paper provides a first step in developing runtime analysis for population-based competitive co-evolutionary algorithms. We provide a mathematical framework for describing and reasoning about the performance of co-evolutionary processes. To illustrate the framework, we introduce a population-based co-evolutionary algorithm called PDCoEA, and prove that it obtains a solution to a bilinear maximin optimisation problem in expected polynomial time. Finally, we describe settings where PDCoEA needs exponential time with overwhelmingly high probability to obtain a solution.

Abstract Real-world applications often involve “uncertain” objectives, i.e., where optimisation algorithms observe objective values as a random variables with positive variance. In the past decade, several rigorous analysis results for evolutionary algorithms (EAs) on discrete problems show that EAs can cope with low-level uncertainties, i.e. when the variance of the uncertain objective value is small, and sometimes even benefit from uncertainty. Previous work showed that a large population combined with a non-elitist selection mechanism is a promising approach to handle high levels of uncertainty. However, the population size and the mutation rate can dramatically impact the performance of non-elitist EAs, and the optimal choices of these parameters depend on the level of uncertainty in the objective function. The performance and the required parameter settings for non-elitist EAs in some common objective-uncertainty scenarios are still unknown. We analyse the runtime of non-elitist EAs on two classical benchmark problems OneMax and LeadingOnes in in the one-bit, the bitwise, the Gaussian, and the symmetric noise models, and the dynamic binary value problem (DynBV). Our analyses are more extensive and precise than previous analyses of non-elitist EAs. In several settings, we prove that the non-elitist EAs outperform the current state-of-the-art results. Furthermore, we provide more precise guidance on how to choose the mutation rate, the selective pressure, and the population size as a function of the level of uncertainty.

Many Real-world optimisation tasks are increasingly large-scale optimisation (LSO) problems. Cooperative co-evolutionary algorithms (CoEAs), which involve more than two populations and utilise the divide-and-conquer approach, have been introduced to solve LSO problems more efficiently. However, the behaviour of cooperative CoEAs is not fully understood because the interactions between two or more populations make analysis challenging. Runtime analysis has improved the under-standing of traditional EAs. We argue that using runtime analysis of CoEAs could provide helpful insights, e.g., how their expected runtime depends on alaorithmic design decisions. In this paper, we show that the expected optimisation time of the basic cooperative co-evolutionary (1+1) EA (CC-(1+1) EA) on linear functions is$\Theta(n\log n)$. This solves an open conjecture by (Jansen and Wiegand, 2004). Moreover, empirical analysis is conducted on two more complicated problems: NK − LANDSCAPE and$k$-MAXSAT problems. Our results show that the CC-(1+1) EA perform similarly to the (1+1) EA on these problems. However, adjusting block length allows us to optimise its performance on the NK − LANDSCAPE problem. Our results provide a more precise bound for the expected runtime of CC-(1+1) EA and a more detailed empirical analysis of its behaviour on more complicated inseparable problems.

Co-evolutionary algorithms have found several applications in game-theoretic applications and optimisation problems with an adversary, particularly where the strategy space is discrete and exponentially large, and where classical game-theoretic methods fail. However, the application of co-evolutionary algorithms is difficult because they often display pathological behaviour, such as cyclic behaviour and evolutionary forgetting. These challenges have prevented the broad application of co-evolutionary algorithms.

Real-world optimisation often involves uncertainty. Previous studies proved that evolutionary algorithms (EAs) can be robust to noise when using proper parameter settings, including the mutation rate. However, finding the appropriate mutation rate is challenging if the occurrence of noise (or noise level) is unknown. Self-adaptation is a parameter control mechanism which adjusts mutation rates by encoding mutation rates in the genomes of individuals and evolving them. It has been proven to be effective in optimising unknown-structure and multi-modal problems. Despite this, a rigorous study of self-adaptation in noisy optimisation is missing. This paper mathematically analyses the runtimes of 2-tournament EAs with self-adapting two mutation rates, fixed mutation rates and uniformly chosen mutation rate from two given rates on LeadingOnes with and without symmetric noise. Results show that using self-adaptation achieves the lowest runtime regardless of the presence of symmetric noise. In supplemental experiments, we extend analyses to other types of noise, i.e., one-bit and bit-wise noise. We also consider another self-adaptation mechanism, which adapts the mutation rate from a given interval. Self-adaptive EAs adapt their mutation rate to the noise level and outperform static EAs in these experiments. Overall, self-adaptation can improve the noise-tolerance of EAs in the noise-models studied here.

Competitive co-evolutionary algorithms (CoEAs) do not rely solely on an external function to assign fitness values to sampled solutions. Instead, they use the aggregation of outcomes from interactions between competing solutions allowing to rank solutions and make selection decisions. This makes CoEAs a useful tool for optimisation problems that have intrinsically interactive domains.

While competitive coevolutionary algorithms are ideally suited to model adversarial dynamics, their complexity makes it difficult to understand what is happening when they execute. To achieve better clarity, we introduce a game named DefendIt and explore a previously developed pairwise dominance coevolutionary algorithm named PDCoEA. We devise a methodology for consistent algorithm comparison, then use it to empirically study the impact of population size, the impact of relative budget limits between the defender and attacker, and the impact of mutation rates on the dynamics and payoffs. Our methodology provides reliable comparisons and records of run and multi-run dynamics. Our supplementary material also offers enticing and detailed animations of a pair of players' game moves over the course of a game of millions of moves matched to the same run's populations' payoffs.

Real-world optimisation problems often involve dynamics, where objective functions may change over time. Previous studies have shown that evolutionary algorithms (EAs) can solve dynamic optimisation problems. Additionally, the use of diversity mechanisms, populations, and parallelisation can enhance the performance of EAs in dynamic environments if appropriate parameter settings are utilised. Self-adaptation, which encodes parameters in genotypes of individuals and allows them to evolve together with solutions, can help configure parameters of EAs. This parameter control mechanism has been proved to effectively handle a static problem with unknown structure. However, the benefit of self-adaptation on dynamic optimisation problems remains unknown. We consider a tracking dynamic optima problem, the so-called Dynamic Substring Matching (DSM) problem, which requires algorithms to successively track a sequence of structure-changing optima. Our analyses show that mutation-based EAs with a fixed mutation rate have a negligible chance of tracking these dynamic optima, while the self-adaptive EA tracks them with an overwhelmingly high probability. Furthermore, we provide a level-based theorem with tail bounds, which bounds the chance of the algorithm finding the current optima within a given evaluation budget. Overall, self-adaptation is promising for tracking dynamic optima.

The usual approach in runtime analysis is to derive estimates on the number of fitness function evaluations required by a method until a suitable element of the search space is found. One justification for this is that in real applications, fitness evaluation often contributes the most computational effort. A tacit assumption in this approach is that this effort is uniform and static across the search space. However, this assumption often does not hold in practice: some candidates may be far more expensive to evaluate than others. This might occur, for example, when fitness evaluation requires running a simulation or training a machine learning model.

Theoretical evidence suggests that non-elitist evolutionary algorithms (EAs) with non-linear selection mechanisms can efficiently overcome broad classes of local optima where elitist EAs fail. However, the analysis assumes a weak selective pressure and mutation rates carefully chosen close to the "error threshold", above which they cease to be efficient. On problems easier for hill-climbing, the populations may slow down these algorithms, leading to worse runtime compared with variants of the elitist (1+1) EA.

Co-evolutionary algorithms have a wide range of applications, such as in hardware design, evolution of strategies for board games, and patching software bugs. However, these algorithms are poorly understood and applications are often limited by pathological behaviour, such as loss of gradient, relative over-generalisation, and mediocre objective stasis. It is an open challenge to develop a theory that can predict when co-evolutionary algorithms find solutions efficiently and reliably.

The exploration vs exploitation dilemma is to balance exploring new but potentially less fit regions of the fitness landscape while also focusing on regions near the fittest individuals. For the tunable problem class SparseLocalOpt, a non-elitist EA with tournament selection can limit the percentage of "sparse" local optimal individuals in the population using a sufficiently high mutation rate (Dang et al., 2021). However, the performance of the EA depends critically on choosing the "right" mutation rate, which is problem instance-specific. A promising approach is self-adaptation, where parameter settings are encoded in chromosomes and evolved.

Most discrete evolutionary algorithms (EAs) implement elitism, meaning that they make the biologically implausible assumption that the fittest individuals never die. While elitism favours exploitation and ensures that the best seen solutions are not lost, it has been widely conjectured that non-elitism is necessary to explore promising fitness valleys without getting stuck in local optima. Determining when non-elitist EAs outperform elitist EAs has been one of the most fundamental open problems in evolutionary computation. A recent analysis of a non-elitist EA shows that this algorithm does not outperform its elitist counterparts on the benchmark problem JUMP. We solve this open problem through rigorous runtime analysis of elitist and non-elitist population-based EAs on a class of multi-modal problems. We show that with 3-tournament selection and appropriate mutation rates, the non-elitist EA optimises the multi-modal problem in expected polynomial time, while an elitist EA requires exponential time with overwhelmingly high probability. A key insight in our analysis is the non-linear selection profile of the tournament selection mechanism which, with appropriate mutation rates, allows a small sub-population to reside on the local optimum while the rest of the population explores the fitness valley. In contrast, we show that the comma-selection mechanism which does not have this non-linear profile, fails to optimise this problem in polynomial time. The theoretical analysis is complemented with an empirical investigation on instances of the set cover problem, showing that non-elitist EAs can perform better than the elitist ones. We also provide examples where usage of mutation rates close to the error thresholds is beneficial when employing non-elitist population-based EAs.

It is largely unknown how the runtime of evolutionary algorithms 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.

Real-world optimisation problems often involve uncertainties. In the past decade, several rigorous analysis results for evolutionary algorithms (EAs) on discrete problems show that EAs can cope with low-level uncertainties, and sometimes benefit from uncertainties. Using non-elitist EAs with large population size is a promising approach to handle higher levels of uncertainties. However, the performance of non-elitist EAs in some common fitness-uncertainty scenarios is still unknown.

Abstract We perform rigorous runtime analyses for the univariate marginal distribution algorithm (UMDA) and the population-based incremental learning (PBIL) Algorithm on LeadingOnes. For the UMDA, the currently known expected runtime on the function is $${\mathcal {O}}\left( n\lambda \log \lambda +n^2\right)$$ O n λ log λ + n 2 under an offspring population size $$\lambda =\Omega (\log n)$$ λ = Ω ( log n ) and a parent population size $$\mu \le \lambda /(e(1+\delta ))$$ μ ≤ λ / ( e ( 1 + δ ) ) for any constant $$\delta >0$$ δ > 0 (Dang and Lehre, GECCO 2015). There is no lower bound on the expected runtime under the same parameter settings. It also remains unknown whether the algorithm can still optimise the LeadingOnes function within a polynomial runtime when $$\mu \ge \lambda /(e(1+\delta ))$$ μ ≥ λ / ( e ( 1 + δ ) ) . In case of the PBIL, an expected runtime of $${\mathcal {O}}(n^{2+c})$$ O ( n 2 + c ) holds for some constant $$c \in (0,1)$$ c ∈ ( 0 , 1 ) (Wu, Kolonko and Möhring, IEEE TEVC 2017). Despite being a generalisation of the UMDA, this upper bound is significantly asymptotically looser than the upper bound of $${\mathcal {O}}\left( n^2\right)$$ O n 2 of the UMDA for $$\lambda =\Omega (\log n)\cap {\mathcal {O}}\left( n/\log n\right)$$ λ = Ω ( log n ) ∩ O n / log n . Furthermore, the required population size is very large, i.e., $$\lambda =\Omega (n^{1+c})$$ λ = Ω ( n 1 + c ) . Our contributions are then threefold: (1) we show that the UMDA with $$\mu =\Omega (\log n)$$ μ = Ω ( log n ) and $$\lambda \le \mu e^{1-\varepsilon }/(1+\delta )$$ λ ≤ μ e 1 - ε / ( 1 + δ ) for any constants $$\varepsilon \in (0,1)$$ ε ∈ ( 0 , <

A key challenge to make effective use of evolutionary algorithms (EAs) is to choose appropriate settings for their parameters. However, the appropriate parameter setting generally depends on the structure of the optimization problem, which is often unknown to the user. Nondeterministic parameter control mechanisms adjust parameters using information obtained from the evolutionary process. Self-adaptation-where parameter settings are encoded in the chromosomes of individuals and evolve through mutation and crossover-is a popular parameter control mechanism in evolutionary strategies. However, there is little theoretical evidence that self-adaptation is effective, and self-adaptation has largely been ignored by the discrete evolutionary computation community. Here, we show through a theoretical runtime analysis that a nonelitist, discrete EA which self-adapts its mutation rate not only outperforms EAs which use static mutation rates on LEADINGONESk but also improves asymptotically on an EA using a state-of-the-art control mechanism. The structure of this problem depends on a parameter k, which is a priori unknown to the algorithm, and which is needed to appropriately set a fixed mutation rate. The self-adaptive EA achieves the same asymptotic runtime as if this parameter was known to the algorithm beforehand, which is an asymptotic speedup for this problem compared to all other EAs previously studied. An experimental study of how the mutation-rates evolve show that they respond adequately to a diverse range of problem structures. These results suggest that self-adaptation should be adopted more broadly as a parameter control mechanism in discrete, nonelitist EAs.

We propose a new black-box complexity model for search algorithms evaluating λ search points in parallel. The parallel unary unbiased black-box complexity gives lower bounds on the number of function evaluations every parallel unary unbiased black-box algorithm needs to optimize a given problem. It captures the inertia caused by offspring populations in evolutionary algorithms and the total computational effort in parallel metaheuristics. We present complexity results for LeadingOnes and OneMax. Our main result is a general performance limit: we prove that on every function every λ-parallel unary unbiased algorithm needs at least a certain number of evaluations (a function of problem size and λ) to find any desired target set of up to exponential size, with an overwhelming probability. This yields lower bounds for the typical optimization time on unimodal and multimodal problems, for the time to find any local optimum, and for the time to even get close to any optimum. The power and versatility of this approach is shown for a wide range of illustrative problems from combinatorial optimization. Our performance limits can guide parameter choice and algorithm design; we demonstrate the latter by presenting an optimal λ-parallel algorithm for OneMax that uses parallelism most effectively.

We introduce a new benchmark problem called Deceptive Leading Blocks (DLB) to rigorously study the runtime of the Univariate Marginal Distribution Algorithm (UMDA) in the presence of epistasis and deception. We show that simple Evolutionary Algorithms (EAs) outperform the UMDA unless the selective pressure µ/λ is extremely high, where µ and λ are the parent and offspring population sizes, respectively. More precisely, we show that the UMDA with a parent population size of µ = Ω (log n) has an expected runtime of eΩ(µ) on the DLB problem assuming any selective pressure [EQUATION], as opposed to the expected runtime of O (nλ log λ + n3) for the non-elitist (µ, λ) EA with µ/λ ≤ 1/e. These results illustrate inherent limitations of univariate EDAs against deception and epistasis, which are common characteristics of real-world problems. In contrast, empirical evidence reveals the efficiency of the bi-variate MIMIC algorithm on the DLB problem. Our results suggest that one should consider EDAs with more complex probabilistic models when optimising problems with some degree of epistasis and deception.

We perform a rigorous runtime analysis for the Univariate Marginal Distribution Algorithm on the LeadingOnes function, a well-known benchmark function in the theory community of evolutionary computation with a high correlation between decision variables. For a problem instance of size n, the currently best known upper bound on the expected runtime is O (nλ log λ + n2) (Dang and Lehre, GECCO 2015), while a lower bound necessary to understand how the algorithm copes with variable dependencies is still missing. Motivated by this, we show that the algorithm requires a eΩ(µ) runtime with high probability and in expectation if the selective pressure is low; otherwise, we obtain a lower bound of [MATH HERE] on the expected runtime. Furthermore, we for the first time consider the algorithm on the function under a prior noise model and obtain an O(n2) expected runtime for the optimal parameter settings. In the end, our theoretical results are accompanied by empirical findings, not only matching with rigorous analyses but also providing new insights into the behaviour of the algorithm.

Estimation of Distribution Algorithms (EDAs) are stochastic heuristics that search for optimal solutions by learning and sampling from probabilistic models. Despite their popularity in real-world applications, there is little rigorous understanding of their performance. Even for the Univariate Marginal Distribution Algorithm (UMDA)—a simple population-based EDA assuming independence between decision variables—the optimisation time on the linear problem OneMax was until recently undetermined. The incomplete theoretical understanding of EDAs is mainly due to the lack of appropriate analytical tools. We show that the recently developed level-based theorem for non-elitist populations combined with anti-concentration results yield upper bounds on the expected optimisation time of the UMDA. This approach results in the bound $$\mathcal {O}\left( n\lambda \log \lambda +n^2\right) $$ on the LeadingOnes and BinVal problems for population sizes $$\lambda >\mu =\varOmega (\log n)$$ , where $$\mu $$ and $$\lambda $$ are parameters of the algorithm. We also prove that the UMDA with population sizes $$\mu \in \mathcal {O}\left( \sqrt{n}\right) \cap \varOmega (\log n)$$ optimises OneMax in expected time $$\mathcal {O}\left( \lambda n\right) $$ , and for larger population sizes $$\mu =\varOmega (\sqrt{n}\log n)$$ , in expected time $$\mathcal {O}\left( \lambda \sqrt{n}\right) $$ . The facility and generality of our arguments suggest that this is a promising approach to derive bounds on the expected optimisation time of EDAs.

Understanding how the time complexity of evolutionary algorithms (EAs) depend on their parameter settings and characteristics of fitness landscapes is a fundamental problem in evolutionary computation. Most rigorous results were derived using a handful of key analytic techniques, including drift analysis. However, since few of these techniques apply effortlessly to population-based EAs, most time complexity results concern simple EAs, such as the (1+1) EA. We present the level-based theorem, a new technique tailored to population-based processes. It applies to any nonelitist process where offspring are sampled independently from a distribution depending only on the current population. Given conditions on this distribution, our technique provides upper bounds on the expected time until the process reaches a target state. The technique is demonstrated on pseudo-Boolean functions, the sorting problem, and approximation of optimal solutions in combinatorial optimization. The conditions of the theorem are often straightforward to verify, even for genetic algorithms and estimation of distribution algorithms which were considered highly nontrivial to analyze. The proofs for the example applications are available in the supplementary materials. Finally, we prove that the theorem is nearly optimal for the processes considered. Given the information the theorem requires about the process, a much tighter bound cannot be proved.

Population diversity is essential for avoiding premature convergence in genetic algorithms (GAs) and for the effective use of crossover. Yet the dynamics of how diversity emerges in populations are not well understood. We use rigorous runtime analysis to gain insight into population dynamics and GA performance for the (μ + 1) GA and the Jump test function. We show that the interplay of crossover followed by mutation may serve as a catalyst leading to a sudden burst of diversity. This leads to significant improvements of the expected optimization time compared to mutation-only algorithms like the (1 + 1) evolutionary algorithm. Moreover, increasing the mutation rate by an arbitrarily small constant factor can facilitate the generation of diversity, leading to even larger speedups. Experiments were conducted to complement our theoretical findings and further highlight the benefits of crossover on the function class.

Unlike traditional evolutionary algorithms which produce offspring via genetic operators, Estimation of Distribution Algorithms (EDAs) sample solutions from probabilistic models which are learned from selected individuals. It is hoped that ED As may improve optimisation performance on epistatic fitness landscapes by learning variable interactions.

Real-world optimisation problems are often dynamic. Previously good solutions must be updated or replaced due to changes in objectives and constraints. It is often claimed that evolutionary algorithms are particularly suitable for dynamic optimisation because a large population can contain different solutions that may be useful in the future. However, rigorous theoretical demonstrations for how populations in dynamic optimisation can be essential are sparse and restricted to special cases. This paper provides theoretical explanations of how populations can be essential in evolutionary dynamic optimisation in a general and natural setting. We describe a natural class of dynamic optimisation problems where a sufficiently large population is necessary to keep track of moving optima reliably. We establish a relationship between the population-size and the probability that the algorithm loses track of the optimum.

Population diversity is essential for the effective use of any crossover operator. We compare seven commonly used diversity mechanisms and prove rigorous run time bounds for the (μ+1) GA using uniform crossover on the fitness function Jumpk. All previous results in this context only hold for unrealistically low crossover probability pc=O(k/n), while we give analyses for the setting of constant pc < 1 in all but one case. Our bounds show a dependence on the problem size~$n$, the jump length k, the population size μ, and the crossover probability pc. For the typical case of constant k > 2 and constant pc, we can compare the resulting expected optimisation times for different diversity mechanisms assuming an optimal choice of μ:

Bi-level optimisation problems have gained increasing interest in the field of combinatorial optimisation in recent years. In this paper, we analyse the runtime of some evolutionary algorithms for bi-level optimisation problems. We examine two NP-hard problems, the generalised minimum spanning tree problem and the generalised travelling salesperson problem in the context of parameterised complexity. For the generalised minimum spanning tree problem, we analyse the two approaches presented by Hu and Raidl ( 2012 ) with respect to the number of clusters that distinguish each other by the chosen representation of possible solutions. Our results show that a (1+1) evolutionary algorithm working with the spanning nodes representation is not a fixed-parameter evolutionary algorithm for the problem, whereas the problem can be solved in fixed-parameter time with the global structure representation. We present hard instances for each approach and show that the two approaches are highly complementary by proving that they solve each other's hard instances very efficiently. For the generalised travelling salesperson problem, we analyse the problem with respect to the number of clusters in the problem instance. Our results show that a (1+1) evolutionary algorithm working with the global structure representation is a fixed-parameter evolutionary algorithm for the problem.

Many metaheuristics such as island models and cellular evolutionary algorithms use a network of distributed populations that communicate search points along a spatial communication topology. The idea is to slow down the spread of information, reducing the risk of "premature convergence", and sacrificing exploitation for an increased exploration.

Population-based EAs can optimise pseudo-Boolean functions in expected polynomial time, even when only partial information about the problem is available [7]. In this paper, we show that the approach used to analyse optimisation with partial information extends naturally to optimisation under noise. We consider pseudo-Boolean problems with an additive noise term. Very general conditions on the noise term is derived, under which the EA optimises the noisy function in expected polynomial time. In the case of the Onemax and Leadingones problems, efficient optimisation is even possible when the variance of the noise distribution grows quickly with the problem size.

Real-world optimisation problems are often dynamic. Previously good solutions must be updated or replaced due to changes in objectives and constraints. It is often claimed that evolutionary algorithms are particularly suitable for dynamic optimisation because a large population can contain different solutions that may be useful in the future. However, rigorous, theoretical demonstrations for how populations in dynamic optimisation can be essential are sparse and restricted to special cases.

Estimation of distribution algorithms (EDA) are stochastic search methods that look for optimal solutions by learning and sampling from probabilistic models. Despite their popularity, there are only few rigorous theoretical analyses of their performance. Even for the simplest EDAs, such as the Univariate Marginal Distribution Algorithm (UMDA) which assumes independence between decision variables, there are only a handful of results about its runtime, and results for simple functions such as Onemax are still missing.

The term selection hyper-heuristics refers to a randomised search technique used to solve computational problems by choosing and executing heuristics from a set of pre-defined low-level heuristic components. Selection hyper-heuristics have been successfully employed in many problem domains. Nevertheless, a theoretical foundation of these heuristics is largely missing. Gaining insight into the behaviour of selection hyper-heuristics is challenging due to the complexity and random design of these heuristics. This paper is one of the initial studies to analyse rigorously the runtime of selection hyper-heuristics with a number of the most commonly used learning mechanisms; namely, simple random, random gradient, greedy, and permutation. We derive the runtime of selection hyper-heuristic with these learning mechanisms not only on a classical example problem, but also on a general model of fitness landscapes. This in turn helps in understanding the behaviour of hyper-heuristics. Our results show that all the considered selections hyper-heuristics have roughly the same performance. This suggests that the learning mechanisms do not necessarily improve the performance of hyper-heuristics. A new learning mechanism that improves the performance of hyper-heuristic on our example problem is presented.

Complete and accurate information about the quality of candidate solutions is not always available in real-world optimisation. It is often prohibitively expensive to evaluate candidate solution on more than a few test cases, or the evaluation mechanism itself is unreliable. While evolutionary algorithms are popular methods in optimisation, the theoretical understanding is lacking for the case of partial information. This paper initiates runtime analysis of evolutionary algorithms where only partial information about fitness is available. Two scenarios are investigated. In partial evaluation of solutions, only a small amount of information about the problem is revealed in each fitness evaluation. We formulate a model that makes this scenario concrete for pseudo-Boolean optimisation. In partial evaluation of populations, only a few individuals in the population are evaluated, and the fitness values of the other individuals are missing or incorrect.

Recently, an easy-to-use fitness-level technique was introduced to prove upper bounds on the expected runtime of randomised search heuristics with non-elitist populations and unary variation operators. Following this work, we present a new and much more detailed analysis of the population dynamics, leading to a significantly improved fitness-level technique. In addition to improving the technique, the proof has been simplified.

Computing unique input output (UIO) sequences is a fundamental and hard problem in conformance testing of finite state machines (FSM). Previous experimental research has shown that evolutionary algorithms (EAs) can be applied successfully to find UIOs for some FSMs. However, before EAs can be recommended as a practical technique for computing UIOs, it is necessary to better understand the potential and limitations of these algorithms on this problem. In particular, more research is needed in determining for what instance classes of the problem EAs are feasible, and for what instance classes EAs are provably better than random search strategies. This paper presents rigorous theoretical and numerical analyses of the runtime of the (1 + 1) EA and random search on several selected instance classes of this problem. The theoretical analysis shows firstly, that there are instance classes where the EA is efficient, while random testing fails completely. Secondly, an instance class that is difficult for both random testing and the EA is presented. Finally, a parametrised instance class with tunable difficulty is presented. The numerical study estimates the constants in the asymptotic expressions obtained in the theoretical analysis, and the variability of the runtime. The numerical results fit well with the theoretical results, even for small problem instance sizes. Together, these results provide a first theoretical characterisation of the potential and limitations of the (1 + 1) EA on the problem of computing UIOs.

Evolutionary computation methods, such as evolutionary algorithms or swarm intelligence algorithms, have been successfully applied to a wide range of difficult problems. These include classical NP-hard combinatorial optimization problems and a variety of hard real-world optimization problems. Real-world problems, in particular, are difficult to solve using traditional search methods because often they are nonlinear, highly constrained, multiobjective, and can include a number of uncertainties.

There is a growing body of work in the field of hyper-heuristics. Hyper-heuristics are high level search methodologies that operate on the space of heuristics to solve hard computational problems. A frequently used hyper-heuristic framework mixes a predefined set of low level heuristics during the search process. While most of the work on such selection hyper-heuristics in the literature are empirical, we analyse the runtime of hyper-heuristics rigorously. Our initial analysis shows that mixing heuristics could lead to exponentially faster search than individual (deterministically chosen) heuristics on chosen problems. Both mixing of variation operators and mixing of acceptance criteria are investigated on some selected problems. It is shown that mixing operators is only efficient with the right mixing distribution (parameter setting). Additionally, some of the existing adaptation mechanisms for mixing operators are also evaluated.

Bi-level optimisation problems have gained increasing interest in the field of combinatorial optimisation in recent years. With this paper, we start the runtime analysis of evolutionary algorithms for bi-level optimisation problems. We examine the NP-hard generalised minimum spanning tree problem and analyse the two approaches presented by Hu and Raidl [7] (2012) in the context of parameterised complexity (with respect to the number of clusters) that distinguish each other by the chosen representation of possible solutions. Our results show that a (1+1) EA working with the spanning nodes representation is not a fixed-parameter evolutionary algorithm for the problem, whereas the global structure representation enables to solve the problem in fixed-parameter time. Furthermore, we present hard instances for each approach and show that the two approaches are highly complementary by proving that they solve each other's hard instances very efficiently.

The interplay between mutation and selection plays a fundamental role in the behavior of evolutionary algorithms (EAs). However, this interplay is still not completely understood. This paper presents a rigorous runtime analysis of a non-elitist population-based EA that uses the linear ranking selection mechanism. The analysis focuses on how the balance between parameter η, controlling the selection pressure in linear ranking, and parameter χ controlling the bit-wise mutation rate, impacts the runtime of the algorithm. The results point out situations where a correct balance between selection pressure and mutation rate is essential for finding the optimal solution in polynomial time. In particular, it is shown that there exist fitness functions which can only be solved in polynomial time if the ratio between parameters η and χ is within a narrow critical interval, and where a small change in this ratio can increase the runtime exponentially. Furthermore, it is shown quantitatively how the appropriate parameter choice depends on the characteristics of the fitness function. In addition to the original results on the runtime of EAs, this paper also introduces a very useful analytical tool, i.e., multi-type branching processes, to the runtime analysis of non-elitist population-based EAs.

This paper introduces an easy to use technique for deriving upper bounds on the expected runtime of non-elitist population-based evolutionary algorithms (EAs). Applications of the technique show how the efficiency of EAs is critically dependant on having a sufficiently strong selective pressure. Parameter settings that ensure sufficient selective pressure on commonly considered benchmark functions are derived for the most popular selection mechanisms. Together with a recent technique for deriving lower bounds, this paper contributes to a much-needed analytical tool-box for the analysis of evolutionary algorithms with populations.

Ant Colony Optimization (ACO) is a powerful metaheuristic for solving combinatorial optimization problems. With this paper we contribute to the theoretical understanding of this kind of algorithm by investigating the classical minimum cut problem. An ACO algorithm similar to the one that was proved successful for the minimum spanning tree problem is studied. Using rigorous runtime analyses we show how the ACO algorithm behaves similarly to Karger and Stein's algorithm for the minimum cut problem as long as the use of pheromone values is limited. Hence optimal solutions are obtained in expected polynomial time. On the other hand, we show that high use of pheromones has a negative effect, and the ACO algorithm may get trapped in local optima resulting in an exponential runtime to obtain an optimal solution. This result indicates that ACO algorithms may be inappropriate for finding minimum cuts.

The complexity theory for black-box algorithms, introduced by Droste et al. (2006), describes common limits on the efficiency of a broad class of randomised search heuristics. There is an obvious trade-off between the generality of the black-box model and the strength of the bounds that can be proven in such a model. In particular, the original black-box model allows polynomial complexity for certain NP-complete problems and provides for well-known benchmark problems relatively small lower bounds, which are typically not met by popular search heuristics.

Multi-objective evolutionary algorithms (MOEAs) have become increasingly popular as multi-objective problem solving techniques. An important open problem is to understand the role of populations in MOEAs. We present two simple bi-objective problems which emphasise when populations are needed. Rigorous runtime analysis points out an exponential runtime gap between the population-based algorithm simple evolutionary multi-objective optimiser (SEMO) and several single individual-based algorithms on this problem. This means that among the algorithms considered, only the population-based MOEA is successful and all other algorithms fail.

Despite the wide-spread popularity of estimation of distribution algorithms (EDAs), there has been no theoretical proof that there exist optimisation problems where EDAs perform significantly better than traditional evolutionary algorithms. Here, it is proved rigorously that on a problem called SUBSTRING, a simple EDA called univariate marginal distribution algorithm (UMDA) is efficient, whereas the (1+1) EA is highly inefficient. Such studies are essential in gaining insight into fundamental research issues, i.e., what problem characteristics make an EDA or EA efficient, under what conditions an EDA is expected to outperform an EA, and what key factors are in an EDA that make it efficient or inefficient.

Parameter setting is an important issue in the design of evolutionary algorithms. Experimental work has pointed out that it is often not useful to work with a fixed mutation rate. Therefore it was proposed that the population be ranked according to fitness and the mutation rate of an individual should depend on its rank. The claim is that this allows the algorithm to explore new regions in the search space as well as progress quickly towards optimal solutions. Complementing the experimental investigations, we examine the proposed approach by presenting rigorous theoretical analyses which point out the differences of rank-based mutation compared to a standard approach using a fixed mutation rate. To this end we theoretically explain the behaviour of rank-based mutation on various fitness landscapes proposed in the experimental work and present new significant classes of functions where the use of rank-based mutation may be both beneficial or detrimental compared to fixed mutation strategies.

In this paper, we rigorously analyse how the magnitude and frequency of change may affect the performance of the algorithm (1+1) EAdyn on a set of artificially designed pseudo-Boolean functions, given a simple but well-defined dynamic framework. We demonstrate some counter-intuitive scenarios that allow us to gain a better understanding of how the dynamics of a function may affect the runtime of an algorithm. In particular, we present the function Magnitude, where the time it takes for the (1+1) EAdyn to relocate the global optimum is less than n2log n (i.e., efficient) with overwhelming probability if the magnitude of change is large. For small changes of magnitude, on the other hand, the expected time to relocate the global optimum is eΩ(n) (i.e., highly inefficient). Similarly, the expected runtime of the (1+1) EAdyn on the function Balance is O(n2) (efficient) for a high frequencies of change and nΩ(√n) (highly inefficient) for low frequencies of change. These results contribute towards a better understanding of dynamic optimisation problems in general and show how traditional analytical methods may be applied in the dynamic case.

Computing unique input output (UIO) sequences is a fundamental and hard problem in conformance testing of finite state machines (FSM). Previous experimental research has shown that evolutionary algorithms (EAs) can be applied successfully to find UIOs on some instances. However, before EAs can be recommended as a practical technique for computing UIOs, it is necessary to better understand the potential and limitations of these algorithms on this problem. In particular, more research is needed in determining for what instances of the problem EAs are feasible. This paper presents a rigorous runtime analysis of the (1+1) EA on three classes of instances of this problem. First, it is shown that there are instances where the EA is efficient, while random testing fails completely. Secondly, an instance class that is difficult for both random testing and the EA is presented. Finally, a parametrised instance class with tunable difficulty is presented. Together, these results provide a first theoretical characterisation of the potential and limitations of the (1+1) EA on the problem of computing UIOs.

Multi-objective evolutionary algorithms (MOEAs) have become increasingly popular as multi-objective problem solving techniques. Most studies of MOEAs are empirical. Only recently, a few theoretical results have appeared. It is acknowledged that more theoretical research is needed. An important open problem is to understand the role of populations in MOEAs. We present a simple bi-objective problem which emphasizes when populations are needed. Rigorous runtime analysis point out an exponential runtime gap between a population-based algorithm (SEMO) and several single individual-based algorithms on this problem. This means that among the algorithms considered, only the populationbased MOEA is successful and all other algorithms fail.

The benefits of neutrality may be said to be a disputed topic within evolutionary computation. To gain a better understanding of neutrality with respect to indirect genotype-phenotype mappings, this work analyses the accessibility of neighbouring neutral networks. Accessibility is a mathematical concept introduced in theoretical biology. The concept is applied on a sufficiently simple indirect genotype-phenotype mapping, termed 2PD0L-mapping

The effect of phenotypic complexity on distance correlation plots is investigated for two developmental mappings, a mapping based on L-systems, and a 2D cellular automata mapping. Our treatment of complexity is based on the theory of Kolmogorov complexity. A new genotype sampling algorithm called cross section walk is introduced.