幾何約束問題求解的方向可選指數(shù)進制步長優(yōu)化算法

周友行，張建勛，董銀松，韋衍

（湘潭大學(xué) 機械工程學(xué)院，湖南 湘潭，411105）

幾何約束問題求解的方向可選指數(shù)進制步長優(yōu)化算法

周友行，張建勛，董銀松，韋衍

（湘潭大學(xué) 機械工程學(xué)院，湖南 湘潭，411105）

針對參數(shù)化設(shè)計中的復(fù)雜幾何約束求解問題，提出1種可選指數(shù)進制變步長數(shù)值求解優(yōu)化算法。在給定的優(yōu)化目標下，采用指數(shù)進制變步長，對每個設(shè)計參數(shù)變量進行“前進、后退、保持一步”的方向選擇式試探判斷，即算法每迭代循環(huán)1次，誤差以指數(shù)方式進行遞減，變量則逐漸逼近先前設(shè)定的參數(shù)目標。利用該優(yōu)化算法，求解相切圓填充和正二十面體優(yōu)化2個經(jīng)典的幾何優(yōu)化問題。研究結(jié)果表明：該算法穩(wěn)定性強，收斂速度快，求解精度高并對初始值不敏感；該算法能夠求解多變量復(fù)雜參數(shù)化設(shè)計問題，并不受優(yōu)化變量個數(shù)的影響；利用方向可選指數(shù)變進制變步長優(yōu)化算法能有效解決二維和三維空間內(nèi)的參數(shù)化幾何約束優(yōu)化問題。

幾何約束；變步長；參數(shù)化設(shè)計；優(yōu)化目標；特殊進制

參數(shù)化設(shè)計是智能CAD技術(shù)在實際應(yīng)用中提出來的，它不僅可使CAD系統(tǒng)具有交互式繪圖功能，還具有自動繪圖的功能[1?2]。其中，幾何約束問題求解作為參數(shù)化設(shè)計的核心組成部分，其性能直接影響整個參數(shù)化系統(tǒng)。目前，國內(nèi)外學(xué)者對其進行了大量的研究，求解此類問題的主要方法有符號計算方法、基于圖論的方法、基于規(guī)則的方法和數(shù)值方法[3?10]。符號的幾何約束求解方法一般能求解出全部滿足約束的解，但求解速度比較慢，通常需要消耗大量的計算時間和空間；基于規(guī)則的方法由于受規(guī)則技術(shù)的限制，從而使該法實現(xiàn)效率低，而且無法處理元素之間的循環(huán)約束問題；基于圖論的方法，其最大問題也是無法求解循環(huán)約束的問題。數(shù)值計算方法是將約束問題轉(zhuǎn)化為求解非線性方程組的問題，特別在實際幾何約束求解中，變量的邊界條件明確，由于具有速度快而且能解其他一些不能解的、大的幾何約束問題，通用性強，當其他方法失效時，最終都用數(shù)值方法來進行求解[11?14]。因此，在幾何約束系統(tǒng)求解中，牛頓迭代法及其改進形式等數(shù)值計算方法仍然被廣泛應(yīng)用。此類數(shù)值算法的有效性取決于搜索策略、初始變量和搜索步長變化規(guī)律三因素。例如在牛頓迭代法及其改進形式中，步長的變化一般是有規(guī)律的，這導(dǎo)致算法搜索空間有限，所以，初始變量的選擇至關(guān)重要。從某種意義上說，數(shù)值算法就是基于搜索策略，尋找問題求解變量組合的一個過程。因此，若能通過搜索策略和步長變化規(guī)律的改變，擴大數(shù)值優(yōu)化算法的搜索空間，就有可能解決此類數(shù)值算法中的初始值敏感問題。在此，本文作者提出一個基于牛頓迭代法原則的指數(shù)進制變步長方向可選數(shù)值優(yōu)化算法，求解參數(shù)化設(shè)計的幾何約束問題。該算法采用最小二乘法設(shè)定優(yōu)化目標，指定步長變化呈指數(shù)形式，每次優(yōu)化搜索時，對步長進行“接受、拒絕或反向接受”的3次試探判斷，擴展數(shù)值優(yōu)化算法的搜索空間，可大幅度降低算法中初始變量選擇的敏感程度。

1 幾何約束與非線性方程組

幾何約束反映了幾何體的形狀和位置關(guān)系。幾何約束問題一般都能轉(zhuǎn)換成求解非線性方程組問題[13]，如圖1所示相切圓填充問題，通過給定三邊以及建立坐標系，則能建立如下非線性方程組式：

圖1 相切圓填充Fig.1 Filling problem for single circularity

可見：通過式（1），可將圖1中的幾何約束問題轉(zhuǎn)化為求解一個非線性方程組的問題。式（1）中的非線性方程組比較簡單，求解難度不大，大多數(shù)數(shù)值算法都能求解。

