  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 $[\tfrac 14, \tfrac 34]$ 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.

Neural and Evolutionary Computing