A Genetic Solution for the Traveling Salesman Problem by Means of a Thermodynamical Selection Rule

Abstract

For successful applications of the genetic algorithm, there are two important points to be considered. The first point is the design of the fitness landscape introduced by the representation of the solution as a chromosome and searching operations such as crossover and mutation. The second is control of the convergence brought about by the selection operation. In the conventional implementation of GA, these two points are mutually dependent, i.e., a suitable selection pressure varies largely depending on, e.g., the crossover operator. Hence, it requires much trial-and-error effort to find a nice configuration of GA. In the present paper, the authors apply a novel selection rule, the Thermodynamical Genetic Algorithm (TDGA) proposed by Mori et al. to the traveling salesman problem (TSP), and propose an adaptive annealing schedule of the temperature in TDGA. Computer simulation with several crossover operators for TSP shows that TDGA reduces the mutual dependency between the fitness landscape and the convergence process. Furthermore, TDGA is applied to a hybrid algorithm which combines GA with the 2-opt method, a local search technique. The effectiveness of the TDGA in the hybrid approach is also confirmed through a comparison with other methods for solving the TSP.