2023, issue 2, p. 32-45
Received 17.07.2023; Revised 24.07.2023; Accepted 25.07.2023
Published 28.07.2023; First Online 18.08.2023
https://doi.org/10.34229/2707-451X.23.2.4
On the Improvement of the Heuristic Algorithm for Packing Circles into a Circle of Minimum Radius
Bohdan Zadorozhnyi 1
*, Oleksandr Mitsa 1 
, Petro Stetsyuk 2
1 Uzhhorod National University, Ukraine
2 V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, Kyiv
* Correspondence: This email address is being protected from spambots. You need JavaScript enabled to view it.
The article is devoted to investigation of a heuristic algorithm for solving the competitive problem "Circles Dense packing into a circle of minimum radius" and development of its improved version using Shor's r-algorithm with step dichotomy. The heuristic algorithm was developed by Bohdan Zadorozhnyi, a third-year student of Uzhhorod National University. The program implemented on its basis took second place in the competition and used less time than the maximum time, which, according to the competition, was allocated for a one-time launch of the program for 50 competitive tasks. The article describes the research results of how the Shor r-algorithm can be used to improve efficiency of the heuristic algorithm.
The algorithm for improving the heuristic solution is implemented according to the following scheme. We start from the best arrangement of circles found by the heuristic algorithm. Then, we perform the following four stages of the algorithm: Stage 1. We set a rather large value of the initial step (we determine it depending on the input data or simply choose it as a large step); Stage 2. We run the r-algorithm from the starting point and find the local minimum of the corresponding nonlinear programming problem; Stage 3. If the local minimum found guarantees a smaller radius of the outer circle, then the local minimum point becomes the starting point; the local minimum found does not guarantee a smaller radius of the outer circle, then the size of the step h is reduced by half. Stage 4. If the step value is greater than the specified value, then we proceed to Stage 2. Otherwise, we finish work of the algorithm with solution improvement.
Python 3.9.5 programming language and NumPy 1.24.2 library were used for software implementation of both algorithms. For 50 competitive tests and different number of iterations of the heuristic algorithm (10, 20, 30, 40 and 50 iterations), the analysis of the obtained results was conducted according to three parameters: the number of points obtained, program execution time and the number of exchanges of circles in one iteration of the heuristic algorithm. For most of the competitive tests, the refined algorithm allows you to get better results in points, in particular, in most cases the improvement is up to 2 points, and in some cases – from 3 to 6 points. The biggest improvements (6 points) are seen in tests, where the circles have the same or close radii. Here, the heuristic algorithm works not so effectively, therefore, for such tests, due to the algorithm with refinement, it is possible to significantly improve the results of competitive tasks in terms of points.
Keywords: circle packing, heuristics, r-algorithm, Python 3.9.5, NumPy 1.24.2.
Cite as: Zadorozhnyi B., Mitsa O., Stetsyuk P. On the Improvement of the Heuristic Algorithm for Packing Circles into a Circle of Minimum Radius. Cybernetics and Computer Technologies. 2023. 2. P. 32–45. https://doi.org/10.34229/2707-451X.23.2.4
References
1. Shor N.Z. Minimization methods for nondifferentiable functions and their applications. Kiev: Naukova dumka, 1979. 200 p. (in Russian)
2. Shor N.Z. Non-Differentiable Optimization and Polуnomial Problems. Kluwer Academic Publishers, Boston, Dordrecht, London. 1998. 412 p.
3. Stetsyuk P.I. Theory and Software Implementations of Shor’s r-Algorithms. Cybern. Syst. Anal. 2017. 53. P. 692–703. https://doi.org/10.1007/s10559-017-9971-1
4. Stetsyuk P., Romanova T., Scheithauer G. On the global minimum in a balanced circular packing problem. Optimization Letters. 2016. No. 10. P. 1347–1360. https://doi.org/10.1007/s11590-015-0937-9
5. Stetsyuk P., Pylypovskyi A., Khomiak O. GNU Octave and Python Implementation of Shor's r-Algorithm with Adaptive Step Control. Cybernetics and Computer Technologies. 2022. 3. P. 98–112. (in Ukrainian) https://doi.org/10.34229/2707-451X.22.3.10
6. Python 3.9.5: https://www.python.org/downloads/release/python-395 (accessed: 09.08.2023)
7. NumPy 1.24.2 Release Notes. https://numpy.org/devdocs/release/1.24.2-notes.html (accessed: 09.08.2023)
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)