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.