Genetic Algorithm to Traveling Salesman Problem
Generate an AI Snapshot to get a quick, structured summary of this paper.
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A new structure of chromosome for TSP is proposed, since in TSP, a tour must pass through edges in E' at least once, it is necessary to involve E' and the information of direction in the chromosome.
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.