Genetic Drift

[…] in a finite-sized population the proportion of alleles fluctuates due to stochastic sampling errors, so even in the absence of any selective pressure, the genes will eventually become fixated at one particular allele. – Thierens 19981

Genetic Drift (or just “drift”) is the phenomenon of the progressive loss of genetic information among less salient building blocks. While the algorithm is working hard to converge the salient building blocks, the less salient building blocks are also converging. But because they have lower marginal fitness contribution, they converge by chance (“drift”) alone.

Studies suggest that the expected time for a gene to converge due to genetic drift alone is, in very general terms, proportional to the population size.

According to the Domino Convergence model (Thierens 19981), time complexity to fully converge on the optimal solution is linear  to the encoding length l (i.e., O(l)) (only for an algorithm exhibiting constant selection intensity, read Domino Convergence).

In the absence of other factors, the conclusion might be that as the encoding length increases, we must increase the population size proportionately to ensure that genetic drift does not overtake domino convergence. In practical observation, we observe that the rule generally seems to hold, but that the required adjustment is somewhat less than strictly linear.

So, dilettante beware! We might expect to observe that as our encoding length increases, if our effective population size is not adjusted to compensate, we may find ourselves suffering from the effects of genetic drift.

References

  1. Domino Convergence, Drift, and the Temporal-Salience Structure of Problems – Dirk Thierens, David E. Goldberg, Angela Guimaraes Pereira, 1998