Abstract
This paper is concerning the finite, homogenous Markov chain modeling of the binary, elitist genetic algorithm (EGA) and provides a set of minimal sufficient conditions for convergence to the global optimum. The case of a GA where each population would be allow to mutate only a small number of bits has not been covered yet by the GA's literature, although it commonly appears in practice. The main result presented here shows that the condition of the one-step transition probability by mutation between two arbitrary strings being larger than zero can be relaxed in the sense that it is also sufficient to achieve the transition by a chain of small mutations. Consequently, even one-bit mutations would be sufficient to make the GA globally convergent, because they can be chained to achieve a multi-bit mutation. All this study is performed with respect to the theory of non-negative matrices and their relationship to Markov chains.
All over this paper the term elitist is associated to a canonical GA maintaining the best solution found over time, without using it to generate new individuals.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
T.E. Davis and J.C. Principe, A Markov Chain Framework for the Simple Genetic Algorithm, Evol. Comp. 1, Vol. 3 (1993) 269–288.
A.E. Eiben, E.H.L. Aarts and K.M. Van Hee, Global Convergence of Genetic Algorithms: a Markov Chain Analysis, in: Parallel Problem Solving from Nature (Springer, Berlin, 1990) 4–12.
D.E. Goldberg and P. Segrest, Finite Markov chain analysis of genetic algortihms, in: Proc. ICCA `87 (Int. Conf On Genetic Algorithms) (Hillsdale, NJ: Lawrence Elbraum, 1987) 1–8.
J.H. Holland, Adaptation in natural and artificial systems, Ann. Arbor, (The University of Michigan Press, 1975).
J. Horn, Finite Markov Chain Analysis of Genetic Algorithms with Niching, in: Proc. ICCA `93 (Int. Conf. on Genetic Algorithms) (1993) 110–117.
M. Iosifescu, Finite Markov chains and applications (Techn. Publ., Bucharest, 1977-in Romanian).
M. Iosifescu, Finite Markov Processes and Their Applications (Chichester: Wiley, 1980).
A.E. Nix and M.D. Vose, Modeling genetic algorithms with Markov chains, Ann. Math. and Artificial Intelligence 5 (1992) 79–88.
G. Rudolph, Convergence Analysis of Canonical Genetic Algorithms, IEEE Trans. on NN. 1, Vol. 5 (1994) 98–101.
X. Qi and F. Palmieri, Theoretical Analysis of Evolutionary Algorithms, parts I-II, IEEE Trans. on NN. 1, Vol. 5 (1994) 102–129.
E. Seneta, Non-negative Matrices and Markov Chains, 2nd edition, (Springer, New York, 1981).
J. Suzuki, A Markov Chain Analysis on A Genetic Algorithm, in: Proc. ICGA'93 (Int. Conf. on Genetic Algorithm, Urbana Illinois) (Morgan Kaufmann, 1993) 46–153.
Y. Uesaka, Convergence of algorithm and the schema theorem in genetic algorithms, in: Proc. ICANGA 1995 210–213.
M.D. Vose, Modeling Simple Genetic Algorithms, in: D.Whitely, ed., Foundations of Genetic Algorithms II (San Mateo, CA: Morgan Kaufmann, 1993) 63–73.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Agapie, A. (1998). Genetic algorithms: Minimal conditions for convergence. In: Hao, JK., Lutton, E., Ronald, E., Schoenauer, M., Snyers, D. (eds) Artificial Evolution. AE 1997. Lecture Notes in Computer Science, vol 1363. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0026600
Download citation
DOI: https://doi.org/10.1007/BFb0026600
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-64169-8
Online ISBN: 978-3-540-69698-8
eBook Packages: Springer Book Archive