隨著產(chǎn)品設(shè)計的復(fù)雜化，由此產(chǎn)生的幾何約束問題往往會產(chǎn)生大型的復(fù)雜非線性方程組。如參數(shù)化設(shè)計圖2所示的正二十面體[15]，其中給定三維空間12個點及它們的約束，其點與點之間棱長為2。

圖2 正二十面體結(jié)構(gòu)Fig.2 Structure of icosahedron

若以P1坐標原點，以P1與P2為坐標系Y軸，P1與P11連線為Z軸建立直角坐標系。根據(jù)30個約束條件，即30條棱的長均為2，則可以建立非線性方程組：

對于式（2）中這樣的復(fù)雜非線性方程組，采用常見數(shù)值優(yōu)化方法，難以確定方程組的初始變量。

2 指數(shù)進制變步長方向可選優(yōu)化算法

2.1 算法基本思想

引理1當給定通過ki取值的選擇，一定存在（其中：d和r為給定值；0＜r＜1，N為任意給定數(shù)值）。證明假設(shè)，則此時當i增加1時，Nq+1有下列3種情況供選擇：

通過選擇kq+1，可找到以此類推，可得呈遞減趨勢。當n→∞時，可得從而引理得證。

備注：εq+n在嚴格數(shù)學(xué)意義上并不會一定趨近于0，但對于幾何約束類的工程設(shè)計問題，只要設(shè)計變量的變化εq+n足夠小即可滿足要求。

引理2任意給定向量x=（x1,x2, …,xm），其中xj′為向量x的初始值。當2, …,m）），一定存在n，在給定均方差誤差ε下，有：

證明根據(jù)引理1，可得在nx1,nx2, …,nxm次疊加下，得到向量x，取n=max（nx1,nx2, …,nxm），lj=nxj,nxj+1,nxj+2, …,n（1≤j≤m），令kilj=0，從而得到式（5）。

2.2 求解幾何約束問題的指數(shù)進制變步長方向可選優(yōu)化算法

復(fù)雜幾何約束問題可轉(zhuǎn)換為非線性方程組式（1）表達，均可轉(zhuǎn)化為式（6） 表示（其中，m為非線性方程個數(shù)）。式中：fm（x）=0可以看為由n個變量x組成的方程；x=[x1, …,xn]。

若式（6）有解x=[x1, …,xn]，據(jù)引理1，經(jīng)過有限次搜索后可得到式（5）。其中搜索策略設(shè)計如下：

在給定誤差ε下，經(jīng)過n次迭代后，其解，從而可得式（6）精確解x。稱該算法為指數(shù)進制變步長方向可選優(yōu)化算法。

2.3 初始變量選則基準

在CAD的參數(shù)化設(shè)計中，根據(jù)已有約束條件，能得到多個設(shè)計變量解區(qū)間大概范圍則在區(qū)間范圍內(nèi)任意選擇初始值xj′，只要算法滿足式（7），根據(jù)引理1，則一定能找到滿足要求的數(shù)值解。

特別是當初始值選取為區(qū)間中點時，式（8）可以化為：

根據(jù)式（9），則可確定dj和rj。因此，針對參數(shù)化設(shè)計中的復(fù)雜幾何問題，都可以根據(jù)先驗知識，計算各設(shè)計變量的初始值xj′，優(yōu)化算法中的dj和rj。

對于如圖1所示的相切圓問題，已知l1=13.6 mm；l2=8.25 mm；l3=16.3 mm，則根據(jù)設(shè)計相關(guān)先驗知識可知設(shè)計變量x2，y2，x4和y4（R）的取值空間不大于（?l1，l1）。任意選取設(shè)計變量初始值為下列4種情況：

對于上述情況，若選擇變進制步長參數(shù)di≥6，且ri≥0.8，則均滿足式（8）和（9）規(guī)定的原則。

3 算法設(shè)計

步驟1初始化參數(shù)，根據(jù)參數(shù)化設(shè)計的復(fù)雜幾何約束問題相關(guān)先驗知識，確定自變量dj，rj和初始條件xj的值xj′，設(shè)置最大迭代次數(shù)N，迭代次數(shù)i以及誤差精度要求ε，計算初始條件下的誤差ε0。

步驟2在每一次搜索過程中，逐個對每個設(shè)計變量進行迭代計算。以設(shè)計變量x1為例，以為步長，進行如下操作：比較初始誤差ε0與ε，若ε0小，則輸出結(jié)果，否則，令求誤差ε1；比較ε1與ε0，若ε1小，則k1i=1，并將此時的誤差賦給ε0，即ε0=ε1，而下一次搜索的否則，令代入式（3），求此時誤差ε2；比較ε2與ε0，若ε2小，則k1i=?1，并將此時的誤差賦給ε0，即ε0=ε2。此時，下一次搜索的否則，令返回原始誤差ε0，令k1i=0，此時，下一次搜索x1不產(chǎn)生變化。

