The article considers a comprehensive comparison of optimization algorithms for solving the problem of placing vector graphic objects on a plane. Algorithms are described in the form of block diagrams, which allows an understanding of their structure and operation principles. These diagrams provide a step-by-step visual representation of the processes involved, making it easier to follow the logical process and identify the critical components of each algorithm. Software was developed to evaluate the effectiveness of these methods. This program uses simplified input data in the form of rectangular objects that are placed on planes of different sizes. A set of rectangular objects and different plane dimensions makes it possible to perform various analyses in different scenarios, guaranteeing the reliability of the results. Research results are carefully presented in graphs and tables that clearly illustrate the effectiveness of each method. Furthermore, the article thoroughly discusses the results and conclusions obtained, indicating the high potential of optimization search methods in solving the problem of placing graphic objects. It highlights the practical implications of these findings, suggesting that these methods can significantly improve efficiency and resource utilization in various applications, such as manufacturing, printing, and layout design. The results of this study can guide future development and innovation in optimization methods, contributing to advances in fields that require accurate and efficient feature placement strategies.
Placing vector objects on a plane is a common challenge in various industries, such as cutting shapes
from paper, metal, wood, and other substrates [
This optimization challenge belongs to the category of NP-hard problems, making exact methods impractical for large datasets. Therefore, it is more suitable to use heuristic optimization methods that can provide acceptable solutions within a reasonable time frame. This paper explores three optimization methods: the genetic algorithm, simulated annealing, and simulation modeling. A software application was developed to evaluate the effectiveness of these algorithms by processing 0000-0003-3213-9747 (B. Havrysh), 0009-0000-3934-5899 (D. Palamarchuk); 0000-0001-6315-9375 (O. Tymchenko); 0000-0001-9088-1144 (B. Kovalskyi); 0000-0003-0926-9156 (O. Khamula) simplified input data, which consisted of rectangular objects placed on planes of various sizes. The findings of this research may contribute to the creation of more efficient algorithms for optimization tasks across various industrial and applied fields, enabling resource savings and improving productivity.
Due to its importance and complexity, the problem of finding optimal solutions is actively studied in various scientific and applied fields. A variety of methods developed to tackle this problem, with the most widely used being genetic algorithms, simulated annealing, and simulation modeling. Each of these methods offers unique approaches to finding optimal solutions.
Simulated Annealing - is an optimization algorithm miming the physical process of annealing
metals [
Simulation modeling is a powerful tool in applied systems analysis that allows the exploration of
complex systems and processes, mainly when decision-making is linked to uncertainty [
Genetic algorithm stands apart from traditional optimization methods and offers several key
advantages [
Analyze and compare the effectiveness of simulated annealing, simulation modeling, and the genetic algorithm for efficiently placing vector graphic objects on a plane.
A software application was developed to demonstrate the performance of the algorithms and
compare their efficiency in optimizing the placement of vector objects on a given plane. This
application was implemented using the Java Swing library [
In the software application (Figure 1), three planes are displayed simultaneously, each using identical input data but applying different algorithms: simulated annealing, simulation modeling, and the genetic algorithm. The quality of the resulting solution is displayed above each plane. Naturally, the higher the quality score, the better the result.
The simulated annealing method has several variations that differ in the temperature change laws
[
Two values are defined: the initial temperature T0 and the final temperature Tend. A valid initial solution x0 is generated, its quality is measured, and the resulting evaluation is saved as r0.
The initial temperature is assigned to the current temperature, T = T0.
A new iteration is initiated. In each iteration, two shapes selected by a random number generator are swapped. New shape indices are recalculated if the chosen shapes cannot be placed in the new positions. The swap is performed once the new indices are determined, resulting in a new solution x.
The new solution is evaluated using the function r=f(x). If r < r0, the solution has improved, and the new solution is stored as the current one x0=x, r0=r. Otherwise, if r > r0, the new solution is accepted as the current one only with the probability: h(∆E ,T ) = 1+ exp(∆E / T ) ∆E = r 0 – r. Thus, the probability of accepting a worse solution as the current one decreases as the temperature lowers and the difference between the current energy r and the optimal energy r0.
The new temperature is calculated as follows:
Ti (k ) =exp(c T (i ,0) ik 1/D ),c i > 0 , (2) where D – is the total number of iterations, k – is the current iteration number, с – is a variable typically used in the general pathfinding problem in a coordinate system to determine the specific temperature at each point. For the optimization problem, we simplify and keep it as a constant с=1. The temperature will decrease according to an exponential law. 7. If T>Tend, proceed to step 4 and continue the search, otherwise, terminate the algorithm.
Simulation modeling is an approach to research in which the natural system is replaced by a model
that accurately describes its functioning [
2. Identify all potential placement options on the plane for the selected shape that satisfy its strict constraints and compile them into the list. 3. Evaluate the quality of each position and place the shape in the most optimal option.
The genetic algorithm is based on natural selection, where better-adapted species are more likely to survive [21, 25]. The application of the genetic algorithm for optimizing the placement of shapes on a plane can be described through the following steps: 1. Input the required number of iterations N, which has been determined experimentally. Use the variable count=0 as a counter. 2. etrieve the list of shapes that have not yet been placed. Based on this, generate an initial valid solution x0. Evaluate this solution using the method f(x) and store the result as r0. 3. Randomly change the order of shapes in the list and generate a new valid solution x based on it, then evaluate the solution as r=f(x). 4. If r<r0, save the new solution as the current one x0=x, r0=r. 5. Increment the counter count++. If count equals N, terminate the search.
The sequence of steps for executing the algorithm is shown in the flowchart in Figure 4.
Three different types of input data were used across 20 experiments to compare and evaluate the performance of each algorithm: 1. a 200x200 grid with 80 shapes, 2. a 300x300 grid with 170 shapes, 3. a 400x400 grid with 300 shapes.
The grid size, number of shapes, and number of iterations were selected experimentally to ensure the algorithms could operate with different grid sizes. In contrast, the number of shapes would not exceed the grid’s capacity. Additionally, the solution search time was kept consistent across different methods. The experiment results are presented in Table 1, which provides the quality scores of the outcomes for each algorithm.
The genetic algorithm consistently delivers the best results across all grid sizes from the presented graphs. The simulated annealing method shows lower efficiency, as it is more difficult to apply to this problem. It requires finding two shapes that can be swapped, which is only sometimes feasible. The simulation modeling method sometimes produces results close to those of the genetic algorithms but lacks sufficient stability.
This paper analyzes applying optimization methods to place vector graphic objects on a plane. To solve this problem, the paper proposes using heuristic optimization methods: genetic algorithms, simulated annealing, and simulation modeling. A software application was developed to compare the effectiveness of these algorithms, using simplified input data in the form of rectangular objects placed on grids of various sizes.
The genetic algorithm showed consistently high simulation results, which are 10-20% better than the method of simulating annealing on all planes. To use the latter, it is necessary to find the shapes that need to be swapped, which is not always possible. It is not advisable to use the simulation modeling method because it shows unstable results that are sometimes close to the genetic algorithm, but can be worse than the annealing simulation method.
The results of this research could contribute to developing more efficient algorithms for optimization tasks in various industrial and applied fields, leading to resource savings and increased productivity. The findings highlight the strong potential of genetic algorithms for optimization tasks involving the placement of graphic objects while also indicating the need for further research to improve these methods and enhance their efficiency under different conditions.
The authors are appreciative of colleagues for their support and appropriate suggestions, which allowed to improve the materials of the article.
[17] A. Raj, A. Kumar, V. Sharma, S. Rani, A. K. Shanu and T. Singh, "Applications of Genetic Algorithm with Integrated Machine Learning," 2023 3rd International Conference on Innovative Practices in Technology and Management (ICIPTM), Uttar Pradesh, India, 2023, pp. 1-6, doi: 10.1109/ICIPTM57143.2023.10118328. [18] W. Jia and Z. He, "Outlier data Mining of large Data Sets relying on fast decomposition simulated annealing algorithm," 2020 International Conference on Robots & Intelligent System (ICRIS), Sanya, China, 2020, pp. 679-682, doi: 10.1109/ICRIS52159.2020.00170. [19] B. Aylaj and S. Nouh, "Degeneration vs Classical of simulated annealing algorithm: performance analysis," 2022 5th International Conference on Advanced Communication Technologies and Networking (CommNet), Marrakech, Morocco, 2022, pp. 1-5, doi: 10.1109/CommNet56067.2022.9993814. [20] I. Zasornova, T. Hovorushchenko, O.Voichur. Study of software testing tools according to the testing levels. Computer Systems and Information Technologies. 2023.No 1. P. 38-46. [21] J. Zhao and H. Wang, "Test Paper Generation Based on Improved Genetic Simulated Annealing Algorithm," 2022 12th International Conference on Information Technology in Medicine and Education (ITME), Xiamen, China, 2022, pp. 384-388, doi: 10.1109/ITME56794.2022.00089. [22] A. Phu-Ang, "Solving The Travelling Salesman Problem by Using Hybrid Simulated Annealing with Tabu Technique," 2022 3rd International Conference on Big Data Analytics and Practices (IBDAP), Bangkok, Thailand, 2022, pp. 61-64, doi: 10.1109/IBDAP55587.2022.9907400. [23] J. Cambeiro, J. Deantoni and V. Amaral, "Supporting the Engineering of Multi-Fidelity Simulation Units With Simulation Goals," 2021 ACM/IEEE International Conference on Model Driven Engineering Languages and Systems Companion (MODELS-C), Fukuoka, Japan, 2021, pp. 317-321, doi: 10.1109/MODELS-C53483.2021.00053. [24] B.Durnyak, I.Hileta, I.Pikh, A.Kudriashova, Y.Petiak Designing a Fuzzy Controller for Prediction of Tactile Product Quality. 1st International Workshop on Di¬gital Content & Smart Multimedia, DCSMart 2019, Lviv, Ukraine, December 23–25, 2019. Pp. 70–81. [25] I. Sitova and J. Pecerska, "Process Mining Techniques in Simulation Model Adequacy Assessment," 2019 60th International Scientific Conference on Information Technology and Management Science of Riga Technical University (ITMS), Riga, Latvia, 2019, pp. 1-4, doi: 10.1109/ITMS47855.2019.8940672.