Population model (evolutionary algorithm)

From WikiProjectMed
Jump to navigation Jump to search

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]

Island models

Example of an island model consisting of eight islands and two neighbourhood 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: E.g. 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 occurred in the island for a given number of generations. Island models introduce a variety of new strategy parameters:[11][12][13][14]

  • 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, synchronous or asynchronous migration
  • 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.

With these parameters, the selection pressure can be influenced to a considerable extent. For example, it increases with the interconnectedness of the islands and decreases with the number of subpopulations or the epoch length.

Neighbourhood models or cellular evolutionary algorithms

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

The neighbourhood model, also called diffusion model or fine grained model, defines a topological neighbouhood relation between the individuals of a population that is independent of their phenotypic properties. The fundamental idea of this model is to provide the EA population with a special structure defined as a connected graph, in which each vertex is an individual that communicates with its nearest neighbours.[2][6] Particularly, individuals are conceptually set in a toroidal mesh, and are only allowed to recombine with close individuals. This leads to a kind of locality known as isolation by distance.[6][7] The set of potential mates of an individual is called its neighbourhood or deme. The adjacent figure illustrates that by showing two slightly overlapping neighbourhoods of two individuals marked yellow, through which genetic information can spread between the two demes. It is known that in this kind of algorithm, similar individuals tend to cluster and create niches that are independent of the deme boundaries and, in particular, can be larger than a deme.[6][7] There is no clear borderline between adjacent groups, and close niches could be easily colonized by competitive ones and maybe merge solution contents during this process. Simultaneously, farther niches can be affected more slowly.[6][7] EAs with this type of population are also well known as cellular EAs (cEA)[8][15] or cellular genetic algorithms (cGA).[7][16]

Examples of neighbouhoods, also called demes, in two-dimensional cellular EAs: linear, compact, diamond and... any other.
Two examples overlapping neighbourhoods (demes) of the one-dimensional ring-shaped neighbourhood model of an EA. The two demes of individuals X and Y overlap minimally, while those of A and B show a maximum overlap.

A commonly used structure for arranging the individuals of a population is a 2D toroidal grid,[1][2][15] although the number of dimensions can be easily extended (to 3D) or reduced (to 1D, e.g. a ring,[6][15] see the figure on the right). The neighbourhood of a particular individual in the grid is defined in terms of the Manhattan distance from it to others in the population. In the basic algorithm, all the neighbourhoods have the same size and identical shapes. The two most commonly used neighbourhoods for two dimesional cEAs are L5 and C9, see the figure on the left. Here, L stands for Linear while C stands for Compact. Each deme represents a panmictic subpopulation within which mate selection and the acceptance of offspring takes place by replacing the parent. 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.[2][6] The first rule is elitist and creates a higher selective pressure than the second non-elitist rule. In elitist EAs, the best individual of a population always survives. In this respect, they deviate from the biological model.

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 better and dynamic balance between breadth and depth search adapted to the search space during a run. Depth search takes place in the niches and breadth search in the niche boundaries and through the evolution of the different niches of the whole population.[17] For the same neighbourhood size, the spread of genetic information is larger for elongated figures like L9 than for a block like C9, and again significantly larger than for a ring.[18] This means that ring neighbourhoods are well suited for achieving high quality results, even if this requires comparatively long run times. On the other hand, if one is primarily interested in fast and good, but possibly suboptimal results, 2D topologies are more suitable.

Comparison

When applying both population models to genetic algorithms,[5][6] evolutionary strategy[18][19] and other EAs,[20][21] 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,[11][22][23] 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.

Parallelism

Since both population models imply population partitioning, they are well suited as a basis for parallelizing an EA.[5][10][24] This applies even more to cellular EAs, since they rely only on locally available information about the members of their respective demes. Thus, in the extreme case, an independent execution thread can be assigned to each individual, so that the entire cEA can run on a parallel hardware platform.[6][25][26] The island model also supports parallelization, e.g. by assigning a processor to each island. If the subpopulations of the islands are organized panmictically, all evaluations of the descendants of a generation can be parallelized additionally.[9][14][27] In real-world applications the evaluations are usually by far the most time-consuming part. Of course, it is also possible to design the island sub-populations as cEAs, so that the statements made before about parallelizing cEAs apply. In this way, hierarchical population structures with the appropriate parallelizations can be created.[9] Not only comparatively expensive computer clusters but also inexpensive graphics cards (GPUs) can be used for parallelization.[28][29]

