几何约束问题求解的方向可选指数进制步长优化算法

周友行，张建勋，董银松，韦衍

(湘潭大学 机械工程学院，湖南 湘潭，411105)

摘要：针对参数化设计中的复杂几何约束求解问题，提出1种可选指数进制变步长数值求解优化算法。在给定的优化目标下，采用指数进制变步长，对每个设计参数变量进行“前进、后退、保持一步”的方向选择式试探判断，即算法每迭代循环1次，误差以指数方式进行递减，变量则逐渐逼近先前设定的参数目标。利用该优化算法，求解相切圆填充和正二十面体优化2个经典的几何优化问题。研究结果表明：该算法稳定性强，收敛速度快，求解精度高并对初始值不敏感；该算法能够求解多变量复杂参数化设计问题，并不受优化变量个数的影响；利用方向可选指数变进制变步长优化算法能有效解决二维和三维空间内的参数化几何约束优化问题。

关键词：几何约束；变步长；参数化设计；优化目标；特殊进制

中图分类号：TP391           文献标志码：A         文章编号：1672-7207(2011)05-1326-06

A variable step-size revisable optimization algorithm to solve geometry constraint

ZHOU You-hang, ZHANG Jian-xun, DONG Yin-song, WEI Yan

(College of Mechanical Engineering, Xiangtan University, Xiangtan 411105, China)

Abstract: To solve the problems of complex geometry constraint in parametric design, a variable step-size revisable optimization algorithm was presented. For the optimization objective, with the exponential notation variable step and the test strategy of “forward, backward or maintain a step” to approach the optimization objective for each design parameter, the precision solution was gotten with iterative search. The filling problem for single circularity and iscsahedron problem were solved using this optimization approach. The results show that this algorithm is not sensitive to initial variable and has high convergence. And by solving the iscsahedron problem, this algorithm is not restricted by the number of parametric design variable and can solve the complex geometric constraint problem. The variable step-size revisable optimization algorithm can solve planar and three-dimensional geometry constraint effectively.

Key words: geometry constraints; variable step-size; parametric design; optimization objective; special scale

参数化设计是智能CAD技术在实际应用中提出来的，它不仅可使CAD系统具有交互式绘图功能，还具有自动绘图的功能^[1-2]。其中，几何约束问题求解作为参数化设计的核心组成部分，其性能直接影响整个参数化系统。目前，国内外学者对其进行了大量的研究，求解此类问题的主要方法有符号计算方法、基于图论的方法、基于规则的方法和数值方法^[3-10]。符号的几何约束求解方法一般能求解出全部满足约束的解，但求解速度比较慢，通常需要消耗大量的计算时间和空间；基于规则的方法由于受规则技术的限制，从而使该法实现效率低，而且无法处理元素之间的循环约束问题；基于图论的方法，其最大问题也是无法求解循环约束的问题。数值计算方法是将约束问题转化为求解非线性方程组的问题，特别在实际几何约束求解中，变量的边界条件明确，由于具有速度快而且能解其他一些不能解的、大的几何约束问题，通用性强，当其他方法失效时，最终都用数值方法来进行求解^[11-14]。因此，在几何约束系统求解中，牛顿迭代法及其改进形式等数值计算方法仍然被广泛应用。此类数值算法的有效性取决于搜索策略、初始变量和搜索步长变化规律三因素。例如在牛顿迭代法及其改进形式中，步长的变化一般是有规律的，这导致算法搜索空间有限，所以，初始变量的选择至关重要。从某种意义上说，数值算法就是基于搜索策略，寻找问题求解变量组合的一个过程。因此，若能通过搜索策略和步长变化规律的改变，扩大数值优化算法的搜索空间，就有可能解决此类数值算法中的初始值敏感问题。在此，本文作者提出一个基于牛顿迭代法原则的指数进制变步长方向可选数值优化算法，求解参数化设计的几何约束问题。该算法采用最小二乘法设定优化目标，指定步长变化呈指数形式，每次优化搜索时，对步长进行“接受、拒绝或反向接受”的3次试探判断，扩展数值优化算法的搜索空间，可大幅度降低算法中初始变量选择的敏感程度。

1  几何约束与非线性方程组

几何约束反映了几何体的形状和位置关系。几何约束问题一般都能转换成求解非线性方程组问题^[13]，如图1所示相切圆填充问题，通过给定三边以及建立坐标系，则能建立如下非线性方程组式：

            (1)

