Genetic Algorithm
Follow step-by-step instructions to solve the traveling salesperson problem with a genetic algorithm.
Genetic algorithms are a class of algorithms that take inspiration from genetics. They simulate the process of natural selection to find solutions to optimization problems through a sequence of steps that starts with randomly creating a population of potential routes, calculating the distance of each solution (route), and selecting the best solutions via a fitness function. The fitness of each solution is the trip’s total distance. The best solutions are combined to create new solutions, and the process will be repeated until a satisfactory solution is found.
Genes/chromosomes
One possible solution (sequence of stores) is a chromosome.
A single element of the chromosome is called a gene. Each gene represents a single store in the order of the trip.
In the simplest case, the population is composed of two chromosomes.
The genetic algorithm repeatedly modifies a population of chromosomes (one possible route).
Selection
Based on the fitness score, a certain percentage of the population is selected. We start with x (in this case, 2) chromosomes that are randomly generated. It’s unlikely that we come across the optimal solution with this first random pick (selection). But it’s also unlikely for the initial chromosome to be the worst route. However, certain chromosomes will be fitter than others.
Crossover
The genetic algorithm combines the best solutions by using a process called crossover. Genes from these two chromosomes are combined (crossover or reproduction) to create new solutions so that now there are two parent solutions and one new offspring solution (which is a combination of parts of the two parent solutions).
New chromosomes are generated until the population number is reached. The smaller the crossover rate, the more new chromosomes are generated.
Mutation
Then, random changes (mutations) are introduced to the new chromosome to explore further routes of the solution space.
All possible solutions are evaluated based on a cost function. If the child is the weakest, we delete it and start with a new mutation. Otherwise, we remove the weaker of the two parents and then repeat the whole process with the two remaining chromosomes.
The genetic algorithm needs parameters such as population size, crossover rate, mutation rate, and selection criteria.
Parameters
The