The applet on this page demonstrates two ways of generating solutions
to the Travelling Salesman problem
- evolution and brute force. If you cannot see the applet, make sure your browser has Java enabled and
that the version of your Java plug-in is 1.5.0 or later.
The basic premise of the Travelling Salesman problem is that there is a salesman who must
visit a set of cities. He must visit each city exactly once and must return to his starting
city. The problem is to find the shortest route. This is not as easy as it might sound because
the number of possible routes increases factorially with the number of cities. In other words, for
5 cities there are 5! (120) possible routes and for 6 cities there are 6! (720). A salesman who
had to visit the 15 European capitals in this example would have 1,307,674,368,000 (over 1.3
trillion) possible routes to consider.
Evolutionary algorithms provide a way to perform a non-exhaustive search of this huge search
space and to still find a good (though not necessarily optimal) solution. The applet on this page
uses the Watchmaker Framework to find routes
using a simple evolutionary algorithm. The evolutionary operators are a mutation operator
that changes the order of cities in a route, and an ordered cross-over operator that splices different
routes together without duplicating or omitting any cities. The fitness function simply calculates the
total length (in kilometres) of the route.
