Degree of population diversity - a perspective on premature convergence in genetic algorithms and its Markov chain analysis

摘要

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 (GAs) within the framework of Markov chain. Under the assumption that the mutation probability is zero, the search ability of GA 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.