×

Theoretical analysis of steady state genetic algorithms. (English) Zbl 1340.68123

The paper analyses the convergence of the heuristic associated to a special type of genetic algorithm, namely the steady state genetic algorithm (SSGA), considered as a discrete-time dynamical system non-generational model. Inspired by the Markov chain results in finite evolutionary algorithms, conditions are given under which the SSGA heuristic converges to the population consisting of copies of the best chromosome.

MSC:

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
60J20 Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.)
68W20 Randomized algorithms
90C59 Approximation methods and heuristics in mathematical programming
PDF BibTeX XML Cite
Full Text: DOI Link

References:

[1] Agapie, A., Modelling genetic algorithms: from Markov chains to dependence with complete connections, Lect. Notes Comput. Sci., 1498, 3-12, (1998)
[2] Agapie, A., Theoretical analysis of mutation-adaptive evolutionary algorithms, Evol. Comput., 9, 127-146, (2001)
[3] Agapie, A., Estimation of distribution algorithms on non-separable problems, Int. J. Comput. Math., 87, 491-508, (2010) · Zbl 1181.62177
[4] Agapie, A.; Agapie, M.; Rudolph, G.; Zbaganu, G., Convergence of evolutionary algorithms on the n-dimensional continuous space, IEEE Trans. Cybern., 43, 1462-1472, (2013)
[5] Agapie, A.; Agapie, M.; Zbaganu, G., Evolutionary algorithms for continuous space optimization, Int. J. Syst. Sci., 44, 502-512, (2013) · Zbl 1307.93475
[6] L. Davis: Handbook of Genetic Algorithms. Van Nostrand Reinhold, New York, 1991.
[7] Mitavskiy, B.; Rowe, J.; Wright, A. H.; Schmitt, L., Quotients of Markov chains and asymptotic properties of the stationary distribution of the Markov chain associated to an evolutionary algorithm, Genet. Program. Evolv. Mach., 9, 109-123, (2008)
[8] G. Rudolph: Convergence Properties of Evolutionary Algorithms. Verlag Dr. Kovać, Hamburg, 1997. · Zbl 0891.93089
[9] Rudolph, G.; Rozenberg, G. (ed.); Bäck, T.H.W. (ed.); Kok, J.N. (ed.), Stochastic convergence, (2012), Berlin
[10] G. Syswerda: A study of reproduction in generational and steady state genetic algorithms. Foundations of Genetic Algorithms. San Mateo, Morgan Kaufman, San Francisco, 1991, pp. 94-101.
[11] M. D. Vose: The Simple Genetic Algorithm. Foundations and Theory. MIT Press, Cambridge, 1999. · Zbl 0952.65048
[12] D. Whitley: The GENITOR algorithm and selection pressure: Why rank-based allocation of reproductive trials is best. Proceedings of the Third International Conference on Genetic Algorithms. Morgan Kaufman, San Francisco, 1989, pp. 116-123.
[13] A. H. Wright, J. Rowe: Continuous dynamical system models of steady-state genetic algorithms. Foundations of Genetic Algorithms-6. Proc. FOGA-6, Morgan Kaufmann Publishers, Orlando, 2002, pp. 209-225. · Zbl 0987.68094
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.