The Travelling Salesman

by Steve Harris


This program is an implementation of the famous Travelling Salesman problem. It tries to work out the shortest possible route that a salesman has to travel to visit several cities in different places. To do this, it uses an artificial intelligence routine called a Genetic Algorithm. You must decide how many cities the salesman has to visit, and how many generations the program must run for (sensible values are 20 cities and 500 generations). The program will then randomly choose the co-ordinates of each city, after which it it will try to find the best order in which to visit them.

At the end of each generation, the maximum fitness of the genetic algorithm will be displayed, along with the best solution to the problem. At the start of the run, these will be poor, with the paths crossing often, but as time passes, they will start to open out, until there are few or no crossings. You can press Escape at any time to return to the Desktop.

More information on this program can be found in the article Nature's Way: Exploring Genetic Algorithms in the magazine.


 Copyright RISC User 1993
