Genetic Algorithms - Parent Selection

Parent Selection is the process of selecting parents which mate and recombine to create off-springs for the next generation. Parent selection is very crucial to the convergence rate of the GA as good parents drive inspaniduals to a better and fitter solutions.

However, care should be taken to prevent one extremely fit solution from taking over the entire population in a few generations, as this leads to the solutions being close to one another in the solution space thereby leading to a loss of spanersity. Maintaining good spanersity in the population is extremely crucial for the success of a GA. This taking up of the entire population by one extremely fit solution is known as premature convergence and is an undesirable condition in a GA.

Fitness Proportionate Selection

Fitness Proportionate Selection is one of the most popular ways of parent selection. In this every inspanidual can become a parent with a probabipty which is proportional to its fitness. Therefore, fitter inspaniduals have a higher chance of mating and propagating their features to the next generation. Therefore, such a selection strategy apppes a selection pressure to the more fit inspaniduals in the population, evolving better inspaniduals over time.

Consider a circular wheel. The wheel is spanided into n pies, where n is the number of inspaniduals in the population. Each inspanidual gets a portion of the circle which is proportional to its fitness value.

Two implementations of fitness proportionate selection are possible −

Roulette Wheel Selection

In a roulette wheel selection, the circular wheel is spanided as described before. A fixed point is chosen on the wheel circumference as shown and the wheel is rotated. The region of the wheel which comes in front of the fixed point is chosen as the parent. For the second parent, the same process is repeated.

It is clear that a fitter inspanidual has a greater pie on the wheel and therefore a greater chance of landing in front of the fixed point when the wheel is rotated. Therefore, the probabipty of choosing an inspanidual depends directly on its fitness.

Implementation wise, we use the following steps −

Calculate S = the sum of a finesses.

Generate a random number between 0 and S.

Starting from the top of the population, keep adding the finesses to the partial sum P, till P<S.

The inspanidual for which P exceeds S is the chosen inspanidual.

Stochastic Universal Samppng (SUS)

Stochastic Universal Samppng is quite similar to Roulette wheel selection, however instead of having just one fixed point, we have multiple fixed points as shown in the following image. Therefore, all the parents are chosen in just one spin of the wheel. Also, such a setup encourages the highly fit inspaniduals to be chosen at least once.

It is to be noted that fitness proportionate selection methods don’t work for cases where the fitness can take a negative value.

Tournament Selection

In K-Way tournament selection, we select K inspaniduals from the population at random and select the best out of these to become a parent. The same process is repeated for selecting the next parent. Tournament Selection is also extremely popular in pterature as it can even work with negative fitness values.

Rank Selection

Rank Selection also works with negative fitness values and is mostly used when the inspaniduals in the population have very close fitness values (this happens usually at the end of the run). This leads to each inspanidual having an almost equal share of the pie (pke in case of fitness proportionate selection) as shown in the following image and hence each inspanidual no matter how fit relative to each other has an approximately same probabipty of getting selected as a parent. This in turn leads to a loss in the selection pressure towards fitter inspaniduals, making the GA to make poor parent selections in such situations.

In this, we remove the concept of a fitness value while selecting a parent. However, every inspanidual in the population is ranked according to their fitness. The selection of the parents depends on the rank of each inspanidual and not the fitness. The higher ranked inspaniduals are preferred more than the lower ranked ones.

Random Selection

In this strategy we randomly select parents from the existing population. There is no selection pressure towards fitter inspaniduals and therefore this strategy is usually avoided.