However, it is important to stress that cEAs, or EAs with a population distributed across islands, represent a search model that differs in many ways from traditional EAs. Moreover, they can run on both sequential and parallel platforms, which highlights the fact that model and implementation are two different concepts.

Bibliography

  • Erick Cantú-Paz (2001): Efficient and Accurate Parallel Genetic Algorithms (PhD thesis, University of Illinois, Urbana-Champaign, USA). Springer, New York, NY. ISBN 978-1-4613-6964-6 doi:10.1007/978-1-4615-4369-5
  • Martina Gorges-Schleuter (1990): Genetic Algorithms and Population Structures - A Massively Parallel Algorithm. PhD thesis, Universität Dortmund, Fakultät für Informatik, Germany.
  • Enrique Alba, Bernabé Dorronsoro (2008): Cellular Genetic Algorithms. Springer, New York, NY. ISBN 978-0-387-77609-5 doi:10.1007/978-0-387-77610-1
  • Dirk Sudholt (2015): Parallel Evolutionary Algorithms. In Janusz Kacprzyk, Witold Pedrycz (eds.): Parallel Evolutionary Algorithms. Springer, Berlin, Heidelberg, pp. 929–959 ISBN 978-3-662-43504-5 doi:10.1007/978-3-662-43505-2 46
  • Gabriel Luque, Enrique Alba (2011): Parallel Genetic Algorithms. Springer, Berlin Heidelberg. ISBN 978-3-642-22083-8 doi:10.1007/978-3-642-22084-5

See also

