Abstract: A Layout Pattern Based Particle Swarm Optimization algorithm (LPPSO) is presented herein for solving the two-dimensional packing problem with constraints. In the optimizing process of LPPSO, some individuals are constructed according to non-isomorphic layout pattern and these individuals are added into the current population of Particle Swarm Optimization (PSO) algorithm to replace the bad individuals, the new population is created as a result. Moreover, a non-isomorphic layout pattern is constructed based on exact boundary line approach to avoid premature convergence and improve the computational efficiency. This study also discussed the basic idea, key problem and the process of the proposed LPPSO algorithm. Two examples of constrained packing problems showed that LPPSO was feasible and effective in the experiments.
INTRODUCTION
Packing problem (Dowsland and Dowsland, 1992) is to reasonably place the equipments and devices called objects (or components) in the container to maximize the use of space while satisfying the following constraints: All the objects should be contained with no overlapping among the components. Packing problem belongs to combinatorial optimization problems and it is generally NP-Hard (Lodi et al., 2002). Constrained packing problems(Teng et al., 1994) are more difficult to solve than pure packing problems. To improve the ability of solving constrained packing problems by EA, the properties of the layout problem and the algorithm should be combined. One important property of layout problem is that its solution approach has a close relationship with layout pattern. Layout pattern has many different definitions. Feng et al. (1999) defined isomorphic and non-isomorphic layout pattern with graph theory and group theory. Li and Teng (2003) defined the layout pattern as the relationship of relative positions among objects and proposed a matrix expression approach to construct homeomorphic and non-homeomorphic layout pattern. Hongfei et al. (1995) discussed homeomorphic and non-homeomorphic layout pattern and gave the hypothesis about relationship between layout pattern and combination explosion. Hongfei et al. (2006) presented homeomorphic and non-homeomorphic layout pattern based on complete incidence graph.
The study uses the Particle Swarm Optimization (PSO) algorithm to solve the 2D layout problem with equilibrium constraints. PSO proposed by Eberhart and Kennedy (1995) is a representative algorithm of SIAs and has been applied in wide fields, such as neural network training, engineering optimization and data mining. PSO is simple, effective and robust. However, the biggest weakness of PSO is that it is easy to get stuck in local optima and suffer from premature convergence when solving multi-peak function optimization problems and its exploitation ability at later search stage is poor.
Previous studies have successfully applied the PSO algorithm for other several problems. Chen (2011) proposed a hybrid algorithm used the PSO algorithm with Taguchi method for the dynamic optimal power flow problem. In 2010, as for the web service selection problems, Fan and Fang (2010) put forward an improvement PSO algorithm (called Niche Particle Swarm Optimization) with feasible and efficient performance in the solving process of web service selection problems. Fang et al. (2011) presented the Discrete Particle Swarm Optimization (DPSO) as a process mining method. With the characteristic of complexity and intractability, the discrete optimization problems were better solved by the simple quantum-inspired PSO algorithm in reference by Gao et al. (2011). Gao et al. (2009) enhanced the local search ability of the PSO algorithm based on the improved chaos searching strategy. Other researchers, such as Jing-Lei and Zhi-Jian (2011), Heng et al. (2006), Liu et al. (2007), Tu et al. (2011), Lu and Chen (2011), Ren and Zhong (2011), employed the PSO algorithms for different angles and issues with some modified strategies or methods.
As for solving the layout optimization problem with constraints, how to use the PSO has also been studied. Li and Dong (2012) proposed a layout pattern-based GA for rectangle and circle packing problem with equilibrium constraints. The proposed approach uses the case retrieval to construct non-isomorphic layout pattern. Therefore, the corresponding case database of the problem is required. This study focuses on the packing problem from the view of the layout pattern. Solving approaches for packing problems are often classified into two categories: Heuristic approaches and stochastic approaches. Heuristic approaches are used to put objects in the container in sequence according to the given rules, without calculating the interference among objects or objects and container, such as BL Method; the other category is putting all the objects in the container (supposed that it is containable) in the random initialization phase, then optimization algorithm is used for optimizing and it requires the interference calculation. Evolutionary Algorithms (EAs) or Swarm Intelligent Algorithms (SIAs) are often used (Gao et al., 2009).
ISOMORPHIC LAYOUT PATTERN AND NON-ISOMORPHIC LAYOUT PATTERN
This section firstly describes isomorphic layout pattern and non-isomorphic layout pattern. For a given layout scheme, Layout Pattern (LP) is defined as a relative position relationship among objects (Hongfei et al., 2006). According to the definition, it can be seen that LP is not related to the interferences among the objects.
It is assumed that there are two layout pattern S1, S2. If the relative position relationship of layout objects’ centroid in S1 is the same with that of S2 (namely LP (S1) = LP (S2)), the layout pattern of the S1 and S2 is defined as the isomorphic, which is denoted by ILP (S1, S2).
| Fig. 1: | Exact boundary line approach illustration, Ai: Circle layout objects, lir: The distance between Ai and Ar |
Conversely, if LP (S1) ≠ LP (S2), the S1 and S2 are non-isomorphic, which is denoted by NLP (S1, S2). According to the literature (Hongfei et al., 1995), non-isomorphic layout pattern can be constructed by two approaches, i.e., the minimum polygon approach and the exact boundary line approach. In this study, the exact boundary line approach is adopted to construct ILP. The specific construct process shown in Fig. 1 can be described as follows: Firstly, two points Ai and Aj are selected randomly, then an exact boundary line Aj A2 is made in the control area of layout pattern about Ai. Ai is randomly moved to the other side of the exact boundary line Aj A2, the new random point denoted by Ar. The distance between Ai and Ar is denoted by lir. It should be assured that the value of lir is less than the maximum value Vmax of the particle velocity in PSO. A random point Ak is selected in the Ar region. Under the same constraints, Ak is moved to the other side of the exact boundary line Aj A2. If the distance between Ak and Aj is too close or too far, it can be adjusted appropriately. Similarly, Ai can be moved to the other side of the exact boundary line Aj A3.
PARTICLE SWARM OPTIMIZATION ALGORITHM BASED ON LAYOUT PATTERN
When particle swarm optimization algorithm is used to solve the constrained packing problems, PSO algorithm is easy to get into a local optimum and get stagnant in the later stage (premature). To overcome above shortcomings of PSO, this study constructs non-isomorphic layout schemes according to the current best individual obtained in the process; then the non-isomorphic schemes as individuals are added into the population to not only increase the population diversity, but also guide the exploration search in new regions with potential solutions. In this way, the PSO algorithm can jump out of the local optima and improve the computational efficiency. The above new approach is named as the Layout Pattern Based Particle Swarm Optimization algorithms (LPPSO). The basic idea of LPPSO is to construct non-isomorphic layout pattern solution using the exact boundary line approach on the basis of better individuals in an initial random layout process. Therefore, the PSO individuals would cover the solution space as large as possible, that is to say the algorithm would be started with good initial points. In the process of evolution with a certain interval (each generation or several generations), the non-isomorphic layout pattern is automatically constructed according to the best individual to replace the worse individual and help the algorithm escape from local optima easily.
KEY STRATEGY OF LPPSO
| • | During initialization, the initial population is randomly generated (k = 0), scale as M, m (0<m<<M) solutions were selected randomly from M, when M≤00 and generally m = Mx10%. Calculating fitness of m random solutions and selecting the mL solutions P mL, by using quasi-boundary line to selected better solutions from mL solutions and then creating mL non-isomorphic layout mode solutions (individuals) to replace randomly M-m individuals so that the population size remains as M |
| • | In the evolution of the iterative process, similarly, constructs the contemporary best individual non-isomorphic layout pattern solution to replace the generation of individual whose fitness is poorer, creating a new generation of population is better able to increase the diversity of groups and jump out of local optima and improve the layout of the problem solving efficiency and accuracy |
LPPSO STEPS OF THE ALGORITHM
This algorithm adopts the iterative formula of the GWPSO (Shi and Eberhart, 1998) and the pseudo codes are described in Fig. 2.
| Fig. 2: | Pseudo codes of LPPSO |
RESULTS AND DISCUSSION
Experiment 1: The example 1 was originated from satellite module layout
optimization design and simplified as a kind of constrained packing problem
with all the optimal solutions known. There were 4 big circles and 5 small ones
that will be arranged in the circular container. Here the problem was to seek
the optimal location of the circles such that the container has the smallest
radius, while satisfying the following constraints: (1) There was no overlapping
between any two circles, (2) Each circle should be include to D (3) The static
non-equilibrium of the packing scheme should not exceed a permissible value,
the smaller and the better. The data of all circles were described as follows:
The radius of 4 big circles was all
As for the packing problems, previous studies have put forward these approach which were employed with well performances, such as the GA (Mahfound, 1995), aiNet (De Castro and von Zuban, 2000), Clonalg (De Castro and von Zuban, 2001), DE (Storn and Price, 1997), TS (Glover, 1989), SA (Kirkpatrick et al., 1983), wPSO (Clerc, 1999), xPSO (Shi and Eberhart, 2001) and GWPSO (Shi and Eberhart, 1998).
This example run on PC with 1000M RAM and CPU was Intel Core Duo T2250 1.73 GHz. This example was solved by GA (Mahfound, 1995), GWPSO (Shi and Eberhart, 1998) and LPPSO that offered in this article. Then those results were compared. Population size of those three algorithms was all 50, Learning factors of GWPSO was 2.05 and initial inertia weight was 0.9. During initialization, LPPSO algorithm of this article selected 5 individuals from 50 individuals generating randomly to evaluate fitness and got three individuals of good fitness. Then solutions of non-isomorphic layout design were structured. At the last three individuals were replaced randomly from other 45 individuals so that initial population is still 50. During the optimization process, LPPSO selected an individual with better fitness from this generation after each 10 iterations. This algorithm constructed the solutions of non-isomorphic layout design by using Quasi-boundary straight-line method. Those solutions were used to replace the worse individuals from this generation. New population was generated. This algorithm was completed by repetitions iteration like this.
For those three algorithms, 50 calculations carried through, respectively. The maximal Evaluation times of fitness (Kmax) is 500000. In Table 1, the average 4 optimization results were shown in which the R was the radius of the envelope circle, T was the static equilibrium amount and ΔS was the intervening parameter. Table 2 showed the best calculated results of the three algorithms in which the xiyi is the packing circles’ coordinates. Judgment conditions of whether calculation was successful are evaluation times of fitness were less than Kmax, intervening parameter (ΔS) was less than 0.01 and static equilibrium amount (T) was less than 0.001. Figure 3 showed the best layout scheme of those three algorithms.
| Fig. 3(a-d): | Layout scheme of nine components in Experiment 1 of (a) Theoretical layout, (b) GA layout, (c) GWPSO layout and (d) LPPOSO layout the number “1, 2,…, 9” stands for the serial number of the layout components |
| Table 1: | Optimized result of experiment 1 |
| t: Calculating time, the success rate is percentage of the calculating successful solution and of all solutions, R: The calculating radius, T: The static equilibrium amount | |
| Table 2: | Optimized center coordinates of circle objects |
| xi: Center’s X coordinates of circle objects, yi: The center’s Y coordinates of circle objects | |
| Table 3: | Object's radius and optimized mass-center coordinates |
| The number 1, 2,…, 9 are the serial number of the layout components, xi: The center’s X coordinates of circle objects, yi: The center’s Y coordinates of circle objects | |
From Fig. 3, all the components had been placed in the big circle as the container, while the interferences in different algorithms should be calculated to determine which performed better.
From the data in Table 1, it was known that compared with GA algorithm and GWPSO algorithm, the operating results of LPPSO algorithm, respectively reduced the radius of envelope circle to 7.16-3.67% and the results of static balance of LPPSO amounted for zero (less than 0.0001 is considered as 0) the results of the interference of GWPSO were bigger and LPPSO was zero; Compared the success rate, LPPSO were increased higher than GA and GWPSO, respectively by 8-12%. In calculating the time-consuming, GA consumed the longest time, while the time of LPPSO consumed was a little smaller than GWPSO, which may be due to the LPPSO employed the isomorphism layout mode which can be faster than PSO evolution.
Experiment 2: The example was originated from integrated circuit layout design and was simplified as a weighted packing problem (Li et al., 2003). This kind packing problem was additionally constrained by circles relationship that each circles in a rectangle should satisfy a certain adjacent relation. The problem can be stated as follows: 15 circles were placed into a two-dimension rectangular space and the adjacent relation weights among them should satisfy a weight matrix Wij (Stand for intimate degree of objects in the position of layout space), the objects were request to meet the following requirements: (1) Objects not to interfere (2) The objects possessed larger weights Wij two objects i, j should be mutually together, which minimized the numerical value of weighted distance C, as in Eq. 1. The rectangular area S of the object was the minimum. The mathematical model was Eq. 2.
The weighted distance C calculating formula was as follows:
| (1) |
Where, dij is the distance between two objects.
For:
X = (xi,yi)T i =
1, 2,…, n |
and satisfy:
| (2) |
where, S standard for the area of the envelope of rectangular, λ was C’s weights that relative to S , Ai and Aj, respectively standed for the area of objects i and j, the radius of objects showed in Table 3. In Table 3, the number “1,2,…,9” stood for the serial number of the layout objects, the mass of each object was presented and xi stood for the center’s X coordinates of circle objects while yi was the center’s Y coordinates of circle objects which were optimized respectively by Genetic Algorithm (GA), global vision of PSO with inertia weight (GWPSO) and LPPSO (this study presented). Besides, the weight matrix can be seen in literature (Che et al., 2010).
The weighting factor can be set λ = 0.8, the containers was rectangular, the layout container size was unlimited and the objects were 15 circles. This was a two-dimension layout problem.
The three algorithms such as Genetic Algorithm (GA), global vision of PSO with inertia weight (GWPSO) and LPPSO (this study presented), were, respectively applied that the article mentioned to solve this example and compare with each other. The initial parameters set of three algorithm was the same as experiment 1. Three algorithms were calculated 20 times and the maximum number of fitness value evaluation Kmax= 500 000.
| Table 4: | Optimized performance indexes of experiment 2 |
| C: Numerical value of weighted distance, S: Rectangular area of the object, Δ: Amount of interference | |
| Table 5: | Optimized average performance indexes of experiment 2 |
| Fig. 4(a-c): | Layout scheme of experiment 2, (a) GA layout, (b) GWPSO layout, (c) LPPSO layout |
| Fig. 5: | Convergence graph of experiment 2 |
The obtained best set of the layout result and data were shown in Table 4. The judgment condition of successful calculation must meet the formula (2) and the interference was less than 0.35. Fig. 4 was the result for the above three algorithms to calculate the optimal layout.
Table 4 showed that LPPSO which in this article was better than GWPSO and GA in solving the layout problem. The envelope rectangular area which was derived from LPPSO optimal results decreased by 9.88-13.88%, respectively compared with GWPSO and GA and weighted distance C relative reduced by 12.66- 9.84%. From Table 5, the results of LPPSO in this article were that average envelope rectangular area minimum, slightly better than GA and GWPSO and GWPSO was the worst, which stood that the layout of the results of LPPSO in this article was a higher space utilization rate. Weighted distance of LPPSO was still slightly better than GA and GWPSO the worst. In the aspect of interference, the average amount interference of LPPSO and GWPSO are both 0, while the average amount interference of GA proceeds was 0.61. LPPSO was higher than GWPSO by 2.95-19.78% less than the GA in average computational time, there had little difference among algorithms, as they belonged to the same order of magnitude. In summary, it can be seen that the LPPSO obtained the best performance in solving the type of layout problems, followed by GA and GWPSO performed worst.
Figure 5 is the calculation convergence map of GA, GWPSO and LPPSO. Early in the calculation, GA performances faster convergence, but after the 20,000 times of functional evaluations, LPPSO lead in GA which may be due to the crossover and mutation-based search strategy of GA that is more conducive the potential solution of layout topology model early in the search, due to weak local search ability of GA late in the search, a lot of better potential solution did not ultimately optimize the feasible solution which satisfy the constraints. In the Fig. 5, LPPSO based on the speed of iterative formula of GWPSO and add non-isomorphic transformation. The Fig. 5 shows plus an unusual structure transform the convergence of the iterative steps (approximately after 1/5 of the number of iteration times Kmax), LPPSO convergence significantly faster than GWPSO. This shows that LPPSO good performance and convergence in solving the layout problem. The reason was that the LPPSO not only inherited the particle swarm algorithm has a better computational performance and robustness and LPPSO a combination of the layout pattern filling the unique knowledge of the layout problem and helped to improve the quality of the calculation and efficiency in the computation of the layout problem. When LPPSO random population initialization, it constructed a number of non-isomorphic layout mode solution to increase the diversity of the population; construct better solutions of non-isomorphic layout and algorithm optimization process solutions to substitute the poor solutions and this makes the algorithm easier to jump out of local optima.
CONCLUSION
In this study, a so-called Layout Pattern-based Particle Swarm Optimization algorithm (LPPSO) is proposed for 2D packing problems. By analyzing results of LPPSO in this study which solve the constrained 2D layout problems, the following conclusions can be obtained: (1) Constructing a reasonable initial layout mode will be useful to reduce combinatorial explosion of solution space and (2) Non-isomorphic layout pattern introduced into the iterative process will help the algorithm escape from local optima and explore search space near the optimum solution to accelerate the optimization process of the algorithm.
It should be noted that the layout pattern is constructed completely according to exact boundary line approach. Non-isomorphic layout individuals are added into the population, which is equal to add the potential good individuals that would guide the algorithm to move into a new region with better solution. How to construct non-isomorphic pattern in a simple and effective way is worthy of further study.
ACKNOWLEDGMENTS
This work was supported by National Natural Science Foundation of People’s Republic of China (Grants No. 51005034, 50975039) and the Fundamental Research Funds for the Central Universities (NCET-11-0055, DUT12LK33).