PaperlayerView exact revision on arXiv

Source-linked AI summary

Level-based Analysis of Genetic Algorithms and other Search Processes

Dogan Corus, Duc-Cuong Dang, Anton V. Eremeev, Per Kristian Lehre

arXiv:1407.7663v2cs.NEq-bio.PE

TL;DR

Runtime analysis has focused largely on simplified evolutionary algorithms, leaving population-based processes less well understood. The paper introduces the level-based theorem, which analyzes finite-population non-elitist processes through population-dependent independent sampling and level-progress conditions. It applies the theorem to GAs and UMDA, obtains upper bounds across several optimization settings, and shows those bounds are close to tight given the theorem’s required information.

  • Problem

    Analyses have largely emphasized simplified EAs, while the time-complexity profiles of more sophisticated population-based EAs remain unclear.

  • Method

    The paper models each generation as independent sampling from a distribution depending on the current population and derives bounds using an ordered level partition with progress conditions.

  • Results

    The theorem yields runtime upper bounds for non-elitist processes including GAs and UMDA, and applications show efficient optimisation on benchmark and combinatorial problems.

  • Takeaways & Limitations

    The framework supports analysis of population-based EAs and can guide theory-led design of algorithms satisfying the theorem’s conditions.

  • Takeaways & Limitations

    The theorem’s bound is limited by how accurately the process can be described through its required parameters, and it does not apply when the sampling distribution depends on additional information beyond the current population.

Abstract

from arXiv · show

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 simplified EAs, such as the (1+1) EA. This paper describes the level-based theorem, a new technique tailored to population-based processes. It applies to any non-elitist 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. We demonstrate the technique on several pseudo-Boolean functions, the sorting problem, and approximation of optimal solutions in combinatorial optimisation. The conditions of the theorem are often straightforward to verify, even for Genetic Algorithms and Estimation of Distribution Algorithms which were considered highly non-trivial to analyse. 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.

1 Introduction

The paper addresses the gap between analyses of simplified evolutionary algorithms and the more complex population-based processes used in practice. It introduces a level-based framework that unifies analyses of non-elitist EAs and UMDA, improves runtime bounds, and is nearly optimal for the covered processes.

  • Motivation: Most existing runtime analyses rely on simplified settings such as population size one, no crossover, or other restricted operators.These assumptions leave the time-complexity profiles of population-based EAs unclear.
  • Contribution: The paper presents a common framework for analysing all non-elitist EAs with or without crossover, including UMDA.The framework extends earlier fitness-level analyses of non-elitist evolutionary algorithms.
  • Contribution: The refined analysis improves the leading runtime term by a factor of Ω(δ^-3), where δ measures how quickly good individuals spread through the population.This particularly strengthens results for noisy optimisation, where δ can be as small as 1/n.
  • Applications: The authors provide guidelines and applications for Genetic Algorithms and UMDA on pseudo-Boolean, combinatorial, and local-optimum search problems.The applications include standard functions, a simple combinatorial problem, and approximation of local optima in NP-hard problems.
  • Contribution: The paper proves that the level-based theorem is close to optimal for the evolutionary processes it covers.Given the information required by the theorem, substantially tighter runtime bounds cannot generally be obtained.

2 Main result

The main result models population-based search as independent sampling from a population-dependent distribution and bounds the time to reach a target level. Its conditions describe progress between ordered levels, require a sufficiently large population, and can be applied through a five-step procedure.

  • Abstract algorithmic scheme: Population-based algorithms are represented by a distribution D(P) over X, with each member of the next generation sampled independently from the current population P.The abstract scheme includes a finite search space, population size λ, an initial population, and a mapping from populations to probability distributions.
  • Abstract algorithmic scheme: Genetic Algorithms fit this scheme because selection, crossover, and mutation induce a distribution D(P) for each current population.Conditioned on the current population, every offspring is independently sampled from the same operator-induced distribution.
  • Level-based theorem: The level-based theorem partitions X into ordered levels and gives an expected-runtime upper bound for reaching the final level when its progress conditions hold.The partition need not be fitness-based, although fitness-level partitions are one possible choice.
  • Level-based theorem: Condition (G1) requires upward sampling probability, (G2) requires growth of higher-level individuals, and (G3) requires a sufficiently large population.Together, these conditions connect the current population to the distribution of the next generation.
  • Application methodology: Applying the theorem involves choosing a progress-reflecting partition, setting theorem parameters, determining the population-size requirement, and computing the resulting runtime bound.The procedure may require iterating over parameter settings to obtain the best bound.
  • Illustrative example: For the illustrative algorithm, λ ≥ 72(ln(n) + 9) yields an expected number of created points O(nλ) until the population contains n.The example uses singleton levels and sets zj = 1/3 for every non-final level.

3 Tools for Analysis of Genetic Algorithms