图1  相切圆填充

Fig.1  Filling problem for single circularity

可见：通过式(1)，可将图1中的几何约束问题转化为求解一个非线性方程组的问题。式(1)中的非线性方程组比较简单，求解难度不大，大多数数值算法都能求解。

随着产品设计的复杂化，由此产生的几何约束问题往往会产生大型的复杂非线性方程组。如参数化设计图2所示的正二十面体^[15]，其中给定三维空间12个点及它们的约束，其点与点之间棱长为2。

图2  正二十面体结构

Fig.2  Structure of icosahedron

若以P₁坐标原点，以P₁与P₂为坐标系Y轴，P₁与P₁₁连线为Z轴建立直角坐标系。根据30个约束条件，即30条棱的长均为2，则可以建立非线性方程组：

         (2)

对于式(2)中这样的复杂非线性方程组，采用常见数值优化方法，难以确定方程组的初始变量。

2  指数进制变步长方向可选优化算法

2.1  算法基本思想

引理1  当给定时，，通过k_i取值的选择，一定存在(其中：d和r为给定值；0＜r＜1，N为任意给定数值)。

证明  假设，则此时ε_q=|N-N_q|。当i增加1时，N_q+1有下列3种情况供选择：

       (3)

据式(3)，可得相应的误差：

   (4)

定义如下规则：

(1) 当＞时，选择。此时，。

(2) 当＜时，若＜，选择。此时，。

(3) 当＜时，若＞，选择。此时，。

通过选择k_q+1，可找到。以此类推，可得ε_q+n≤…≤ε_q+2≤ε_q+1≤ε_q，可知ε_q+n呈递减趋势。当时，可得，，从而引理得证。

备注：ε_q+n在严格数学意义上并不会一定趋近于0，但对于几何约束类的工程设计问题，只要设计变量的变化ε_q+n足够小即可满足要求。

引理2  任意给定向量x=(x₁, x₂, …, x_m)，其中

为向量x的初始值。当时(j=(1, 2, …, m))，一定存在n，在给定均方差误差ε下，有：

         (5)

证明  根据引理1，可得在n_x1, n_x2, …, n_xm次叠加下，得到向量x，取n=max(n_x1, n_x2, …, n_xm)，l_j=n_xj, n_xj+1, n_xj+2, …, n (1≤j≤m)，令k_ilj=0，从而得到式(5)。

2.2  求解几何约束问题的指数进制变步长方向可选优化算法

复杂几何约束问题可转换为非线性方程组式(1)表达，均可转化为式(6) 表示(其中，m为非线性方程个数)。

        (6)

式中：f_m(x)=0可以看为由n个变量x组成的方程；x=[x₁, …, x_n]。

若式(6)有解x=[x₁, …, x_n]，据引理1，经过有限次搜索后可得到式(5)。其中搜索策略设计如下：

指定优化目标＜，设定其m次迭代的误

差为。

在给定误差下，经过n次迭代后，其解

，从而可得式(6)精确解x。称该算法为指数进制变步长方向可选优化算法。

2.3  初始变量选则基准

在CAD的参数化设计中，根据已有约束条件，能得到多个设计变量解区间大概范围。则在区间范围内任意选择初始值，只要算法满足式(7)，根据引理1，则一定能找到满足要求的数值解。

      (7)

进一步简化式(7)，可以得出：

        (8)

特别是当初始值选取为区间中点时，式(8)可以 化为：

             (9)

根据式(9)，则可确定d_j和r_j。因此，针对参数化设计中的复杂几何问题，都可以根据先验知识，计算各设计变量的初始值，优化算法中的d_j和r_j。

对于如图1所示的相切圆问题，已知l₁=13.6 mm；l₂=8.25 mm；l₃=16.3 mm，则根据设计相关先验知识可知设计变量x­₂，y₂，x₄和y₄(R)的取值空间不大于(-l₁，l₁)。任意选取设计变量初始值为下列4种情况：

；

；

；

。

对于上述情况，若选择变进制步长参数d_i≥6，且r_i≥0.8，则均满足式(8)和(9)规定的原则。

3  算法设计

步骤1  初始化参数，根据参数化设计的复杂几何约束问题相关先验知识，确定自变量d_j，r_j和初始条件x_j的值，设置最大迭代次数N，迭代次数i以及误差精度要求ε，计算初始条件下的误差ε₀。

