Premature convergence

Premature convergence

The main problem with evolutionary algorithms is definitely premature convergence.

Generation after generation individuals in the population tend to be all alike, the population converges to a single point in the search space, all recombination operators become quite ineffective and the evolution process almost stops. In such a condition, an EA behaves like an overloaded, inefficient random-mutation hillclimber.

Premature convergence is an endemic problem of evolutionary computation. In nature, natural selection, also, leads to divergence of character; for more living beings can be supported on the same area the more they diverge in structure, habits, and constitution. However, in artificial evolution there is no explicit environment since its effects are modeled through the fitness function.Consequently, the divergence of character, i.e., one of the pillar of the Darwinian theory of evolution, is completely missing.

Several contributions describe methodologies to tackle this problem. Authors proposed to preserve the diversity of the population by aging individuals, limiting interactions or other quite complex mechanisms. However, none of these artificial mechanisms can be called a panacea, and practitioners still need to tackle premature convergence on a problem-specific basis.

The approach used in µGP has been detailed at the Genetic and Evolutionary Computation Conference (GECCO) in 2008. See: G. Squillero and A. Tonda, A novel methodology for diversity preservation in evolutionary algorithms.

Suggested readings

• E.K. Burke, S. Gustafson, and G. Kendall, Diversity in genetic programming: an analysis of measures and correlation with fitness, IEEE Transactions on Evolutionary Computation, vol. 8, no. 1, pp. 47-62, February 2004.
• K. De Jong J. Sarma, An Analysis of the Effects of Neighborhood Size and Shape on Local Selection Algorithms International Conference on Parallel Problem Solving From Nature, Berlin, 1996, pp. 236--244.