Implementing Common Selection Strategies
Balancing genetic diversity with strong solutions can be difficult to achieve without a smart selection strategy. Fortunately, there are common selection strategies that are battle-tested and proven to work well for many different problem sets.
The strategies you’ll learn about in this section are:
- Elitism selection
- Random selection
- Tournament selection
- Roulette selection
You’ll see how these strategies work, what each of their drawbacks are, and how to implement them in Elixir so you can add them to your toolbox.
Elitism Selection
Elitism selection is the simplest and most common selection strategy. The idea is simple: choose the best n chromosomes to reproduce. Elitism selection gives preference to the most elite chromosomes.
The problem with elitism selection is that it doesn’t factor genetic diversity into the mix at all. It’s common with elitism selection that your algorithms will converge onto a strong solution quickly but fail to improve from that point on because your population is too similar. Fortunately, you can counteract the lack of diversity with mutation, large populations, and even large chromosomes.
The algorithm behind elitism selection is straightforward. Given a population of sorted chromosomes, select the n best. The image shown should help you visualize elitism selection.
In Elixir, elitism selection is easy to implement using Enum.take/2. Open lib/genetic/toolbox/selection.ex and add the following function:
| | def elite(population, n) do |
| | population |
| | |> Enum.take(n) |
| | end |
That’s all there is to it. Because you took the time to sort your population in the evaluation step of your algorithm, you don’t need to worry about handling it here. Sorting guarantees that the first n chromosomes in the population are the best n chromosomes. That means you can simply call Enum.take/2 which returns the first n elements of an enumerable.
Elitism selection is fast and simple, but it can lend itself to premature convergence.
Random Selection
Random selection, when compared to elitism selection, lies on the opposite end of balancing genetic diversity and fitness. Random selection pays no mind to a chromosome’s fitness and instead selects a completely random sample of chromosomes from the population.
Random selection can be useful if your problem absolutely requires genetic diversity. This is an uncommon requirement, but it can pop up in certain cases. For example, novelty search is the search for new, different solutions. Rather than rewarding solutions for being strong, novelty search rewards solutions for being different.
One unique application of novelty search is scenario generation. In scenario generation, you’re trying to come up with different, valid scenarios from a set of starting scenarios. For example, you could use novelty search to generate different starting configurations for Sudoku or crossword puzzles.
In novelty search, you could also design a fitness function that evaluates chromosomes based on how different they are; however, this could also overcomplicate your problem. Perhaps you want fitness to reflect a different aspect of your problem, like the difficulty of the puzzle. You could then use random selection to ensure you’re maintaining your population’s genetic diversity.
Random selection, like elitism selection, is straightforward. You can think of random selection like picking cards out of a shuffled deck or choosing names out of a hat.
Elixir provides a convenient function named Enum.take_random/2 that makes the implementation of random selection almost identical to elitism selection. Add the following function to Genetic.Toolbox.Selection:
| | def random(population, n) do |
| | population |
| | |> Enum.take_random(n) |
| | end |
Enum.take_random/2 selects n random chromosomes from the population. This function will select chromosomes without any consideration of fitness.
Random selection is uncommon, but it can be useful in special cases. If your goal is genetic diversity, random selection is the way to go.
Tournament Selection
Tournament selection is a strategy that pits chromosomes against one another in a tournament. While selections are still based on fitness, tournament selection introduces a strategy to choose parents that are both diverse and strong.
Tournament selection works like this:
- Choose a pool of n chromosomes where n is the “tournament size.”
- Choose the fittest chromosome from the tournament.
- Repeat.
The image might help you visualize tournament selection a little better.
The beauty of tournament selection is that it’s simple, yet it effectively balances genetic diversity and fitness. The strongest solutions will still get selected, but they’ll be mixed in with weak solutions that might otherwise have not been picked.
In tournament selection, tournaments can be any n-way: the tournament size can be any number from 1 to the size of the population. Notice, however, a 1-way tournament is equivalent to random selection, and a tournament the size of your population is equivalent to elitism selection.
Tournament selection works well in parallel and can effectively balance genetic diversity and fitness. One drawback of tournament selection is that it might not be appropriate for smaller populations.
You can implement tournament selection with two approaches: with duplicates and without duplicates. If you allow duplicate parents to be selected, you risk allowing your population to become less genetically diverse; however, you greatly simplify and speed up your algorithm. If you don’t allow duplicates, your algorithm is slower, but genetic diversity will increase.
This is how you implement tournament selection with duplicates in Elixir:
| | def tournament(population, n, tournsize) do |
| | 0..(n-1) |
| | |> Enum.map( |
| | fn _ -> |
| | population |
| | |> Enum.take_random(tournsize) |
| | |> Enum.max_by(&(&1.fitness)) |
| | end |
| | ) |
| | end |
Allowing duplicates simplifies tournament selection. This implementation uses a range to create and then map over a list of size n. A tournament is conducted at every iteration where the strongest individual is selected from the tournament pool. The result is a list of selected chromosomes—some of which will be identical.
Alternatively, the following is how you implement tournament selection without duplicates in Elixir:
| | def tournament_no_duplicates(population, n, tournsize) do |
| | selected = MapSet.new() |
| | tournament_helper(population, n, tournsize, selected) |
| | end |
| | |
| | defp tournament_helper(population, n, tournsize, selected) do |
| | if MapSet.size(selected) == n do |
| | MapSet.to_list(selected) |
| | else |
| | chosen = population |
| | |> Enum.take_random(tournsize) |
| | |> Enum.max_by(&(&1.fitness)) |
| | tournament_helper(population, n, tournsize, MapSet.put(selected, chosen)) |
| | end |
| | end |
This implementation is slightly longer and uses a helper function, but the idea is the same. You use a MapSet to ensure no duplicate chromosomes are selected. Notice that this implementation uses the same code to implement a tournament at every iteration.
One thing you might notice is that the code can be optimized a little using tail-recursive calls. You can disregard this for now as it will be covered in Chapter 11, Optimizing Your Algorithms.
Tournament selection is useful when you want to effectively balance genetic diversity with fitness. One thing you should remember is that tournament size will affect the balance in your selected parents. You can experiment with different tournament sizes to see what gives you the best results.
Roulette Selection
Roulette selection, also known as fitness-proportionate selection, chooses parents with a probability proportional to their fitness. Roulette selection puts every chromosome on a roulette wheel based on their fitness. Individuals with higher fitness occupy a larger space on the roulette wheel—meaning they have a higher chance of getting picked. You then spin the wheel to select parents. Like tournament selection, roulette selection can be implemented with or without duplicates.
Roulette selection attempts to balance genetic diversity and fitness based on probability. Individuals that are more fit have a higher chance of getting selected; however, it’s still possible that individuals that are less fit will get selected as well. Think of it like this: in Wheel of Fortune, the more valuable spaces have a smaller area, meaning the probability of landing on them is lower. The relationship is the same in roulette selection, albeit in reverse.
The following image might help you visualize roulette selection:
Roulette selection is by far the slowest and most difficult algorithm to implement; however, it does a great job of maintaining the fitness of a population while including some diverse parents.
This is how you can implement roulette selection with duplicates in Elixir:
| | def roulette(chromosomes, n) do |
| | sum_fitness = |
| | chromosomes |
| | |> Enum.map(&(&1.fitness)) |
| | |> Enum.sum() |
| | |
| | 0..(n - 1) |
| | |> Enum.map(fn _ -> |
| | |
| | u = :rand.uniform() * sum_fitness |
| | chromosomes |
| | |> Enum.reduce_while( |
| | 0, |
| | fn x, sum -> |
| | if x.fitness + sum > u do |
| | {:halt, x} |
| | else |
| | {:cont, x.fitness + sum} |
| | end |
| | end |
| | ) |
| | end) |
| | end |
To get a better understanding of what’s going on here, look at each section of code starting with the following section:
| | sum_fitness = |
| | chromosomes |
| | |> Enum.map(&(&1.fitness)) |
| | |> Enum.sum() |
This section calculates the total fitness of the population. This step is necessary to determine the proportion of the roulette wheel that each chromosome will occupy.
Now, examine the following section:
| | 0..(n-1) |
| | |> Enum.map(fn _ ->) |
You should be familiar with this pattern by now. It’s necessary to simulate a loop from 0 to n. In this case, you need to loop n times because you want to select n individuals.
| | u = :rand.uniform() * sum_fitness |
| | chromosomes |
| | |> Enum.reduce_while( |
| | 0, |
| | fn x, sum -> |
| | if x.fitness + sum > u do |
| | {:halt, x} |
| | else |
| | {:cont, x.fitness + sum} |
| | end |
| | end |
This is where the real magic happens. The first line calculates a random value u, which represents one spin of the wheel. You then use Enum.reduce_while/3 to loop over individuals in the population until you’re within the selected area. Once you reach the selected area, you stop the reduction and return the selected individual.
Roulette selection is the slowest and most complex selection strategy presented here. You should try simpler strategies like tournament selection before experimenting with roulette selection.
Other Types of Selection
These selection strategies are by no means the only ones out there. You’ll see numerous takes on selection and selection strategies. You can find descriptions of new and unique selection strategies in academic papers and in tutorials online. You might find it useful to research the following and try to implement them on your own.
- Boltzmann selection: selection according to a “temperature” function.
- Stochastic universal sampling: selection at evenly spaced intervals.
- Rank selection: selection based on “rank” in the population.
Remember, selection strategies are nothing more than algorithms for choosing samples from a population. Any statistical sampling strategy would work as a selection strategy. You could even implement your own unique selection strategy.