×

Toward a unifying framework for evolutionary processes. (English) Zbl 1343.92364

Summary: The theory of population genetics and evolutionary computation have been evolving separately for nearly 30 years. Many results have been independently obtained in both fields and many others are unique to its respective field. We aim to bridge this gap by developing a unifying framework for evolutionary processes that allows both evolutionary algorithms and population genetics models to be cast in the same formal framework. The framework we present here decomposes the evolutionary process into its several components in order to facilitate the identification of similarities between different models. In particular, we propose a classification of evolutionary operators based on the defining properties of the different components. We cast several commonly used operators from both fields into this common framework. Using this, we map different evolutionary and genetic algorithms to different evolutionary regimes and identify candidates with the most potential for the translation of results between the fields. This provides a unified description of evolutionary processes and represents a stepping stone towards new tools and results to both fields.

MSC:

92D15 Problems related to evolution
92D10 Genetics and epigenetics

Software:

ECJ; GALib
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Affenzeller, M., Population Genetics and Evolutionary Computation: Theoretical and Practical Aspects (2005), Trauner: Trauner Linz
[2] Altenberg, L.; Feldman, M. W., Selection, generalized transmission and the evolution of modifier genes. I. The reduction principle, Genetics, 117, 3, 559-572 (1987), URL 〈http://www.genetics.org/content/117/3/559〉
[3] Altenberg, L., Resolvent positive linear operators exhibit the reduction phenomenon, Proc. Natl. Acad. Sci., 109, 10, 3705-3710 (2012), URL 〈http://www.pnas.org/content/109/10/3705〉 · Zbl 1287.47034
[6] Altenberg, L., Proof of the Feldman-Karlin conjecture on the maximum number of equilibria in an evolutionary system, Theor. Popul. Biol., 77, 4, 263-269 (2010), URL 〈http://www.sciencedirect.com/science/article/pii/S0040580910000183〉 · Zbl 1403.92164
[8] Barton, N. H.; Turelli, M., Natural and sexual selection on many loci, Genetics, 127, 1, 229-255 (1991), URL 〈http://www.genetics.org/content/127/1/229〉
[9] Barton, N. H.; Turelli, M., Effects of genetic drift on variance components under a general model of epistasis, Evolution, 58, 10, 2111-2132 (2004), URL http://onlinelibrary.wiley.com/doi/10.1111/j.0014-3820.2004.tb01591.x/abstract
[10] Beyer, H. G.; Schwefel, H. P., Evolution strategies—a comprehensive introduction, Nat. Comput., 3-52 (2002) · Zbl 1014.68134
[12] Cahon, S.; Melab, N.; Talbi, E.-G., ParadisEOa framework for the reusable design of parallel and distributed metaheuristics, J. Heurist., 10, 3, 357-380 (2004)
[13] Cavalli-Sforza, L. L.; Feldman, M. W., Evolution of continuous variationdirect approach through joint distribution of genotypes and phenotypes, Proc. Natl. Acad. Sci. U. S. A., 73, 5, 1689-1692 (1976), URL 〈http://www.ncbi.nlm.nih.gov/pmc/articles/PMC430365/〉 · Zbl 0349.92020
[14] Chastain, E.; Livnat, A.; Papadimitriou, C.; Vazinari, U., Algorithms, games and evolution, Proc. Natl. Acad. Sci., 111, 29, 10620-10623 (2014) · Zbl 1355.91017
[15] Corus, D.; Dang, D.-C.; Eremeev, A. V.; Lehre, P. K., Level-based analysis of genetic algorithms and other search processes, (Bartz-Beielstein, T.; Branke, J.; Filipico, B.; Smith, J., Parallel Problem Solving from Nature - PPSN XIII, Lecture Notes in Computer Science, vol. 8672 (2014), Springer International Publishing: Springer International Publishing Ljubljana, Slovenia), 912-921
[16] De Jong, K. A., Evolutionary Computation: A Unified Approach (2006), MIT Press: MIT Press Cambridge, MA · Zbl 1106.68093
[17] Dieckmann, U., Can adaptive dynamics invade?, Trends Ecol. Evol., 12, 4, 128-131 (1997)
[18] Doerr, B.; Winzen, C., Towards a complexity theory of randomized search heuristicsranking-based black-box complexity, Comput. Sci.—Theory Appl., 15-28 (2011), URL 〈http://link.springer.com/chapter/10.1007/978-3-642-20712-9_2〉 · Zbl 1330.68110
[22] Droste, S.; Jansen, T.; Wegener, I., Upper and lower bounds for randomized search heuristics in black-box optimization, Theory Comput. Syst., 39, 4, 525-544 (2006) · Zbl 1103.68115
[23] Falconer, D. S.; Mackay, T. F.C., Introduction to Quantitative Genetics (1996), Benjamin Cummings: Benjamin Cummings Essex, UK
[24] Gillespie, J. H., Some properties of finite populations experiencing strong selection and weak mutation, Am. Nat., 121, 5, 691-708 (1983), URL 〈http://www.jstor.org/stable/2460872〉
[25] Goldberg, D. E., Genetic Algorithms in Search Optimization and Machine Learning (1989), Addison-Wesley: Addison-Wesley Boston, MA, USA · Zbl 0721.68056
[26] Harik, G. R.; Lobo, F. G.; Goldberg, D. E., The compact genetic algorithm, IEEE Trans. Evol. Comput., 3, 4, 287-297 (1999)
[28] Jansen, T.; Sudholt, D., Analysis of an asymmetric mutation operator, Evol. Comput., 18, 1, 1-26 (2010)
[30] Kirkpatrick, S.; Gelatt, C. D.; Vecchi, M. P., Optimization by simulated annealing, Science, 220, 671-680 (1983) · Zbl 1225.90162
[31] Kirkpatrick, M.; Johnson, T.; Barton, N., General models of multilocus evolution, Genetics, 161, 4, 1727-1750 (2002), URL 〈http://www.genetics.org/content/161/4/1727〉
[32] Larrañaga, P.; Lozano, J. A., Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation (2002), Kluwer Academic Publishers: Kluwer Academic Publishers New York, NY, USA · Zbl 0979.00024
[33] Lehre, P. K.; Witt, C., Black-box search by unbiased variation, Algorithmica, 1-20 (2012) · Zbl 1264.68221
[35] Lewontin, R. C., The interaction of selection and linkage. I. General considerations; heterotic models, Genetics, 49, 1, 49-67 (1964), URL 〈http://www.genetics.org/content/49/1/49〉
[38] Matessi, C.; Schneider, K. A., Optimization under frequency-dependent selection, Theor. Popul. Biol., 76, 1, 1-12 (2009) · Zbl 1213.92045
[42] Moran, P. A.P., Random processes in genetics, Math. Proc. Camb. Philos. Soc., 54, 01, 60-71 (1958) · Zbl 0091.15701
[43] Nowak, M., Evolutionary Dynamics: Exploring the Equations of Life (2006), Belknap Press: Belknap Press Cambridge, Mass · Zbl 1115.92047
[44] Price, G. R., Selection and covariance, Nature, 227, 520-521 (1970)
[45] Price, G. R., Extension of covariance selection mathematics, Ann. Human Genet., 35, 4, 485-490 (1972), URL 〈http://onlinelibrary.wiley.com/doi/10.1111/j.1469-1809.1957.tb01874.x/abstract〉 · Zbl 0231.92006
[46] Rabani, Y.; Rabinovich, Y.; Sinclair, A., A computational view of population genetics, Random Struct. Algorithm, 12, 4, 313-334 (1998) · Zbl 0955.92023
[49] Schafer, R., Structure of genetic algebras, Am. J. Math., 71, 1, 121-135 (1949) · Zbl 0034.02004
[50] Schneider, K. A., Long-term evolution of polygenic traits under frequency-dependent intraspecific competition, Theor. Popul. Biol., 71, 3, 342-366 (2007) · Zbl 1124.92037
[51] Slatkin, M., Selection and polygenic characters, Proc. Natl. Acad. Sci. U. S. A., 66, 1, 87-93 (1970), URL 〈http://www.ncbi.nlm.nih.gov/pmc/articles/PMC286091/〉
[52] Stadler, B. M.R.; Stadler, P. F.; Wagner, G. P.; Fontana, W., The topology of the possibleformal spaces underlying patterns of evolutionary change, J. Theor. Biol., 213, 2, 241-274 (2001)
[53] Syswerda, G., A study of reproduction in generational and steady state genetic algorithms, (Rawlins, G. J., Foundations of Genetic Algorithms 1991 (FOGA 1) (1991), Morgan Kaufmann: Morgan Kaufmann San Francisco, CA, USA)
[55] Turelli, M.; Barton, N. H., Will population bottlenecks and multilocus epistasis increase additive genetic variance?, Evolution, 60, 9, 1763-1776 (2006), URL 〈http://onlinelibrary.wiley.com/doi/10.1111/j.0014-3820.2006.tb00521.x/abstract〉
[56] Vose, M. D., Random heuristic search, Theor. Comput. Sci., 229, 1, 103-142 (1999) · Zbl 0938.68027
[57] Vose, M. D., The Simple Genetic Algorithm: Foundations and Theory (1999), The MIT Press: The MIT Press Cambridge, Mass · Zbl 0952.65048
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.