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

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 by crossover, 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, that 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,[1][5] and the neighbourhood models, which assign individuals to overlapping neighbourhoods,[4][6] also known as cellular genetic or evolutionary algorithms (cGA or cEA).[7][8] The associated division of the population also suggests a corresponding parallelization of the procedure. For this reason, the topic of population models is also frequently discussed in the literature in connection with the parallelization of EAs.[1][2][4][5][9][10]

  1. ^ a b c Cantú-Paz, Erik (1998). "A survey of parallel genetic algorithms" (PDF). Calculateurs Paralleles. 10 (2): 141–171.
  2. ^ a b 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, ISBN 978-1-55860-299-1
  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.
  4. ^ a b c 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 Cantú-Paz, Erik (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.
  6. ^ Gorges-Schleuter, Martina (1991), Schwefel, Hans-Paul; Männer, Reinhard (eds.), "Explicit parallelism of genetic algorithms through population structures", Parallel Problem Solving from Nature, Lecture Notes in Computer Science, vol. 496, Berlin/Heidelberg: Springer-Verlag, pp. 150–159, doi:10.1007/bfb0029746, ISBN 978-3-540-54148-6, retrieved 2022-12-15
  7. ^ 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.
  8. ^ Giacobini, M.; Tomassini, M.; Tettamanzi, A.G.B.; Alba, E. (October 2005). "Selection Intensity in Cellular Evolutionary Algorithms for Regular Lattices". IEEE Transactions on Evolutionary Computation. 9 (5): 489–505. doi:10.1109/TEVC.2005.850298. ISSN 1089-778X. S2CID 3184685.
  9. ^ 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. pp. 124–131. doi:10.1145/3415958.3433041. ISBN 978-1-4503-8115-4. S2CID 227179748.
  10. ^ Sudholt, Dirk (2015), Kacprzyk, Janusz; Pedrycz, Witold (eds.), "Parallel Evolutionary Algorithms" (PDF), Springer Handbook of Computational Intelligence, Berlin, Heidelberg: Springer, pp. 929–959, doi:10.1007/978-3-662-43505-2_46, ISBN 978-3-662-43504-5, retrieved 2023-02-13