Abstract:
This paper analyzes the convergence properties of the canonical genetic algorithm (CGA) with mutation, crossover and proportional reproduction applied to static optimizat...Show MoreMetadata
Abstract:
This paper analyzes the convergence properties of the canonical genetic algorithm (CGA) with mutation, crossover and proportional reproduction applied to static optimization problems. It is proved by means of homogeneous finite Markov chain analysis that a CGA will never converge to the global optimum regardless of the initialization, crossover, operator and objective function. But variants of CGA's that always maintain the best solution in the population, either before or after selection, are shown to converge to the global optimum due to the irreducibility property of the underlying original nonconvergent CGA. These results are discussed with respect to the schema theorem.<>
Published in: IEEE Transactions on Neural Networks ( Volume: 5, Issue: 1, January 1994)
DOI: 10.1109/72.265964
References is not available for this document.
Select All
1.
J. H. Holland, Adaptation in natural and artificial systems, Ann Arbor:The University of Michigan Press, 1975.
2.
A. E. Eiben, Ε. H. L. Aarts and K. M. Van Hee, "Global convergence of genetic algorithms: A Markov chain analysis" in Parallel Problem Solving from Nature, Berlin and Heidelberg:Springer, pp. 4-12, 1991.
3.
D. B. Fogel, Evolving artificial intelligence, 1992.
4.
D. E. Goldberg, Genetic Algorithms in Search Optimization and Machine Learning, MA, Reading:Addison Wesley, 1989.
5.
E. Seneta, Non-negative Matrices and Markov Chains, New York:Springer, 1981.
6.
M. Iosifescu, Finite Markov Processes and Their Applications, Chichester:Wiley, 1980.
7.
T. E. Davis and J. C. Principe, "A simulated annealing like convergence theory for the simple genetic algorithm", Proceedings of the fourth Conference on Genetic Algorithms, pp. 174-181, 1991.
8.
W. Feller, An Introduction to Probability Theory and Its Applications, Singapore:Wiley, vol. 1, 1970.
9.
K. A. De Jong, "Are genetic algorithms function optimizers?" in Parallel Problem Solving from Nature, Amsterdam:North Holland, vol. 2, pp. 3-13, 1992.
10.
T. E. Davis, Toward an extrapolation of the simulated annealing convergence theory onto the simple genetic algorithm, 1991.
11.
T. Bäck, "The interaction of mutation rate selection and self-adaptation within a genetic algorithm" in Parallel Problem Solving from Nature, Amsterdam:North Holland, vol. 2, pp. 85-94, 1992.
12.
H. Mühlenbein, "How genetic algorithms really work I: Mutation and hillclimbing" in Parallel Problem Solving from Nature, Amsterdam:North Holland, vol. 2, pp. 15-25, 1992.
