An exploration with Python
You can view the notebook for this project here.
Travelling Salesman Problem
The Travelling Salesman Problem, TSP, describes a scenario where a salesman wishes to visit a number of cities, while taking the shortest possible route, before returning home to the start point. While it may appear simple, this problem not only has no known polynomial time solution, but there is also no time-efficient way to prove that a given solution is in fact optimal.
Instead, we often use heuristic algorithms to give an approximate solution that is sufficient for many practical uses. In this article, we will explore a different approach to generating a ‘good’ solution using a Genetic Algorithm. For a more in-depth discussion of the difficulties of the TSP, as well as a summary of some of the heuristic methods used to solve it, check out this article.
Genetic Algorithm
A Genetic Algorithm, GA, is a machine learning technique that is modelled on biological evolution. It is a guided random search algorithm that can explore a large solution space very efficiently. A GA involves building a population of ‘chromosomes’ which act as potential solutions to the…
Be the first to comment