Premature convergence

Last updated

Premature convergence is an unwanted effect in evolutionary algorithms (EA), a metaheuristic that mimics the basic principles of biological evolution as a computer algorithm for solving an optimization problem. The effect means that the population of an EA has 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, 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. [3]

Contents

Strategies for preventing premature convergence

Strategies to regain genetic variation can be:

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

A general strategy to reduce the risk of premature convergence is to use structured populations instead of the commonly used panmictic ones.

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. [6] 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. [7]

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. [8] 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. [7] 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. [7] 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. [9] 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. [7]

Panmictic populations

Most EAs use unstructured or panmictic populations where basically every individual in the population is eligible for mate selection based on fitness. [10] [11] 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 [12] [13] 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, [12] the evolution strategy, [14] other EAs [15] or memetic algorithms. [15] [16]

See also

Related Research Articles

<span class="mw-page-title-main">Genetic programming</span> Evolving computer programs with techniques analogous to natural genetic processes

Genetic programming (GP) is an evolutionary algorithm, an artificial intelligence technique mimicking natural evolution, which operates on a population of programs. It applies the genetic operators selection according to a predefined fitness measure, mutation and crossover.

<span class="mw-page-title-main">Genetic algorithm</span> Competitive algorithm for searching a problem space

In computer science and operations research, a genetic algorithm (GA) is a metaheuristic inspired by the process of natural selection that belongs to the larger class of evolutionary algorithms (EA). Genetic algorithms are commonly used to generate high-quality solutions to optimization and search problems via biologically inspired operators such as selection, crossover, and mutation. Some examples of GA applications include optimizing decision trees for better performance, solving sudoku puzzles, hyperparameter optimization, and causal inference.

<span class="mw-page-title-main">Evolutionary algorithm</span> Subset of evolutionary computation

Evolutionary algorithms (EA) reproduce essential elements of the biological evolution in a computer algorithm in order to solve “difficult” problems, at least approximately, for which no exact or satisfactory solution methods are known. They belong to the class of metaheuristics and are a subset of evolutionary computation, which itself is part of the field of computational intelligence. The mechanisms of biological evolution that an EA mainly imitates are reproduction, mutation, recombination and selection. Candidate solutions to the optimization problem play the role of individuals in a population, and the fitness function determines the quality of the solutions (see also loss function). Evolution of the population then takes place after the repeated application of the above operators.

<span class="mw-page-title-main">Evolutionary computation</span> Trial and error problem solvers with a metaheuristic or stochastic optimization character

Evolutionary computation from computer science is a family of algorithms for global optimization inspired by biological evolution, and the subfield of artificial intelligence and soft computing studying these algorithms. In technical terms, they are a family of population-based trial and error problem solvers with a metaheuristic or stochastic optimization character.

<span class="mw-page-title-main">Particle swarm optimization</span> Iterative simulation method

In computational science, particle swarm optimization (PSO) is a computational method that optimizes a problem by iteratively trying to improve a candidate solution with regard to a given measure of quality. It solves a problem by having a population of candidate solutions, here dubbed particles, and moving these particles around in the search-space according to simple mathematical formulae over the particle's position and velocity. Each particle's movement is influenced by its local best known position, but is also guided toward the best known positions in the search-space, which are updated as better positions are found by other particles. This is expected to move the swarm toward the best solutions.

<span class="mw-page-title-main">Fitness function</span> Objective function of evolutionary algorithm

A fitness function is a particular type of objective or cost function that is used to summarize, as a single figure of merit, how close a given candidate solution is to achieving the set aims. It is an important component of evolutionary algorithms (EA), such as genetic programming, evolution strategies or genetic algorithms. An EA is a metaheuristic that reproduces the basic principles of biological evolution as a computer algorithm in order to solve challenging optimization or planning tasks, at least approximately. For this purpose, many candidate solutions are generated, which are evaluated using a fitness function in order to guide the evolutionary development towards the desired goal. Similar quality functions are also used in other metaheuristics, such as ant colony optimization or particle swarm optimization.

