Introduction to Genetic Algorithm with a website to watch it solve Traveling Salesman Problem live
❤️ Source Code on Github: Link to Repository
📦 Demo: Link to Website
Genetic Algorithm is a programming technique that mimics animal evolutions to solve intractable problems. In one sentence, it is “randomly try out solutions, select the ones that are better (they have better genes), breed them over generation.” 🦍🐒🚶
As summarized above, these are the characteristics a problem should have in order to use Genetic Algorithm (GA):
- ✅ We want the best “solution”
- ✅ There is no known algorithm to solve this problem efficiently
- ✅ We can QUANTIFY how good or bad a solution is
- ✅ We can combine parts of two (or more) solutions
Traveling Salesman Problem (TSP) is such a problem. The formal definition is this:
Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?
TSP is a perfect match for GA. We want the shortest tour. It can’t be solved in polynomial time (NP-Hard) because suppose there are 19 cities, then I have 19 choices of which one to visit first, 18 choices of which one to visit second, …, 1 choice of which one to visit at last. In total, that’s 19! possibilities and if I have a computer that can test 1 billion tours per second, it’s going to take 19! / 1,000,000,000 ~ 3.85 years to finish. Therefore, I will use Genetic Algorithm and Google Maps API to solve and visualize this problem.
Genetic Algorithm can be divided into 5 parts: Initialize. Current Population. Calculate Fitness. Selection. Crossover/Mutation. I will walk through them sequentially.
Initialize is fairly simple. We just randomly generate a sequence/array of cities to travel. For example, [0,5,3,2,1,4] means we will travel to city 0 first, then city 5, then city 3, then city 2, then city 1, and finally city 4. We call this sequence/array an individual. 🐵
Current Population is nothing different, except we will have an array of individual. This array is the population we want to breed and evolve. It has a size of popSize. 🐵🐵🐵🐵🐵🐵🐵🐵
Calculate Fitness is the process to rank/sort the population based on each individual’s fitness. In TSP, an individual’s fitness is the total distance travelled. To give a concrete example, if we have the following population,
then individual #0 has a fitness of 75 because traveling from city 0 to city 2 to city 4 to city 5 to city 3 to city 1 takes 75 miles in total.
Selection. Just like Darwin’s theory of natural selection (or survival of the fittest), we also want the individuals that have less total distance to survive. However, we just want them to be more likely to survive instead of entirely wiping out other individuals, this way we avoided converging to local optimal solution too quickly. There are many ways and published papers about how to select. For me, I am going to use the following simple technique (6 and 3 are just magic numbers):
- Initially give each individual the same probability to be selected = 1/8
- Multiply the two fittest (shortest distance) individuals’ probability by 6
- Multiply the remaining top half individuals’ probability by 3
- Normalize the probabilities
For the above population, individual #3 and #0 are the two with the shortest distance, and individual #2 and #1 follow. So this is each individual’s probability to be selected after normalization:
Finally, it is time to generate our next population! We want to select pairs (i.e. 2 individuals) for popSize times so that the selected pair can “give birth to” new individual (breeding). 👶
For the pairs selection part, we will simply generate a number between 0 and 1 called threshold. And we start from 0, accumulate as we walk through the Selection Chance array, whenever the current cumulative sum is ≥ threshold, we select the individual with the current index we are at, and we repeat this process another time to select two individuals. Here is an example pair:
For the breeding part, we will use the following method:
- Randomly decide parent A or parent B goes first
- Randomly generate a crossover index from 1 to popSize — 2
- Copy cities from the first parent [0…crossover index]
- Copy any cites that aren’t already in the child from the second parent
Again, to give a concrete example, suppose parent #1 goes first and the crossover index is 2, then the child individual is this as we first copy from parent #1[0…2] = [0,5,3] and then any cities not included in child from parent #3:
Finally, we should add the notion of mutation to increase a little bit more randomness to prevent early convergence. For this, we define a variable representing mutation chance mutChance. If we mutate, simply pick two random indices in the child and swap their values.
This is one iteration of the Genetic Algorithm. Once we have popSize children generated, we are going to replace the current population with the new population and ready to move on to the next iteration. We will repeat all of the above numIterations times. After all iterations, we select the fittest individual in the final population as the solution.
🌏 To give a more direct sense of Genetic Algorithm, I have actually implemented the above process via Google Maps API. Each “city” described above is an address the user inputs in the search bar. Variables popSize, mutChance, numIterations are actual variables I used in the implementation. Again, here are the links:
THAT’S IT! GENETIC ALGORITHM IS NOW UNDER YOUR VAULT OF ALGORITHMS🎉🎉🎉！！！