A Comprehensive Guide to Genetic Algorithms (and how to code them)

On the Origin of Genetic Algorithms

Rishabh Anand
Aug 28, 2018 · 10 min read
Charles Darwin, 19th century evolution theorist and author of the book, ‘On the Origin of Species’

Original article by Rishabh Anand

In the mid 19th century, Charles Darwin postulated the theory of evolution and how it played a key role in enabling organisms to adapt to their environments through natural selection – a process where the fittest in a given population survive and live long enough to pass on their traits and characteristics to future generations to ensure their survival.


What’s happening currently?

Harnessing the sheer amount of computational power we now possess, ML algorithms, specifically deep neural networks, have leveraged our large pools of data, both structured and unstructured, to deliver insights, leads, predictions and much more with a high degree of accuracy.

Inception V4: state-of-the-art Computer Vision model vastly used for classification and transfer learning

State-of-the-art ML models can now classify, categorise, and generate data from scratch with a few hours/days of training. Deep Neural Networks have now proliferated into multiple domains, now being able to work with different data formats ranging from images to audio, many of such networks having surpassed human level capabilities in said areas. Below is an instance of an agent playing Atari games:

An RL agent playing Breakout on an Atari emulator

Enter, Reinforcement Learning

The reinforcement learning loop.

Where do Genetic Algorithms fit in?

Genetic Algorithms (GA) work on the basic principles of evolution as it is a meta heuristic to natural selection and the various subprocesses that occur spontaneously. This involves incorporating the 4 fundamental steps of evolution:

  • Fitness
  • Selection
  • Crossover
  • Mutation

Together, these 4 processes, when performed on a population of agents yield the fittest agent for the task being performed.

From this point onwards, when I mention the word “survive” or any variant of the word, I mean to say that the agent remains part of the top few agents that are viable enough to move on to the next generation.

Model Fitness

For different tasks, the fitness function undergoes slight modifications. However, in essence, its primary function is to play the role of a differentiator in the population that separates the stronger learners from the weaker learners.

Model Selection

This leaves us with empty slots in the population giving us space for the new stronger offspring on the remaining parent agents.

Model Crossover

During crossover, all the properties of one of the agents are split up or broken down into more fundamental units and half of them are exchanged with those of the other parent agent. Biologically speaking, a part of the genes from one parent are connected to another part of the genes from the other to create an offspring that has two sets of gene segments increasing its chances of survival in terms of fitness.

A diagram visualising the process of crossover where part of the DNA (combination of binary digits) is split up and exchanged with the remaining part of the DNA of the other parent to create an offspring with two segments of different DNA.

Model Mutation

Similar to the Fitness function, the mutation function also needs to be finalised beforehand. This mutation can range from a point mutation that occurs in one specific location in the gene sequence (DNA) or in multiple locations.

Either way, mutation is an integral component of the evolutionary process as our model cannot survive for long without it.

Stopping criteria

In most cases it’s a single minimum threshold value that an agent needs to cross in order to complete the activity or task. In others, there can be a range of criteria or a group of thresholds that the model needs to cross every generation to be called the fittest/one of the fittest in the population.

The genetic algorithm cycle starts from assessing the fitness score of all the agents in current generation, selecting the top percentage of all models, crossing over the models with one another randomly and finally mutating them to introduce randomness into the population. The cycle resets from this point onwards and stops if the stopping criteria is met.

All together, these 4 processes enable the production of new, stronger, more viable offspring that are capable of surviving in an environment.


Learning through application

While studying about GA, I came across loads of interesting projects ranging from the famous traveling salesman problem to the knapsack problem. I even found myself discovering schedule-building agents that create the optimal schedule for events.

While all this did seem interesting, I wanted to take things to the next level. I created a network optimisation algorithm that takes an existing Neural Network architectures hyper-parameters and enhances it to perform better with higher accuracies on the testing set. You’d probably say this is discount NASNet, but this endeavour was slightly challenging, thereby making the final outcome more wholesome and fulfilling 🎉.

