Jump to content

Population model (evolutionary algorithm)

Edit links
From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Studi90 (talk | contribs) at 10:43, 19 December 2022 (Further text passages backed up by quotations). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.
  • Comment: Quite a lot of the content is unreferenced. DoubleGrazing (talk) 15:04, 9 December 2022 (UTC)


Title: Population model (evolutionary algorithm)

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 the 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.

The simplest and widely used population model in EAs is the global or panmictic model, which corresponds to an unstructured population.[1][2] It allows each individual to choose any other individual of the population as a partner for the production of offspring, whereby the details of the selection are irrelevant as long as the fitness of the individuals plays a significant role. Due to global mate selection, the genetic information of even slightly better individuals can prevail in a population after a few generations (iteration of an EA), provided that no better other offspring have emerged in this phase. If the solution found in this way is not the optimum sought, this is called premature convergence.[3] This effect can be observed more often in panmictic populations.[4]

In nature global mating pools are rarely found. What prevails is a certain and limited isolation due to spatial distance. The resulting local neighbourhoods initially evolve independently and mutants have a higher chance of persisting over several generations. As a result, genotypic diversity in the gene pool is preserved longer than in a panmictic population.

It is therefore obvious to divide the previously global population by substructures. Two basic models were introduced for this purpose, the island models, which are based on a division of the population into fixed subpopulations that exchange individuals from time to time,[5] and the neighbourhood models, which assign individuals to overlapping neighbourhoods.[4] The associated division of the population also suggests a parallelisation of the procedure. For this reason, the topic of population models is also frequently discussed in the literature in connection with the parallelisation of EAs.[1][2][4][5][6][7]

Island models

Example of an island model consisting of eight islands and two neigbourhood structures: a simple unidirectional ring (black arrows) and a more complex structure (green and black arrows)

In the island model, also called the migration model or coarse grained model, evolution takes place in strictly divided subpopulations. These can be organised panmictically, but do not have to be. From time to time an exchange of individuals takes place, which is called migration.[2][5] The time between an exchange is called an epoch and its end can be triggered by various criteria: After a given time or given number of completed generations, or after the occurrence of stagnation. Stagnation can be detected, for example, by the fact that no fitness improvement has been detected in the island for a given number of generations. Island models introduce a variety of new strategy parameters:[6][8]

  • Number of subpopulations
  • Size of the subpopulations
  • Neighbourhood relations between islands: they determine which islands are considered neighbouring and can thus exchange individuals, see picture of a simple unidirectional ring (black arrows) and its extension by additional bidirectional neighbourhood relations (additional green arrows).
  • Criteria for the termination of an epoch
  • Migration rate: number or proportion of individuals involved in migration.
  • Migrant selection: There are many alternatives for this. E.g. the best individuals can replace the worst or randomly selected ones. Depending on the migration rate, this can affect one or more individuals at a time.

Neighbourhood models

Two examples of overlapping neighbourhoods (demes) of the one-dimensional ring-shaped neighbourhood model of the population of an evolutionary algorithm

The neighbourhood model, also called diffusion model or fine grained model, defines a topological neighbourhood relation between the individuals of a population that is independent of their phenotypic properties.[1] In the simplest case, this is a ring structure as shown in the picture on the right.[7] Each individual has a neighbourhood (called deme) of individuals. In the picture on the right, for example, these are the two neighbours to the right and to the left of individual X. Together with X, they form the deme of X. Each deme represents a panmictic subpopulation within which mate selection and the acceptance of offspring takes place by replacing the parent X. The rules for the acceptance of offspring are local in nature and based on the neighbourhood: for example, it can be specified that the best offspring must be better than the parent being replaced or, less strictly, only better than the worst individual in the deme.[4][7] The first rule is elitist and creates a higher selective pressure than the second non-elitist rule.[4][7] In elitist EAs, the best individual of a population always survives. In this respect, they deviate from the biological model.

The neighbourhoods of the individuals overlap, as exemplified in the picture for two neighbourhoods each consisting of four neighbours. The demes of individuals X and Y overlap only minimally, as both individuals are further apart on the ring than individuals A and B with maximum overlap. The overlap of the neighbourhoods causes a mostly slow spread of genetic information across the neighbourhood boundaries, hence the name diffusion model. A better offspring now needs more generations than in panmixy to spread in the population. This promotes the emergence of local niches and their local evolution, thus preserving genotypic diversity over a longer period of time. The result is a self-adapting balance between breadth and depth search. Depth search takes place in the niches and breadth search through the evolution of the different niches of the whole population.[4]

Torus structure (right) with two exemplary two-dimensional neighborhood figures (left). The block-shaped demes of individuals A and B have the two common neighbors shown in yellow.

An alternative to the one-dimensional ring structure is the two-dimensional torus structure, on which a closed lattice structure is applied, as shown on the right side of the adjacent picture.[9] EAs based on this are also called cellular EAs.[10] On the left side of the picture, two only slightly overlapping block-shaped neighbourhoods of individuals A and B are shown, each with eight neighbours. With the grid, more neighbourhood figures are possible than with the ring. For example, there are also vertical or diagonal crosses or asymmetrical demes. The spread of genetic information is greater with the same neighbourhood sizes for elongated figures such as a cross than with a block and again significantly greater than with a ring.[11] Thus, the selective pressure is lower for the ring than for the torus. This means that ring neighbourhoods are well suited for achieving a high quality of results, even if it requires comparatively long run times. If, on the other hand, one is primarily interested in fast and good but possibly suboptimal results, the mesh topologies are better suited.[11]

Comparison

When applying both models to genetic algorithms[5][4], evolutionary strategy[9][11] and other EAs,[12][13] the splitting of a total population into subpopulations usually reduces the risk of premature convergence and leads to better results overall more reliably and faster than would be expected with panmictic EAs.

Island models have the disadvantage compared to neighbourhood models that they introduce a large number of new strategy parameters. Despite the existing studies on this topic in the literature,[8] a certain risk of unfavourable settings remains for the user. With neighbourhood models, on the other hand, only the size of the neighbourhood has to be specified and, in the case of the two-dimensional model, the choice of the neighbourhood figure is added.

References

  1. ^ a b c Cantú-Paz, Erik (1998). "A survey of parallel genetic algorithms". Calculateurs Paralleles. 10 (2): 141–171.
  2. ^ a b c Gordon, V.S.; Whitley, D. (1993), Forrest, S. (ed.), "Serial and Parallel Genetic Algorithms as Function Optimizers", Proceedings of the Fifth International Conference on Genetic Algorithms, San Mateo, CA: Morgan Kaufmann, pp. 177–183
  3. ^ Yee Leung; Yong Gao; Zong-Ben Xu (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.
  4. ^ a b c d e f g Gorges-Schleuter, Martina (1990). Genetic Algorithms and Population Structures - A Massively Parallel Algorithm (PhD). Universität Dortmund, Fakultät für Informatik, Germany.
  5. ^ a b c d Cantú-Paz, Erik (1999). Efficient and Accurate Parallel Genetic Algorithms (PhD). University of Illinois, Urbana-Champaign, USA.
  6. ^ a b Khalloof, Hatem; Mohammad, Mohammad; Shahoud, Shadi; Duepmeier, Clemens; Hagenmeyer, Veit (2020-11-02). "A Generic Flexible and Scalable Framework for Hierarchical Parallelization of Population-Based Metaheuristics". Proceedings of the 12th International Conference on Management of Digital EcoSystems. Virtual Event United Arab Emirates: ACM: 124–131. doi:10.1145/3415958.3433041. ISBN 978-1-4503-8115-4.
  7. ^ a b c d Gorges-Schleuter, Martina (1991), Schwefel, Hans-Paul; Männer, Reinhard (eds.), "Explicit parallelism of genetic algorithms through population structures", Parallel Problem Solving from Nature, vol. 496, Berlin/Heidelberg: Springer-Verlag, pp. 150–159, doi:10.1007/bfb0029746, ISBN 978-3-540-54148-6, retrieved 2022-12-15
  8. ^ a b Cantú-Paz, Erick (1999), "Topologies, Migration Rates, and Multi-Population Parallel Genetic Algorithms", Proc. of the 1st Annual Conf. on Genetic and Evolutionary Computation (GECCO), pp. 91–98
  9. ^ a b Sprave, Joachim (1994), "Linear neighborhood evolution strategy" (PDF), Proceedings of the 3rd Annual Conference on Evolutionary Programming, Singapore: World Scientific, pp. 42–51, retrieved 2022-11-05
  10. ^ Gordon, V. Scott; Mathias, Keith; Whitley, Darrell (1994). "Cellular genetic algorithms as function optimizers: locality effects". Proceedings of the 1994 ACM symposium on Applied computing - SAC '94. Phoenix, Arizona, United States: ACM Press: 237–241. doi:10.1145/326619.326732. ISBN 978-0-89791-647-9.
  11. ^ a b c 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, vol. 1498, Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 367–377, doi:10.1007/bfb0056879, ISBN 978-3-540-65078-2, retrieved 2022-11-03
  12. ^ 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.
  13. ^ Alba, Enrique; Dorronsoro, Bernabé; Alfonso, Hugo (2005). "Cellular Memetic Algorithms". Journal of Computer Science and Technology. 5 (4): 257–263. Retrieved 2022-11-04.

Bibliography

Retrieved from "https://en.wikipedia.org/w/index.php?title=Population_model_(evolutionary_algorithm)&oldid=1128288670"