Chapter 7 Preventing Premature Convergence

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

👈 What You Learned | TOC | Breaking Codes with Genetic Algorithms 👉

The previous two chapters were dedicated to the process of making better populations from an existing population. Chapter 5, ​Selecting the Best​, focused on choosing solutions for reproduction that give you the best opportunity to increase the overall fitness of your population. Chapter 6, ​Generating New Solutions​, focused specifically on the process of creating new solutions.

Correctly applying selection and crossover on populations is vital to the success of your genetic algorithms. Selection and crossover alone are sufficient for a complete genetic algorithm — you don’t need any additional steps for varying your population if you don’t want to. However, using selection and crossover alone can lead you into a common pitfall: premature convergence.

Premature convergence refers to the stalling of progress in your algorithms as a result of a lack of genetic diversity in your population. As you saw in Chapter 5, ​Selecting the Best​, over time, populations tend to drift toward a similar genetic pattern. To understand why this can be problematic, consider this small population of binary chromosomes as shown in the image.

Notice the first gene in every chromosome. If your objective was to maximize the number of 1s in each sequence, it would be impossible for you to reach an optimal solution with crossover alone. The first gene in every chromosome is a 0 — there’s no way to turn that gene into a 1. In practice, you would call this a converged allele.

Remember from Chapter 3, ​Encoding Problems and Solutions​, an allele is simply the value of a particular gene. A converged allele is one that is the same in a majority of the solutions of the population.

While it’s not practical to have a population size of 5 with chromosomes of size 5, it doesn’t mean this phenomenon isn’t possible in practice. In the next section, you’ll implement a genetic algorithm with and without mutation to see the very real impact of premature convergence.

Population Diversity and Premature Convergence

INFORMATION

It’s generally agreed upon that mutation works to prevent premature convergence because it helps maintain population diversity. It’s understood that a decrease in population diversity has a direct correlation to premature convergence; however, there’s no real formalized understanding or measures of population diversity. So, while you may intuitively understand your algorithm stopped improving because there’s insufficient diversity in the population, there’s no formal definition for when a population is considered converged.

👈 What You Learned | TOC | Breaking Codes with Genetic Algorithms 👉

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.