As always, the code for this article can be found here on my GitHub.

Note: I’m experimenting with the Polacode VS Code plugin that allows users to take aesthetic polaroid pictures of the selected code in the editor. If the code in the images is too small or jarring, please do tell me in the comments below so I can go back to using GitHub Gists.

For visibility purposes, I suggest reading the following part of the article on a large display such as a monitor or laptop.


Project brief

Now, for the bigger picture, we have a Network agent that comes up with a bunch of random hyper-parameters. There is a built-in function in Keras, model.predict() , that calculates the average fitness score for each Network agent over the testing set and assigns that score as the accuracy for the secondary agent.

Over time, the agent that has the better hyper-parameters comes out on top and is identified as the one with the best set of model hyper-parameters.


Functions and Objects involved

The Network agent object

Moving on to the main event loop, we have the necessary functions such as fitness(), selection(), crossover(), mutate() as discussed above. The fitness() calculates the accuracy of the model with the random hyper-parameters. Some of the model architectures do not work and break the code due to dimensionality issues or other errors, which is why we place the training and evaluation functions in a try-except block.. The selection() function is pretty self-explanatory and simple to understand — the top 20% of the models are allowed to move on to the next generation.

The Fitness function trains the model, evaluates the model and assigns the model its accuracy.
The Selection function sorts the models in terms of their accuracies from highest to lowest and selects the first 20% to move on to the next generation.

The important functions to look out for are the crossover() and mutation() functions. The quality of the child agents depend on the the quality of these functions ie. it creates offspring that are almost completely different from the parents and adds randomness and novelty to the gene pool and population.

For the crossover() function, the hyper-parameters of the parents are split between the two child agents created. A proportion of the hidden units are assigned to the child agents. The function isn’t that fancy (kinda ironic based on what I mentioned earlier) but this is just a project to explain a concept and I wanted to keep things simple (also, I couldn’t think of ‘interesting’ crossover and mutation functions).

The Crossover function for the Secondary Agents

For the Mutation function, I’ve summed the original hidden units with a random integer between 0 and 100 (as I said, I couldn’t think of an interesting function). The chances of a mutation occurring should be less that 0.1. This controls the randomness to a small but certain extent.

The Mutation function for the Secondary Agents

Down below, the main() function spawns agents into the environment. Every generation, the above-mentioned functions are run one after the other. At the end, the model that crosses the accuracy threshold of 99.5% is considered the best

The main event loop involves spawning agents, assessing their fitness, selecting the top few, crossing over to create new agents, and finally mutating some of them.

The code snippets above are only parts of the entire thing. So I urge you to visit the repo to get the source code for the project (Stars are appreciated 😁). All together, the different components work together in unison to generate the fittest model possible to achieve the task at hand (in this case, achieve an accuracy of 99.5% and above — again really ambitious).


In a nutshell

Feel free to clone the project repo and experiment with different architectures, crossover functions, and mutation functions! Any interesting results? Drop them down in the comments below!

Note: If there are any errors in the code, please do highlight them here. Much appreciated!


I have decided to (probably) make this a series on Genetic Algorithms and their applications in the real world with code examples to accompany them (if time permits). If you have any suggestions on what you want to read or want to chat in general, don’t hesitate to drop a line! You can contact me on LinkedIn! I love to talk about technology and its application in the real world!

Shoutout to Sarvasv Kulpati for his feedback on the draft-work. Go check out his profile for articles on science, tech and philosophy!

Here are some of the other articles I’ve written on Machine Learning and things related to up-and-coming technology:

Till then, I’ll see you in the next one!

Sigmoid

Making Machine Learning more accessible. One line of code at a time.

Rishabh Anand

Written by

Student • CV and NLP Practitioner • Journalist • Co-founder @ MLBlocks • Open-source Ninja • https://rish-16.github.io

Sigmoid

Sigmoid

Making Machine Learning more accessible. One line of code at a time.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade