1. Intuition behind Genetic Algorithms
Let’s start with the famous quote by Charles Darwin:
It is not the strongest of the species that survives, nor the most intelligent , but the one most responsive to change.
You must be thinking what has this quote got to do with genetic algorithm? Actually, the entire concept of a genetic algorithm is based on the above line.
Let us understand with a basic example:
Let’s take a hypothetical situation where, you are head of a country, and in order to keep your city safe from bad things, you implement a policy like this.
- You select all the good people, and ask them to extend their generation by having their children.
- This repeats for a few generations.
- You will notice that now you have an entire population of good people.
Now, that may not be entirely possible, but this example was just to help you understand the concept. So the basic idea was that we changed the input (i.e. population) such that we get better output (i.e. better country).
Now, I suppose you have got some intuition that the concept of a genetic algorithm is somewhat related to biology. So let’s us quickly grasp some little concepts, so that we can draw a parallel line between them.
2. Biological Inspiration
I am sure you would remember:
Cells are the basic building block of all living things.
Therefore in each cell, there is the same set of chromosomes. Chromosome are basically the strings of DNA.
Traditionally, these chromosomes are represented in binary as strings of 0’s and 1’s.
Source : link
A chromosome consists of genes, commonly referred as blocks of DNA, where each gene encodes a specific trait, for example hair color or eye color.
I wanted you to recall these basics concept of biology before going further. Let’s get back and understand what actually is a genetic algorithm?
3. What is a Genetic Algorithm?
Let’s get back to the example we discussed above and summarize what we did.
- Firstly, we defined our initial population as our countrymen.
- We defined a function to classify whether is a person is good or bad.
- Then we selected good people for mating to produce their off-springs.
- And finally, these off-springs replace the bad people from the population and this process repeats.
This is how genetic algorithm actually works, which basically tries to mimic the human evolution to some extent.
So to formalize a definition of a genetic algorithm, we can say that it is an optimization technique, which tries to find out such values of input so that we get the best output values or results.
The working of a genetic algorithm is also derived from biology, which is as shown in the image below.
Source: link
So, let us try to understand the steps one by one.
4. Steps Involved in Genetic Algorithm
Here, to make things easier, let us understand it by the famous Knapsack problem.
If you haven’t come across this problem, let me introduce my version of this problem.
Let’s say, you are going to spend a month in the wilderness. Only thing you are carrying is the backpack which can hold a maximum weight of 30 kg. Now you have different survival items, each having its own “Survival Points” (which are given for each item in the table). So, your objective is maximise the survival points.
Here is the table giving details about each item.
4.1 Initialisation
To solve this problem using genetic algorithm, our first step would be defining our population. So our population will contain individuals, each having their own set of chromosomes.
We know that, chromosomes are binary strings, where for this problem 1 would mean that the following item is taken and 0 meaning that it is dropped.
This set of chromosome is considered as our initial population.
4.2 Fitness Function
Let us calculate fitness points for our first two chromosomes.
For A1 chromosome [100110],
Similarly for A2 chromosome [001110],
So, for this problem, our chromosome will be considered as more fit when it contains more survival points.
Therefore chromosome 1 is more fit than chromosome 2.
4.3 Selection
Now, we can select fit chromosomes from our population which can mate and create their off-springs.
General thought is that we should select the fit chromosomes and allow them to produce off-springs. But that would lead to chromosomes that are more close to one another in a few next generation, and therefore less diversity.
Therefore, we generally use Roulette Wheel Selection method.
Don’t be afraid of name, just take a look at the image below.
I suppose we all have seen this, either in real or in movies. So, let’s build our roulette wheel.
Consider a wheel, and let’s divide that into m divisions, where m is the number of chromosomes in our populations. The area occupied by each chromosome will be proportional to its fitness value.
Based on these values, let us create our roulette wheel.
So, now this wheel is rotated and the region of wheel which comes in front of the fixed point is chosen as the parent. For the second parent, the same process is repeated.
Sometimes we mark two fixed point as shown in the figure below.
So, in this method we can get both our parents in one go. This method is known as Stochastic Universal Selection method.
4.4 Crossover
So in this previous step, we have selected parent chromosomes that will produce off-springs. So in biological terms, crossover is nothing but reproduction.
So let us find the crossover of chromosome 1 and 4, which were selected in the previous step. Take a look at the image below.
This is the most basic form of crossover, known as one point crossover. Here we select a random crossover point and the tails of both the chromosomes are swapped to produce a new off-springs.
If you take two crossover point, then it will called as multi point crossover which is as shown below.
4.5 Mutation
Now if you think in the biological sense, are the children produced have the same traits as their parents? The answer is NO. During their growth, there is some change in the genes of children which makes them different from its parents.
This process is known as mutation, which may be defined as a random tweak in the chromosome, which also promotes the idea of diversity in the population.
A simple method of mutation is shown in the image below.
So the entire process is summarise as shown in the figure.
Source : link
The off-springs thus produced are again validated using our fitness function, and if considered fit then will replace the less fit chromosomes from the population.
But the question is how we will get to know that we have reached our best possible solution?
So basically there are different termination conditions, which are listed below:
- There is no improvement in the population for over x iterations.
- We have already predefined an absolute number of generation for our algorithm.
- When our fitness function has reached a predefined value.