Genetic Algorithms

Tournament Selection in Genetic Algorithms

Tournament selection is one of the many selection strategies we use in Genetic Algorithms (GAs) to select individuals for crossover. In this article, we will take a quick look at GAs, selection strategies, and finally learn about tournament selection in detail.

Genetic Algorithm (GA)

Genetic Algorithms are metaheuristic algorithms based on the natural process of evolution that we use to solve optimization problems. This is particularly useful when the optimization problem is combinatorial and the search space is huge.

In GAs, we first randomly generate possible combinations. Every combination is called an individual. Then, we develop a fitness function that decides how fit an individual is and assigns a score to every individual in the population. Here, the population is the collective of all individuals. The fittest individual will give us the most optimal solution.

After this, we select the individuals from the population based on their fitness score to engage in crossover. A crossover is a process during which individuals exchange a portion of their combination. A selection strategy decides who gets selected and who doesn’t for crossover. Next, we select the individuals who would make it to the next generation and repeat the whole process. We continue repeating these steps either a certain number of times or until the average fitness score of the population plateaus.

The whole idea of GAs is to find the most optimal combination by having the most optimal individuals in a population exchange a part of their combination over and over again. However, the effectiveness of GAs depends on how we select these individuals. We call the strategies we use for selecting individuals selection strategies. Let’s now briefly examine what selection strategies try to do.

Selection Strategies

We generate individuals randomly so that we can search the search space for the optimal solution in many different places. However, if we keep searching in random places, we are never going to find the solution quickly enough. So, with time, we need to narrow down our search in such a way that we will be able to find the optimal solution.

This is the reason why we select the most fit individuals for crossover. By doing this, we hope that we will search in the right direction by following the most fit individuals. When the selected individuals engage in crossover, we randomize the solutions once again but within a limited search space. As we keep repeating this, we hope that we will continue to narrow the search space down in the right direction.

However, this may not always be the case. Sometimes, our algorithm can get stuck in a local optima. A local optima is the most optimal solution within a limited search space. The actual optimal solution, which we call the global optima, might exist in a different part of the search space. We call searching within a limited search space that gets narrower and narrower exploitation while we call searching the search space more broadly exploration.

Exploration vs. Exploitation

Exploitation leads to faster convergence but doesn’t guarantee that we will find the global optima. On the other hand, exploration takes a long time to converge but helps us find the global optima. For better results, we need to strike the right balance between exploration and exploitation.

It becomes exploitation if we repeatedly select only the most fit individuals for crossover. So, we use different selection strategies to find the right balance between exploitation and exploration. At the same time, each strategy may have its own parameters that we can adjust to decide the degree of exploitation and exploration.

We use the term selection pressure to refer to how far exploitation or exploration can occur. The selection pressure is proportional to the probability of the algorithm selecting the most fit individuals. When the selection pressure is high, exploitation becomes high, and vice versa. Nonetheless, we need to remember that what works for one problem might not work for another and it is important that we experiment with different selection strategies and hyperparameters.

There are various different selection strategies such as roulette wheel selection, tournament selection, rank selection, and steady-state selection. In this article, we will look at tournament selection in detail.

Tournament Selection

In tournament selection, we conduct tournaments among randomly selected members of a population and select the winner for crossover. We choose a winner based on the fitness score. The number of individuals participating in a tournament is a parameter that developers can tune. If the tournament size is high, then the selection pressure is high. This leads to exploitation.

The selection pressure goes up with the tournament size because a bigger tournament is more likely to have fitter individuals in the population. So, the weaker ones are less likely to win. On the other hand, in a small tournament, there is a high chance of weaker individuals contesting against each other. This reduces the selection pressure, leading to more exploration. If the tournament size is 1, then it becomes a random selection.

There are two varieties of tournament selection, namely with replacement and without replacement. Replacement refers to putting the individuals who take part in a tournament back into the population. When we perform replacement, we allow one individual to be selected more than once for crossover. This also gives the losers of tournaments additional chances of getting selected for crossover. When we don’t perform replacement, every individual gets the chance to take part in at least one tournament. This encourages exploration.

However, when we don’t replace individuals, the number of individuals we select for crossover is going to be less than the population size. This has to be accounted for when we select individuals for the next generation. Mostly, in addition to the individuals we select for crossover, we will have to use some strategy to find individuals from the current population to pass to the next generation to ensure the population size remains constant.

Summary

Genetic algorithms are metaheuristic algorithms based on evolution, which we use in combinatorial optimization problems. Selection strategies allow us to play around with the degree of exploitation and exploration in genetic algorithms. Tournament selection is one such strategy and it works by randomly selecting individuals for tournaments and selecting the most fit individual in a tournament for crossover. We can tune the tournament size to adjust the degree of exploitation and exploration.

Originally published at https://www.thearmchaircritic.org on September 29, 2023.