Premature convergence

In evolutionary algorithms (EA), the term of premature convergence means that a population for an optimization problem converged too early, resulting in being suboptimal. In this context, the parental solutions, through the aid of genetic operators, are not able to generate offspring that are superior to, or outperform, their parents. Premature convergence is a common problem found in evolutionary algorithms in general and genetic algorithms in particular, as it leads to a loss, or convergence of, a large number of alleles, subsequently making it very difficult to search for a specific gene in which the alleles were present.^[1]^[2] An allele is considered lost if, in a population, a gene is present, where all individuals are sharing the same value for that particular gene. An allele is, as defined by De Jong, considered to be a converged allele, when 95% of a population share the same value for a certain gene (see also convergence).^[3]

Strategies for preventing premature convergence

Strategies to regain genetic variation can be:

a mating strategy called incest prevention,^[4]
uniform crossover,
favored replacement of similar individuals (preselection or crowding),
segmentation of individuals of similar fitness (fitness sharing),
increasing population size.

The genetic variation can also be regained by mutation though this process is highly random.

One way to reduce the risk of premature convergence is to use structured populations instead of the commonly used panmictic ones, see below.

Identification of the occurrence of premature convergence

It is hard to determine when premature convergence has occurred, and it is equally hard to predict its presence in the future.^[2]^[1] One measure is to use the difference between the average and maximum fitness values, as used by Patnaik & Srinivas, to then vary the crossover and mutation probabilities.^[5] Population diversity is another measure which has been extensively used in studies to measure premature convergence. However, although it has been widely accepted that a decrease in the population diversity directly leads to premature convergence, there have been little studies done on the analysis of population diversity. In other words, by using the term population diversity, the argument for a study in preventing premature convergence lacks robustness, unless specified what their definition of population diversity is.^[6]

Causes for premature convergence

There are a number of presumed or hypothesized causes for the occurrence of premature convergence.

Self-adaptive mutations

Rechenberg introduced the idea of self-adaptation of mutation distributions in evolution strategies.^[7] According to Rechenberg, the control parameters for these mutation distributions evolved internally through self-adaptation, rather than predetermination. He called it the 1/5-success rule of evolution strategies (1 + 1)-ES: The step size control parameter would be increased by some factor if the relative frequency of positive mutations through a determined period of time is larger than 1/5, vice versa if it is smaller than 1/5. Self-adaptive mutations may very well be one of the causes for premature convergence.^[6] Accurately locating of optima can be enhanced by self-adaptive mutation, as well as accelerating the search for this optima. This has been widely recognized, though the mechanism's underpinnings of this have been poorly studied, as it is often unclear whether the optima is found locally or globally.^[6] Self-adaptive methods can cause global convergence to global optimum, provided that the selection methods used are using elitism, as well as that the rule of self-adaptation doesn't interfere with the mutation distribution, which has the property of ensuring a positive minimum probability when hitting a random subset.^[8] This is for non-convex objective functions with sets that include bounded lower levels of non-zero measurements. A study by Rudolph suggests that self-adaption mechanisms among elitist evolution strategies do resemble the 1/5-success rule, and could very well get caught by a local optimum that include a positive probability.^[6]

Panmictic populations

Most EAs use unstructured or panmictic populations where basically every individual in the population is eligible for mate selection based on fitness.^[9]^[10] Thus, The genetic information of an only slightly better individual can spread in a population within a few generations, provided that no better other offspring is produced during this time. Especially in comparatively small populations, this can quickly lead to a loss of genotypic diversity and thus to premature convergence.^[1] A well-known countermeasure is to switch to alternative population models which introduce substructures into the population^[11]^[12] that preserve genotypic diversity over a longer period of time and thus counteract the tendency towards premature convergence. This has been shown for various EAs such as genetic algorithms,^[11] the evolution strategy,^[13] other EAs^[14] or memetic algorithms.^[14]^[15]

References

