Summary

The provided content discusses the role and nuances of mutation in genetic algorithms, particularly in the context of Elixir programming, emphasizing the balance between diversity and fitness to prevent premature convergence and improve algorithm performance.

Abstract

Mutation in genetic algorithms is analogous to biological mutation, introducing random changes to a chromosome's genes to maintain genetic diversity and avoid premature convergence, especially in scenarios with binary genotypes and small population sizes. It acts as a catalyst for change, providing a "push" to explore new solutions when selection and crossover alone are insufficient. The challenge lies in balancing mutation rates to ensure enough exploration without compromising the exploitation of good solutions. Typically, a mutation rate of around 5% is recommended to maintain this balance, although the effectiveness of mutation can be unpredictable and may require experimentation. Additionally, the concept of mutation aggressiveness is introduced as a way to fine-tune the extent of changes made during mutation, allowing for more granular control over the exploration process.

Opinions

Mutation is crucial for preventing premature convergence in genetic algorithms, which does not necessarily indicate the discovery of optimal solutions.
The mutation rate is a delicate parameter; too high and the algorithm behaves like a random search, too low and it may stagnate.
A static mutation rate around 5% is common, but dynamic rates that decay over time may also be used, drawing parallels to learning rates in other machine learning algorithms.
Mutation aggressiveness, an underutilized concept, can offer additional control over the mutation process by determining the extent of genetic changes.
The effectiveness of mutation is not guaranteed and can be difficult to quantify, necessitating empirical testing to assess its benefits.
The author suggests that readers may benefit from experimenting with different mutation rates and aggressiveness levels to optimize their genetic algorithms.

Understanding Mutation

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

👈 Breaking Codes with Genetic Algorithms | TOC | Customizing Mutation in Your Framework 👉

As with most of the other aspects of a genetic algorithm, mutation has a loose analogy to a real biological process. In biology, mutation is a random change in an individual’s DNA sequence that often manifests itself in physical traits. For example, if you have blue eyes, you can thank genetic mutation.

Mutation in genetic algorithms works in much the same way. It’s a random change to some or all of the genes in a chromosome. The purpose of mutation is to introduce genetic diversity into the population.

If you recall from Chapter 1, Writing Your First Genetic Algorithm, the algorithm you wrote to solve the One-Max problem struggled to find the best solution until you added mutation. When dealing with binary genotypes, premature convergence is more common because genes can only take on one of two values. The possibility of premature convergence increases when dealing with small population sizes relative to your search space.

Stimulating Change

Mutation works by stimulating change — it prevents your algorithm from becoming complacent. Imagine you roll a ball down a small hill. Halfway down the hill there’s a slight rise in elevation, but afterwards, the hill declines again very sharply. You roll the ball down the hill, but it doesn’t have enough momentum to make it over the bump. What do you do? You give it a little push. You can visualize this in the following image:

The purpose of mutation is to give your algorithms a little push in a different, possibly better direction. Mutations drive change when selection and crossover are otherwise not enough. The goal of mutation is to introduce new solutions that may improve upon or be better than old ones.

One thing that’s important to note is that premature convergence doesn’t necessarily mean your algorithm has reached a global or even local optimum. That is to say, premature convergence doesn’t mean your algorithm has found good solutions. Premature convergence simply means you’re no longer able to produce different solutions due to a lack of population diversity.

A final consideration is that while the intent of mutation is to stimulate change, it can be difficult to quantify whether or not it actually works. Genetic algorithms are sensitive to the random nature of their operators. Mutation is random, and sometimes it doesn’t improve your algorithms at all. For example, perhaps your first solution to the codebreaking problem converged faster than your second. It’s hard to predict or even prove that mutation will offer you any benefits at all. Sometimes you just have to try it.

Balancing Diversity and Fitness

The key struggle with mutation is finding a balance between population diversity and overall fitness.

Remember from Chapter 1, Writing Your First Genetic Algorithm, the struggle between exploration and exploitation. Mutation is a means of exploration. If you mutate too much, your algorithm works essentially the same as random search, and you have no way of exploiting the environment around you.

Mutation rate is the rate at which you mutate chromosomes. Some genetic algorithms call for the mutation of every child, some call for the mutation of only a few children, and some call for the mutation of only surviving chromosomes. The choice of who to mutate isn’t necessarily as important to your algorithm as the choice of how many you mutate.

A mutation rate of 5% essentially means that you mutate about 5% of your population every generation. It’s common to have a mutation rate at or around 5%, because it’s low enough that it still allows your algorithm to progress but high enough that it maintains the genetic diversity of your population. You may want to experiment with different mutation rates to see how they affect your algorithms.

One uncommon technique is to use a changing mutation rate. For example, you might want your mutation rate to decay over time — indicating that your algorithm should stop exploring at later generations. This technique is common with learning rates in other machine learning algorithms, but it’s not as effective with genetic algorithms.

Mutation Aggressiveness

An additional parameter that’s not often mentioned with mutation is the notion of mutation aggressiveness. The aggressiveness of a mutation dictates how much it changes a chromosome. For example, you can choose to change all of the genes in a chromosome with new genes, or you can choose to replace only some.

Most of the algorithms you find online will opt to mutate the entire chromosome, but sometimes you might find it useful to further control your mutations. In a later section, you’ll see exactly how you can introduce additional parameters to control how aggressive your mutations are.

👈 Breaking Codes with Genetic Algorithms | TOC | Customizing Mutation in Your Framework 👉

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.