Sharp Bounds for Genetic Drift in Estimation of Distribution Algorithms

Abstract

Estimation of Distribution Algorithms (EDAs) are one branch of Evolutionary Algorithms (EAs) in the broad sense that they evolve a probabilistic model instead of a population. Many existing algorithms fall into this category. Analogous to genetic drift in EAs, EDAs also encounter the phenomenon that updates of the probabilistic model not justified by the fitness move the sampling frequencies to the boundary values. This can result in a considerable performance loss. This paper proves the first sharp estimates of the boundary hitting time of the sampling frequency of a neutral bit for several univariate EDAs. For the UMDA that selects $\mu$ best individuals from $\lambda$ offspring each generation, we prove that the expected first iteration when the frequency of the neutral bit leaves the middle range $[\frac{1}{4},\frac{3}{4}]$ and the expected first time it is absorbed in 0 or 1 are both $\Theta (\mu )$. The corresponding hitting times are $\Theta (K^2)$ for the cGA with hypothetical population size $K$. This paper further proves that for PBIL with parameters $\mu$, $\lambda$, and $\rho$, in an expected number of $\Theta (\mu /{\rho }^2)$ iterations the sampling frequency of a neutral bit leaves the interval $[\Theta (\rho /\mu ),1-\Theta (\rho /\mu )]$ and then always the same value is sampled for this bit, that is, the frequency approaches the corresponding boundary value with maximum speed. For the lower bounds implicit in these statements, we also show exponential tail bounds. If a bit is not neutral, but neutral or has a preference for ones, then the lower bounds on the times to reach a low frequency value still hold. An analogous statement holds for bits that are neutral or prefer the value zero.

References in corpus (2)

• A Tight Runtime Analysis for the cGA on Jump Functions---EDAs Can Cross Fitness Valleys at No Extra Cost
• On the Limitations of the Univariate Marginal Distribution Algorithm to Deception and Where Bivariate EDAs might help

Cited by in corpus (11)

• The Runtime of the Compact Genetic Algorithm on Jump Functions
• A Survey on Recent Progress in the Theory of Evolutionary Algorithms for Discrete Optimization
• A Simplified Run Time Analysis of the Univariate Marginal Distribution Algorithm on LeadingOnes
• From Understanding Genetic Drift to a Smart-Restart Parameter-less Compact Genetic Algorithm
• Choosing the Right Algorithm With Hints From Complexity Theory
• Estimation-of-Distribution Algorithms for Multi-Valued Decision Variables
• Runtime Analysis of the Compact Genetic Algorithm on the LeadingOnes Benchmark
• From Understanding Genetic Drift to a Smart-Restart Mechanism for Estimation-of-Distribution Algorithms
• Bivariate Estimation-of-Distribution Algorithms Can Find an Exponential Number of Optima
• When Non-Elitism Meets Time-Linkage Problems
• A Fresh Look at Lamarckian Evolution and the Baldwin Effect