The Genetic AlgorithmQuentin Lee - 14 November 2018
Recently I learned a lot about genetic algorithms and how these algorithms could be used to solve specific problems. This post will explain the concepts of a genetic algorithm and how every step of the genetic algorithm works.
A genetic algorithm is an evolutionary strategy to find the optimal solution of a certain problem. This algorithm can be compared to the way species evolve. If you have a population, after several years the weakest individuals will die, while the strongest individuals will survive and create new children. After thousands of years, species will have evolved to species that can live much better in the current environment, because only the strongest individuals will be able to reproduce.
So how are we going to use this in the genetic algorithm. To explain the genetic algorithm better, we are going to use a well known problem which is often solved using a genetic algorithm. The problem we will try to solve is the traveling salesman problem. This problem is about a salesman who has to visit some cities and he wants to know what the best order is to visit the cities. So what we need to find out is in which order the salesman will travel the least distance.
First we need to find a way to encode different solutions for this problem. Genetic algorithms use chromosomes and genes to encode the solution. Chromosomes are in this case a list of genes which contains the order the salesman will visit the cities. You could say a chromosome is a possible solution. A gene is in this case an integer which will refer to a city.
Now we have found a way to encode different solution, we are able to create the first generation of solutions. Often, you just randomly create different solutions. After that you calculate the fitness of each solution using a specified function. In this case you should use a function like 1/(distance traveled), because the shorter the route the better the solution. After that you need to sort all solution based on the fitness.
The next step is to find 2 parents for the reproduction of the next generation. A common way to select 2 parents, is using roulette wheel selection. In the previous step, the fitness of all individuals has been calculated. Roulette wheel selection creates a slice for every individual in the 'wheel'. The size of the slice corresponds to the fitness. A higher fitness will result in a bigger slice, so the chance an individual with a high fitness will be chosen as a parent is higher than an individual with a low fitness. After that we start the roulette wheel twice and the 2 individuals which has been selected are the parents for the next generation.
Once we have 2 parents, the next step is to create the next generation. For every new chromosome in the next generation, we first apply crossover to the 2 parent chromosomes. You can find more about crossover here. After that we will apply mutation to the chromosome. First we have to specify a mutation rate. This mutation rate will specify the amount of mutations that occur for 1 individual. We often want a small mutation rate, because otherwise the decent solution you found, may become worse and it could very long to find the best solution. What mutation should occur, depends on the situation. In our case, we should randomly swap 2 genes, but in other cases, we might want to just change the value of a gene.
After applying crossover and mutation for many children, we have created a new generation. For this generation we will apply the same process. So we need to calculate the fitness, choose two parents and create a new generation. We repeat these steps until a stopping condition has met. Such stopping condition could be a number of generations. Another example of a stopping condition is when we have not found better solutions after several generations. At the end, the individual with the highest fitness of the generation will contain the best solution for the specified problem
These are the basics of a genetic algorithm. First you have to find a way to encode the different solutions. Then you will create the first generation. For this generation you will calculate the fitness of each individual, select 2 parents and create a new generation until a stopping condition has been met. There are many ways to optimize a genetic algorithm, which I will talk about in a different post.