步骤2  在每一次搜索过程中，逐个对每个设计变量进行迭代计算。以设计变量x₁为例，以为步长，进行如下操作：比较初始误差ε₀与ε，若ε₀小，则输出结果，否则，令，求误差ε₁；比较ε₁与ε₀，若ε₁小，则k_1i=1，并将此时的误差赋给ε₀，即ε₀=ε₁，而下一次搜索的；否则，令，代入式(3)，求此时误差ε₂；比较ε₂与ε₀，若ε₂小，则k_1i=-1，并将此时的误差赋给ε₀，即ε₀=ε₂。此时，下一次搜索的；否则，令，返回原始误差ε₀，令k_1i=0，此时，下一次搜索x₁不产生变化。

以此类推，逐步对设计变量x_j进行上述操作，直到满足精度要求或达到迭代次数为止。

4  应用实例

4.1  填充问题

采用上述算法求解图1所示的相切圆填充问

题^[12]。给定优化目标精度ε=10^-12，选择变进制步长参数d_i=6，r_i=0.8，按照前述4种不同的初始值，优化计算结果如表1所示。从表1可看出：算法求解精度相当高，搜索次数较小，而且对于不同的设计变量初始值，采用相同的d_i和r_i，可获得基本一致的求解结果，而且优化次数没有发生很大的改变。

利用表1中第二组初始变量求解时，可得各设计变量的逼近真值过程，相切圆填充参数化优化过程如图3所示。

4.2  正二十面体设计求解问题

采用该算法求解图2所示的正二十面体问题时，设计变量初始值选其解区间中点值，根据式(8)，可取：d_i=2，r_i=0.96。算法迭代400次后，其误差精度达到10^-8，其整个运算时间为1.8 s(所用计算机基本参数为赛扬CPU 2.66 kHz，内存512 M)。迭代400次后的数值解如下：

[x₁, y₁, z₁, …, x₁₂, y₁₂, z₁₂]=[0, 0, 0, 0, 1.701 301 616 084 34, 1.051 462 227 188 68,

1.618 033 985 558 91, 0.525 731 108 449 10,

1.051 462 227 188 68, 0.999 999 991 981 59,

-1.376 381 923 364 48, 1.051 462 227 188 68,

-1.000 000 006 541 15, 1.376 381 915 359 66,

1.051 462 227 188 68, -1.618 033 989 748 76,

表1  填充问题优化计算结果

Table 1  Optimization compution results of filling problem

图3  填充问题优化过程图

Fig.3  Geometric optimization processes for filling problem

0.525 731 117 603 62, 1.051 462 227 188 68,

1.000 000 002 907 04, 1.376 381 918 334 23,

2.752 763 843 162 73, 1.618 033 985 528 92,

-0.525 731 118 195 13, 2.752 763 843 162 73,

-8.233 035 292 02×10^-9, -1.701 301 617 3,

2.752 763 843 162 73, -1.618 033 991 935 53,

0.525 731 106 235 17, 2.752 763 843 162 73,

-0.999 999 997 922, 1.376 381 924 456 33,

2.752 763 843 162 73, 0, 0, 3.804 226 066 248 38]。

其误差优化过程如图4所示(图中，i为搜索次数；c为误差)，几何图形参数化优化过程如图5所示。

图4  优化过程

Fig.4  Optimization process

图5  二十面体几何优化过程

Fig.5  Geometric optimization processes for icosahedron

5  结论

将参数化设计中的几何约束问题转化为约束方程组的求解问题，提出了一种指数进制变步长方向可选优化算法。本文针对算法基本思想，提出并证明了2个引理。在此基础上，应用该算法求解了2个典型的几何约束问题，计算结果表明该算法具有以下优点：

(1) 应用该算法求解参数化设计中的复杂几何问题时，可有效利用工程设计相关的先验知识，粗略确定设计变量初始值进行优化计算，而且该算法对设计变量初始值不敏感。

(2) 算法设计简单，而且不受几何约束形状的限制，能求解二维和三维空间问题，算法收敛速度快，求解精度高。

(3) 对于极为复杂的多参数设计问题(如设计参数多于30个)，要充分利用设计中的先验知识，缩小设计参数的取值空间，可有效提高算法的迭代次数。

参考文献：

[1] 林强, 高小山, 刘媛媛, 等. 基于几何约束求解的完备方法[J]. 计算机辅助设计与图形学学报, 2007, 19(7): 829-836.
LIN Qiang, GAO Xiao-shan, LIU Yuan-yuan, et al. The complete method based on geometric constraint solving[J]. Journal of Computer Aided Design & Computer Graphics, 2007, 19(7): 829-836.

