２ＯＯ９年第０６期 第２５卷 （总２１０期） 吉林省教育学院学报 ＪＯＵＲＮＡＬＯＦＥＤＵＣＡＴＩＯＮＡＬＩＮＳＴＩＴＩＹｒＥＯＦＪＩＬＩＮ ＰＲＯＶＩＮＣＥ Ｎｏ．０６，２００９ Ｖｏ１．２５ Ｔｏｔａｌ Ｎｏ．２１０ 优化法求解几何约束 孙年芳 （湖南娄底职业技术学院，湖南娄底４１７０００） 摘要：本文介绍了一般的优化法在几何约束求解中的应用。提出了一个新的优化函数。用来解决过约束和欠约束的问题。 关键词：优化技术；约束求解 中图分类号：０１０ 文献标识码：Ａ 文章编号：ｌ６７ｌ—ｌ５８０（２０ｏ９）ｏ６—Ｏ１４７—ｏ２ 从传统的角度来看，约束求解与优化技术分属 不同的领域。前者属于计算机科学及人工智能领 域，而后者则属于数学中的运筹学范畴。但是由于 二者在求解技术上的互补性以及解决实际问题的需 要，近年来它们在不断地互相融合。 对于参数化设计系统来说，不可避免地要用到 ｋ＋１次迭代值，Ｆ（ｘ ）为方程的值。Ｊ（ｘ ）为雅可 比矩阵，在计算时，要求Ｊ（ ）可逆，因此，对于过约 束或欠约束系统，就不能采用该方法求解。可以使 用Ｊ（ｘ ）的广义逆。但是广义逆的求解是比较麻烦 的，也不能保证迭代过程的收敛性。使用优化解法， 可以对方程的左边平方和求极小值，即对（１—３）式 数值解法。对于循环约束求解的问题，更需要使用 到数值求解法。优化方法在几何约束中的应用，由 葛建新首先提出。该方法求解循环约束最常被使用 的数值方法为人Ｎｅｗｔｏｎ—Ｒａｐｈｓｏｎ法。这种方法要 求给定的初始值，在精确解的附近，这样，才能保证 迭代过程的稳定。在实际设计系统中，不可避免地 有过约束和欠约束问题的存在，对于这种问题，使用 求极小值。 血 ． 仃（ｘ）＝三ｆｉ（ｘ） （１—３） 实际设计过程中，过约束和欠约束的情况经常 出现。特别在图纸设计初期，图形往往是欠约束的， 即使在设计结束后，由于一些不太重要的尺寸并没 有标出来，此时图形还可能处在欠约束状态。工程 图纸一般很少出现过约束的情况，这种情况一般是 由于在用变量化设计系统设计的时候，系统能够自 动识别图形中的约束情况，在随后的设计过程中，设 计者根据需要对约束进行增加或修改而引起的。 由于优化方法对变量的个数没有要求，因此即 使出现欠约束或过约束的情况，也可以较容易的进 牛顿法，不能够得到解。而使用优化的方法则可得 到一个合适的解，使其在一定程度上符合设计的 要求。 优化方法的提出 一、般来说，几何约束问题可以用下面的方程组 来表示： ｆ１（Ｘｌ，Ｘ２，…Ｘ ）：Ｏ； 一行处理，并得到合理的结果。使用优化求解的方法， 对于中等规模的几何约束问题是很容易进行求解 的，但是当几何约束增加的时候，用这种方法求解所 需要的时间就较长。可以采用方程分解的方法，把 方程分解为如下的形式： Ｐｌ（ｘｌ，Ｘ２，…ｘ。１）＝Ｏ； Ｐ２（Ｘｌ，Ｘ２，…Ｘｎｌ＋ｎ２）＝０； ｆ２（ｘｌ，ｘ２，…Ｘｎ）＝０； （１—１） ……ｆⅢ（ｘｌ，Ｘ２，… ）＝Ｏ； 这样，问题就变成了求解（１一１）式表示的方程 组。使用牛顿法的公式如下： Ｘ…＝Ｘｋ—Ｊ（ｘｋ） Ｆ（Ｘｋ）（１—２） 在（１—２）式中，ｘ 为第ｋ次迭代值，ｘ ＋，为第 收稿日期：２ｏ０９—０３一Ｉｌ 作者简介：孙年芳（１９７４一）．女．湖南双峰人，湖南娄底职业技术学院，讲师。研究方向：软件工程，计算机辅助设计。 １４７ Ｐｔ（ｘ１，…ｘｎ１＋．．．＋ｍ）＝０； Ｐｉ为原方程的一个子集，这样可以按照顺序依 次进行求解。 另一种方式是，根据我们二维特征的定义，把图 形分解成由多个二维形状特征的组合，这样就使约 束分成了多个层次，分别求解。当约束含有不等式 的时候，求解的过程就变得较为复杂。因为上述的 方法，有时只能求出局部最优解，要获得全局最优 解，可以用一些全局优化的办法来进行，如遗传算 法，模拟退火等方法。 二、新的优化函数的提出 在求解过约束和欠约束问题的时候，从上节可 以看出，采用优化算法可以得到一个比较合理的结 果，最终得到的结果应该和给定的初始值比较靠近。 但是，优化算法中没有任何措施来明确地保证这一 点。设初始值为Ｘ０，令结果为ｘ，若对他们间的距 离求极小值，则可以保证，计算结果同初始值间的距 离最小。即对下式求极小： ｄｉｓ＝ｆＩ Ｘ一）（ｏ ＩＩ（１－４） 对上式求极小的同时，还要保证能满足约束的 要求。这样，问题就转变为如下‘的约束求解的 问题： ｒａｉｎ Ｉｌ ｘ一）（０ ＩＩ ｓ．ｔ．Ｆ（Ｘ）＝０（１—５） 对于一般儿何约束的问题，变量主要是点的坐 标，和圆的半径。可以取（１—４）式为： ｄｉｓ＝． ｌ ｘｌｉ—ｘ Ｉ（１—６）或者，可取：ｄｉｓ＝． （ＸＪｉ—Ｘｎｉ） （１—７） 在原约束的情况下，对（１—７）式或（１—６）式 求极小，就可以保证约束求解后，得到的结果同初始 值间的距离最小，能保证在一定程度上符合设计的 意图。如果，取目标函数为（１—７）式，那么，有约束 优化问题可转变为如下的无约束优化问题： ｒａｉｎ． （ｘｌｉ—ｘ ｉ） ＋Ｐ・Ｆ（ｘ）（１—８） 在上式中，Ｐ为待定系数矢量，Ｐ＝｛ｐｌ，ｐ２，…， ｐｍ｝。采用无约束优化问题的求解方法，对上式中 的未知量求导，并令为０，可得： ｒ２（ｘ—Ｘ０）＋Ｐ・Ｆ１（Ｘ）＝０ ｉＦ（ｘ）：０（１—９） 在上述方程组中，方程组的个数为ｍ＋ｎ个，变 量的个数为ｍ十ｎ个，因此，对于欠约束问题可以根 据上述方程组，求得结果。还可以看出，如果变量在 目标函数中出现，而在约束中不出现，那么变量的值 将保持初始值不变。对于过约束的问题，由于在（１ ｌ４８ —９）式中并没有消除矛盾方程，因此，对方程组（１— ９）的求解，还必须使用优化方法才能得到解决。 三、在程序中实现欠约束的求解 由于在设计的时候，欠约束的问题是经常出现 的，因此，在参数化设计系统中，必须能够对其进行 简洁的处理。在对图形中的元素进行充分地分解 后，欠约束问题，归结为单个元素的欠约束处理的 问题。 定理：参数化设计图形中的元素，经过充分分解 后，必然可以归结为单个几何元素的欠约束求解 问题。 证明：采用反证法，如果上述结论不成立，那么， 在多元素耦合块中，必然存在欠约束的情况，在该耦 合块中，必然有元素ｓ受到的约束度小于其自由度， 则元素Ｓ，可以从其约束方程中单独求解。而高耦 合系统是不可再分解系统，因此，和假定矛盾，故定 理成立。 根据上述的定理，可以对单个几何元素的欠约 束求解问题进行分别讨论，并用于实际的参数化设 计系统中。 在二维几何约束系统中，设几何元素有：点，直 线，圆。首先假定，圆的直径已知。那么几何元素的 自由度为２。在几何元素欠约束的情况下，几何元 素只能受到一个约束度为１的约束。如果几何元素 没有受到任何约束，那么几何元素不需要参与运算。 如果图形的更新是实时的，每个元素加入后，立 刻使其受到的约束发生作用，那么，每次求解只需要 保存刚加入元素的初始值，而如果约束不是立刻发 生作用，那么就需要保存每次元素的初始值，用来确 定欠约束的解。在图形立刻更新，约束立刻发生作 用的情况下，欠约束的计算可以使用位移最小的概 念进行求解。 四、小结 采用优化的方法来求解几何约束问题，试验证 明这种方法能有效求解循环约束问题，对过约束和 欠约束的问题也能得到比较满意的解。 ［参考文献】 ［１］Ｈｏｏｋｅｒ Ｊ．Ｎ．．Ｌｏｇｉｃ，ｏｐｔｉｍｉｚａｔｉｏｎ ａｎｄ ｃｏｎｓｔｒａｉｎｔ ｐｒｏｇｒａｍｍｉｎｇ． ＩＮＦＯＲＭＳ Ｊｏｕｍａｌ Ｏｎ Ｃｏｍｐｕｔｉｎｇ。２００２。１４（４）：２９５￣３２１． ［２】袁亚湘，孙文瑜．最优化理论与方法［Ｍ】．北京：科学出版 社，２００１． ［３］葛建新等，基于约束的形状自动求解新算法［Ｊ］．计算机学 报，１９９５（２）． ［４］葛建新等，几何因果定性推理的基本原理和算法［Ｊ】．软件 学报。１９９７。４．
