The Traveling Salesman Problem

The traveling salesman problem(TSP) is: given N cities, if a salesman starting from his home city is to visit each city exactly once and then return home, find the order of a tour such that the total distance traveled is minimum. The TSP is a classical NP-complete problem which has extremely large search spaces and is very difficult to solve. People have tried to use both exact and heuristic or probabilistic methods to solve the TSP.

The objective function for the N cities two dimensional Euclidean TSP is the sum of Euclidean distances between every pair of cities in the tour. That is:

Where, , are the coordinates of city i and , equals , . We also make some changes to the encoding, selection, and recombination.

Recombination

Our sequential path representation (a ordered list of cities to visit) means that traditional crossover and mutation operators are not suitable for TSPs. Instead we use Greedy Crossover [5]. Greedy crossover selects the first city of one parent, compares the cities leaving that city in both parents, and chooses the closer one to extend the tour. If one city has already appeared in the tour, we choose the other city. If both cities have already appeared, we randomly select a non-selected city. Mutation is implemented by swapping two randomly chosen sites.

Selection

When using traditional roulette wheel selection, the best individual has the highest probability of survival but does not necessarily survive. We use CHC selection to guarantee that the best individual will always survive in the next generation [2]. In CHC selection if the population size is N, we generate N children by using roulette wheel selection, then combine the N parents with the N children, sort these 2N individuals according to their fitness value and choose the best N individuals to propagate to the next generation. We found that with CHC selection the population converges quickly compared to roulette wheel selection and the performance is also better. To prevent convergence to a local optimum, when the population has converged we save the best of the individuals and re-initialize the rest of the population randomly. This results in slightly better performance.