Abstract: Geometric constraint problem is equivalent to the problem of solving a set of nonlinear equations substantially. The constraint problem can be transformed to an optimization n problem. We can solve the problem with GeesePSO optimization. In this paper, an improved algorithm is proposed using the characteristics of the flight of geese for reference. The improved algorithm has superiority over PSO; for one thing, it keeps the population various by ordering all the particles and making each particle fly following its anterior particle; for another thing, it strengthens cooperation and competition between particles by making each particle share more useful information of the other particles. The experiment shows that it can improve the geometric constraint solving efficiency and possess better convergence property than the compared algorithms.
INTRODUCTION
The parametric design is a geometric constraint-solving problem. Geometric constraint solving approaches are made of three approaches: algebraic-based solving approach based solving approach and graph-based solving approach (Bo, 1999). One constraint describes a relation that should be satisfied. Once a user defines a series of relations, the system will satisfy the constraints by selecting proper state after the parameters are modified. The idea is named model-based constraints. Constraint solver is a segment for the system to solve the constraints.
Particle Swarm Optimization (PSO) is a new Swarm intelligence computation (Holland, 1975) originating from researching the movement behavior of birds and fishes and proposed by Eberhart and Kennedy for solving the complex problem. PSO is also based on group iteration and similar with inherited algorithm. But there are no crossover and mutation operators. Its advantages are the simple ideas, easy to implement and there are not any parameters needed to adjust. Therefore, PSO as a hot spot of researching and application, not only emerges a large number of researching results but also has been widely used in function optimization, neural network training, industrial system optimization, indistinct system controlling and so on. As PSO has shortcomings that are easy to be distributed and fallen into local optimization, there are all kinds of improvements to enhance performance and also pay a corresponding price that in accordance with “no free lunch theory”.
In this paper, we introduce two improvements using the characteristics of the flight of geese for reference for the shortcoming above: On the one hand, the global extreme value is transformed to individual extreme value front of the optimum particle ordered by appropriate optimal value. So, all particles can’t fly to the same optimum direction, avoiding the harmonization, maintaining the diversity and expanding the searching area. On the other hand, every particle makes use of the useful information of more other particles, weighted average by individual extreme value, strengthens the cooperation and competition among particles.
IMPROVED PARTICLE SWARM OPTIMIZATION ALGORITHM
Standard PSO algorithm and improved algorithms are focused on how can explore the optimum solution in the solution space more effectively. But in the late search, particles trend to harmonization, this one limits the search scope. To expand the search scope, it should increase the number of particles or weaken to chase the global optimal point. To increase the number of particles will lead to increase the computational complexity of algorithms while weaken the number of particles to chase global optimal point will not be easy to convergence. Improvements in this paper as follow (Jin-Yang et al., 2006).
Learning from the characteristics of the flight of geese to improve PSO: When geese fighting, the first goose flapped wings and generated eddy. Then all of geese that trailing the first one can magnify the flight. So, the first one is the most difficult and usually is the strongest, others turn to the back order. Learning from the enlightenment of geese, we can view the strong degree of geese as pros and cons of the particles that is the bad or good of the history optimal value. Therefore, all particles ordered by history optimal value, select the best fitness value of particles as the first geese, others followed to the rear. After each of iteration, update the history best fitness value of every particle and reordered.
Geese accordance with the history best fitness value line up from front to rear, the back of each follow the front which is view the individual extreme value of the front as the global extreme value of the behind. p(i-1)d replaced pgd and the global extreme value of the first geese is also its individual extreme value. The improvement to the global extreme value of PSO is based on the characteristics of geese. The updated speed formula is:
| (1) |
p(i-1)d is the individual extreme value of the previous i-1 better geese that sorted according to the history of the best fitness value.
When geese are flying, they can promote and collaborate with each other by the “wake”. The reason why they can work efficient is the teamwork. As text, Beekman and Rantnieks (2000) said, the purpose of teamwork: First, each individual can help other members in the growing progress; Second, teamwork can improve efficiency. In other words, each individual can help others search and provide information to the group, as the cooperation and competition of multi-intelligent swarm. Wilson (1975) proved that at least in theory, each individual can benefit from the new discoveries of the group and the individual experiences of other individuals. Except the first geese, transform the individual extreme value of each goose to the average weight f (Xi) of its individual extreme value and current fitness value.
| (2) |
The advantages that the pid is improved for the pad as follows: Particles make use of more information to decide their own behavior which make the local optimal probability reduced. However, individuals got greater incentives strengthen cooperation and competition, accelerate the convergence speed.
Above the two improvements, the speed and position updated formula of new algorithm as follows:
| (3) |
| (4) |
The new algorithm learns from the characteristics of the flight of geese. On the one hand, global extreme value is transformed to the individual extreme value that in the front of the better particle that sorted according to the best fitness value. So, ll particles fly to more than one direction, to avoid these particles trending to harmonization and maintain the diversity of particles. On the other hand, the new algorithm makes use of more information of every other particles and individual extreme value will be replaced for the weighted average of individual extreme value of each particles and its fitness value. The individual incentives got larger and strengthen cooperation and competition of particles. In some degree, combinations of both balance the conflicts between the searching speed and accuracy. This algorithm is called an efficient improvement to particle swarm optimization, donated GeesePSO.
GeesePSO steps:
| Step 1: | Initialize the particle swarm: given population size M, the solution space dimension N, random location of each particle Xi, the speed Vi |
| Step 2: | Benchmark test function f (X) was calculated for each particle’s current fitness value |
| Step 3: | Update individual extreme value: evaluate the fitness value of each particle. That is the current fitness value of ith particle compare to its fitness Pi of individual extreme value. If the former is superior, then update Pi, otherwise remain Pi |
| Step 4: | PSO sorting: Sort all particles according to the history best fitness value (Pi’s fitness value), select the particle of history best fitness value as the first geese, others turn to the back |
| Step 5: | Calculate the new individual extreme value: The individual extreme value of the first geese unchanged, calculate new individual extreme value Pa of others with the formula (3) |
| Step 6: | Calculate the new global extreme value: The global extreme value of the first geese unchanged, each goose set the individual extreme value of the front geese as global extreme value |
| Step 7: | Update speed and position: update the speed Vi and position Xi of each particle with formula (3) and (4) |
| Step 8: | Check it whether or not meet the termination conditions (maximum iterations or minimum error threshold algebra), if satisfied, exit; otherwise, go to step (2) |
GEOMETRIC CONSTRAINT SOLVING
The constraint problem can be formalized as (E, C) (Sheng-Li et al., 2003), here E = (e1, e2, …,en), it can express geometric elements, such as point, line, circle, etc; C = (c1, c2, … , cm), ci is the constraint set in these geometric elements. Usually one constraint is represented by an algebraic equation, so the constraint can be expressed as follows:
| (5) |
Xi are some parameters, for example, planar point can be expressed as (x1, x2). Constraint solving is to get a solution x to satisfy formula (5).
| (6) |
Apparently, if Xj can satisfy F (Xj) = 0, then Xj can satisfy formula (5). So the constraint problem can be transformed to an optimization problem and we only need to solve min (F (Xj)<ε. ε is a threshold. In order to improve the speed of GeesePSO, we use the absolute value of fi instead of the square sum to express constraint equation set. From formula (6) and the solving min (F (Xj )<ε by Geese PSO.
Application instance and result analysis: With a parametric dimension-driven two-dimensional drawing, for example, a user using system dimensioning commands marked graph, then you can always modify a parameter value. Figure 1 has four segments and four rounds, four segments can be decomposed into four straight and eight segment endpoints and therefore, the geometric constraint system has 16 geometric elements, with a total of 36 degrees of freedom, constraint degree is 27.
| Table 1: | The comparison of GA, PSO and GeesePSO |
| Fig. 1: | A design instance |
| Fig. 2: | The draft after some parameters modifying |
Sketch of the geometric constraints constraint relations, includes seven sizes, four straight lines and circles tangent constraints, two concentric constraint, a common point constraint, a horizontal restraint, 8-point restraint in a straight line, four points in the round the constraints. The following are examples of geometric design elements.
We will change pc1 and pc3 distance from 120 to 96, l1 and l2 angle changed from π/3 to π/2, 2rc1 change from 60 into 50, 2rc2 changed from the original 32 into 26. 29 nonlinear equations by the iterative solution are corresponding geometric elements 16 to 36 positions variable.
The graph in Fig. 1 is draft in engineering design. The Fig. 2 is an auto-produced graph after some sizes of the Fig. 1 are modified by CMO. From the Fig. 1 and 2, we can realize from the above figures that once a user defines a series of relations, the system will satisfy the constraints by selecting proper state after the parameters are modified by GeesePSO.
As can be seen from Table 1, using GeesePSO geometric constraint solving algorithm, relative to the comparison algorithm can get better performance and better convergence. New algorithm not only has a high search speed and high convergence accuracy, balance to some extent, the algorithm searches the conflict between speed and accuracy.
CONCLUSIONS
Geometric constraint solving has been the core of design parameters. This geometric constraint problem will transform constraint equations into the optimization model, then the constraint solving problem can be transformed into the optimization problem. Representation as one of the methods of swarm intelligence, particle swarm optimization to a large number of non-linear, non-differentiable and multi-peak optimization problems to solve complex provides a new way of thinking and solutions but there are also easy to fall into local optimum, easy divergence and other shortcomings. In this paper learning from geese flying characteristics, we propose an improved PSO algorithm. The one hand, new algorithms will transform the global order after the extreme front of the better individual particles, so that all particles than toan optimal solution in the direction to avoid the particles tend to the same technology, maintaining the diversity of particle; the other hand, the new algorithm makes use of other particle particles more useful information, will replace all the individual particles of extreme individual extreme value with the current adapted weighted average, larger individual incentives, strengthened between the particles cooperation and competition.
ACKNOWLEDGMENTS
This work is supported by “the Fundamental Research Funds for the Central Universities” (Project number: N100404002). This work is supported by “Opening fund of State Key Laboratory of Geohazard Prevention and Geoenvironment Protection (Chengdu University of Technology) (Project number: SKLGP2011K004).