“Any sufficiently advanced technology is indistinguishable from magic.” Arthur C. Clarke

In the context of artificial intelligence and machine learning, this quote by Arthur C. Clarke rings particularly true. One such “magical” technology is the Genetic Algorithm, a search heuristic that is inspired by Charles Darwin’s theory of natural evolution. This algorithm reflects the process of natural selection where the fittest individuals are selected for reproduction to produce the offspring of the next generation.

At first glance, the Genetic Algorithm may seem like a conjuring trick, a complex and mysterious process that magically solves optimization and search problems. It’s a spectacle to behold as it evolves a population of random solutions into a near-optimal solution, seemingly pulling the answer out of a hat.

But the real magic of the Genetic Algorithm is not in its ability to solve problems as if by magic, but in its elegant simplicity. Once you peek behind the curtain and understand its inner workings, you realize that its magic lies in its mimicry of the very processes that have shaped life on Earth.

In this blog post, we will demystify the Genetic Algorithm, breaking down its mechanisms and illustrating how it can be simply implemented in code. By the end, you will see that the true magic of technology is not in its complexity, but in the beauty of its design and the elegance of its execution. So, let’s pull back the curtain and explore the magic of Genetic Algorithms together.

What is a Genetic Algorithm?

In nature a living population evolves in order to better adapt to its environment, thereby improving its chances of survival and growth with every new generation. As individuals in each generation reproduce, they create new individuals with new characteristics (DNA). The stronger of these individuals are more likely to survive and pass their characteristics on to the following generation in what is known as natural selection or survival of the fittest. As the population evolves over a long time and many generations, it gets better, stronger, and more adapted to its particular environment.

A genetic algorithm takes these concepts and abstracts them so that by simulating the process of evolution it can evolve better and better solutions to a given problem with every new generation. In the algorithm individuals represent possible solutions to the problem and their DNA represents the input variables that influence the outcome of the solution. As the algorithm unfolds, solutions “reproduce” to create new solutions, the better ones survive, and over many many generations, the solutions get better and better until we reach our desired optimum, or the solutions simply stop improving.If this is still hard to grasp, don’t worry! We’ll break it down into pseudocode first, and then walk through the actual implementation.

Anatomy of a Genetic Algorithm

Despite its unquestionable power, the basic structure of a genetic algorithm is quite simple and involves only a few operations. Starting with a random population of individuals (each representing a potential solution to the problem being optimized), the algorithm proceeds to “evolve” new solutions through three main processes, Selection, Crossover, and Mutation.

There are various other processes and operations involved, and many different ways to go about implementing a genetic algorithm. Below is simple pseudocode that captures the essence of the algorithm and the main steps required.

Implementation

We only really need three main classes for this simple implementation:

• Population — A collection of individuals

• Individual — Represents a possible solution as a binary string of 0’s and 1's

• Fitness Function — Operates on an Individual’s binary sequence to evaluate the individual’s fitness

Population

Individual

An individual represents a possible solution in the population and is nothing more than a binary sequence of 0s and 1s. There are many representations that can be used, and we don’t need to use binary values explicitly, but a list of 0s and 1s is really easy to manipulate making the implementation of the other methods such as mutation and crossover much simpler.

We use the binary sequence to encode the input variables to the problem we are trying to optimize. As the individuals undergo Crossover and Mutation, their binary sequences of 0s and 1s are shuffled and altered. If we then decode these sequences after the changes, we will have new values for the variables they represent in order for us to evaluate the fitness of the new individual.

Fitness Function

We define an interface for all fitness functions. Each fitness function will have an Evaluate method that takes an individual and returns a double value representing the individual’s fitness. It will also provide a DecodeBinarySequence method that takes an individual and decodes its binary sequence into an array of doubles.

Initialization

In order for the algorithm to function it needs an initial population to work with. We initialize this population with a value indicating its size, or the number of individuals in the population. Each individual will have a random binary sequence of a given length.

We then evaluate the fitness of each individual in the population using a fitness function. The fitness function takes an individual and from its binary string calculates a value indicating how “good” that individual is. It essentially assigns a score to each individual so that we can later use this to select the best-performing individuals in the population. This evaluated population is the starting point for the genetic algorithm.

Selection: Survival of the fittest

Given the initial population, we now need to select some individuals as parents to produce children. There are various selection methods that can be implemented including Fitness Proportional Selection, Reward-based Selection, and Tournament Selection. The goal here is to select the better-performing individuals out of the population to ensure that the next generation is better than the previous.

