Parent selection is the primary source of selection pressure in a Genetic Algorithm. This process determines which individuals from the current population will get to reproduce, thereby guiding the search toward better regions of the solution space. The key challenge is to balance the exploitation of the best-known solutions with the exploration needed to maintain population diversity. An overly aggressive selection strategy can lead to premature convergence, where a single, highly-fit individual quickly dominates the population, stifling the search for a true global optimum.

7.1 Fitness Proportionate Selection

This is one of the most common selection strategies, where the probability of an individual being selected as a parent is directly proportional to its fitness score. Fitter individuals have a higher chance of being chosen.

• Roulette Wheel Selection: This mechanism can be visualized as a circular roulette wheel divided into segments, where the size of each individual’s segment is proportional to its fitness. A fixed point is set, the wheel is “spun,” and the individual whose segment lands on the point is selected. The process is repeated to select another parent. Implementation typically involves these steps:
  1. Calculate the sum (S) of all fitness values in the population.
  2. Generate a random number between 0 and S.
  3. Iterate through the population, accumulating fitness values, until the partial sum exceeds the random number. The individual at that point is chosen.
• Stochastic Universal Sampling (SUS): This is an improvement over the Roulette Wheel method. Instead of one fixed pointer, SUS uses multiple, evenly-spaced pointers on the wheel. In a single “spin,” all parents for the next generation are selected simultaneously. By using evenly-spaced selection points, SUS ensures that the number of times a chromosome is selected is more tightly proportional to its expected selection count. This mechanism significantly reduces the sampling error where a single unlucky spin might miss a highly-fit individual or a lucky spin might over-select a less-fit one.
• Limitation: A critical drawback of these methods is that they do not work with negative fitness values.

7.2 Tournament Selection

In K-Way Tournament Selection, K individuals are chosen at random from the population. These K individuals then “compete,” and the one with the highest fitness is selected as a parent. This process is repeated to select the next parent.

• Key Advantage: A significant benefit of tournament selection is its ability to function correctly even with negative fitness values, making it more versatile than fitness proportionate methods.

7.3 Rank Selection

Rank selection is designed to solve a specific problem that can arise late in a GA’s run: when all individuals have very similar fitness values. In this scenario, fitness proportionate selection loses its selection pressure, as every individual has a nearly equal chance of being chosen.

Rank selection addresses this by ignoring the absolute fitness values. Instead, it first ranks all individuals in the population from best to worst based on their fitness. The selection probability is then based on this rank, not the fitness value itself. For example, as shown in the table below, even though individuals C, E, and B have very close fitness scores, their distinct ranks ensure they have different selection probabilities.

7.4 Random Selection

In this strategy, parents are chosen completely at random from the population. Because it applies no selection pressure toward fitter individuals, it effectively turns the GA’s search into a random walk and is therefore usually avoided.

After parents have been carefully selected, they are used to generate the next generation of solutions through the operators of crossover and mutation.