Solving TSP with a genetic algorithm (C++)

This is an implementation of a genetic algorithm that solves the traveling salesman problem, created as a part of an online course in artificial intelligence for game programming. Code written from scratch, theoretical information on TSP and genetic algorithms obtained mostly online besides an introductory lecture. Source and readme can be found here.

Here’s the output when calculating the best path between 20 cities each with a pair of coordinates ranging from (0,0) to (1000,500), 30 chromosomes and an end condition of 10000 of generations without improvement.

That run took about a second. You can find a path for any number of cities in a relatively short amount of time, especially if you tweak all of the different settings. Playing around with mutation rate and crossover probability can also yield some interesting results.

Help, I have no idea what all this is!
What you need to know about the traveling salesman problem can be found at Wikipedia and can be summarized in one sentence:

Given a list of cities and their pairwise distances, the task is to find the shortest possible route that visits each city exactly once and returns to the origin city.

Sound easy enough, but it’s actually a pretty interesting problem. One possible way to go about solving this is by using a genetic algorithm, this site provides and excellent introduction: http://www.obitko.com/tutorials/genetic-algorithms/index.php. Armed with this information, start out by reading the readme and then glance through the code again to get a feel for how I implemented each step of the algorithm. Keep in mind the outline of the basic algorithm:

  1. [Start] Generate random population of n chromosomes (suitable solutions for the problem)
  2. [Fitness] Evaluate the fitness f(x) of each chromosome x in the population
  3. [New population] Create a new population by repeating following steps until the new population is complete
  4. [Selection] Select two parent chromosomes from a population according to their fitness (the better fitness, the bigger chance to be selected)
  5. [Crossover] With a crossover probability cross over the parents to form a new offspring (children). If no crossover was performed, offspring is an exact copy of parents.
  6. [Mutation] With a mutation probability mutate new offspring at each locus (position in chromosome).
  7. [Accepting] Place new offspring in a new population
  8. [Replace] Use new generated population for a further run of algorithm
  9. [Test] If the end condition is satisfied, stop, and return the best solution in current population
  10. [Loop] Go to step 2

Recent Posts