Research On The Algorithm For Solving Two-dimensional Rectangle Packing Problem Based On Fitness

Our country's industry and manufacturing industry are currently at a critical stage of transformation.Benefit from the advantages of our country's entire industrial chain and the blowout progress of our country's science and technology in recent years,emerging technologies such as intelligent manufacturing have become hotter.The repeated raging of the covid-19 worldwide will have a continuous impact on the world economy in the next few years.This was unimaginable before.In order to improve their competitiveness in the economic cold,factories are reducing costs and improving their resource utilization The demand for rate will become more and more urgent.Therefore,it is still of considerable practical value to carry out research on the application of the nesting problem of the two-dimensional plane rectangle in daily life.The two-dimensional rectangular Packing problem is a classic NP-hard problem.Nowadays,there are more and more high-rise buildings in the city.Inspired by the skyscrapers at night,the concept of Skyline is introduced.The concept mainly uses the straight line at the top of the rectangular block to represent the width of the action space,while recording the X and Y coordinates of the left end of the skyline,the predecessor and subsequent X and Y coordinates,and we can calculate the left and right height of the current action space.At the same time,the concept of fitness is added to facilitate the selection and priority placement of more qualified rectangular blocks to generate a more"flat"action space.The fitness not only considers the placement of relatively suitable rectangles,but also considers the remaining space after the placement is completed.The status lays a good foundation for subsequent operations.This paper takes fitness as the core,uses fitness scoring strategy to select the rectangular blocks with the greatest fitness in the current situation for placement,and uses the heap and Segment Tree to quickly find the action space and target rectangular blocks.Based on this strategy,the basic algorithm is derived,The main idea of this algorithm is to select the best rectangular block that meets the placement conditions through the fitness strategy under the current pattern and complete the placement action until all the rectangular blocks are placed into the large rectangular container to obtain the termination pattern,and the highest termination pattern The point is the minimum height required for this calculation.Therefore,a good fitness scoring strategy can improve the accuracy and efficiency of the basic algorithm in the same calculation time.At the same time,in order to improve the randomness of the algorithm and obtain a better solution,we use the random swap rectangle strategy combined with the basic algorithm to design an enhanced algorithm.In the enhanced algorithm,the algorithm will perform N iterations,where N is the number of rectangular blocks.In each iteration,any two pairs of rectangular block IDs in the sequence of rectangular blocks that have been sorted are exchanged,and then operated according to the selection of the basic algorithm and placement strategy,and the calculation is completed to obtain the solution H~*,and the calculation process is saved The smallest H~*that appears in,until the calculation time limit or the end of the calculation,H~*is the optimal solution of the algorithm.Compared with the basic algorithm,within a specified time period,the order and answers of the rectangles placed using this algorithm are more diverse,and it is easier to get the optimal solution.Therefore,how to randomly exchange rectangles is an important part of the algorithm.Comparing the experimental results of calculation examples C,N,NT,CX,and 2SP with the experimental results of other excellent algorithms,it is verified that the algorithm is accurate and efficient.