UNIV. NEWS. NORTH-CAUCAS. REG. TECHNICAL SCIENCES SERIES. 2022; 1: 5-10
http://dx.doi.org/10.17213/1560-3644-2022-1-5-10
COMPARISON OF THE PATH AND ORDER REPRESENTATIONS IN SOLVING THE COMMIVIGER PROBLEM WITH THE TWO-STEP MODIFIED GOLDBERG MODEL
Kobak Valeriy G. – Doctor of Technical Sciences, Associate professor, Department «The Software of Computer Facilities and Auto-mated Systems», valera33305@mail.ru
Kushnareva Alina E. – Student, Department «The Software of Computer Facilities and Automated Systems».
Abstract
A comparison of the application of path and order representations in solving the traveling salesman problem by a two-stage modified Goldberg model is considered. The traveling salesman problem belongs to the class of NP - complete problems and is used in operations research, combinatorial optimization, as well as in theoretical computer science. There are the following approaches to finding the best solution: branch and bound method, exhaustive search method, dynamic programming. Since the traveling salesman problem cannot be solved with any number of cities, the above approaches require a long time and a large amount of computing power. Genetic algorithms operate not with solutions, but with some of their encodings, thereby modeling the natural mechanisms of reproduction and natural selection. These mechanisms are realized through various crossovers, mutations and selection. In this paper, the ordered crossover and exchange mutation are used for the path representation, and the classical crossover and mutation are used for the ordinal representation. To solve the traveling salesman problem, a software tool is implemented that allows you to choose a crossover option and obtain the corresponding results. Also, the work presents tables of the results of running a genetic algorithm with a different number of individuals and repetitions, a comparison of the path and ordinal representations when solving the traveling salesman problem with a one-stage and two-stage modified Goldberg model, and a conclusion is drawn on how different representations allow obtaining the optimal solution.
Keywords: traveling salesman problem, genetic algorithm, two-stage genetic algorithm, modified Goldberg model, path representation, ordinal representation, order crossover, exchange mutation, classical crossover, classical mutation
Full text: [in elibrary.ru]
References
- Levitin А.V. Algorithms. Introduction to development and analysis. Мoscow: «Williams»; 2006. 159-160. (In Russ.).
- Thomas H. Cormen, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. Algorithms: construction and analysis. Мoscow: «Williams»; 2006. 1296. (In Russ.).
- Mudrov В.В. Traveling Salesman Problem. Мoscow: Booking home «Librocom»; 2019. 62 р. (In Russ.).
- Copech D. Classic Computer Science Problems in Python. Moscow: Progress book; 2021. 128 р. (In Russ.).
- Panchenko Т.V. Genetic algorithms. Astrakhan: Astrakhan University; 2007. 15 p. (In Russ.).
- Kobak V.G., Zhukovsky A.G., Peshkevich A.A. An approach to decreasing the running time of a two-stage genetic algorithm for solving the Traveling Salesman problem. Izv. vuzov. Sev.-Kavk. region. Techn. nauki=Bulletin of Higher Educational Institutions. North Caucasus Region. Technical Sciences. 2020; (1):5-10. DOI: 10.17213/1560-3644-2020-1-5-10 (In Russ.).
- Anand E. Panneerselvam R. A Study of Crossover Operators for Genetic Algorithm and Proporsal of a New Crossover Operator to Solve Shop Scheduling Problem. American Journal of Industrial and Business Management. 2016; (6):774-789. Available at: scirp.org/journal/PaperInformation.aspx?PaperID=67660 (accessed 24.12.2021).
- Kashirina I.L. An Introduction to Evolutionary Modeling. Voronezh: Voronezh State University. 2007. 22 p. (In Russ.).
- Kobak V.G., Zhukovsky A.G., Peshkevich A.A. Comparison of the track and order approaches in solving the Traveling Salesman problem by the modified Goldberg model. Izv. vuzov. Sev.-Kavk. region. Techn. nauki=Bulletin of Higher Educational Institutions. North Caucasus Region. Technical Sciences. 2017; (1):3-7. doi: 10.17213/0321-2653-2017-1-3-7 (In Russ.).
- TSPLIB. The Zuse Institute Berlin (ZIB). Available at: elib.zib.de/pub/mptestdata/tsp/tsplib/tsplib.html (accessed 26.12.2021).