The paper derives corollaries of the level-based theorem for genetic algorithms with non-permanent or permanent crossover, then shows how common selection mechanisms satisfy the required conditions.

  • Non-permanent use of crossover: Corollary 5 adapts the level-based theorem to Algorithm 2 when crossover is used with probability pc < 1.The setting includes pc = 0, where only unary variation operators are used.
  • Non-permanent use of crossover: For pc < 1, selection and mutation conditions ensure progress from A≥j to A≥j+1 with probability at least (1 + δ)γ.The proof combines selection, mutation, and the probability 1 − pc of omitting crossover.
  • Non-permanent use of crossover: The resulting corollary applies beyond Algorithm 2 because any operator can replace crossover without changing the proof.The stated result therefore covers a wider range of algorithms than the original algorithm specification.
  • Permanent use of crossover: Corollary 6 adapts the theorem to permanent crossover, pc = 1, using conditions on selection, crossover, mutation, and population size.Its proof constructs higher-level offspring by selecting parents from suitable levels and applying crossover without destructive mutation.
  • Selection mechanisms: The paper parameterises k-tournament, (µ, λ)-selection, linear ranking, and exponential ranking so their selection conditions hold.Ranking selection is represented by a ranking function α, with linear and exponential forms specified by parameter η.

4 Applications to Genetic Algorithms for Different Problems

The paper applies its level-based analysis to genetic algorithms across pseudo-Boolean optimisation, sorting, local-optimum search, and combinatorial approximation. Under specified mutation, crossover, selection, and population-size conditions, it derives expected-runtime guarantees.

  • Pseudo-Boolean optimisation: Moderate crossover use, pc = 1 − Ω(1), allows Corollary 5 to provide expected-runtime upper bounds for the considered functions and classes.The result applies to the stated GA settings across the analysed pseudo-Boolean functions.
  • Pseudo-Boolean optimisation: Theorem 9 gives an expected-runtime bound for the GA with any crossover operator, bitwise mutation rate χ/n, and the listed selection mechanisms under sufficiently large selection parameters.The required parameters are at least (1 + δ)eχ/(1 − pc), with δ > 0 constant.
  • Pseudo-Boolean optimisation: For OneMax, the expected runtime is O(nλ) when the population size satisfies λ = Ω(ln n).The bound follows after simplifying the level-sum contribution to O(n).
  • Pseudo-Boolean optimisation: Mask-based crossover satisfies condition (C3) with ε = 1/2 for OneMax and LeadingOnes.If both parents have the same LeadingOnes value j, the offspring retains at least j leading ones with probability 1; otherwise it exceeds the smaller parent value with probability at least 1/2.
  • Sorting: For sorting, the GA with moderate crossover, Exchange mutation, suitable selection parameters, and λ ≥ c ln n reaches the SortingInv optimum in O expected time.The supplied passage states the asymptotic result but does not preserve the omitted bound expression.
  • Local optima and combinatorial optimisation: With appropriate parameters, the GA reaches a local optimum after a polynomially bounded expected number of fitness evaluations and reaches a 1/2-approximate Max-SAT or Max-CUT solution within the stated bounds.The local-optimum guarantee uses constant-radius Hamming neighbourhoods; the approximation bounds are O(m′λ ln λ + nm′) for Max-SAT and O(|E|λ ln λ + |V||E|) for Max-CUT.

5 Estimation of Distribution Algorithms

The section applies the level-based framework to UMDA, showing how its sampling process fits the general scheme and yielding runtime bounds for OneMax and LeadingOnes. It also summarizes applications of the framework to genetic algorithms and combinatorial optimization.

  • UMDA framework: UMDA samples a finite population from a frequency vector, then updates that vector from selected solutions; this matches the paper’s general algorithmic scheme.The algorithm is an estimation-of-distribution process with independent bit sampling and population-based frequency updates.
  • UMDA parameters: A positive margin m′ prevents premature convergence to non-optimal fixation; the analysis uses m′ = µ/n.The algorithm uses parent population size µ, offspring population size λ, and margin parameter m′.
  • OneMax: O(nλ ln λ) is the expected optimisation time for UMDA on OneMax when b ln(n) ≤ λ ≤ n/γ0, µ = γ0λ, and m′ = µ/n.The result holds for positive constants δ and γ0 satisfying γ0 ≤ 1/((1+δ)13e).
  • LeadingOnes: UMDA on LeadingOnes has an upper bound with λ ≥ b ln(n), while the previous result requires a larger population and gives a longer runtime bound.The section states that this analysis does not use Feige’s inequality.
  • Combinatorial optimization: The framework also summarizes bounds for GA applications to 1/2-approximation of Max-SAT and Max-CUT.The listed bounds are O(nm′ + m′λ ln λ) for Max-SAT and O(|V||E| + |E|λ ln λ) for Max-CUT.

6 The level-based theorem is almost tight

