Efficiency of optimization algorithms in the problem of graphic objects placement⋆ Bohdana Havrysh 1, ∗, †, Dmytro Palamarchuk1,∗,†, Oleksandr Tymchenko1, ∗,†, Bohdan Kovalskyi1,† and Orest Khamula1,†, 1 Lviv Polytechnic National University, Stepana Bandery Street, 12, Lviv, 79000, Ukraine Abstract 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. Keywords optimization, comparative analysis, vector graphic objects, genetic algorithm, simulation modeling, annealing simulation method 1 1. Introduction Placing vector objects on a plane is a common challenge in various industries, such as cutting shapes from paper, metal, wood, and other substrates [1, 21]. The optimal arrangement becomes essential when cutting many pieces, as it helps conserve material and handle non-standard plane shapes efficiently. Optimizing the placement of vector objects on a plane is a complex problem due to the vast number of possible configurations and the need to consider multiple parameters for each object. For example, the rotation of objects can significantly influence the overall efficiency of the placement. Furthermore, maintaining sufficient spacing between objects is vital to prevent material damage or other production defects. 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 AdvAIT-2024: 1st International Workshop on Advanced Applied Information Technologies, December 5, 2024, Khmelnytskyi, Ukraine - Zilina, Slovakia ∗ Corresponding author. † These authors contributed equally. dana.havrysh@gmail.com (B. Havrysh); dmytro.palamarchuck@gmail.com (D. Palamarchuk); alextymchenko53@gmail.com (O. Tymchenko); bkovalskyi@ukr.net (B. Kovalskyi); khamula@gmail.com (O. Khamula) 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) © 2024 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). CEUR ceur-ws.org Workshop ISSN 1613-0073 Proceedings 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. 2. Analysis of recent researches and publications 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 [2, 13-15]. In this method, the system is "heated" to explore various possibilities and then "cooled" to avoid getting trapped in local minima. This algorithm is effective for optimizing complex spaces with many local optima. It offers several key advantages, including simplicity of implementation and the ability to find optimal solutions for various problems. However, it may require significant time and parameter tuning. Due to its flexibility and ability to find optimal solutions in challenging environments, simulated annealing is widely applied to optimization tasks such as the traveling salesperson problem, scheduling, and task allocation. 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 [3, 18-20]. Compared to other methods, it enables consideration of many alternatives, improves the quality of management decisions, and forecasts their consequences. However, using simulation modeling in practical management is relatively common due to the complexity of the mathematical framework and the processing of large datasets. The method is based on replicating the functioning process of a system, including its interaction with the external environment, and its model can be represented as functionally implemented blocks, either in software or hardware. Simulation modeling allows include of a wide range of factors in decision-making. It is one of the most powerful tools for analyzing complex systems and processes, particularly under conditions of subjectivity and uncertainty, where reliable analytical tools are required. Genetic algorithm stands apart from traditional optimization methods and offers several key advantages [4, 15-17]. It operates on encoded values and searches within a population, enabling efficient solution space exploration. This method does not require objective function derivatives, employs probabilistic selection rules to avoid getting stuck in local optima, and features inherent parallelism to explore multiple search directions simultaneously. It excels in complex search domains, can manage numerous parameters concurrently, and requires no additional problem- specific information while delivering solutions quickly. However, a significant limitation is the inability to create a universal code for describing functions and optimization criteria due to varying initial conditions. Genetic algorithms are widely applied across scientific and technical fields, including neural network design, production management, economics, medicine, mathematics, etc [5, 6, 22]. 3. Objective of the work Analyze and compare the effectiveness of simulated annealing, simulation modeling, and the genetic algorithm for efficiently placing vector graphic objects on a plane. 4. Presentation of the main research material 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 [5, 7, 23] and written in Kotlin. The application's input data includes the board's size and the number of objects to be placed on it. To simplify the problem, only rectangular shapes were used, ranging in size from 1 to 40 cells in height and width, with randomly generated dimensions. The goal of the application is to place the shapes on the plane while occupying the least available space. The shapes are arranged row by row, starting from the top left corner of the plane. The application evaluates the quality of the solution based on the number of empty cells remaining from the bottom-right corner. 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. Figure 1: Software application. 4.1. Simulated annealing method The simulated annealing method has several variations that differ in the temperature change laws [6, 10-12]. Each variation has advantages and disadvantages, such as speed, the guarantee of finding the global minimum, and implementation complexity. A modification of the algorithm called "Very Fast Annealing" was selected for this task. To better understand how the algorithm works in the problem of optimal object placement on a plane, it can be represented as the following sequence of steps: 1. Two values are defined: the initial temperature T0 and the final temperature Tend. 2. A valid initial solution x0 is generated, its quality is measured, and the resulting evaluation is saved as r0. 3. The initial temperature is assigned to the current temperature, T = T0. 4. 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. 5. 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: 1 h( ∆E ,T ) = , (1) 1 + exp( ∆E / T ) ∆E = r0 – 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. 6. The new temperature is calculated as follows: =Ti (k ) T( i ,0 ) exp(c i k 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. The flowchart of the algorithm is shown in Figure 2. 4.2. Simulation modeling Simulation modeling is an approach to research in which the natural system is replaced by a model that accurately describes its functioning [8, 9, 24]. In the context of optimizing the placement of shapes on a plane, this algorithm can be broken down into the following steps: 1. Select a shape that still needs to be placed. 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 flowchart in Figure 3 illustrates the working principle of the algorithm. Figure 2: Flowchart of the simulated annealing method. Figure 3: Flowchart of the simulation modeling method. 4.3. Genetic algorithm 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