ABSTRACTS OF ARTICLES OF THE JOURNAL "INFORMATION TECHNOLOGIES".
No. 11. Vol. 24. 2018

DOI: 10.17587/it.24.691-697

V. M. Kureichik, Professor, CAD Department Senior Researcher, Vmkureychik@sfedu.ru, J. A. Logunova, Graduate Student, Julia1000@yandex.ru, Federal State-Owned Autonomy Educational Establishment of Higher Education Southern Federal University, Taganrog, Russia

The Genetic Algorithm Application Prospects Analysis for the Traveling Salesman Problem Solution

This work belongs to the artificial intelligence field. The Traveling salesman problem (TSP) is considered in this article, which is actively used in transport tasks, intellectual design, in search optimization solving problems. The development of new solving methods for TSP is still an urgent task. It is NP-hard problem. Usually, the algorithm time complexity finding the exact solution is a factorial or exponential dependence on the input data. It is possible to allocate a separate class of optimization methods among a lot of search procedures for TSP solving, which imitates real nature processes: genetic and bio-inspired algorithms. These algorithms are used for large dimensions tasks. In this case the optimal solution cannot be obtained over the acceptable time. In this situation you need sacrifice the accuracy of the solution and find a good solution in a relatively short time. The solution quality depends greatly on choice of algorithm parameter values. The genetic algorithm can lead to the population degradation in the wrong choice of operator, and, as a result, the obtained solution is far from optimal. In this regard, we propose to use some special indicators for investigating the prospects of using the genetic algorithm. This indicators show the population diversity degree. Also they can be used to algorithm parameters adjust. Specially developed software allowed testing the GA on the well-known benchmark for TSP with 48 cities (att-48) and showåd the usefulness of the developed indicators in practice.
Keywords: traveling salesman problem, genetic algorithm, crossover, population, chromosome, artificial intelligence, Dammerau-Lowenstein distance

P. 691 - 697

To the contents