Solution of the traveling salesman problem using a two-stage genetic algorithm
Abstract
Solution of the traveling salesman problem using a two-stage genetic algorithm
Incoming article date: 21.09.2018The article considers the application of a modified two-stage genetic algorithm to solve the traveling salesman problem. The traveling salesman problem is a classical combinatorial optimization problem known since 1930. The traveling salesman problem is NP-complex. With the number of cities 66 or more, it is impossible to solve it by exhaustive search. To test the proposed approach to the solution, we consider a graph with 51 vertices from the package TSP_LIB. At the first stage, a modified Goldberg model with small parameter values works to obtain the first generation of the second stage with better performance than the random formation of individuals. The second stage works with increased values of genetic algorithm parameters. These values vary from experiment to experiment, the results of which are presented in diagrams. Also, the results of the two-stage algorithm are compared with the results of the one-stage algorithm. A modified Goldberg model of the genetic algorithm is used. The genetic algorithm uses a waypoint representation of a traveling salesman's route with a two-point ordered crossover and a "greedy" mutation. The experimental results showed the effectiveness of the proposed approach. The modified two-stage algorithm allows to obtain a solution close to the optimal one.
Keywords: traveling salesman problem, genetic algorithm, Goldberg model, crossover, mutation, individual, route, Hamiltonian cycle, distance matrix