References

  1. ^ a b c d Cantú-Paz, Erik (1998). "A survey of parallel genetic algorithms" (PDF). Calculateurs Paralleles. 10 (2): 141–171.
  2. ^ a b c d e f 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 c d e 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. ^ a b c d e f g h i 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. ^ a b c d e 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. ^ a b 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. ^ a b c 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. ^ a b 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
  11. ^ 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
  12. ^ Belkadi, K.; Gourgand, M.; Benyettou, M. (2006-11-08). "Parallel genetic algorithms with migration for the hybrid flow shop scheduling problem". Journal of Applied Mathematics and Decision Sciences. 2006: 1–17. doi:10.1155/JAMDS/2006/65746. ISSN 1173-9126.
  13. ^ Abdelhafez, Amr; Alba, Enrique; Luque, Gabriel (September 2019). "Performance analysis of synchronous and asynchronous distributed genetic algorithms on multiprocessors". Swarm and Evolutionary Computation. 49: 147–157. doi:10.1016/j.swevo.2019.06.003. S2CID 196193164.
  14. ^ a b Adar, N.; Kuvat, G. (2016). "Parallel Genetic Algorithms with Dynamic Topology using Cluster Computing". Advances in Electrical and Computer Engineering. 16 (3): 73–80. doi:10.4316/AECE.2016.03011. ISSN 1582-7445.
  15. ^ a b c Alba, Enrique; Troya, José Ma (2000), Schoenauer, Marc; Deb, Kalyanmoy; Rudolph, Günther; Yao, Xin (eds.), "Cellular Evolutionary Algorithms: Evaluating the Influence of Ratio", Parallel Problem Solving from Nature PPSN VI, vol. 1917, Berlin, Heidelberg: Springer, pp. 29–38, doi:10.1007/3-540-45356-3_3, ISBN 978-3-540-41056-0, retrieved 2023-02-11
  16. ^ Folino, G.; Pizzuti, C.; Spezzano, G. (1998). "Combining cellular genetic algorithms and local search for solving satisfiability problems". Proceedings Tenth IEEE International Conference on Tools with Artificial Intelligence (Cat. No.98CH36294). Taipei, Taiwan: IEEE. pp. 192–198. doi:10.1109/TAI.1998.744842. ISBN 978-0-7803-5214-8. S2CID 8048158.
  17. ^ Alba, Enrique; Dorronsoro, Bernabé (2008). Cellular genetic algorithms. New York: Springer. p. 12. ISBN 978-0-387-77610-1. OCLC 370728730.
  18. ^ a b 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, pp. 367–377, doi:10.1007/bfb0056879, ISBN 978-3-540-65078-2, retrieved 2023-02-11
  19. ^ 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
  20. ^ 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.
  21. ^ Alba, Enrique; Dorronsoro, Bernabé; Alfonso, Hugo (2005). "Cellular Memetic Algorithms". Journal of Computer Science and Technology. 5 (4): 257–263. Retrieved 2022-11-04.
  22. ^ Wen-Yang Lin; Tzung-Pei Hong; Shu-Min Liu (2004). "On adapting migration parameters for multi-population genetic algorithms". 2004 IEEE International Conference on Systems, Man and Cybernetics (IEEE Cat. No.04CH37583). Vol. 6. The Hague, Netherlands: IEEE. pp. 5731–5735. doi:10.1109/ICSMC.2004.1401108. ISBN 978-0-7803-8567-2. S2CID 31844333.
  23. ^ Hong, Tzung-Pei; Lin, Wen-Yang; Liu, Shu-Min; Lin, Jiann-Horng (2007-04-20). "Dynamically Adjusting Migration Rates for Multi-Population Genetic Algorithms". Journal of Advanced Computational Intelligence and Intelligent Informatics. 11 (4): 410–415. doi:10.20965/jaciii.2007.p0410. ISSN 1883-8014.
  24. ^ Luque, Gabriel; Alba, Enrique (2011). Parallel Genetic Algorithms. Studies in Computational Intelligence. Vol. 367. Berlin, Heidelberg: Springer. doi:10.1007/978-3-642-22084-5. ISBN 978-3-642-22083-8.
  25. ^ Luque, Gabriel; Alba, Enrique; Dorronsoro, Bernabé (July 2009). "An asynchronous parallel implementation of a cellular genetic algorithm for combinatorial optimization". Proceedings of the 11th Annual conference on Genetic and evolutionary computation. Montreal Québec Canada: ACM. pp. 1395–1402. doi:10.1145/1569901.1570088. ISBN 978-1-60558-325-9. S2CID 14113702.
  26. ^ Zhongwen Luo; Hongzhi Liu (2006). "Cellular Genetic Algorithms and Local Search for 3-SAT problem on Graphic Hardware". 2006 IEEE International Conference on Evolutionary Computation. Vancouver, BC, Canada: IEEE. pp. 2988–2992. doi:10.1109/CEC.2006.1688685. ISBN 978-0-7803-9487-2. S2CID 8142372.
  27. ^ Cahon, S.; Melab, N.; Talbi, E.-G. (May 2004). "ParadisEO: A Framework for the Reusable Design of Parallel and Distributed Metaheuristics". Journal of Heuristics. 10 (3): 357–380. doi:10.1023/B:HEUR.0000026900.92269.ec. ISSN 1381-1231. S2CID 14972999.
  28. ^ Jähne, Paul (2016). Mayr, Heinrich Christian; Pinzger, Martin (eds.). Overview of the current state of research on parallelisation of evolutionary algorithms on graphic cards (PDF). Bonn: Gesellschaft für Informatik, FRG. ISBN 978-3-88579-653-4. OCLC 962381748. {{cite book}}: |work= ignored (help)
  29. ^ García-Calvo, Raúl; Guisado, Jl; Diaz-del-Rio, Fernando; Córdoba, Antonio; Jiménez-Morales, Francisco (January 2018). "Graphics Processing Unit–Enhanced Genetic Algorithms for Solving the Temporal Dynamics of Gene Regulatory Networks". Evolutionary Bioinformatics. 14. doi:10.1177/1176934318767889. ISSN 1176-9343. PMC 5898668. PMID 29662297.
Retrieved from "https://mdwiki.org/wiki/Population_model_(evolutionary_algorithm)"