Genetic Algorithm to Traveling Salesman Problem

Abstract

In this paper, we apply a genetic algorithm to TSP. Since in TSP, a tour must pass through edges in E' ( E) at least once, it is necessary to involve E' and the information of direction in the chromosome. However, if we use the existing chromosome structure, the length of the chromosome becomes 2 jE0j and the size of the solution space becomes 2jE0j jE0j!. In the previous study, since the chromosome uses two kinds of information (E' and the direction), the results and the time to find a near-optimal solution vary according to the method of applying genetic operators. To resolve these defects, this paper proposes a new structure of chromosome for TSP.