Travelling Salesman Solving Genetic Algorithm

The travelling salesman problem is basically: how to visit every city once, taking the shortest route between them. This problem has a lot of relevance still today, for example, postal routes and rubbish disposal routes e.t.c.

This project uses a hill climber algorithm to approximate the solution, this is much faster than using brute force to check every possible route for the shortest solution. The basic premise of a hill climber algorithm is that you start with a sub optimal solution, usually a random one, then you mutate it, if the mutated solution is better you keep it, if not, you undo the mutation and try again. This leads to a ratcheting effect where the solution can only ever get better. Due to the introduction of random mutation which are selected on, leading to an improvement over time, the hill climber is considered a genetic algorithm, albeit a very simple one.

Once the website is completed this project is a prime candidate for my first "Javascript + HTML5 Canvas" project, that would mean you could try it out on this website, instead of needing to download it.

Try it yourself: Salesman.jar

Source code (MIT License): Github

Help

If you are having trouble running the program, please try this quick guide.

What Am I Looking At?

Each blue circle on the screen represents a city. The white arrows that form a path between the cities are the 'tour'.

Whenever a city is added, it is added to the tour, meaning all cities are linked by the tour at all times. To start with the tour will follow a random path between all of the cities, the program will be constantly looking for a shorter path and will update the tour whenever it finds one.

At the top of the screen are some numbers:

Improved [x] seconds agoThis counts how many seconds it has been since the last improvement to the tour was found.
Generation: This is the number of 'generations' i.e. the number of times the genetic algorithm has been run on the current tour, this is reset every time the user modifies the number or location of the cities.
Improvements: This is the number of generations in which the mutation to the tour has shortened it. As time goes by and more improvements are made, it becomes harder to find a beneficial mutation and therefore the rate at which improvements are made will decrease.

At the bottom of the screen, next to the "Next Method" button, there is a box. The writing in the box describes the current type of mutation being used by the genetic algorithm.

Types of Mutation

How the different types of mutation work can be a little confusing, so here are two explanations of how they work:

A technical description of the process:

Randomise city position: A single city is chosen at random, the cities before and after it in the tour are joined and it is reinserted into the tour between another two cities.
Randomise city positions: The above mutation is performed between 2 and n times, where n is the length of the entire tour.
Reverse direction of tour section: This method takes a small section of the tour and 'untwists' it. Analogous to having a rubber band in a figure 8 and untwisting one side to make it a figure 0. This method is great at removing crossed paths.
Move one end of tour: This method cuts a random number of cities off the end of a tour, reverses the order of the route between them and then sticks the old end into the tour where the cut was made.
Swap two cities: This method chooses two random cities and then the cities before each of them in the tour are swapped round and the cities after them in the tour are swapped.

An abstract representation of the changes, ABC means a tour from city A to city B to City C:

Randomise city position: ABCDE -> ACDBE
Randomise city positions: ABCDE -> AECBD
Reverse direction of tour section: ABCDE -> ADCBE
Move one end of tour: ABCDE -> ABEDC
Swap two cities: ABCDE -> ADCBE

The Interface

A quick run through of what each button does:

Remove All Cities: This button resets the entire program.
Reset Solution: This button leaves all cities in the same place but resets the route the tour takes to a random one.
Add Random City: This button adds a city at a random location on the screen and adds it into the tour at a random location. This will reset the Generations and Improvements counters.
Add 10 Random Cities: This button is equivalent to pressing the previous button 10 times in succession.
Add 6 * 6 Grid: This button adds 36 cities, evenly spaced to form a grid. It will not remove any cities that are already present. This will reset the Generations and Improvements counters.
Add 10 * 10 Grid: This button adds 100 cities, evenly spaced to form a grid. It will not remove any cities that are already present. This will reset the Generations and Improvements counters.
Loop Tour: This checkbox allows the user to toggle whether the first and last cities in the tour are joined.

New City: When this option is selected, a new city is placed wherever the user clicks. This will reset the Generations and Improvements counters.
Move City: When this option is selected, The user can click on and then drag existing cities around, if a city is dragged off screen it is removed from the tour. This will reset the Generations and Improvements counters.
Delete City: When this option is selected, any city that the user clicks on will be removed from the tour. This will reset the Generations and Improvements counters.

Pause: When selected, the algorithm is not run. The user can still interact with the cities, placing, deleting and moving them, however the tour will not be changed and the type of mutation currently being used will not cycle automatically.
Automatic?: When selected, they type of mutation being used by the algorithm will cycle through a list of possible mutations. When set to automatic, the type of mutation will change every 2000 generations.
Next Method: This button allows the user to manually cycle through the current type of mutation being used by the algorithm.

Development log

~ February 2014 ~

Before publishing this project on my website I wanted to make sure that it was completely bug free and easy to use. I also noticed that most TSP solvers work with a complete circuit, so I added the option to seamlessly toggle between a tour which loops back to the starting city, and one which does not.

The major features added in this build are:

The menu has been split up to make it easier to use on thinner screens.
An option to loop the tour has been added.
The number of generations and improvements are displayed.
The method being used to mutate the tour is visible and can be controlled.

~ March 2013 ~

This update represents a large improvement in terms of the front and back end of the program.

The user interface has been made much simpler, instead of pressing keys it is now possible to interact with the mouse.

The structure of the program has also been significantly cleaned up, improving efficiency massively and allowing for the genetic algorithm to apply more intricate mutations to the tour. This means that there are no longer any local optima in the fitness landscape and the algorithm can never get stuck with a sub-optimal solution forever.

While technically possible to evolve a perfect solution in every situation, if there are 100s of cities in a tour, it might take a very long time to untangle particular sub-optimal sections of a route.

Try it yourself: salesman-032013.jar

The major features added in this build are:

The user can now interact more easily, using the mouse instead of keys.
Performance improvement by removing the need for multiple tours on which to run the algorithm.

~ April 2012 ~

This program creates 50 random tours, it improves all of them using a hill climber algorithm. It displays the best or worst solution, decided by the user. The reason for having so many tours at the same time is that my current algorithm can get stuck in a fitness landscape valley.

Try it yourself: salesman-042012.jar

The major features added in this build are:

A grid of cities can be added to the tour.
The user can add randomly placed cities to the tour.
There is a help screen which lists the keys used to place and remove cities.
A red bar indicates how frequently new improvements are being made.