This section examines how closely the level-based theorem’s upper bounds can match actual runtimes. It shows that the theorem is nearly optimal given only the process information encoded in its parameterisation.

  • Tightness framework: The theorem’s tightness is evaluated by comparing its upper bound with runtimes of operators satisfying the same parameterisation Θ.The class DΘ contains all operators meeting the theorem’s conditions for the chosen levels and parameters.
  • Parameterisation accuracy: The theorem’s bound depends on how accurately the chosen parameterisation describes the process; looser upgrade-probability bounds include slower processes.More precise information, such as the variance of D(Pt), could potentially yield a more accurate runtime bound.
  • Consequences: Given the information supplied through Θ, the lower bound is close to the upper bound, so substantial improvement requires more process information.For some unary-variation settings, the resulting bounds are within O(ln λ) of parallel unbiased black-box lower bounds, and the LeadingOnes bound is asymptotically tight in a stated population-size range.
  • Lower-bound construction: Theorem 16 constructs an operator satisfying the level-based conditions whose expected hitting time approaches the theorem’s upper bound.The construction advances through a sequence of search points across the levels, with transition probabilities determined by the theorem parameters.
  • Proof structure: The process is divided into phases between successive levels, with separate sub-phases for population growth and discovery of the next level.The first sub-phase uses drift analysis, while the second ends geometrically when an individual reaches the next level.

7 Conclusion

The conclusion presents the level-based theorem as a technique for analysing complex non-elitist population processes, including GAs and UMDA. It reports efficient runtimes in several settings, parameter guidance for guaranteed bounds, and near-tightness of the theorem.

  • Conclusion: The paper addresses the need for runtime-analysis techniques tailored to population-based algorithms beyond simplified EAs without populations or crossover.Earlier analyses often focused on variants of the (1+1) EA and other simplified settings.
  • Conclusion: The level-based theorem yields upper bounds for complex non-elitist search processes and shows efficient optimisation by GAs on benchmark and combinatorial problems.For populations that are not overly large, the conclusion states that populations do not cause asymptotic slowdown relative to standard non-population EAs, while parallel evaluation can provide speedups.
  • Conclusion: The theorem’s conditions provide sufficient settings for population size, mutation, crossover, and selection parameters to guarantee a time-complexity bound.This supports theory-led design of EAs that satisfy the theorem’s conditions.
  • Conclusion: The framework extends runtime analysis to UMDA, an EDA with few previous theoretical results, and its upper bounds are shown to be close to tight for a concrete process.The tightness claim is based on lower bounds for the runtime of a concrete process.

Appendix A

The appendix collects standard inequalities used in the paper’s runtime analyses. These lemmas provide logarithmic and exponential bounds and a concentration inequality for independent bounded variables.

  • Appendix A: For x ≥ 0, x ≥ ln(1 + x) ≥ x(1 − x/2).
  • Appendix A: For n ∈ N and x ≥ 0, 1 − (1 − x)^n is bounded below using an exponential expression and the rational form xn/(1 + xn).
  • Appendix A: The appendix states a concentration lemma for sums of independent random variables supported in [0, 1].The variables have finite expectations, and the lemma is cited as a result used in the paper’s analysis.

Appendix B

Appendix B supplies auxiliary lemmas and proof details for drift-based arguments, including the additive drift theorem and binomial inequalities. It also establishes super-martingale reasoning and supporting stochastic-dominance properties used in the analysis.

  • Drift analysis: The additive drift theorem bounds the expected time to reach Z_t ≤ a when the conditional drift before T_a is at least ε toward the target.The proof uses a stopped process S_t := Z_{t∧T_a} + ε(t∧T_a) and shows it is a super-martingale.
  • Drift analysis: The proof handles times before and after T_a separately, then combines the conditional-expectation inequalities to establish the super-martingale property.After the hitting time, the stopped process remains unchanged in expectation; before it, condition 1 supplies the required inequality.
  • Auxiliary probabilistic lemmas: Lemma 23 improves a binomial lower bound when p ≥ (i/λ)(1 + δ), using an auxiliary binomial variable and a monotonicity argument.The proof reduces the claim to monotonicity of h(i), then derives a positive lower bound from polynomial inequalities in δ.
  • Auxiliary probabilistic lemmas: Lemma 24 gives a bound that is tight at x = 0 and x = z, while its z → 0 limit recovers the bound from Lemma 17.The appendix also derives a binomial corollary by applying this inequality with z = cμ.
  • Auxiliary probabilistic lemmas: The appendix proves stochastic dominance for threshold counts: conditioning on at least b samples above j can only increase the distribution of counts above j + c.This yields both a probability inequality and an expectation inequality for every non-decreasing function f.

Appendix C

Appendix C develops results used to assess the tightness of the level-based theorem. It includes a lower-bound version of additive drift analysis and additional binomial estimates.

  • Tightness analysis: The lower-bound additive drift theorem reverses the drift inequality and uses a sub-martingale argument to obtain a runtime lower bound.Its proof starts from the same stopped process as the upper-bound theorem but reverses the inequality directions.
  • Tightness analysis: The proof of the lower-bound theorem overestimates X_Ta by a after applying the sub-martingale argument.This is the key difference from the corresponding upper-bound proof.
  • Binomial estimates: For X ∼ Bin(n,p), it also bounds E[max(X,y)] by max(np,y) + (1/2)√np.The proof uses Jensen’s inequality for the square root.
  • Binomial estimates: For X ∼ Bin(n,p), the appendix bounds the conditional positive count by E[X | X > 0] ≤ np + 1.The result follows by expressing the conditional expectation through Pr(X > 0) and applying an earlier binomial inequality.
Loading 1407.7663v2…