Characteristic analysis and prevention on premature convergence in genetic algorithms

The identification and characteristics of premature convergence in genetic algorithms (GAs) are investigated. Through a detailed quantitative analysis on the search capability and the degree of population diversity, the cause of premature convergence in GAs is recognized, and attributed to the maturation effect of the GAs: The minimum schema deduced from current population, which is the largest search space of a GA, converges to a homogeneous population in probability 1 (so the search capability of the GA decreases and premature convergence occurs). It is shown that, as quantitative features of the maturation effect, the degree of population diversity converges to zero with probability 1, and the tendency for premature convergence is inversely proportional to the population size and directly proportional to the variance of the fitness ratio of zero allele at any gene position of the current population. Based on the theoretical analysis, several strategies for preventing premature convergence are suggested. A specific GA formulation that converges assuredly to the global optimum without appearance of premature convergence is proposed.