Genetic Algorithm on TSP

In the previous blog post we discussed how Simulated Annealing can tackle the Travelling Salesperson Problem of connecting $n$ cities with the shortest path (with every city visited exactly once). In this blog post we investigate another method, inspired by biology and Darwin's theory of evolution. 

We introduce some evolutionary terms and how they relate to the optimization task; 

• an individual is a given solution/route, 
• a population $N$ of individuals is the set of $N$ solutions/routes, 
• a generation is the iteration count of the algorithm, 
• the fitness of an individual is determined by the objective value (the lower the total distance of a route, the fitter that route is),
• the reproductive selection process, where individuals are stochastically chosen to become parents and reproduce to give offspring,
• the chromosome/gene of a solution is an encoding of that solution,
• the mutation of a chromosome is an elementary stochastic transformation of that solution that occurs with some (typically small) probability $p_{\text{mut}}$,
• the crossover between two (or more) parent chromosomes is their stochastic combination yielding the offspring chromosome,
• the survival selection process is the process of choosing the fittest $N$ solutions/routes to survive in the end of each generation (we choose $N$ so that the population stays constant across generations).

The Genetic Algorithm is summarised by the pseudocode template that follows. The algorithm returns the fittest individual of the last generation.

Simulated Annealing can be thought of as a special case of the Genetic Algorithm, with population size

$N=1$ and $p_{\text{mut}}=1$. In such a case there is no selection or crossover and the mutation operations correspond to the elementary operations of Simulated Annealing such as the 2-opt/reversal of nodes and the transport operation discussed in the previous blog post. Hence, we set the mutation operations to be 2-opt and transport with equal probability $0.5$ each.  

Two common choices for stochastic reproductive selection of parents are the tournament selection (which draws $k<N$ individuals from the population and accepts the fittest one) 

and roulette wheel selection (which draws individuals with probability proportional to their fitness). 

According to Razali, tournament selection converges slower, allowing more exploration of the search space and hence outperforms the latter in solving TSP. 

Finally, the crossover operation between two chromosomes is a rather complicated process described in this blogpost. 

Overall, the genetic algorithm is more complicated and slower than Simulated Annealing and it has not been proven to consistently overperform the latter, but it is a promising competitor nonetheless.