# A New Method for Lower Bounds on the Running Time of Evolutionary Algorithms

@article{Sudholt2013ANM, title={A New Method for Lower Bounds on the Running Time of Evolutionary Algorithms}, author={Dirk Sudholt}, journal={IEEE Transactions on Evolutionary Computation}, year={2013}, volume={17}, pages={418-435} }

In this paper a new method for proving lower bounds on the expected running time of evolutionary algorithms (EAs) is presented. It is based on fitness-level partitions and an additional condition on transition probabilities between fitness levels. The method is versatile, intuitive, elegant, and very powerful. It yields exact or near-exact lower bounds for LO, OneMax, long k-paths, and all functions with a unique optimum. Most lower bounds are very general; they hold for all EAs that only use… Expand

#### 140 Citations

Level-Based Analysis of Genetic Algorithms and Other Search Processes

- Computer Science, Biology
- IEEE Transactions on Evolutionary Computation
- 2018

The level-based theorem is presented, a new technique tailored to population-based processes where offspring are sampled independently from a distribution depending only on the current population that provides upper bounds on the expected time until the process reaches a target state. Expand

Level-Based Analysis of Genetic Algorithms and Other Search Processes

- Computer Science
- IEEE Trans. Evol. Comput.
- 2018

The level-based theorem is presented, a new technique tailored to population-based processes where offspring are sampled independently from a distribution depending only on the current population that provides upper bounds on the expected time until the process reaches a target state. Expand

A Lower Bound Analysis of Population-Based Evolutionary Algorithms for Pseudo-Boolean Functions

- Mathematics, Computer Science
- IDEAL
- 2016

The results imply that the increase of population size, while usually desired in practice, bears the risk of increasing the lower bound of the running time and thus should be carefully considered. Expand

Fitness levels with tail bounds for the analysis of randomized search heuristics

- Mathematics, Computer Science
- Inf. Process. Lett.
- 2014

This work proves that the running time of randomized local search on OneMax is sharply concentrated around n ln n - 0.1159, and supplements the fitness-level method from the analysis of randomized search heuristics with tail bounds, including lower tails. Expand

Refined upper bounds on the expected runtime of non-elitist populations from fitness-levels

- Mathematics, Computer Science
- GECCO
- 2014

A new and much more detailed analysis of the population dynamics is presented, leading to a significantly improved fitness-level technique, which shows that the current bounds on the runtime of EAs with non-elitist populations on many example functions can be significantly reduced. Expand

Running-time analysis of evolutionary programming based on Lebesgue measure of searching space

- Mathematics, Computer Science
- Neural Computing and Applications
- 2016

An analysis of the running time of two EP algorithms based on Gaussian and Cauchy mutations, using an absorbing Markov process model, shows that the upper bounds are impacted by individual number, problem dimension number, searching range, and the Lebesgue measure of the optimal neighborhood. Expand

Lower bounds on the run time of the Univariate Marginal Distribution Algorithm on OneMax

- Computer Science, Mathematics
- Theor. Comput. Sci.
- 2020

A lower bound of Ω ( λ + μ n + n log n ) , where μ and λ are algorithm-specific parameters, on its expected run time is proved, the first direct lower bound on the run time of UMDA. Expand

General Upper Bounds on the Running Time of Parallel Evolutionary Algorithms

- Computer Science
- ArXiv
- 2012

A new method is presented for analyzing the running time of parallel evolutionary algorithms with spatially structured populations based on the fitness-level method, which yields upper bounds on the expected parallel running time and identifies which number of processors yield asymptotically optimal speedups. Expand

On Proportions of Fit Individuals in Population of Mutation-Based Evolutionary Algorithm with Tournament Selection

- Computer Science, Mathematics
- Evolutionary Computation
- 2018

A fitness-level model of a non-elitist mutation-only evolutionary algorithm (EA) with tournament selection that provides upper and lower bounds for the expected proportion of the individuals with fitness above given thresholds is considered. Expand

On Proportions of Fit Individuals in Population of Evolutionary Algorithm with Tournament Selection

- Computer Science
- 2015

A fitness-level model of a non-elitist mutation-only evolutionary algorithm (EA) with tournament selection that provides upper and lower bounds for the expected proportion of the individuals with fitness above given thresholds is considered. Expand

#### References

SHOWING 1-10 OF 61 REFERENCES

General Lower Bounds for the Running Time of Evolutionary Algorithms

- Mathematics, Computer Science
- PPSN
- 2010

We present a new method for proving lower bounds in evolutionary computation based on fitness-level arguments and an additional condition on transition probabilities between fitness levels. The… Expand

Runtime Analysis of the ( + 1) EA on Simple Pseudo-Boolean Functions

- Computer Science, Medicine
- Evolutionary Computation
- 2006

A newproof technique is developed that bounds the runtime of the ( + 1) EA and investigates the stochastic process for creating family trees of individuals; the depth of these trees is bounded and the progress of the population towards the optimum is captured. Expand

Simplified Drift Analysis for Proving Lower Bounds in Evolutionary Computation

- Mathematics, Computer Science
- Algorithmica
- 2010

The present paper picks up Hajek's line of thought to prove a drift theorem that is very easy to use in evolutionary computation and shows how previous analyses involving the complicated theorem can be redone in a much simpler and clearer way. Expand

Optimizing Linear Functions with Randomized Search Heuristics - The Robustness of Mutation

- Mathematics, Computer Science
- STACS
- 2012

The standard mutation probability p = 1/n is optimal for all linear functions, and the (1+1) EA is found to be an optimal mutation-based algorithm that turns out to be surprisingly robust since large neighborhood explored by the mutation operator does not disrupt the search. Expand

Runtime Analysis of the ( μ +1) EA on Simple Pseudo-Boolean Functions

- Mathematics
- 2006

Although Evolutionary Algorithms (EAs) have been successfully applied to optimization in discrete search spaces, theoretical developments remain weak, in particular for population-based EAs. This… Expand

The use of tail inequalities on the probable computational time of randomized search heuristics

- Computer Science, Mathematics
- Theor. Comput. Sci.
- 2012

A new inequality that is based on the general form of the Chernoff inequality and previous methods such as ''fitness-based partitions'' and ''potential functions'', which have been used to analyze the expected running time of RSHs are demonstrated. Expand

A rigorous analysis of the compact genetic algorithm for linear functions

- Mathematics, Computer Science
- Natural Computing
- 2006

First rigorous runtime analyses of a simple EDA, the compact genetic algorithm (cGA), for linear pseudo-Boolean functions on n variables are presented, proving a general lower bound for all functions and a general upper bound forall linear functions. Expand

Time complexity of evolutionary algorithms for combinatorial optimization: A decade of results

- Computer Science
- Int. J. Autom. Comput.
- 2007

This paper presents a survey of the results obtained in the last decade along computational time complexity analyzes of evolutionary algorithms, and the most common mathematical techniques are introduced. Expand

Adaptive population models for offspring populations and parallel evolutionary algorithms

- Mathematics, Computer Science
- FOGA '11
- 2011

We present two adaptive schemes for dynamically choosing the number of parallel instances in parallel evolutionary algorithms. This includes the choice of the offspring population size in a (1+λ) EA… Expand

Tight Bounds on the Optimization Time of the (1+1) EA on Linear Functions

- Computer Science
- ArXiv
- 2011

The standard mutation probability $p=1/n$ is optimal for all linear functions, and the (1+1) EA is found to be an optimal mutation-based algorithm. Expand