Degree of population diversity - a perspective on premature convergence in genetic algorithms and its Markov chain analysis
- 1 September 1997
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Neural Networks
- Vol. 8 (5), 1165-1176
- https://doi.org/10.1109/72.623217
Abstract
In this paper, a concept of degree of population diversity is introduced to quantitatively characterize and theoretically analyze the problem of premature convergence in genetic algorithms (GA's) within the framework of Markov chain, Under the assumption that the mutation probability is zero, the search ability of the GA's is discussed, It is proved that the degree of population diversity converges to zero with probability one so that the search ability of a GA decreases and premature convergence occurs, Moreover, an explicit formula for the conditional probability of allele loss at a certain bit position is established to show the relationships between premature convergence and the GA parameters, such as population size, mutation probability, and some population statistics. The formula also partly answers the questions of to where a GA most likely converges, The theoretical results are all supported by the simulation experiments.Keywords
This publication has 6 references indexed in Scilit:
- ASYMPTOTIC CONVERGENCE PROPERTIES OF GENETIC ALGORITHMS AND EVOLUTIONARY PROGRAMMING: ANALYSIS AND EXPERIMENTSCybernetics and Systems, 1994
- ADAPTIVE PROBABILITIES OF CROSSOVER AND MUTATION IN GENETIC ALGORITHMSIEEE Transactions on Systems, Man, and Cybernetics, 1994
- An introduction to simulated evolutionary optimizationIEEE Transactions on Neural Networks, 1994
- Convergence analysis of canonical genetic algorithmsIEEE Transactions on Neural Networks, 1994
- Control of parallel population dynamics by social-like behavior of GA-individualsLecture Notes in Computer Science, 1994
- Population Diversity in an Immune System Model: Implications for Genetic SearchPublished by Elsevier BV ,1993