Research On New Algorithm Of Geometric Constraints Sloving Based On Graph Theory And Numerical Methods

The geometric constraint solving technology is one of the central technologies in the parametric design methods on the basis of constraint satisfaction. This thesis analyses the technique of the geometric constraint solving based on graph theory and numerical methods. As for the defects of the classical algorithm, two modified geometric constraint solving algorithms are put forward from the angle of the graph theory and numerical methods. They are the geometric constraint decomposition algorithm based on the cluster division and the geometric constraint solving algorithm based on the improved quantum genetic algorithm.First, for the disadvantage of Clipping-Reducing algorithm in processing of the geometric constraint problem with high coupling, we proposed a geometric constraint decomposition algorithm bsaed on the cluster division. Firstly, it uses the cluster to divided the constraint graph, and by using the associated nodes between the clusters we can get the skeleton of the constraint graph. Then, we apply the Clipping-Reducing algorithm on the skeleton. Once the node of the skeleton are placed, we can get general construction sequence of the constraint graph. It greatly reduces the coupling degree of the constraint graph which the Clipping-Reducing applied on, thus the Clipping-Reducing can obtain a better performance.Second, for the defects of the traditional numerical iterative algorithms, such as initial value sensitive problem, we build up the optimization model of the geometric constraint problem, and adopt the quantum genetic algorithm to solve the geometric constraint problem. In the traditional quantum genetic algorithm, the exchange of information between the individuals is not sufficient and it is easy to make the algorithm fall into local optimal, so we proposed the Dynamic Population Divide Quantum Genetic Algorithm (DPDQGA). And because the the traditional quantum genetic algorithm unable to make full use of the unmature individuals in the population, we put forward the Interact Update Mode Quantum Genetic Algorithm (IUMQGA). In the DPDQGA, the entire population is divided into two sub-populations, these two sub-populations search the solution space at the same time. And a dynamic population divided process is designed to increase the information exchange between the individuals of the population. It can avoid getting in the local best solution. The IUMQGA uses an interact update strategy to implement the crossover operate of the genetic algorithm with the use of quantum gate. That not noly increases the information exchange between the individuals but also makes full use of the information of the unmature individuals and improves the converge speed of the algorithm.At the last, we use the DPDQGA algorithm and IUMQGA algorithm to solve some instances and compare them with the classical quantum genetic algorithm. The experimental results show that the DPDQGA algorithm and IUMQGA algorithm can get better accuracy and efficiency.The results of this paper have certain theoretical significance and application value. It provides further expansion for the geometric constraint solving techniques.