[2] 高曙明, 彭群生. 一种基于几何推理的参数化设计方法[J]. 计算机学报, 1994, 17(11): 816-822.
GAO Shu-ming, PENG Qun-sheng. An approach to parametric design based on geometric reasoning[J]. Chinese Journal of Computers, 1994, 17(11): 816-822.

[3] 高小山, 蒋鲲. 几何约束求解研究综述[J]. 计算机辅助设计与图形学学报, 2004, 16(4): 385-396.
GAO Xiao-shan, JIANG Kun. Survey on geometric constraint solving[J]. Journal of Computer-Aided Design & Computer Graphics, 2004, 16(4): 385-396.

[4] Quak E, Weyich N. Decomposition and reconstruction algorithms for spline wavelets on a bounded internal[J]. Applied and Computational Harmonic Analysis, 1994, 1(3): 217-231.

[5] 石志良, 陈立平, 王小刚. 三维装配约束推理的球面几何和球面机构法[J]. 计算机辅助设计与图形学学报, 2007, 18(7): 924-947.
SHI Zhi-liang, CHEN Li-ping, WANG Xiao-gang. Assembly constraint solving with spherical geometry and spherical linkage mechanism[J]. Journal of Computer-Aided Design & Computer Graphics, 2006, 18(7): 942-947.

[6] Kramer G. Solving geometric constraints systems: A case study in kinematics[M]. Cambridge, MA: MIT Press, 1992: 149-158.

[7] Lathem R S, Middleditch A E. Connectivity analysis: A tool for processing geometric constraints[J]. Computer-Aided Design, 1996, 28(11): 917-928.

[8] Verroust A, Schonek F, Roller D. Rule oriented method for parameterized computer aided design[J]. Computer-Aided Design, 1992, 24(10): 531-540.

[9] GAO Xiao-shan, HUANG Lei-dong. Geometric constraint solving with geometric transformation[J]. Science in China: Series F, 2001, 44(1): 50-59.

[10] Ge J X, Chou S C, Gao X S. Geometric constraint satisfaction using optimization methods[J]. Computer-Aided Design, 2000, 32(14): 867-879.

[11] 李庆扬, 莫孜中, 祁力群. 非线性方程组的数值求解[M]. 北京: 科学出版社, 1987: 77-98.
LI Qing-yang, MO Zi-zhong, QI Li-qun. Numerical solution of nonlinear equations[M]. Beijing: Science Press, 1987: 77-98.

[12] 王书亭, 王战江. 粒子群优化算法求解非线性问题的应用研究[J]. 华中科技大学学报: 自然科学版, 2005, 33(12): 4-7.
WANG Shu-ting, WANG Zhan-jiang. Study of the application of PSO algorithms for nonlinear problems[J]. Journal of Huazhong University of Science and Technology: Natural Science, 2005, 33(12): 4-7.

[13] 向晓林. 非线性代数方程组与几何约束问题求解[D]. 成都: 四川大学数学学院, 2003: 72-122.
XIANG Xiao-lin. Nonlinear algebraic polynomial system and solving geometry constrained problem[D]. Chengdu: Sichuan University. Mathematical College, 2003: 72-122.

[14] 梁昔明, 朱灿, 颜东煌. 基于物种选择的遗传算法求解约束非线性规划问题[J]. 中南大学学报: 自然科学版, 2009, 40(1): 185-189.
LIANG Xi-ming, ZHU Can, YAN Dong-huang. Novel genetic algorithm based on species selection for solving constrained non-linear programming problems[J]. Journal of Central South University: Science and Technology, 2009, 40(1): 185-189.

[15] Hillyard R, Braid I. Analysis of dimension and tolerances in computer-aided mechanical design[J]. CAD, 1978, 10(3): 161-166.

(编辑 陈灿华)

收稿日期：2010-05-12；修回日期：2010-07-25

基金项目：湖南省高校创新平台开放基金资助项目(10K063)；教育留学回国人员科研启动基金资助项目(2009-1590)；湖南省科技计划项目(2010NK3044)

通信作者：周友行(1971-)，男，湖南双峰人，博士，副教授，从事数字化制造、算法设计研究；电话：0731-58292222；E-mail: zhouyouhang@xtu.edu.cn