Efficient Algorithms For The Equal Circle Packing Problem

As a classic NP-hard problem,the Packing problem has always been of high research value in industry and academia.According to the difference between the shape of the container and the loaded objects,the Packing problem can be subdivided into many classes.The text research is to put circular objects with a certain radius equal in the circular container without overlap as the equal circle Packing problem.Here,two effective algorithms are proposed for small-scale and large-scale equal-circle Packing.When the number of circles is less than 320,an efficient quasi-physical quasi-human(QPQH)algorithm is adopted.The circles to be placed are regarded as elastic small balls,and the elastic potential energy is generated when overlapping,so the classical Broyden–Fletcher–Goldfarb–Shanno(BFGS)algorithm is proposed for local optimization,but the local optimization strategy is designed to speed up the calculation;when the local optimum is reached,the efficient basin-hopping strategy is used to shrink container sizes to different extents,to achieve a better pattern;use the two methods iteratively until a global optimal solution is found.With this scheme,66 layout schemes superior to the current international optimal solution are found in the 320 examples of the number n of circles from 1 to 320.When the number of circles is larger,it is difficult to obtain an optimal solution using the gradient descent for the entire system.By combining the stochastic gradient descent method mentioned in machine learning with the traditional quasi-Newton method,a circular packing algorithm based on variable batch random optimization is designed.We start to randomly batch circles,and reduce the gradient of the current batch circle in each step.In subsequent iterations,the scale of the batch is gradually enlarged until the batch contains all the circles.Experiments show that the circular packing algorithm based on variable batch random optimization obtains a close-quality solution in a reasonable time on 8 large-scale examples of n=300,400...800,1100,1300,and the solution of n=300 is the same as the current world record.