1 Introduction
The problem of placing non-overlapping objects (such as circles and spheres) into a regular convex container (such as squares and regular hexahedrons in a two-dimensional or higher-dimensional Euclidean space) to maximize the packaging density is a large number of problems that have been widely studied. For two-dimensional Euclidean space, the corresponding type of problem is called circle packing problems. One of the most representative problems is the problem of putting circles of the same size into a square [packing equal circles in a square (PECS)]. Correspondingly, for three-dimensional Euclidean space, the corresponding type of problem is called sphere packing problem, among which the most studied one is putting spheres of the same size into a regular hexahedron [packing equal spheres in a cube (PESC)].
2Problem description
PECS: Given unit circles, we need to convert themwithout overlappingPut it into a square container while minimizing the side length of the container.
Its mathematical model is as follows:
Among them, the center of the square is the origin of the two-dimensional Cartesian coordinate system; and represent the unit circle and the center coordinates of the unit circle respectively. Constraints (2) are called non-overlapping constraints, which ensure that there is no overlap between the two unit circles (the distance between the circle centers is not less than 2); constraints (3) (4) are called containment constraints, which ensure that each unit circle is completely contained in the square container (the distance between the circle center and the boundary is not less than 1).
Extend this model to the PESC problem in three-dimensional Euclidean space:
Among them, the center of the regular hexahedron is the origin of the three-dimensional Cartesian coordinate system; and represent the coordinates of the center of the unit sphere and the unit sphere respectively. Constraint (6) ensures that there is no overlap between the two unit spheres, and constraints (7)~(9) ensure that each unit sphere is completely accommodated in the regular hexahedral container.
3. Central idea of sub-problem modeling of PECS and PESC
Since the objective functions of PECS and PESC are monotonic with respect to the side length, we can continuously modify the size and use the penalty function to transform the original constrained optimization problem into an unconstrained optimization sub-problem with gradually smaller side lengths as parameters, and then solve these sub-problems through unconstrained optimization methods.
PECS with fixed side length (PECS-L)
The goal of the unconstrained subproblem mentioned earlier (denoted by PECS-L) is to try to find a way to place unit circles in a square container with fixed side lengths without overlapping. We use the sum of squares of the depth of the overlapping part as the objective function (penalty function).
Given a fixed side length of a square container and a candidate placement method, expressed as a coordinate vector of a circle, the objective function of PECS-L is defined as:
Among them:
Among them, represents the depth of overlap between the unit circle and , represents the depth of overlap between the unit circle and the vertical boundary, represents the depth of overlap between the unit circle and the horizontal boundary, as shown in the following figure:
The objective function describes the degree to which the placement violates the constraints of the original problem in a square container with side length . In other words, it is a feasible solution if and only then.
PESC with fixed side length (PESC-L)
PESC is a natural extension of PECS in three-dimensional Euclidean space. Correspondingly, its unconstrained subproblem PESC-L is defined as follows:
Given the fixed side length and placement of the regular hexahedron container, which represents the coordinates of the center of the unit sphere, the objective function is defined as:
where represents the depth of overlap between the unit sphere and , represents the depth of overlap between the unit sphere and the plane or , represents the depth of overlap between the unit sphere and the plane or , represents the depth of overlap between the unit sphere and the plane or . Likewise, it is a feasible solution if and only then.
4PBTS algorithm
The perturbation-based thresholding search algorithm (PBTS) is a stochastic optimization algorithm used to solve PTCS and PTSC.
Algorithm main framework
The pseudo code is as follows:
Among them, and represent the currently searched optimal feasible placement method and its corresponding side length, indicating the current solution.
We can see that the entire search process is divided into two stages: the first stage aims to quickly find a high-density placement method by gradually reducing the side length; the second stage uses a multistart approach to find the global optimal solution. In order to ensure the efficiency of the search, the algorithm uses a container adjustment method and a thresholding search procedure integrating a mixed perturbation strategy and local optimization.
In the first stage, we start from the empirically estimated packaging density (the ratio of the total area (volume) area of the circle (ball) to the total area (volume) area of the container, that is, for PECS,), calculate the initial container size, and randomly generate the initial placement method (generallyNot feasible). Then, we continuously reduce the value of the objective function through the threshold search method to find a value under the current side length.feasiblesolution. Then, we gradually increase the density while ensuring that it is feasible (correspondingly,shorten side length), continue to try to find a feasible solution through the threshold search method until a feasible solution cannot be found (the final solution is stillNot feasible). Finally, the previously obtained solution is adjusted through the container adjustment method.Local optimization adjustment, getFeasible solutionSaved in and.
In the second stage, at the beginning of each iteration, a placement method is first randomly generated, and then the threshold search method is used toTry to find a feasible solution. If a feasible solution is found, the container adjustment method is used on the premise of ensuring that it is feasible.Minimize side length. If the resulting side length is better than , then update the sum. In order to improve the robustness of the algorithm, if the current iteration fails to find a feasible solution or improve the optimal side length, a different perturbation method will be used in the next iteration (represented by Flag in the pseudo code). The iteration stops when the time limit is reached.
Below, we will introduce the threshold search method and container adjustment method in the main framework of the algorithm respectively; before that, we first introduce the local optimization method and two disturbance operators used in the threshold search method:
local optimization
Given a placement method, in order to achieve a local optimal solution with respect to the objective function and the container adjustment method, both the threshold search method and the container adjustment method use a popular and efficient quasi-Newton method - the limited variable scaling method (L-BFGS). L-BFGS uses a linear search method, which can achieve high accuracy in most calculation examples.
About what is L-BFGS:
https://cloud.tencent.com/developer/article/1573935
About what is norm:
https://blog.csdn.net/qq_24819773/article/details/85718335
perturbation operator
In order to ensure effectiveness and versatility, the threshold search method uses two complementary and universal perturbation methods to avoid falling into local optima: uniform random perturbation (URP) and sequential random perturbation (SRP). As mentioned before, the optimization process adaptively uses these two perturbation methods to improve robustness.
The pseudocode for uniform random perturbation is as follows:
Among them, is the candidate solution containing variables, is the disturbance intensity, and the default value is 0.8 (according to Grosso et al. (2010)). The URP operator makes (uniformly distributed) changes to each variable.
The pseudocode for uniform random perturbation is as follows:
The SRP operator aims to skip low-quality local optima through continuous small-scale perturbation and local optimization, so that the optimization process can overcome small obstacles in the objective function without changing the global optimal solution, as shown in the following figure:
Among them, the black solid line is the curve of the objective function, and the red dotted line is the expected effect after the SRP process. It can be seen that the SRP process smoothes the objective function by jumping out of the smaller convex part of the objective function. Through this effect, the SRP operator helps the algorithm find a smaller and more promising sample set to produce the global optimum (the minimum point of the smoothed function), and at the same time helps the objective function reach the global optimum without changing the global optimum solution in many cases.
It is worth noting that SRP has strong versatility and can be used for any function with a non-convex first-order derivative function, and has good results.
After introducing the local optimization method and two perturbation operators, let's get to know the threshold search method:
threshold search method
In order to search for the global optimal solutions of PECS-L and PESC-L, we need to use the threshold search method, which includes a local search process and the two perturbation operators mentioned in the previous section. The pseudo code is as follows:
It can be seen that the initial solution entering the function is first locally optimized and used as the current optimal solution found in the function; then it enters the loop to continue optimizing it. When iterations exceed a certain number (represented by , representing the search depth) without improvement or when a feasible solution is found (it should be noted that the problem to be solved has a fixed side length), the iteration stops.
In each iteration process, the current solution first undergoes a URP or SRP perturbation, determined by. As mentioned in the previous section, the perturbation intensity value of URP is always 0.8. In order to ensure the balance between intensity and degree of differentiation, we use the following periodic function to calculate the perturbation intensity of SRP:
Among them, is the current number of iterations; is the period, here set to 72; and represent the minimum and maximum values respectively (obtained from experiments). The cyclical changes are shown in the figure below:
Next, we perform local optimization on the perturbed solution, and then compare its objective function value with the objective function value before optimization, and record the difference as . If it is less than the threshold and (generally means no improvement or symmetrical invalid improvement), it is accepted as the new current solution. and respectively record the number of times to accept and reject the current solution update. If, that is, when the number of acceptances is too many, the threshold needs to be lowered to, otherwise, raised to. where represents the expected acceptance rate, coefficient.
It is worth noting that, similar to SRP, the threshold search method also has strong versatility and can be used in the global optimization of other non-convex differentiable functions.
Container Adjustment Method
The container adjustment method makes the solution feasible by making small adjustments to the side lengths and the center coordinates of the unit circle (sphere), and locally optimizes the side lengths.
What is used here is the penalty function method (SUMT), also known as the external point method and sequential unconstrained minimization technology. This method transforms the constrained optimization problem models of PECS and PESC in the previous article into a series of unconstrained problems, and then solves them sequentially until a local feasible minimum is reached. The unconstrained problem of transformation is expressed as follows:
Among them, is the penalty factor, each value of which corresponds to an unconstrained optimization function; the definition of is basically the same as (ignoring items for PECS):
Regarding the penalty function method:
https://zhuanlan.zhihu.com/p/376587367
The pseudocode is as follows:
Among them, the initial value of the penalty factor is , and is increased by 5 times each time in the sub-local optimization to enhance the intensity of the penalty, so that in the end a solution that is considered feasible is obtained.
The above is the entire content of PBTS, do you understand?
Machine-translated from the Chinese original 基于扰动的阈值搜索算法(PBTS)解决等圆与等球包装问题(PECS&PESC) (published 2023-09-11). WeChat original ↗