Implementing Common Mutation Strategies

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

👈 Customizing Mutation in Your Framework | TOC | Other Methods to Combat Convergence 👉

You’ll likely only ever need to work with a few mutation strategies depending on the genotype of your solutions. The mutation strategy you use has less of an impact on your algorithm than, say, crossover strategy or selection strategy. The presence of mutation matters more — so long as the mutation strategy you choose maintains the validity of your solutions.

In this section, you’ll learn how to implement three different types of mutation that you can use for binary, permutation, and real-value genotypes. At the end of this section, you’ll find a list of other common mutation strategies to research and implement on your own.

Flip Mutation

Flip mutation, also known as bit flip mutation, is the type of mutation proposed in the Holland’s original genetic algorithm. It’s simple and effective on binary genotypes. Flip mutation “flips” some or all of the bits in the chromosome. So, if a gene is a 1, it’s flipped to a 0. If a gene is a 0, it’s flipped to a 1.

The following image depicts flip mutation:

Flip mutation can be implemented in a few lines of code using Elixir’s Enum library. First, at the top of your Toolbox.Mutation module, add the following line:

​ ​use​ Bitwise

Bitwise is a module in the Elixir standard library for working with bitwise operations. Bitwise is applicable here because flip mutation is essentially just a bitwise XOR between 1 and the value of a gene. XOR with 1 produces the desired flip because 1 XOR 1 is 0 and 0 XOR 1 is 1.

To implement flip mutation in Elixir, add the following code to your Toolbox.Mutation module:

​ ​def​ flip(chromosome) ​do​
​   genes =
​     chromosome.genes
​     |> Enum.map(& &1 ^^^ 1)
​ 
​   %Chromosomes{​genes:​ genes, ​size:​ chromosome.size}
​ ​end​

This function maps over every gene in chromosome and performs a bitwise XOR with the value at the gene and 1. Of course, this function changes every gene in the chromosome. Sometimes, you want to implement something less aggressive. The following function performs flip mutation with a given probability:

​ ​def​ flip(chromosome, p) ​do​
​   genes =
​     chromosome.genes
​     |> Enum.map(
​         ​fn​ g ->
​           ​if​ ​:rand​.uniform() < p ​do​
​             g ^^^ 1
​           ​else​
​             g
​           ​end​
​         ​end​
​       )
​ 
​   %Chromosome{​genes:​ genes, ​size:​ chromosome.size}
​ ​end​

This function simply adds a “coin-flip” to determine which genes to flip. The probability of a gene being flipped is equal to the provided parameter p. You can modify this p to adjust the aggressiveness of the flip mutation. In practice, a probability of around 50%, or 50% of the genes in a chromosome being flipped, is usually suitable.

Flip mutation is simple and effective. One drawback, however, is that it only applies to binary genotypes.

Scramble Mutation

Scramble mutation is the type of mutation you implemented in Chapter 1, ​Writing Your First Genetic Algorithm​. You simply shuffled all of the genes in a given chromosome to create a new chromosome. While shuffling the bits had no impact on the fitness of a chromosome, it served to ensure some percentage of your population remained different from the rest.

Scramble mutation is versatile in that it can apply to almost all genotypes. You saw it in practice with binary genotypes, but it also can apply to permutation genotypes and some real-value genotypes.

Scramble mutation is like shuffling a deck of cards. The following image demonstrates scramble mutation on a permutation genotype:

You can implement scramble mutation in Elixir using the Enum.shuffle/1 method. The following function demonstrates scramble mutation:

​ ​def​ scramble(chromosome) ​do​
​   genes =
​     chromosome.genes
​     |> Enum.shuffle()
​ 
​   %Chromosome{​genes:​ genes, ​size:​ chromosome.size}
​ ​end​

This function uses Enum.shuffle/1 to scramble or randomize all of the genes in the chromosome to create a new chromosome. You can also implement scramble mutation on a random slice of size n, like this:

​ ​def​ scramble(chromosome, n) ​do​
​   start = ​:rand​.uniform(n-1)
​   {lo, hi} =
​     ​if​ start + n >= chromosome.size ​do​
​       {start - n, start}
​     ​else​
​       {start, start + n}
​     ​end​
​   head = Enum.slice(chromosome.genes, 0, lo)
​   mid = Enum.slice(chromosome.genes, lo, hi)
​   tail = Enum.slice(chromosome.genes, hi, chromosome.size)
​   %Chromosome{​genes:​ head ++ Enum.shuffle(mid) ++ tail, ​size:​ chromosome.size}
​ ​end​

In this function, you pick a start point for your random slice. You then choose whether to slice forward or backward, based on the start point. Once you determine lo and hi, you divide your chromosome into three slices: head, mid, and tail. You recombine the slices, but shuffle mid.

Scramble mutation is versatile and effective. It does a good job of ensuring chromosomes change sufficiently to avoid premature convergence.

Gaussian Mutation

Gaussian mutation is a mutation operator meant specifically for real-value representations of chromosomes. It generates Gaussian random numbers based on the provided chromosome. A Gaussian random number is just a random number from a normal distribution.

The normal distribution is perhaps the most common distribution in statistics. If you know what a bell curve is, then you know what the normal distribution is. It’s a bell curve centered around 0 that slopes off in both directions as shown in the image.

In Gaussian mutation, you calculate the mean and standard deviation of the genes in the chromosome, and then use them to generate numbers in the distribution.

The idea behind Gaussian mutation is that you are able to slightly adjust a chromosome without changing it too much. The random numbers that replace the genes in your chromosome belong to the same distribution as the existing genes in your chromosome. It’s like picking new CEOs and managers from inside a company, rather than introducing new personnel to the mix.

To implement Gaussian mutation in Elixir, you first need to calculate the mean and standard deviation, and then you generate new numbers at every gene with :rand.normal/2. :rand.normal/2 pulls random numbers from a Gaussian or normal distribution. This code implements Gaussian mutation:

​ ​def​ gaussian(chromosome) ​do​
​   mu = Enum.sum(chromosome.genes) / length(chromosome.genes)
​ 
​   sigma =
​     chromosome.genes
​     |> Enum.map(​fn​ x -> (mu - x) * (mu - x) ​end​)
​     |> Enum.sum()
​     |> Kernel./(length(chromosome.genes))
​ 
​   genes =
​     chromosome.genes
​     |> Enum.map(​fn​ _ ->
​       ​:rand​.normal(mu, sigma)
​     ​end​)
​ 
​   %Chromosome{​genes:​ genes, ​size:​ chromosome.size}
​ ​end​

The variable mu represents the mean of the genes in the chromosome which is calculated by the sum of the genes divided by the length of the genes. sigma represents the standard deviation which is calculated by the sum of the distance squared between every gene in the chromosome and the mean divided by the length. You can think of standard deviation as a measure of how far something is from the mean.

After you calculate mu and sigma, you map through every gene in the chromosome and replace it with a number using :rand.normal/2.

Gaussian mutation is useful for real-value genotypes. It’s perhaps one of the most effective types of mutation for real-value genotypes because it introduces diversity to the population with small, incremental changes. Over time, Gaussian mutation does a great job of balancing diversity and fitness.

Other Mutation Strategies

Numerous mutation strategies aim to maintain the diversity of your population while also increasing the overall fitness of your population. Some are specific to specific genotypes and others are generalized for all genotypes. Below is a list of just a few. See if you can implement them:

• Swap: swap random pairs of genes.
• Uniform: replace genes with uniform random numbers.
• Invert: invert the order of the chromosome.

👈 Customizing Mutation in Your Framework | TOC | Other Methods to Combat Convergence 👉

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.