In this implementation, I’ve opted for Tournament Selection. This involves selecting a number of potential candidates (the tournament size) and out of those, choosing the best candidate (the tournament winner).

It’s important to note that the goal here is to select better individuals more often than we select worse individuals to become the parents of new offspring. The value for the tournamentSize parameter is important here. We can see from the code that if tournamentSize is 1, we are going to get a purely random selection. If it is a large number, say 100 times the population size, then we are going to select the same individuals over and over again (i.e. the best of the best). We are going to use a value of 2 to ensure we get good diversity as well as fit parents. This is known as Binary Tournament Selection.

Crossover

Crossover is the algorithmic equivalent of Netflix and Chill. The genetic material from the two parents selected in the Selection process is mixed up to create new offspring. As with selection and other genetic operators, there are various different methods available including Single Point, Double Point, and Uniform Crossover. Depending on the nature of the problem being solved, some may be more appropriate than others but the goal is the same — create new unique individuals that share part of their DNA with their parents.

For a single-point crossover, a point along the parents’ binary sequences is chosen at random. All the bits in the sequence beyond this point are exchanged resulting in two new offspring.

Mutation

Mutation is a mechanism that introduces diversity within a population by introducing random changes in the genetic sequence of individuals. Because it is random it can create both low-performing individuals (i.e. bad solutions) and, just like the X-Men, superhero individuals (i.e. much much better solutions). The less fit get left behind during selection, and the superheroes will begin to pass their better genes to the next generation improving overall fitness.

In code, this is implemented as a method that operates on an individual’s binary sequence switching 0s to 1s and 1s to 0s.

Mutation is good in small quantities! Typically, very small values for mutationProbability are used to introduce randomness, and therefore variety, in the gene pool. This is a good thing as it increases the potential of evolving better solutions. We also need to remember to set individual.Fitness to 0 after mutation.

Elitism

Elitism is a mechanism that guarantees that the next generation is at least as good as the previous one. This is achieved by selecting a percentage of the best-performing individuals (elite individuals) from the current population and including them, without mutation, in the new generation.

In code, we select a percentage of the population and sort it in descending order by Individual.Fitness the Individual.IsElite property to true.

The BinaryMutation method discussed above only mutates individuals whose IsElite property is set to false. This ensures that the best of the best are included in the next generation, unchanged.

Full Implementation Code

You can have a look at the entire implementation of the classes and methods discussed above on Github.

Time for a test run!

Now that we have the code implemented, it’s time to have some fun! In order to test the Genetic Algorithm we need a problem challenging enough for the solver and with a known global minimum. Schaffer’s Binary F6 Function provides a perfect test landscape for the GeneticSolver as it has a singular global minimum at a point (0,0) and a myriad of peaks and valleys. The valleys represent local optima where the algorithm could get stuck. Knowing that we need to minimize the function to (0,0).

• Setting up the fitness function. We formulate the fitness function to evaluate the individual’s fitness based on Shaffer’s Binary F6 function by splitting the DNA binary sequence in two and converting the first half of the sequence to a double to represent the x coordinate, and the second half to a double to represent the y coordinate.

To run the solver we simply need to set some configuration parameters and call the GeneticSolver.Run() method. The configuration I used below was found by tweaking initial parameters to find a suitable configuration for the problem.

As the above results demonstrate, we begin with a completely random population of individuals and thanks to the magic of evolution we are able to minimize the test function to a point at (-2.3841E-05, -2.3841E-05). It’s not exactly (0, 0) and never will be, but it’s pretty close! Certainly within an acceptable tolerance for this test.

Notice how average population fitness over the course of some 40 generations converges towards 1.0. Since the GA would just keep going if not stopped, we should also define a stopping criteria. We can stop the algorithm based on one of three conditions; we reach a desired fitness threshold, the rate of change of fitness across generations falls below some threshold, or we reach a predetermined maximum number of generations.

Let’s take a moment to marvel at the extraordinary capabilities of this seemingly simple algorithm. We embarked on this journey with a completely random initial population, where x and y were birthed from an unpredictable binary string. Yet, through the application of a few straightforward processes that mirror the essence of biological evolution — elitism, selection, crossover, and mutation — the algorithm astoundingly evolved an optimal solution to our problem!

This is the true magic of the Genetic Algorithm: its ability to transform chaos into order, and randomness into precision, all while following the fundamental laws of nature.