^ ^a ^b ^c Leung, Yee; Gao, Yong; Xu, Zong-Ben (1997). "Degree of population diversity - a perspective on premature convergence in genetic algorithms and its Markov chain analysis". IEEE Transactions on Neural Networks. 8 (5): 1165–1176. doi:10.1109/72.623217. ISSN 1045-9227. PMID 18255718.
^ ^a ^b Baker, James E. (1985), Grefenstette, John J. (ed.), "Adaptive Selection Methods for Genetic Algorithms", Proceedings of the First International Conference on Genetic Algorithms and their Applications, Hillsdale, NJ: L. Erlbaum, pp. 101–111, ISBN 9780805804263
^ De Jong, Kenneth A. (1975). An analysis of the behavior of a class of genetic adaptive systems (PhD). Ann Arbor, MI: University of Michigan. hdl:2027.42/4507.
^ Michalewicz, Zbigniew (1996). Genetic Algorithms + Data Structures = Evolution Programs, 3rd Edition. Berlin, Heidelberg: Springer-Verlag. p. 58. ISBN 3-540-60676-9.
^ Srinivas, M.; Patnaik, L.M. (April 1994). "Adaptive probabilities of crossover and mutation in genetic algorithms". IEEE Transactions on Systems, Man, and Cybernetics. 24 (4): 656–667. doi:10.1109/21.286385.
^ ^a ^b ^c ^d Rudolph, Günther (August 2001). "Self-adaptive mutations may lead to premature convergence" (PDF). IEEE Transactions on Evolutionary Computation. 5 (4): 410–414. doi:10.1109/4235.942534. hdl:2003/5378.
^ Rechenberg, I. (1973). Evolutionsstrategie: Optimierung technischer Systeme nach Prinzipien der biologischen Evolution. Frommann-Holzboog Verlag, Stuttgart.
^ Rudolph, Günther (1999). "Self-adaptation and global convergence: A counter-example" (PDF). Proceedings of the 1999 Congress on Evolutionary Computation-CEC99 (Cat. No. 99TH8406). Washington, DC: IEEE. pp. 646–651. doi:10.1109/CEC.1999.781994. hdl:2003/5368. ISBN 978-0-7803-5536-1. S2CID 569395.
^ Gordon, V.S.; Whitley, D. (1993), Forrest, S. (ed.), "Serial and Parallel Genetic Algorithms as Function Optimizers" (PDF), Proceedings of the Fifth International Conference on Genetic Algorithms, San Mateo, CA: Morgan Kaufmann, pp. 177–183
^ Cantú-Paz, Erik (1998). "A survey of parallel genetic algorithms" (PDF). Calculateurs Paralleles. 10 (2): 141–171.
^ ^a ^b Gordon, V. Scott; Mathias, Keith; Whitley, Darrell (1994). "Cellular genetic algorithms as function optimizers". Proceedings of the 1994 ACM symposium on Applied computing - SAC '94. Phoenix, Arizona, United States: ACM Press. pp. 237–241. doi:10.1145/326619.326732. ISBN 978-0-89791-647-9. S2CID 6418773.
^ Cantú-Paz, Erick (1999). Efficient and Accurate Parallel Genetic Algorithms (PhD thesis, University of Illinois, Urbana-Champaign, USA). Genetic Algorithms and Evolutionary Computation. Vol. 1. Springer, New York, NY. doi:10.1007/978-1-4615-4369-5. ISBN 978-1-4613-6964-6.
^ Gorges-Schleuter, Martina (1998), Eiben, Agoston E.; Bäck, Thomas; Schoenauer, Marc; Schwefel, Hans-Paul (eds.), "A comparative study of global and local selection in evolution strategies", Parallel Problem Solving from Nature — PPSN V, Lecture Notes in Computer Science, vol. 1498, Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 367–377, doi:10.1007/bfb0056879, ISBN 978-3-540-65078-2, retrieved 2022-12-04
^ ^a ^b Jakob, Wilfried (2010-09-01). "A general cost-benefit-based adaptation framework for multimeme algorithms". Memetic Computing. 2 (3). p. 207: 201–218. doi:10.1007/s12293-010-0040-9. ISSN 1865-9292. S2CID 167807.
^ Alba, Enrique; Dorronsoro, Bernabé; Alfonso, Hugo (2005). "Cellular Memetic Algorithms". Journal of Computer Science and Technology. 5 (4): 257–263. Retrieved 2022-11-04.