Parallelizing the ant colony algorithm for solving the knapsack problem as an example using Python
M.R. Vagizov, S.P. Khabarov
Upload the full text
Abstract. The paper considers the ant colony algorithm and describes the process of its parallelization using Python and multiprocessing module. Using the example of the knapsack problem, it is shown that distributing tasks among a number of processes allows to improve the performance of the algorithm while maintaining its efficiency. Compared to exact methods, like dynamic programming, the use of the ant colony algorithm showed a significant reduction in execution time with an acceptable level of deviation from the optimal solution. The advantage of parallelization algorithms is the efficient utilization of the computing system, where all available processor cores are used, resulting in faster execution of more iterations in the same time. The results obtained confirm the potential of AСO for solving complex problems with limited computation time.
Keywords: ant colony algorithm, forest resource optimization, knapsack problem, heuristic algorithms
For citation. Vagizov M.R., Khabarov S.P. Parallelizing the ant colony algorithm for solving the knapsack problem as an example using Python. News of the Kabardino-Balkarian Scientific Center of RAS.2024. Vol. 26. No. 5. Pp. 73–83. DOI: 10.35330/1991-6639-2024-26-5-73-83
References
- Darintsev O.V., Migranov A.B. Using the ant algorithm to search for a strategy for the behavior of a group of mobile robots on a work field with obstacles. Multiphase systems. 2022. Vol. 17. No. 3−4. Pp. 177−186. DOI: 10.21662/mfs2022.3.016. (In Russian)
- Minin A.A., Nemtinov V.A. Application of the ant colony algorithm for creating technological processes of cutting. Engineering technologies. 2023. No. 3. Pp. 31−36. EDN: LAMZQA. (In Russian)
- Pavlovskaya K.A., Chervinsky V.V. Routing in MANET networks based on ant algorithms taking into account energy saving. Bulletin of Donetsk National University. Series G: Technical Sciences. 2023. No. 1. Pp. 4−10. EDN: SWIUGB. (In Russian)
- Vagizov M.R., Khabarov S.P. Constructing program trajectories of motion based on solving the Dubins Machine problem. Information and Space. 2021. No. 3. Pp. 116–125.
EDN: DDDWFN. (In Russian) - Korenev A.S., Skrypka A.S., Khabarov S.P. Autonomous navigation on operating vessels. Marine Bulletin. 2022. № 1(81). Pp. 92–95. EDN: MIPIOP. (In Russian)
- Khabarov S.P., Shilkina M.L. Geometric approach to solving the problem for Dubins machines in the formation of program trajectories of motion. Bulletin of information technologies, mechanics and optics. 2021. Vol. 21. No. 5. Pp. 653–663. DOI: 10.17586/2226-1494-2021-21-5-653-663. (In Russian)
- Dumov M.I. Modeling of wireless networks in the OMNeT++ environment using the INET framework. Scientific and Technical Bulletin of Information Technologies, Mechanics and Optics. 2019. Vol. 19. No. 6. Pp. 1151–1161. DOI: 10.17586/2226-1494-2019-19-6-1151-1161. (In Russian)
Information about the authors
Marsel R. Vagizov, Candidate of Technical Sciences, Head of the Department of Information Systems and Technologies, Saint Petersburg State Forest Engineering University named after S.M. Kirov;
194021, Russia, Saint Petersburg, 5 Institutsky lane;
bars-tatarin@yandex.ru, ORCID: https://orcid.org/0000-0003-4848-1619, SPIN-code: 4811-8943
Sergey P. Khabarov, Candidate of Technical Sciences, Associate Professor of the Department of Information Systems and Technologies, St. Petersburg State Forest Engineering University named after S.M. Kirov;
194021, Russia, Saint Petersburg, 5 Institutsky lane;
Serg.Habarov@mail.ru, ORCID: https://orcid.org/0000-0003-1337-0150, SPIN-code: 4365-2033