Network-based models in Control

Dynamic adaptation of genetic algorithm for the large-scale routing problems

V. V. Zakharov, A. V. Mugayskikh

Saint-Petersburg State University, Saint-Petersburg

Abstract: This paper is devoted to implementation of the dynamic adaptation procedure for genetic algorithm used for the traveling salesman problem on large-scale networks. It is shown that solutions obtained by genetic algorithm can be improved during its dynamic adaptation and allow finding the more effective routes for the equal time. To evaluate effectiveness of new approach computational experiments were performed on well-known benchmark instances from TSPLib. As a result, the experimental level of time consistency of improved solution considerably increases compare to basic one. Dynamically adapted genetic algorithm has demonstrated possibility to produce solutions with higher level of time consistency. At the same time proposed procedure reduces length of the one solution in certain experiment as well as average length of all routes in it.

Keywords: временная состоятельность, генетический алгоритм, задачи маршрутизации.

UDC: 519.854.2 + 519.83
BBK: 22.18

Received: April 17, 2017
Published: May 31, 2018

DOI: 10.25728/ubs.2018.73.6

Bibliographic databases:

•