Jump to content

Mating pool

From Wikipedia, the free encyclopedia
Visual representation of the position of the mating pool during the genetic algorithm process.

A mating pool is a concept used in evolutionary computation, which refers to a family of algorithms used to solve optimization and search problems.[1]

The mating pool is formed by candidate solutions that the selection operators deem to have the highest fitness in the current population. Solutions that are included in the mating pool are referred to as parents. Individual solutions can be repeatedly included in the mating pool, with individuals of higher fitness values having a higher chance of being included multiple times. Crossover operators are then applied to the parents, resulting in recombination of genes recognized as superior. Lastly, random changes in the genes are introduced through mutation operators, increasing the genetic variation in the gene pool. Those two operators improve the chance of creating new, superior solutions. A new generation of solutions is thereby created, the children, who will constitute the next population. Depending on the selection method, the total number of parents in the mating pool can be different to the size of the initial population, resulting in a new population that’s smaller. To continue the algorithm with an equally sized population, random individuals from the old populations can be chosen and added to the new population.[1][2][3]

At this point, the fitness value of the new solutions is evaluated. If the termination conditions are fulfilled, processes come to an end. Otherwise, they are repeated.

The repetition of the steps result in candidate solutions that evolve towards the most optimal solution over time. The genes will become increasingly uniform towards the most optimal gene, a process called convergence. If 95% of the population share the same version of a gene, the gene has converged. When all the individual fitness values have reached the value of the best individual, i.e. all the genes have converged, population convergence is achieved.[1][4]

Mating pool creation

[edit]
Parental selection methods used in the creation of a mating pool.

Several methods can be applied to create a mating pool. All of these processes involve the selective breeding of a particular number of individuals within a population. There are multiple criteria that can be employed to determine which individuals make it into the mating pool and which are left behind. The selection methods can be split into three general types: fitness proportionate selection, ordinal based selection and threshold based selection.

Fitness proportionate selection

[edit]

In the case of fitness proportionate selection, random individuals are selected to enter the pool. However, the ones with a higher level of fitness are more likely to be picked and therefore have a greater chance of passing on their features to the next generation.[1][4]

One of the techniques used in this type of parental selection is the roulette wheel selection. This approach divides a hypothetical circular wheel into different slots, the size of which is equal to the fitness values of each potential candidate. Afterwards, the wheel is rotated and a fixed point determines which individual gets picked. The greater the fitness value of an individual, the higher the probability of being chosen as a parent by the random spin of the wheel. Alternatively, stochastic universal sampling can be implemented. This selection method is also based on the rotation of a spinning wheel. However, in this case there is more than one fixed point and as a result all of the mating pool members will be selected simultaneously.[4][5]

Ordinal based selection

[edit]

The ordinal based selection methods include the tournament and ranking selection. Tournament selection involves the random selection of individuals of a population and the subsequent comparison of their fitness levels. The winners of these “tournaments” are the ones with the highest values and will be put into the mating pool as parents. In ranking selection all the individuals are sorted based on their fitness values. Then, the selection of the parents is made according to the rank of the candidates. Every individual has a chance of being chosen, but higher ranked ones are favored[4][5]

Threshold based selection

[edit]

The last type of selection method is referred to as the threshold based method. This includes the truncation selection method, which sorts individuals based on their phenotypic values on a specific trait and later selects the proportion of them that are within a certain threshold as parents.[6]

References

[edit]
  1. ^ a b c d Regupathi, R. “Cost Optimization Of Multistoried Rc Framed Structure Using Hybrid Genetic Algorithm.” International Research Journal of Engineering and Technology (IRJET), vol. 04, no. 07, July 2017, p. 890., www.irjet.net/archives/V4/i7/IRJET-V4I7211.pdf.
  2. ^ Schatten, Alexander (19 June 2002). "Genetic Algorithms".
  3. ^ Mitchell, Melanie; Taylor, Charles E. (November 1999). "Evolutionary Computation: An Overview". Annual Review of Ecology and Systematics. 30 (1): 593–616. doi:10.1146/annurev.ecolsys.30.1.593. ISSN 0066-4162.
  4. ^ a b c d Beasley, D., Bull, D. R., & Martin, R. R. (1993). An overview of genetic algorithms: Part 1, fundamentals. University computing, 15(2), 56-69.
  5. ^ a b Gandhi, Sonali (4 September 2020). "A Comparative Analysis of Selection Scheme" (PDF). International Journal of Soft Computing and Engineering (IJSCE). 2: 131–134.
  6. ^ Hartmut, Pohlheim. "Evolutionary Algorithms 3 Selection". Geatbx. Retrieved 15 September 2020.