A genetic solution for the traveling salesman problem by means of a thermodynamical selection rule

A genetic solution for the traveling salesman problem by means of a thermodynamical selection rule

0.00 Avg rating0 Votes
Article ID: iaor19981971
Country: Japan
Volume: 33
Issue: 9
Start Page Number: 939
End Page Number: 946
Publication Date: Sep 1997
Journal: Transactions of the Society of Instrument and Control Engineers
Authors: , , , ,
Keywords: heuristics, programming: integer
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 dependence 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.

Reviews

Required fields are marked *. Your email address will not be published.