Institutional Repository of Vilnius University
Dirbtinės bičių kolonijos algoritmo keliaujančio pirklio uždaviniui spręsti lygiagretinimas /
Abstract
dc:descriptionThe Travelling Salesman Problem (TSP) is a well-known problem in graph theory that is usually formulated as follows: the task is to find the shortest route by which the travelling salesman would visit all the required cities once and return to his starting city. Many exact and approximate algorithms have been devised to solve this problem. One category of approximate algorithms is called population based-algorithms. One of the best known population algorithms is called Ant Colony Optimization (ACO). It simulates the working of a real ant colony in search of the shortest route to food around obstacles. Several parallelization strategies have been considered for this algorithm. Artificial Bee Colony (ABC) algorithm is a newer and much less studied population-based algorithm. It is decided to try to use one of the parallel versions of the ant colony optimization, called PACO, to parallelize two closely related versions of the ABC algorithm: Combinatorial Artificial Bee Colony (CABC) and quick Combinatorial Artificial Bee Colony (qCABC). In both versions each worker bee has its own route, which it repeatedly tries to improve using general subtour mutation (GSTM). The implemented algorithms are tested with several problem instances of different sizes from the TSP instance dataset “TSPLIB”. The results are compared with those of the PACO algorithm. Various combinations of the algorithms’ parameters are tested. Test results show that parallelization is beneficial for CABC and qCABC: good (but not optimal) tours are found after much less iterations with more cores.
Degree
thesis:*- Grantor dc:publisher
- Institutional Repository of Vilnius University
- Year dc:date
- 2023
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Pukšta, Andrius,
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:ELABAETD192847191&prefLang=en_US