How can we apply genetic algorithm to solve traveling salesman problem?

What is a genetic algorithm?

A genetic algorithm is a heuristic search and optimization technique inspired by the process of natural selection and genetics. It's used to find approximate solutions to optimization and search problems by mimicking the process of natural evolution.

How does it work?

The core functionality of a genetic algorithm can be described by the following steps:

1. Initialization: A population of candidate solutions (often called individuals or chromosomes). Typically, this first generation is randomly generated. Each individual represents a potential solution to the problem being optimized.
2. Fitness Evaluation: The fitness of each individual in the population is evaluated using a fitness function. This function quantifies how good or bad each individual is as a solution to the problem. Individuals with higher fitness scores are considered better solutions.
3. Selection: Individuals are selected from the current population to undergo genetic operations (such as crossover and mutation) to create a new generation of individuals. The selection process is typically biased towards selecting individuals with higher fitness scores, increasing the likelihood that better solutions are preserved and improved upon in subsequent generations.
4. Genetic Operations:
   • Crossover: Pairs of individuals are selected from the population, and their genetic information is exchanged to create new offspring. This mimics the process of reproduction and introduces new combinations of traits from the parent individuals.
   • Mutation: Random changes are introduced into the genetic information of individual solutions to explore new areas of the solution space. Mutation helps prevent the algorithm from converging to a local optimum and promotes diversity within the population.
5. Replacement: The new generation of individuals replaces the previous generation. The population size remains constant throughout the evolution process.
6. Termination: The algorithm terminates when a stopping criterion is met, such as reaching a maximum number of generations, finding a satisfactory solution, or when improvement in solutions stagnates over several generations.

Traveling salesman problem

Now let's think of why would we want to apply this approach to solve the Traveling salesman problem we described in What is the travelling salesman problem?. As we know from that article, the complexity of the problem grows so rapidly with the amount of cities, that looking for the solution by checking all the possibilities can take so long, long time.

If we want to shorten this time, and we are satisfied with getting not the most optimal solution, genetic algorithm can fulfill our expectations.

Fit the problem into the algorithm

Fitting the Traveling Salesman Problem (TSP) into a genetic algorithm involves representing the problem in a way that allows genetic operators (such as crossover and mutation) to manipulate and evolve candidate solutions efficiently. Here's how the TSP can be incorporated into a genetic algorithm:

1. Encoding the Solutions: Each individual in the population represents a potential solution to the TSP, which is a permutation of the cities to be visited. We can represent this as an array, where each element of that array corresponds to a city, and the order of the elements determines the order in which the cities are visited.
2. Initialization: The initial population is randomly generated, with each individual representing a random permutation of cities.
3. Fitness Evaluation: In the context of the TSP, the fitness function computes the total distance traveled for each individual's route. The goal is to minimize this distance. Individuals with shorter total distances (better routes) receive higher fitness scores.
4. Selection: Individuals are selected from the current population to undergo genetic operations based on their fitness scores. We can make the selection by creating a mating pool where each individual appears as many times as good its relative fitness is.
5. Genetic Operators:
   • Crossover: Pairs of individuals are selected from the population to undergo crossover, which involves exchanging genetic information to create new offspring. We can do this by selecting a subset of cities from one parent and filling the rest with cities coming form the other.
   • Mutation: Random changes are introduced into the genetic information of individuals to explore new areas of the solution space. We can simply achieve this by replacing an individual with a new random one, based at the mutation rate parameter.
6. Replacement: The new offspring generated through crossover and mutation replace the old generation and the process can start over again.
7. Termination: The algorithm terminates when a stopping criterion is met, such as reaching a maximum number of generations, finding a satisfactory solution, or when improvement in solutions stagnates over several generations.

By following these steps, the genetic algorithm iteratively evolves a population of solutions, gradually improving the quality of solutions over successive generations until a satisfactory solution is found, or the termination criterion is met.

Summary

Using genetic algorithms for the Traveling Salesman Problem offers an efficient, heuristic-driven approach to explore large solution spaces, balance exploration and exploitation, leverage parallelization, and adapt to problem specifics, resulting in high-quality solutions for TSP instances with many cities.

In the Implementing genetic algorithm in TypeScript we are going to look at the implementation.

See you really soon!