×

Estimation of distribution algorithms on non-separable problems. (English) Zbl 1181.62177

Summary: The evolutionary algorithms discussed in this paper do not use crossover, nor mutation. Instead, they estimate and evolve a marginal probability distribution, the only distribution responsible for generating new populations of chromosomes. So far, the analysis of this class of algorithms was confined to proportional selection and additive decomposable functions. Dropping both assumptions, we consider truncation selection and non-separable problems with a polynomial number of distinct fitness values. The emergent modelling is half theoretical - with respect to selection, completely characterized by stochastic calculus – and half empirical – concerning the generation of new individuals. For the latter operator, we sample the chromosomes arbitrarily, one for each selected level of fitness. That is the break-symmetry point, making the difference between the finite and infinite population cases, and ensuring the convergence of the model.

MSC:

62P10 Applications of statistics to biology and medical sciences; meta analysis
90C59 Approximation methods and heuristics in mathematical programming
92D10 Genetics and epigenetics
68W20 Randomized algorithms
68Q25 Analysis of algorithms and problem complexity
62G30 Order statistics; empirical distribution functions
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Abramowitz M., Handbook of Mathematical Functions (1970)
[2] Agapie A., Evolutionary Algorithms – Modeling and Convergence (2007) · Zbl 1126.60059
[3] Bäck T., Parallel Problem Solving from Nature 2 pp 85– (1992)
[4] David H. A., Order Statistics, 2. ed. (1981) · Zbl 0553.62046
[5] DOI: 10.1016/S0304-3975(01)00182-7 · Zbl 1002.68037
[6] Falconer D. S., Introduction to Quantitative Genetics, 3. ed. (1989)
[7] DOI: 10.1162/evco.1999.7.2.173 · Zbl 05412792
[8] DOI: 10.1016/S0004-3702(02)00381-8 · Zbl 1082.68802
[9] Johnson N. L., Continuous Univariate Distributions 1, 2. ed. (1994) · Zbl 0811.62001
[10] Keller G., Equilibrium States in Ergodic Theory (1998) · Zbl 0896.28006
[11] DOI: 10.1023/B:NACO.0000023416.59689.4e · Zbl 1074.68063
[12] Larranaga P., Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation (2001)
[13] Malliavin P., Integration and Probability, 2. ed. (1995)
[14] Mühlenbein H., Parallel Problem Solving from Nature 2 pp 15– (1992)
[15] DOI: 10.1162/evco.1997.5.3.303 · Zbl 05412787
[16] DOI: 10.1162/evco.1999.7.4.353 · Zbl 05412789
[17] DOI: 10.1162/evco.1993.1.1.25 · Zbl 05412791
[18] DOI: 10.1109/TEVC.2003.819419 · Zbl 05452070
[19] DOI: 10.1016/S0167-2789(96)00163-7 · Zbl 0943.92026
[20] Rudolph G., Convergence Properties of Evolutionary Algorithms (1997)
[21] Vose M., The Simple Genetic Algorithm: Foundations and Theory (1999) · Zbl 0952.65048
[22] DOI: 10.1109/TEVC.2003.819431 · Zbl 05452207
[23] DOI: 10.1109/TEVC.2003.820663 · Zbl 05452210
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.