Applying Genetic Algorithms to the Traveling Salesman Problem

Shortest route in current generation

Shortest route found

Starting distance:
Shortest distance found:
Number of possible routes:
Current generation:
Individuals screened:

Algorithm Parameters

Population size
Mutation rate
Crossover rate
Elitism

An explanation of the algorithm parameters and implementation can be found here .

Instructions

  • Press START to begin searching for shortest route between the default provided points.
  • Algorithm parameters can be changed using the interface to the left.
  • To run the algorithm against a custom set of points, click CLEAR and then click on the canvas to specify points.
  • The app must be RESET before algorithm parameters are altered for the changes to take effect.

Background

The traveling salesman problem (TSP) is a classic algorithmic problem that seeks to find the most efficient route that traverses every given city and returns the salesman to the original city. The TSP, classified as NP-hard, is highly studied in theoretical computer science and is and has important applications in operations research .
A brute force approach to solving for the shortest route runs in O(n!) time, making this approach unrealistic for sample sizes of greater than a handful of cities. Assuming routes are symmetric (i.e. the distance between two cities is the same if the route is reversed), there exist (n-1)!/2 possible permutations. A problem consisting of 10 cities has 181,440 possible routes; 16 cities yields 653,837,184,000 possibilities. For even small sample sizes, this approach quickly becomes too computationally expensive for practical use.
Genetic algorithms are optimization algorithms inspired by the principle of Darwinian natural selection. Solutions to a problem are represented as individual chromosomes within a population and are evaluated for individual fitness/performance. The fittest individuals in the population reproduce, producing offspring with a combination of the parents' traits; the least fit individuals are removed from the population and replaced with the children. Further population variance/diversity is driven by random events modeled after chromosomal crossover and genetic mutation, resulting in a population that converges toward a more optimal solution with each generation.
This project visualizes the use of a genetic algorithm to solve the traveling salesman problem - points are chosen on a map/plane and the algorithm attempts to find the shortest path that traverses every point. Individual solutions are comprised of combinations of routes between two points on a map (genes). The individual's fitness is defined by the combined total distance covered by its component routes.