Neuroevolution, or neuro-evolution, is a form of artificial intelligence that uses evolutionary algorithms to generate artificial neural networks (ANN), parameters, and rules. It is most commonly applied in artificial life, general game playing and evolutionary robotics. The main benefit is that neuroevolution can be applied more widely than supervised learning algorithms, which require a syllabus of correct input-output pairs. In contrast, neuroevolution requires only a measure of a network's performance at a task. For example, the outcome of a game can be easily measured without providing labeled examples of desired strategies. Neuroevolution is commonly used as part of the reinforcement learning paradigm, and it can be contrasted with conventional deep learning techniques that use backpropagation with a fixed topology.

<span class="mw-page-title-main">Evolutionary programming</span> Evolutionary algorithm with a defined structure

Evolutionary programming is an evolutionary algorithm, where a share of new population is created by mutation of previous population without crossover. Evolutionary programming differs from evolution strategy ES() in one detail. All individuals are selected for the new population, while in ES(), every individual has the same probability to be selected. It is one of the four major evolutionary algorithm paradigms.

<span class="mw-page-title-main">Mutation (evolutionary algorithm)</span> Genetic operation used to add population diversity

Mutation is a genetic operator used to maintain genetic diversity of the chromosomes of a population of an evolutionary algorithm (EA), including genetic algorithms in particular. It is analogous to biological mutation.

Metaheuristic in computer science and mathematical optimization is a higher-level procedure or heuristic designed to find, generate, tune, or select a heuristic that may provide a sufficiently good solution to an optimization problem or a machine learning problem, especially with incomplete or imperfect information or limited computation capacity. Metaheuristics sample a subset of solutions which is otherwise too large to be completely enumerated or otherwise explored. Metaheuristics may make relatively few assumptions about the optimization problem being solved and so may be usable for a variety of problems. Their use is always of interest when exact or other (approximate) methods are not available or are not expedient, either because the calculation time is too long or because, for example, the solution provided is too imprecise.

<span class="mw-page-title-main">Evolution strategy</span>

Evolution strategy (ES) from computer science is a subclass of evolutionary algorithms, which serves as an optimization technique. It uses the major genetic operators mutation, recombination and selection of parents.

In population genetics and population ecology, population size is a countable quantity representing the number of individual organisms in a population. Population size is directly associated with amount of genetic drift, and is the underlying cause of effects like population bottlenecks and the founder effect. Genetic drift is the major source of decrease of genetic diversity within populations which drives fixation and can potentially lead to speciation events.

In computer programming, genetic representation is a way of presenting solutions/individuals in evolutionary computation methods. The term encompasses both the concrete data structures and data types used to realize the genetic material of the candidate solutions in the form of a genome, and the relationships between search space and problem space. In the simplest case, the search space corresponds to the problem space. The choice of problem representation is tied to the choice of genetic operators, both of which have a decisive effect on the efficiency of the optimization. Genetic representation can encode appearance, behavior, physical qualities of individuals. Difference in genetic representations is one of the major criteria drawing a line between known classes of evolutionary computation.

<span class="mw-page-title-main">Memetic algorithm</span> Algorithm for searching a problem space

In computer science and operations research, a memetic algorithm (MA) is an extension of an evolutionary algorithm (EA) that aims to accelerate the evolutionary search for the optimum. An EA is a metaheuristic that reproduces the basic principles of biological evolution as a computer algorithm in order to solve challenging optimization or planning tasks, at least approximately. An MA uses one or more suitable heuristics or local search techniques to improve the quality of solutions generated by the EA and to speed up the search. The effects on the reliability of finding the global optimum depend on both the use case and the design of the MA.

<span class="mw-page-title-main">Gaussian adaptation</span> Evolutionary algorithm designed for maximizing manufacturing yield

