【作者】 袁华；

【导师】 李文辉；

【作者基本信息】 吉林大学 ， 计算机应用技术， 2009， 博士

【摘要】 本文对几何约束求解中几何约束图的分解策略、几何约束求解精度、多解、初值敏感及求解稳定性等核心关键技术进行研究:1、提出一种基于图分解的几何约束求解策略:首先确定传播的起点S（e_i）,不断寻找约束图中定位其它几何体的几何元素,将他们析出放入Si（e_i）集;将由该几何体出发的所有出弧视为已知并移除,同时不断将完全被定位的几何元素析出逆序放入T（e_i）。重复上述过程,直至有向约束依赖图的所有几何体全部析出,得到S₁（e_i）, S₂（e_i）,…,S_n（e_i） ,T（e_n,…,e₂,e₁）约束分解路径。分解后的路径中含有约束的传播起点,从该起点出发,依次求解后面的实体。由于已经分析出整个约束图中所有几何元素之间的连接关系,使得求解过程由总体下降到局部,避免了对数学方程的大规模数值求解,提高求解的效率和可靠性。这样,设计中对草图进行局部修改时,只需要对与约束变动相关的结点重新排序,有效提高了草图修改的效率。2、提出禁忌粒子群算法求解几何约束,提高求解精度:新算法根据搜索过程中解的质量动态地变化求解策略,将禁忌搜索独有的记忆能力引入到粒子群算法的搜索过程中。一方面利用禁忌算子的集中性搜索策略,加强对当前搜索到的优良解邻域作进一步的搜索。另一方面利用禁忌搜索的发散性搜索策略,构建跃变算子增加多样性搜索,跳出局部极值的陷阱,较好地解决了集中性搜索与多样性搜索之间的矛盾,有效提高优化算法求解几何约束的求解精度。3、提出免疫蚂蚁算法,解决几何约束问题中良约束下多解问题:针对蚂蚁算法初期信息素匮乏,求解速度慢的缺点,引入免疫机制,动态生成蚂蚁抗体群。用赌轮盘选择机制选择蚂蚁抗体群进行约束求解,其选择概率正比于聚合适应度;在群体更新时,随机增加N个蚂蚁抗体,从2N个抗体中选取聚合适应度较高的N个抗体组成下一代群体。这样既可保留具有优秀适应度的抗体,又可抑制浓度过高的抗体,形成一种新的多样性保持策略。算法具有优良的多解搜索能力,很好的解决了几何约束求解问题中良约束条件下的多解问题。4、提出平行搜索算法,解决非线性方程组求解时初值敏感及求解稳定性问题:单纯形法是确定性下降方法,混沌算法是随机、遍历性搜索算法。将两种选择机制上存在如此差异的算法进行混合,丰富搜索行为。新算法1)采用混沌序列初始化变量,利用混沌提高种群的多样性和搜索的遍历性,解决算法对初值敏感的问题;2)通过单纯形中反射、收缩、延伸等策略不断缩小搜索空间,有效地调整搜索移向,加快收敛速度;3)以整个单纯形搜索到的最优位置为基础产生混沌序列,把产生的混沌序列中的最优位置替代当前单纯形中的个体的位置,产生局部最优解的许多邻域点,帮助惰性个体逃离局部极小点,提高求解稳定性。更多还原

【Abstract】 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.更多还原