Travelling Salesman Problem The Travelling Salesman Problem, TSP, is a well known and popular problem that has become a standard for testing computational algorithms. The basic problem is that of a salesman working out the minimum distance tour of a number of cities, given their locations. Every city must be visited, but only once and the optimal solution has the lowest total distance and therefore the lowest travel costs. A TSP solver can find direct applications with similar cost benefits to a number of fields: route planning, job scheduling, electronic circuit board drilling, integrated circuit fabrication, etc. In this demonstration each solution is a set of numbers. The numbers correspond to the city names and the number of numbers in each solution equals the number of cities chosen for the problem. Solutions are treated like genes in a genetic algorithm. However care is taken to ensure that all solutions are 'legal' - each city is represented, but only once in the solution. Initially a population of 20 random, but 'legal', solutions are generated. Then, following the genetic algorithm, each generation of solutions is first tested and ordered in order of increasing total tour distance. Some of those with the shortest tours ( highest scorers ) are copied directly across to the next generation of population. The remainder of the next generation is then made up either by evolution (mutation) of single high scoring members of the last generation, or by children derived (genetic crossover) from a pair of high scoring parents in the last generation. Each genetic or evolutionary algorithm is applied in such a way as to lead only to 'legal' solutions. | |
|
