A gentle introduction to genetic algorithm
When starting to conduct research about artificial intelligent, you may have heard about something called ‘Genetic algorithm’. After seeing this term, you might reluctant to dig into it as it contains the word ‘algorithm’. Fear not! In this article, I’ll show you the simplicity of genetic algorithm and hopefully inspire you to build one for your own.
What is genetic algorithm?
Genetic algorithm is basically a method that heavily inspired by the process of natural selection to find the best solution to a problem.
In nature, only the strong one survive, the process of eliminating the weak is called natural selection. Genetic algorithm use that same principle to eliminate the “weak” solutions and finally produce the best solution.
Usually, genetic algorithm is used when you cannot know what the solution will be like. For instance, you want to create a car that can navigate through different kind of terrains. You cannot know how that car is going to look like, but you know the goal of the car. In this case, the genetic algorithm can be used to generate the car to travel of different terrains but the car design will be decided by the algorithm.
The working process of genetic algorithm
As mentioned before, the genetic algorithm is heavily inspired by the natural selection so to see how genetic algorithm work, you should actually, look into how natural selection work.
The diagram above illustrates the process of natural selection. It is clear that this process involves 5 main steps. The initial step is selection, in this step, nature will select individuals that has strong gene from the initial population, after that they begin to step into the next stage which is mating. After been through mating step, they’ll produce a child, we call this step: “reproduction”. That specific child then mutated to add some variation to the gene and finally moved back into the population.
The process of genetic algorithm is pretty similar to the process above, the only different is that it added some additional details.
To begin with, the working process of genetic algorithm also start by having an initial population. The first main stage is calculate fitness, calculate fitness can be consider as a part of the selection process as it basically used to calculate the “score” of each individuals to indicate whether its a strong individual or a weak one. All the strong entities then selected and passed to a stage called cross over, this stage is like the mating stage in the previous diagram. In this stage, 2 random parents is selected from the strong entity list to perform something called crossover which we will discuss later. After performing cross over, a child is created and also mutated to add some variation to the gene. Finally, this child rejoin the population and the process repeat again.
What the heck is fitness
In genetic algorithm, fitness plays a pivotal role in the selection stage. Fitness is the “score” for picking an entity that get to pass on its traits. For example, if a person have a serious illness, his “fitness score” will be low and less likely to have a chance to have kids as his kids would also inherit his illness. Therefore, if a solution’s fitness is low, you might not want to create another solution base on it as the result would be as bad as the old solution.
Try to imagine you are given a problem, the problem is to find the best route for red riding hood to travel to her grandma house. Let's assume that she want to reach her grandma house in the shortest time as possible, therefore the fitness of a route can be calculated using the time it took her to travel. If there is a route that has the length of 400 meters and it took her 10 minutes to travel then its fitness will definitely less than the fitness of a route that is 500 meters long but only took her 8 minutes to travel as the fitness of a route is calculating base on the travel time, not the length of it. Therefore the 500 meters long route would be more likely to be selected to combine with other routes.
Selecting the good one!
Selecting the appropriate solution is what the genetic algorithm’s selection stage all about. After calculating the fitness score, the next step is to use some mysterious methods to select a list of solutions that can later be use to produce a better solution.
Although you can create your own way of selecting the fitting solutions, there are some famous methods that you can use:
- Fitness proportionate selection
- Tournament selection
- Truncation selection
- Fitness uniform selection
The list above is not an adequate list, you can find out more methods here.
Let’s take the first method as an example. Unlike its name, the actual concept behind this method is absurdly simple. The fitness proportionate selection A.K.A the roulette wheel selection, is the method of selecting “potential” solutions for recombination.
Imagine, if there are 10 marbles in a bag, specifically, 5 blue marbles, 3 red marbles and 2 white marbles. You can easily calculate that if you pick out a random marble from the bag, you will have 5/10 chance to pick a blue one, 3/10 for red and 2/10 for white. That’s how the fitness proportionate selection works, however, the process is a bit different.
In the fitness proportionate selection, a random number is first picked, then it will be used to compare with the fitness of a random picked solution. The fitness value is usually constrained to go from 0 to 1. If the random value is less than that fitness score then the solution will be picked. Thus, the higher the fitness of a solution is, the higher chance that it will be picked. For instance, if a random number goes from 0 to 1, there are 50% it will be less than 0.5 and 80% it will be less than 0.8, however, it will not likely to be less than 0.2, that means, if a solution has a 0.8 fitness, there are 80% it will be picked for recombination and solution that have 0.2 fitness will only have 20% to be picked. Although the 0.2 fitness solution is rarely picked but it also help variate the solution traits as that solution can contain some attributes that needed for later success.
Performing crossover
Crossover is the stage where selected solutions are combined to form new solutions. Just like the selecting stage, there are also many techniques of crossover and you can also find them here.
Similar to selection stage, in crossover stage, you can also invent your own crossover techniques, however, there are also some techniques that you can use:
- Single-point crossover
- Two-point crossover
- Uniform crossover
- Three parent crossover
For better understanding, I’ll explain the uniform crossover technique which is the technique that I reckon the most easiest technique to implement.
The uniform crossover method involved picking random part of the gene of 2 solution randomly to combine and create a new (hopefully better) solution.
The first step in uniform crossover is to select 2 random solutions from the set of solutions which are picked in the previous selection stage. Then each parts of the 2 solutions will be chose to add the the child solution base on a variable called the mixing ratio. The mixing ratio is the thing that decide the chance that a solution is likely to be picked to add to the child solution. For instance, there are 2 solutions: A and B and you want the child solution to have more parts which taken from solution A, you can increase the mixing ratio, after that loop through every parts of the solution A and B. In every loop, create a new random number and compare it with the mixing ratio, if it’s less than the mixing ratio then pick the solution A part else pick the B. Similarly, if the mixing ratio is 0.5 then A and B will have approximately 50% of being picked.
The picture above, demonstrate the child solution C generated using solution A and B with the mixing ratio of 0.5 or 50%. Each part of both of the solutions was decided to be picked or not base on the mixing ratio and the mixing ratio was compared with a random number to decide. It is like tossing a coin to pick where A should be use instead of B and vice versa.
Mutate the child !
No no no, we are not going to transform our children into some guys with metal claws and let them die on a random tree trunk!
Instead, adding mutation to a child is like helping them to
By thinking different, an individual can whether become the leader of the herd or a complete dumb-ass.
As you can see, the red child is going on a different path compared to other children. The reason for this, is because, when the red child is following the herd, we added some mutation to him and therefore, help him to pick a different path. Of course, that different path can also be a dead end, but clearly, in this case, the path is leading to success! That’s the true purpose of mutation stage.
To mutate a child, there are also a variety of techniques that you can use:
- Bit string mutation
- Flip Bit
- Non-Uniform
- Uniform
You can find more of them here.
To understand this better, I’ll demonstrate the “bit string mutation” technique.
Imagine, you’re making a bot to avoid objects in front of it. The bot will have to avoid all objects to reach the final destination and its natural state is moving forward. To avoid object, its gene will be a series of ‘left’ and ‘right’ strings which indicates how to bot will move.
The “bit string mutation” is usually used for binary string as this method flip 1 or more random selected bits in the gene. For example:
Now, try to transform 1 and 0 into left and right and think of how the bot will perform. As the bot can get stuck when it encountered a large object, the mutation will help its offspring to pick a new direction to move and avoid that object. Imagine, for many generations, the bot only turns right when he meet an object and die, but, in the next generation, the bot suddenly turned left as a right string in its gene was flipped to left and the bot eventually reached its destination. That’s basically how the ‘bit string mutation’ works.
The end of the process
After mutating the child, it will be joining back with other mutated child to reform a new population and the whole process start over.
So when does it stop? The answer is extremely simple, when do you stop practicing typing keyboard with 10 fingers? When your typing skill is perfect of course. Same thing with genetic algorithm, the process will stop if a certain solution’s fitness reached the desired fitness. For instance, you want the bot in the previous example to reach the destination with the smallest amount of time as possible.
You set the fitness threshold to 4 minutes, if the bot’s time to finish is more than 4 minutes, that means the process will repeat until the bot’s finish time is less than or equals to 4 minutes.
Conclusion
That’s the end of my article, I hope that after this article, you will have a better insights into genetic algorithm have inspired to build one of your own.
Here are some links for you to explore more about genetic algorithm:
- Daniel Shiffman videos about genetic algorithm:
- My example for using genetic algorithm to guess a passcode
- tutorialspoint tutorial about genetic algorithm
- Goran Muric video about an example using genetic algorithm to find path
