|
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:
временная состоятельность, генетический алгоритм, задачи маршрутизации.
Received: April 17, 2017 Published: May 31, 2018
Citation:
V. V. Zakharov, A. V. Mugayskikh, “Dynamic adaptation of genetic algorithm for the large-scale routing problems”, UBS, 73 (2018), 108–133
Linking options:
https://www.mathnet.ru/eng/ubs956 https://www.mathnet.ru/eng/ubs/v73/p108
|
Statistics & downloads: |
Abstract page: | 299 | Full-text PDF : | 417 | References: | 29 |
|