Institutional Repository of Vilnius University
Skirtingų genetinio algoritmo kryžminimo operatorių palyginimas sprendžiant keliaujančio pirklio problemą /
Abstract
dc:descriptionSolving NP-hard problems with heuristic algorithms is one of the main tasks of computer science. The travelling salesman problem is one of the classic examples of NP-hard problem. This paper determines how the accuracy of an answer changes in travelling salesman problem depending on the implementation of an algorithm - different crossover operators and selection techniques are analyzed. The theoretical part of the work systematizes the most important information about genetic algorithms, the traveling salesman problem, and how traveling salesman problem can be solved using genetic algorithms. The research tool was constructed according to the instructions, additionally necessary crossover operators and selection techniques were implemented. A new crossover operator was proposed - alternating position continued crossover (APC). Experiments were performed on graphs with known optimal solution using different crossover operators and selection techniques. Based on the results of the experiment, a comparative study was performed on different variants of algorithm changing the size of population.
Degree
thesis:*- Grantor dc:publisher
- Institutional Repository of Vilnius University
- Year dc:date
- 2022
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Maksimiak, Lukas,
Rights
dc:rights- Statement dc:rights
-
- info:eu-repo/semantics/openAccess
- Language dc:language
- lit
Identifiers
dc:identifier.*- Repository record dc:identifier
- https://repository.vu.lt/VU:ELABAETD146236998&prefLang=en_US