Research On Constraint Solving Based On Genetic Algorithms And Simulated Annealing

Parametric Design is a very important part of modern CAD technology, the foundation of parametric design technique is over-constraint solving of geometric drawing. Geometry constraint solving is the key of the quality of the parametric design system to weigh to whether the geometric constraint technology is good and mature or not.First of all, this paper reviews the history of the development of CAD technology, analyzes some typical parametric technology and constraint solving technology and then families the main methods to achieve existing parametric system and design.It points out that constraint solving is the key of parametric system.Then,this paper makes a broad and profound research on the constraint solving, explores the elements and the core of constraint solving, and discusses the feasibility and the disadvantage of constraints that have been used in CAD field after analyzing them comparetively.Because those methods have some problems in over-constraint, less-constraint and multiple solutions, we combine the global search capability of Genetic Algorithms with local optimality of the Simulated Annealing and put forward a mixed Genetic Algorithm Simulated Annealing(GASA) for geometric constraint solution. GASA is introduced into GCS(geometry constraint solving).The over-constrained and under-constrained problem can be solved naturally in our approach because that a constraint problem is transformed into an optimal problem doesn't entail that the number of constraint equations equal to the one of constraint variables.GASA is characteristic of many advantages,such as the calculating robustness,implied inherent parallelism,global searching and local convergence.These advantages are integrated in GCS in our method and make the constraint problems solved robustly and efficiently.Also many experimental data provided in this thesis.Compared with these constraint models,the constraint model in this paper is simpler and can make the calculation amount reduce greatly.Through simulation results show that the algorithm has good validity and feasibility.Finally,in the Visual Studio2005 development environment,C++ language is used in the research to verify the correctness and feasibility of the algorithm based on algorithm design and object-oriented thinking.Experiments show that the algorithm can solve problems in over-constraint,less-constraint and multiple solutions;it can change the prematurity of the traditional genetic algorithm and poor local optimality, make up the global search capability of the simulated annealing algorithm, and improve its efficiency greatly.