以此類推，逐步對設(shè)計變量xj進行上述操作，直到滿足精度要求或達到迭代次數(shù)為止。

4 應(yīng)用實例

4.1 填充問題

采用上述算法求解圖1所示的相切圓填充問題[12]。給定優(yōu)化目標精度ε=10?12，選擇變進制步長參數(shù)di=6，ri=0.8，按照前述4種不同的初始值，優(yōu)化計算結(jié)果如表1所示。從表1可看出：算法求解精度相當高，搜索次數(shù)較小，而且對于不同的設(shè)計變量初始值，采用相同的di和ri，可獲得基本一致的求解結(jié)果，而且優(yōu)化次數(shù)沒有發(fā)生很大的改變。

利用表1中第二組初始變量求解時，可得各設(shè)計變量的逼近真值過程，相切圓填充參數(shù)化優(yōu)化過程如圖3所示。

4.2 正二十面體設(shè)計求解問題

采用該算法求解圖2所示的正二十面體問題時，設(shè)計變量初始值選其解區(qū)間中點值，根據(jù)式（8），可?。篸i=2，ri=0.96。算法迭代400次后，其誤差精度達到10?8，其整個運算時間為1.8 s（所用計算機基本參數(shù)為賽揚CPU 2.66 kHz，內(nèi)存512 M）。迭代400次后的數(shù)值解如下：

表1 填充問題優(yōu)化計算結(jié)果Table 1 Optimization compution results of filling problem

圖3 填充問題優(yōu)化過程圖Fig.3 Geometric optimization processes for filling problem

其誤差優(yōu)化過程如圖4所示（圖中，i為搜索次數(shù)；c為誤差），幾何圖形參數(shù)化優(yōu)化過程如圖5所示。

圖4 優(yōu)化過程Fig.4 Optimization process

圖5 二十面體幾何優(yōu)化過程Fig.5 Geometric optimization processes for icosahedron

5 結(jié)論

將參數(shù)化設(shè)計中的幾何約束問題轉(zhuǎn)化為約束方程組的求解問題，提出了一種指數(shù)進制變步長方向可選優(yōu)化算法。本文針對算法基本思想，提出并證明了2個引理。在此基礎(chǔ)上，應(yīng)用該算法求解了2個典型的幾何約束問題，計算結(jié)果表明該算法具有以下優(yōu)點：

（1） 應(yīng)用該算法求解參數(shù)化設(shè)計中的復(fù)雜幾何問題時，可有效利用工程設(shè)計相關(guān)的先驗知識，粗略確定設(shè)計變量初始值進行優(yōu)化計算，而且該算法對設(shè)計變量初始值不敏感。

（2） 算法設(shè)計簡單，而且不受幾何約束形狀的限制，能求解二維和三維空間問題，算法收斂速度快，求解精度高。

（3） 對于極為復(fù)雜的多參數(shù)設(shè)計問題（如設(shè)計參數(shù)多于30個），要充分利用設(shè)計中的先驗知識，縮小設(shè)計參數(shù)的取值空間，可有效提高算法的迭代次數(shù)。

[1] 林強, 高小山, 劉媛媛, 等. 基于幾何約束求解的完備方法[J].計算機輔助設(shè)計與圖形學(xué)學(xué)報, 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] 高曙明, 彭群生. 一種基于幾何推理的參數(shù)化設(shè)計方法[J].計算機學(xué)報, 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]. 計算機輔助設(shè)計與圖形學(xué)學(xué)報, 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] 石志良, 陳立平, 王小剛. 三維裝配約束推理的球面幾何和球面機構(gòu)法[J]. 計算機輔助設(shè)計與圖形學(xué)學(xué)報, 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] 李慶揚, 莫孜中, 祁力群. 非線性方程組的數(shù)值求解[M]. 北京： 科學(xué)出版社, 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] 王書亭, 王戰(zhàn)江. 粒子群優(yōu)化算法求解非線性問題的應(yīng)用研究[J]. 華中科技大學(xué)學(xué)報： 自然科學(xué)版, 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] 向曉林. 非線性代數(shù)方程組與幾何約束問題求解[D]. 成都：四川大學(xué)數(shù)學(xué)學(xué)院, 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] 梁昔明, 朱燦, 顏東煌. 基于物種選擇的遺傳算法求解約束非線性規(guī)劃問題[J]. 中南大學(xué)學(xué)報： 自然科學(xué)版, 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.

（編輯 陳燦華）

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）

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.

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

TP391

A

1672?7207（2011）05?1326?06

2010?05?12；

2010?07?25

湖南省高校創(chuàng)新平臺開放基金資助項目（10K063）；教育留學(xué)回國人員科研啟動基金資助項目（2009-1590）；湖南省科技計劃項目（2010NK3044）

周友行（1971?），男，湖南雙峰人，博士，副教授，從事數(shù)字化制造、算法設(shè)計研究；電話：0731-58292222；E-mail： zhouyouhang@xtu.edu.cn