Customizing Selection in Your Framework

Genetic Algorithms in Elixir — by Sean Moriarity (45 / 101)

👈 Exploring Selection | TOC | Implementing Common Selection Strategies 👉

In Chapter 2, ​Breaking Down Genetic Algorithms​, you briefly learned about hyperparameters and how to pass configuration options to your framework. At the time, the only hyperparameter you could change was population size.

Selection introduces two more hyperparameters: selection strategy and selection rate. In this section, you’ll tweak your framework to allow for changes in both.

Creating a Selection Toolbox

Before you begin, you’ll want a place to store some common selection strategies that you may need to solve some of the problems you encounter. Create a new folder called toolbox. toolbox is your toolbox of genetic operators. You’ll implement modules for selection, crossover, and mutation in the toolbox so you always have them available when you need them.

For now, create selection.ex and add the following module definition:

​ ​defmodule​ Toolbox.Selection ​do​
​ 
​   ​# ...strategies here​
​ 
​ ​end​

Whenever you implement a new selection strategy, add it to your toolbox so you never have to implement it again.

Changing Selection Strategies

Open up genetic.ex and examine select. It looks like this:

​ ​def​ select(population, opts \\ []) ​do​
​   population
​   |> Enum.chunk_every(2)
​   |> Enum.map(&List.to_tuple(&1))
​ ​end​

Right now, your algorithm implements elitism selection in which you always select the most fit chromosomes for crossover. You’ll want to adjust it so it can accept many different kinds of selection. To do that, add the following:

​ ​def​ select(population, opts \\ []) ​do​
​   select_fn =
​     Keyword.get(opts, ​:selection_type​, Toolbox.Selection.elite/2)
​   parents =
​     select_fn
​     |> apply([population])
​   ​# rest goes here​
​ ​end​

Keyword.get/3 takes the option list and searches for the key :selection_type. If nothing is there, it defaults to Toolbox.Selection.elite/2. You haven’t implemented this yet, but you will later.

apply/2 takes a reference to a function and a list of arguments and applies the function. All of your selection strategies will take a population as input, so that’s the only parameter you pass for now. In the next section, you’ll pass the additional parameter that’s required.

Adjusting the Selection Rate

In your first few genetic algorithms, you selected 100% of the population for reproduction. The purpose of this was to simplify your algorithms. Now, you’ll need to account for different selection rates.

First, change select so it looks like this:

​ ​def​ select(population, opts \\ []) ​do​
​   select_fn =
​     Keyword.get(opts, ​:selection_type​, &Toolbox.Selection.elite/2)
​   select_rate = Keyword.get(opts, ​:selection_rate​, 0.8)
​ 
​   n = round(length(population) * select_rate)
​   n = ​if​ rem(n, 2) == 0, ​do​: n, ​else​: n+1
​ 
​   parents =
​     select_fn
​     |> apply([population, n])
​ 
​   leftover =
​     population
​     |> MapSet.new()
​     |> MapSet.difference(MapSet.new(parents))
​ 
​   parents =
​     parents
​     |> Enum.chunk_every(2)
​     |> Enum.map(& List.to_tuple(&1))
​ 
​   {parents, MapSet.to_list(leftover)}
​ ​end​

A few things are going on here. First, you extract the selection rate from opts. Next, you calculate n, which represents the number of parents to select. The math and if statement simply ensure you have enough parents to make even pairs.

Next, you extract the parents using apply/2 and your selection strategy. You then determine who wasn’t selected using Elixir’s MapSet. Finally, you turn the parents into tuples for crossover and you return a tuple containing the parents and the leftover.

Now, you’ll need to slightly modify evolve to reflect the changes you’ve made here. Change run to look like this:

​ ​def​ evolve(population, problem, generation, opts \\ []) ​do​
​   population = evaluate(population, &problem.fitness_function/1, opts)
​   best = hd(population)
​   IO.write(​"​​\rCurrent best: ​​#{​best.fitness​}​​"​)
​   ​if​ problem.terminate?(population, generation) ​do​
​     best
​   ​else​
​     {parents, leftover} = select(population, opts)
​     children = crossover(parents, opts)
​     children ++ leftover
​     |> mutation(opts)
​     |> evolve(problem, generation+1, opts)
​   ​end​
​ ​end​

Here you adjust run to account for select returning a tuple of parents and leftover chromosomes. Then you obtain the children by passing parents into crossover. Finally, you recombine children with leftover and mutate them before running an evolution again.

The practice of replacing parents with children in a genetic algorithm is fairly common. You’ll learn more about reinsertion strategies in Chapter 8, ​Replacing and Transitioning​. For now, this naive approach works fine.

Now you can customize your algorithms with any selection strategy you implement by passing in a reference to your selection function.

👈 Exploring Selection | TOC | Implementing Common Selection Strategies 👉

Genetic Algorithms in Elixir by Sean Moriarity can be purchased in other book formats directly from the Pragmatic Programmers. If you notice a code error or formatting mistake, please let us know here so that we can fix it.