Understanding Reinsertion

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

👈 Creating a Class Schedule | TOC | Experimenting with Reinsertion 👉

Reinsertion is the process of taking chromosomes produced from selection, crossover, and mutation and inserting them back into a population to move on to the next generation. Look at evolve/4 in genetic.ex. It looks 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​}​​\tGeneration: ​​#{​generation​}​​"​)
​   ​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​

If you recall from Chapter 5, ​Selecting the Best​, you combined children and leftover and mutated the result to form a new population. This was a naive approach, but it ensured your population size remained fixed and worked well enough at the time.

Your goal with reinsertion is to utilize all of the chromosomes at your disposal to create a new population that has a good amount of genetic diversity and has a better fitness than your previous one. Your previous reinsertion strategy was to replace your parents with their children. This approach works well enough, but you’ll want to be able to experiment with different reinsertion strategies and take smarter approaches to creating new populations.

Now, you will see how you can implement a few common reinsertion strategies and integrate them in your framework. First, edit evolve/4 so that it matches this:

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

Here, you’ve broken your population down into four parts: parents, leftover, mutants, and children. mutants and children are combined to form offspring — this is the most traditional approach; however, you could just as easily choose to mutate your children or mutate your new combined population.

Next, you call reinsertion/4 to create a new_population. reinsertion/4 will use one of a number of reinsertion strategies to create a new population for you. Finally, you call evolve/4 on the new population.

You can create reinsertion/4 like this:

​ ​def​ reinsertion(parents, offspring, leftover, opts \\ []) ​do​
​   strategy = Keyword.get(opts,
​                          ​:reinsertion_strategy​,
​                          &Toolbox.Reinsertion.pure/3)
​   apply(strategy, [parents, offspring, leftover])
​ ​end​

In this function, you use apply to apply the specified reinsertion strategy. To customize a reinsertion strategy, you’d pass a function to the :reinsertion_strategy argument.

Next, you’ll want to edit the mutation function so that it only returns the chromosomes it’s mutated:

​ ​def​ mutation(population, opts \\ []) ​do​
​   mutate_fn = Keyword.get(opts, ​:mutation_type​, &Toolbox.Mutation.scramble/1)
​   rate = Keyword.get(opts, ​:mutation_rate​, 0.05)
​   n = floor(length(population) * rate)
​   population
​   |> Enum.take_random(n)
​   |> Enum.map(& apply(mutate_fn, [&1]))
​ ​end​

Next, you need to create your reinsertion toolbox. Create a file reinsertion.ex in toolbox. Inside the file, define a module Toolbox.Reinsertion. This module will contain all of your reinsertion strategies.

You now need to define a few reinsertion strategies in your toolbox.

Pure Reinsertion and Generational Replacement

Pure reinsertion is the type of reinsertion you used in the first few chapters of this book. Every chromosome in the old population is replaced with an offspring of the new population. With pure reinsertion, you can either treat mutants as offspring — which is fairly common — and ensure your selection rate and your mutation rate add to 1. Another option is to simply have a selection rate of 1 and mutate children.

Pure reinsertion is a type of generational replacement. Generational replacement refers to the process of creating an entirely new population so that there’s no overlap between populations. Technically, in a generational replacement strategy, offspring directly replace parents.

You’re likely to encounter two derivatives of generational replacement when working with genetic algorithms. They are μ+λ, read “mu plus lambda” and μ,λ, read “mu comma lambda.” In μ+λ replacement, a child competes with its parent for survival — the winner being the one with the larger fitness. In μ,λ replacement, more children than the required population size are created and the best children survive. You might also see μ,λ replacement referred to as fitness-based insertion.

Given parents, offspring, and leftovers, you can implement pure reinsertion like this:

​ ​def​ pure(_parents, offspring, _leftovers), ​do​: offspring

Notice only offspring is returned to the next generation.

Pure reinsertion maintains none of the strengths of the old population and instead relies on the ability of selection, crossover, and mutation to form a stronger population. Pure reinsertion is fast, but you could potentially eliminate some of your stronger characteristics in a population as a result.

Elitist Reinsertion

Elitist reinsertion or elitist replacement is a type of reinsertion strategy in which you keep a top-portion of your old population to survive to the next generation. With this strategy, you introduce the notion of a survival rate. The survival rate dictates the percentage of parent chromosomes that survive to the next generation. With a population of 100 and a survival rate of 20% or 0.2, you’d keep the top 20% of your parents.

One thing to consider with elitist reinsertion is how survival rate affects your population size. Later in this chapter, you’ll see how your population grows based on different survival rates.

Given parents, offspring, leftovers, and a survival_rate, this is how you would implement elitist reinsertion:

​ ​def​ elitist(parents, offspring, leftovers, survival_rate) ​do​
​   old = parents ++ leftovers
​   n = floor(length(old) * survival_rate)
​   survivors =
​     old
​     |> Enum.sort_by(& &1.fitness, &>=/2)
​     |> Enum.take(n)
​   offspring ++ survivors
​ ​end​

In this function, you combine parents and leftovers to represent your old population. You ensure the old population is sorted by each chromosome’s fitness in descending order. You then select the first n where n is calculated from the population size and the survival rate. Next, you combine offspring with the top n chromosomes from your old population.

Elitist reinsertion is probably the most common reinsertion strategy. It’s reasonably fast with small populations, and it works well because it preserves the strengths of your old population. The purest form of elitist reinsertion maintains only the strongest individual from the previous population. You can do this by specifying a selection rate that selects only one chromosome from the old population to move on to the next generation.

Uniform Reinsertion

Uniform reinsertion or random replacement is a reinsertion strategy that selects random chromosomes from the old population to survive to the next generation. The purpose of uniform reinsertion is to maintain as much genetic diversity as possible in the new population. Uniform reinsertion isn’t very common, but it’s worth trying to see what happens.

Just as with elitist reinsertion, you need to consider how your survival rate will impact your population size when using uniform reinsertion. With uniform reinsertion, you select n random chromosomes from the old population to survive to the next generation.

Given parents, offspring, leftover, and a survival_rate, you can implement uniform reinsertion like this:

​ ​def​ uniform(parents, offspring, leftover, survival_rate) ​do​
​   old = parents ++ leftover
​   n = floor(length(old) * survival_rate)
​   survivors =
​     old
​     |> Enum.take_random(n)
​   offspring ++ survivors
​ ​end​

This implementation of uniform reinsertion is very similar to elitist reinsertion with a few key differences. First, there’s no need to sort the old population based on fitness because you don’t care about the fitness when selecting survivors. Second, you use take_random/2 rather than take/2 to sample random chromosomes from the old population.

You’ll likely never want to use uniform reinsertion, but it can be good in maintaining the genetic diversity of your population.

👈 Creating a Class Schedule | TOC | Experimenting with Reinsertion 👉

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.