Gaussian adaptation (GA), also called normal or natural adaptation (NA) is an evolutionary algorithm designed for the maximization of manufacturing yield due to statistical deviation of component values of signal processing systems. In short, GA is a stochastic adaptive process where a number of samples of an n-dimensional vector x[xT = (x1, x2, ..., xn)] are taken from a multivariate Gaussian distribution, N(m, M), having mean m and moment matrix M. The samples are tested for fail or pass. The first- and second-order moments of the Gaussian restricted to the pass samples are m* and M*.

<span class="mw-page-title-main">Evolutionary multimodal optimization</span>

In applied mathematics, multimodal optimization deals with optimization tasks that involve finding all or most of the multiple solutions of a problem, as opposed to a single best solution. Evolutionary multimodal optimization is a branch of evolutionary computation, which is closely related to machine learning. Wong provides a short survey, wherein the chapter of Shir and the book of Preuss cover the topic in more detail.

<span class="mw-page-title-main">Cellular evolutionary algorithm</span> Kind of evolutionary algorithm

A cellular evolutionary algorithm (cEA) is a kind of evolutionary algorithm (EA) in which individuals cannot mate arbitrarily, but every one interacts with its closer neighbors on which a basic EA is applied.

Biogeography-based optimization (BBO) is an evolutionary algorithm (EA) that optimizes a function by stochastically and iteratively improving candidate solutions with regard to a given measure of quality, or fitness function. BBO belongs to the class of metaheuristics since it includes many variations, and since it does not make any assumptions about the problem and can therefore be applied to a wide class of problems.

<span class="mw-page-title-main">Fly algorithm</span>

The Fly Algorithm is a computational method within the field of evolutionary algorithms, designed for direct exploration of 3D spaces in applications such as computer stereo vision, robotics, and medical imaging. Unlike traditional image-based stereovision, which relies on matching features to construct 3D information, the Fly Algorithm operates by generating a 3D representation directly from random points, termed "flies." Each fly is a coordinate in 3D space, evaluated for its accuracy by comparing its projections in a scene. By iteratively refining the positions of flies based on fitness criteria, the algorithm can construct an optimized spatial representation. The Fly Algorithm has expanded into various fields, including applications in digital art, where it is used to generate complex visual patterns.

<span class="mw-page-title-main">Population model (evolutionary algorithm)</span> Population models of evolutionary algorithms

The population model of an evolutionary algorithm (EA) describes the structural properties of its population to which its members are subject. A population is the set of all proposed solutions of an EA considered in one iteration, which are also called individuals according to the biological role model. The individuals of a population can generate further individuals as offspring with the help of the genetic operators of the procedure.

References

  1. 1 2 3 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.
  2. 1 2 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
  3. ↑ 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.
  4. ↑ Michalewicz, Zbigniew (1996). Genetic Algorithms + Data Structures = Evolution Programs, 3rd Edition. Berlin, Heidelberg: Springer-Verlag. p. 58. ISBN   3-540-60676-9.
  5. ↑ Simões, José Maria; Lourenço, Nuno; Machado, Penousal (2023). "All You Need is Sex for Diversity". Genetic Programming. Springer Nature Switzerland: 276–291. doi:10.1007/978-3-031-29573-7_18.
  6. ↑ 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.
  7. 1 2 3 4 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.
  8. ↑ Rechenberg, I. (1973). Evolutionsstrategie: Optimierung technischer Systeme nach Prinzipien der biologischen Evolution. Frommann-Holzboog Verlag, Stuttgart.
  9. ↑ 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.
  10. ↑ 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
  11. ↑ Cantú-Paz, Erik (1998). "A survey of parallel genetic algorithms" (PDF). Calculateurs Paralleles. 10 (2): 141–171.
  12. 1 2 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.
  13. ↑ 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.
  14. ↑ 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
  15. 1 2 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.
  16. ↑ Alba, Enrique; Dorronsoro, Bernabé; Alfonso, Hugo (2005). "Cellular Memetic Algorithms". Journal of Computer Science and Technology. 5 (4): 257–263. Retrieved 2022-11-04.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.