Evolving Solutions With Genetic Algorithms

7 min readNov 27, 2017

Hi and welcome to this weeks post on algorithms inspired by nature. The previous weeks can be found the following links:

Ultimately as a deep learning enthusiast, I try to create neural solutions to the various problems I have to solve daily. Neural networks are comprised of weights and biases, which are optimised by an algorithm called backpropagation. As there is no free lunch, there are cases where backpropagation is not feasible, such as using a neural network to make a sequence of actions in an environment. Calculating the error the network made, and therefore the gradient to be back propagated is a non-trivial task, often because the success or failure of the network may not be realised until much later after it’s actions. In the reinforcement learning scene, there is a lot of work studying this issue of credit assignment, and alot of it is incredibly exciting, successful and I recommend checking it out if you are not familiar with the recent triumphs of RL.

As deep learning dudes and dudettes, is in these kinds of gradient-less optimisation techniques that we might turn to evolutionary algorithms, so that we can optimise the parameters (and or the architecture) of neural networks in order to get a policy (a neural network) that works robustly in a given environment. Next time I’ll use evolution to optimise a neural networks weights, but before I do that, we’ll look at the genetic algorithm, and apply it to a predefined optimisation task, such as the Rastrigin function.

What is a Genetic Algorithm?

First things first, as a genetic algorithm is from the metaheuristic algorithmic family, so what is a metaheuristic? A metaheuristic is a poor name for stochastic (random) optimisation algorithm which are often considered a last resort before using random or brute-force search in cases where one might not know how to find a good solution, but one would know how to grade a candidate solution. This family has covered all of the algorithms covered in the natural computing series so far.

The genetic algorithm was invented by John Holland in the 1970s, and of course, is based loosely on the theories of evolution.

In 1831, Charles Darwin set sail on the HMS Beagle on what would be a five year journey circumnavigating the world. The above illustration was published with Darwin’s notes, and it highlighted how four different sub-groups of Galapagos finches evolved with different beaks in geographically close, yet distinct islands with varying ecosystems. Natural selection favoured the beak that was best suited to the respective ecosystems major food source; species with a stronger beak prefered hard seeds whereas a smaller beak was better suited to insects. Therefore, the birds that had the beaks most suited to the environment they were in, would be more likely to survive and be observed by Charles Darwin.

It is this process of natural selection, that lead to distinct characteristics of birds, and that will lead to successful candidates for our optimisation problems. But how do we get and select these candidates?

Selection

There are several factors that characterise a genetic algorithm, and one is selection. In a genetic algorithm, there is a population of candidate solutions, which are often referred as genotypes, genes or chromosomes. I will use them interchangeably throughout this article. Once we have objectively measured each member of the population, like the birds beaks effectiveness in its environment, the genetic algorithm can select the fittest genes to remain the genepool.

In the above code, we see that each gene is rated by an objective function, and then it’s chance of passing on it’s genes is directly proportional to its fitness. This is known as roulette wheel selection, and whilst there are other forms of selection like tournament selection, it is fairly simple and robust method to implement. So what do we do with successful parents?

Crossover

When we have two parents (and note we are not limited to two — we could have n parents,) we perform a procedure called crossover. This is the genetic algorithm’s distinguishing feature and it involves how you mix parent’s genes to form children.

Studying the crossover code above, we see that there is uniformly random chance of inheriting either parent’s genes, for each index of the genetic vector. This is not the most simple method of crossover, as one could just take the first half of parent one, and the second half of parent two and concatenate the two to create the child. In practice though, I have noticed that I get better diversity by using the crossover method in the code above.

It is important to note that crossover is not a global search function. If you take a set of genetic vectors and perform various types of crossover on them, it will be folly to expect every conceivable vector from the crossover procedure. The reality will be that we are doomed to search within a finite space of possible vectors. To search effectively and beyond this finite space, you need something called mutation, which is effectively an injection of stochastic noise. However before we review that, I should mention that crossover isn’t entirely useless; it enables highly fit individuals to easily propagate their good genes across the population, so that improvements might be built, or found, on top of those.

Mutation

The next step after obtaining a new child is to mutate the genes, to search the feature space. It is a simple procedure, which can either be applied vector-wise or index-wise.

This will ensure that the search continues to grow and try new types of solutions.

A Genetic Algorithm Class

Taking the aforementioned points and combining them gives us a simple class, and I have embedded it here for ease of access. It is not however essential to memorise it, as a summary on it’s usage will be provided in the code box after!

Using it is very straightforward. The optimisation process is two fold, we firstly get the dna solutions via the .get_solutions() method, we evaluate the genepool with some external method related to the problem we are trying to solve, and then we supply the fitness list to the class so it knows which chromosomes are worth keeping and which are not.

A Toy Problem

The Rastrigin function is a performance test problem for optimisation algorithms such as genetic algorithm. It is typical of a nonlinear multimodal function, and is a difficult problem to solve as it is has many local minima and a large search space. The maths behind it is rendered in glorious LaTeX here:

Using the equation, we can create a hacky class that returns an error surface and that is also able to evaluate a single point (or gene.)

Running the above code gives us the below image, and so a surface to optimise with our genetic algorithm. The more yellow, the higher the surface, and therefore the worse the position, whereas, the darker and bluer, the better. The global optima is at the position [0.0, 0.0], and this is what we want our genetic algorithm to find.

Optimising Rastrigin

Taking all that we have seen so far, we can optimise and animate everything using matplotlib like the below gif. We begin behind a high hill but the GA still finds its way past that and down to the global optima.

Interestingly, a low mutation size or rate will mean the genetic algorithm will prematurely optimise to local minima. Increase this and we will find the global optima. The code to reproduce this is as such:

Conclusion

Wrapping it up, I have demonstrated the important metaheuristic, the genetic algorithm and how it works via crossover and mutation to search the feature space to find solutions. Here is a genetic flowchart of the optimisation process.

I have also introduced the rastrigin optimisation test function. Let me know if you have any questions in the comments below, or hit me up on twitter!

References and links

This blog post wouldn’t have been made without these links: