# Genetic Algorithm for Travelling Salesman Problem

## Introduction

In my previous blog post “Travelling Salesman Problem”, I have presented the non-approximate brute force and integer linear programming solvers for solving TSP problems. However, since TSP problems are NP-hard, the brute force and integer linear programming solvers are just too slow to solve large TSP problems.

In this blog post, I would like to present a genetic algorithm solver for solving TSP problems approximately. Usually the genetic algorithm will produce solutions that are not too worse than the global optimum.

## Genetic Algorithm

### General Genetic Algorithm

The general genetic algorithm for solving an optimization problem usually follows the following protocol.

- Initialize the population randomly.
- Determine the fitness of the individuals.
- Until done, repeat:
- Select parents.
- Breed children by performing crossover and mutation.
- Determine the fitness of the children.
- Select the new population from the parents and the children.

### Genetic Algorithm for Travelling Salesman Problem

The solution of the TSP problem could be represented as an ordered list of size $n$ consisting of $1,2,\cdots,n$. Here we will fix the first value of the ordered list to be always $1$. The population could be initialized with random permutations of the ordered list $[1,2,\cdots,n]$. The fitness metric could just be the TSP travelling distance of the solution. The parents would be the individuals which have the highest fitness.

Because the TSP solution does not allow duplicated elements, the crossover operation and the mutation operation are a little bit special. We will perform crossover for ordered list and swap mutation for the TSP solution representations. For example, order 1 crossover was performed specifically in our implementation.

### Genetic Algorithm Solver for Travelling Salesman Problem Python Implementation

1 | from typing import List, Tuple, Union, Callable, Any |

We will inherit the most of the code for TSP baseline solutions from my previous blog post “Travelling Salesman Problem”.

1 | from itertools import permutations |

### TSP Problem Solver Execution

Running the following program will print out the solution for the TSP problem in the terminal.

1 | $ python tsp.py |

We happen to get the global optimum solution for the TSP problem. However, in most of the cases, we can’t get the global optimum.

### Genetic Algorithm Caveats

There are a lot of parameters used in the genetic algorithm, which will affect the convergence and the best fitness could possibly be achieved in certain iterations. When the algorithm almost converges, all the individuals would be very similar in the population, preventing the further exploration for the global optimum solution. There are some tricks to improve this situation, such as decreasing the parent pool size from generation to generation and increasing crossover size and mutation rate, which we did not investigate in our implementation of the genetic algorithm for TSP problems.

## Reference

Genetic Algorithm for Travelling Salesman Problem

https://leimao.github.io/blog/Genetic-Algorithm-For-Travelling-Salesman-Problem/