The Research On Key Technique Of Geometric Constraint Solving

The capacity of developing and applying CAD technology has became one of the major indexes measuring a nation's modernization of science, technology, and industry. Parameterization technology and the more advanced Variational technology provided more opportunities to future development of CAD technology.Parameterization design technique has become an effective way on preliminary design, modeling, modification, multi-scheme comparison, and dynamical design in design process due to its powerful sketch design and size-driven graph modification functions. It has drawn more and more attentions from people all over the world. Geometry Constraint Solving technique (GCS) is the core component of parameter design methods on the basis of constraint satisfaction. Many issues in engineering area can be categorized under GCS. Further research on the theory of Geometric Constraint Solving technology will significantly improve parametric level and industrial competition ability.Geometry constraint solving means that once the dimension constraints and topological constraints were provided, the system will generate the drafts automatically. Geometric constraints solving involves some key technologies such as modeling, decomposition, constraint maintenance and solving.This thesis makes a broad and in-depth research on the key technique-geometric constraint solving for Parametric and Variational design. While further studies are done with many existing methods, many new techniques are also proposed and numerical solution is provided to confirm its superiority.1. In this paper, a new method for decomposing geometric constraint graph is described. The basic idea of the graphic method is to build a Geometric Constraint Graph (GCG) for the GCS. In GCG, the vertex represents the geometric entity and the edge represents the constraint. The method also uses related theories and constraint information from real business to decompose and combine the geometric constraint graph. The purpose of decomposition is to slice the strongly coupled graph into sub-graphs, solve each individual sub-graph and then combine them as a whole.The Geometric Constraint Graph can be presented as non-directed graph and direced graph. The Directed Geometric Constraint graph (DGCG) takes plenty consideration of the constraint's spread directions which is easier to be presented in geometric terms.The basic idea of Geometric Constraint Solving is to "divide and rule", which a large problem can be decomposed into several smaller questions. We use constraint network graph to express constraint system. Decomposition paths are used to reduce the scale of constraint solving problem, decompose it from global scope into many local sub-problems , avoid a large-scale of numerical solution. The algorithm can separately calculate the sub-problems geometrically with great improvement in efficiency and robustness.2. Constraint solving can be transformed into optimization. However, since the speciality of nonlinear equation will easily lead the optimization process to focus more on local extremum, the optimization issues transformed from the nonlinear equations may not always be able to reach a global optimal solution.Comparing between the global and local optimization algorithm, the global optimization algorithm is better on wide-range searching but not on local searching and vise versa. To be benefitted from both algorithms, the paper is going to introduce a global-local optimization strategy called Tabu Particle Swarm Optimization.Particle Swarm Optimization (PSO) is a Parallel searching algorithm with multi-memory points. Most researchers have focused their efforts on how to promote the convergence rate and avoid the premature convergence. The better solution on relieving premature convergence of the algorithm is to ensure the diversity of swarm population or by introducing a new mechanism to break away the limitation of local optimums.My solution is to introduce tabu search strategy into PSO. Tabu Search is a new intelligence optimization algorithm. Its flexible memory structure and corresponding tabu criterion prevent recurrence searching. Iis strong mountain climbing function prevents prematurity.Tabu search strategy enhances the search of the neighborhood of excellent neighborhood in some certain phases. And then it builds up a jump-operator for diversity search which could increase the search area, change search direction, and break away from the trap of local optimums in latter phases. To improve the precision of the optimization algorithm of geometric constrain problem solving,the paper presents tabu search embedded in particle swarm algorithm.3. It is proposed to introduce immune mechanism into ant algorithm to solve multi-solutions of geometric constraint in the good-constrained solution. The over-constrained and Under-constrained problem can be solved naturally in our approach because transforming a constraint problem into an optimal problem doesn't require the number of constraint equations to equal the one of constraint variables. It can only get one solution to solve the geometric constraint problem by numeric iteration method. The Ant Colony Optimization (ACO) algorithm base on immune mechanism is present to solve geometric constraint multi-solutions problem.My solution for preventing ACO from premature convergence and improving the precision of local optimization algorithm is to develop ant operators with immunity based on the basic Principles of artificial immune systems. The immune ant operators will create better balance between exploration and exploitation by keeping the diversity of ant colony, maintaining the intensification in the later iteration phase, and improving the precision of local optimization algorithm.ACO is a rising optimization tool with positive feedback, distributing computing and heuristic searching functions. ACO can significantly reduce calculative burthen for multi-solution optimization processes. My proposal of introducing ACO algorithm to the sequence of equations solving in the paper is based on the multi-solution function of geometric constraint solving and path-seeking function from ACO.Using the characteristics of immune operator can simultaneously search a series of points in solution space, which generate the initial pheromone distribution related to questions. We fully utilize the capability of parallel, positive feedback, the high precision of ant algorithm. Mutli-solution can extract one time.Experiments results show that the new algorithm has the capability of effectively improve optimization speed and the quality of optimization, settles multi-solution question in good-constraint problem. 4. Parallel Search algorithm is proposed for solving nonlinear equations. The most common method for numerical solving is Newton iteration method. Generally, the method can reach the solution quickly. It needs a well-designed initial value and is quite sensitive to the initial value. When the initial value changed slightly, the method may emanate or converge the process and generate an unexpected solution. The random selection of the initial value in the initial design stage often makes the initial condition not good enough and gives Newton-Raphson method difficulties to converge. We've revealed two major defects after analysis on the traditional numerical method in the application of the nonlinear equation solution: (1) It is too relied on the initial point; (2) The convergence results lack of consistency. I believe the ergodicity of chaos algorithm introduced in this paper can help resolve the issues mentioned above.Chaos is a general nonlinear phenomenon laying in the nonlinear system. Chaos does not mean"disorder". Instead, it is a class of nonlinear phenomenon that has exquisite intrinsic structure. By using the ergodicity and randomness of the chaotic system, the optimal solution is picked up directly by transforming the chaotic variables into optimizing variables in Chaotic Algorithm. Its ergodicity is an effective mechanism to avoid being trapped into local minima during the searching process.Parallel Chaos optimization algorithm improves the efficiency of searching in a big range by constantly shrinking the areas of optimization variables. It focuses on the low precision and suddenly slow downed convergence speed near the optimization point. The results have been improved after integrated Simplex Search into parallel chaos optimization. Simulation results have also proved that this hybrid algorithm worked as expected.The basic principle of the new algorithm is to adopt chaos initialization to improve individual quality and utilize Chaos Perturbation to avoid the search being trapped into local optimum. The new algorithm will then calculate the reliable approximate solution by using reflection, contraction, and extension fuincgtions of simplex to constantly shrink the search and solution areas.Features of the hybrid algorithm are highlighted below:(1)Uses the properties of chaos initialization to seek the optimal areas and dirctions from the population of existing potential solutions. It also resolves the issue that the current algorithm is too relied on the initial value. (2)Uses Simplex to enhance the searching capacity. In the mean time, it also provides new models and increases the variety of the population.(3)Employs chaotic mapping to search subtly in the neighboring domain of the present optimal solution in the latter algorithm.Experimental results have proved that the new algorithm embedded with initialization technique based on chaotic has more superiority than the conventional stochastic approach.