Parallelizing the ant colony algorithm for solving the knapsack problem as an example using Python

M.R. Vagizov, S.P. Khabarov

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