基于遺傳算法的散亂數(shù)據(jù)點(diǎn)的NURBS 曲面擬合與優(yōu)化

張志強(qiáng)，李建軍，趙 堅(jiān)

(天津城市建設(shè)學(xué)院 能源與機(jī)械工程系，天津 300384)

基于截面數(shù)據(jù)點(diǎn)的 NURBS 曲面擬合優(yōu)化問(wèn)題的解決已比較成熟，但基于散亂數(shù)據(jù)點(diǎn) NURBS曲面擬合優(yōu)化問(wèn)題的解決還不夠完善．曲面擬合優(yōu)化問(wèn)題可以描述為：給定散亂數(shù)據(jù)點(diǎn) Pi(i=1 2 …n)、對(duì)應(yīng)的矢量參數(shù)及容差 Tol，求在給定容差下，以盡量少的控制頂點(diǎn)表示出逼近給定數(shù)據(jù)點(diǎn)Pi的樣條曲面 r(u，v)，并要求曲面較為光順．這樣，可以對(duì)復(fù)雜曲面進(jìn)行簡(jiǎn)潔表達(dá)，在數(shù)控加工過(guò)程中，能減少 NC代碼輸入長(zhǎng)度，提高曲面加工速度和精度．

1 遺傳算法與NURBS曲面表達(dá)

遺傳算法是由美國(guó) Michigan大學(xué)的 John Holland提出的自適應(yīng)隨機(jī)搜索算法[1-3]．遺傳算法依據(jù)優(yōu)勝劣汰和適者生存的自然法則，從初始種群出發(fā)，采用基于適應(yīng)值比例的選擇策略在當(dāng)前種群中選擇個(gè)體，使用雜交和變異來(lái)產(chǎn)生下一代種群．通過(guò)一代代的競(jìng)爭(zhēng)淘汰，直到滿(mǎn)足期望的終止條件．遺傳算法廣泛應(yīng)用于函數(shù)優(yōu)化等領(lǐng)域，從理論上講，在不限制遺傳代數(shù)的條件下，它以概率1逼近全局最優(yōu)解．遺傳算法最初用于求解無(wú)約束優(yōu)化問(wèn)題，經(jīng)過(guò)改進(jìn)，可以進(jìn)行多目標(biāo)，多條件約束優(yōu)化問(wèn)題的求解[4-6]．

NURBS方法表達(dá)自由曲線和曲面有很多優(yōu)勢(shì)，利用控制頂點(diǎn)、權(quán)因子和矢量函數(shù)可對(duì)曲面進(jìn)行完全表述．NURBS曲面的表達(dá)式為[7]其中，wi,j(i=0，1，…，m；j=0，1，…，n)稱(chēng)為權(quán)或權(quán)因子(weights)，分別與控制頂點(diǎn) di,，j相聯(lián)系，di,j呈拓?fù)渚匦侮嚵?，形成一個(gè)控制網(wǎng)格．規(guī)定四角頂點(diǎn)處的權(quán)因子(w0,0，…，w0,n，wm,0，…，wm,n)均大于 0，其余wi,j≥0，以防止分母為零，保留凸包性質(zhì)并保證曲線不致因權(quán)因子而退化為一點(diǎn)．Ni,k(u)(i=0，1，…，m)，Nj,l(v)(j=0，1，…，n)是分別由節(jié)點(diǎn)矢量 U=[u0，u1，…，um+k+1]，V=[v0，v1，…，vn+l+1]按 De Boor-Cox 遞推公式?jīng)Q定的k，l次規(guī)范B樣條基函數(shù)．

2 改變權(quán)因子優(yōu)化NURBS曲面

2.1 遺傳因子的選擇

控制頂點(diǎn)、權(quán)因子和矢量函數(shù)一經(jīng)確定，則曲線或曲面就可完全確定．如果將其全部設(shè)置為遺傳因子，則計(jì)算量過(guò)于龐大．在控制頂點(diǎn)和權(quán)因子確定后，節(jié)點(diǎn)矢量求取有比較成熟的方法，如里森費(fèi)爾德(Riesenfeld)方法和哈特利(Hartley)-賈德(Judd)方法，因此將節(jié)點(diǎn)矢量設(shè)置為權(quán)因子并不合適．由文獻(xiàn)[2]和文獻(xiàn)[3]可知，若權(quán)因子修改適當(dāng)，它對(duì)曲面修改的效果與同時(shí)修改控制頂點(diǎn)和權(quán)因子的效果是相似的．基于以上考慮，利用 Hartley-Judd方法計(jì)算內(nèi)節(jié)點(diǎn)矢量值，選擇控制頂點(diǎn)的權(quán)因子作為遺傳基因．基因編碼方式主要有兩種：二進(jìn)制編碼和真值編碼．對(duì)于變量較多的優(yōu)化問(wèn)題，采用真值編碼，可使用較高的交叉概率和變異概率，以提高優(yōu)化的概率．因而對(duì)于該問(wèn)題，采用參數(shù)真值編碼．

2.2 評(píng)價(jià)函數(shù)的確定．

評(píng)價(jià)函數(shù)的確定基于以下思想，即曲面設(shè)計(jì)完成后，要求生成的曲面與給定的散亂數(shù)據(jù)點(diǎn)的容差不大于給定值，且比較光順．進(jìn)行控制頂點(diǎn)權(quán)值優(yōu)化以達(dá)到采用盡量少的控制頂點(diǎn)來(lái)描述符合上述要求的曲面．因此，在評(píng)價(jià)函數(shù)中既有容差項(xiàng)，又有光順項(xiàng)．

2.2.1 容差項(xiàng)的確定

容差的含義為所有各散亂數(shù)據(jù)點(diǎn) Pi與所求得的曲面上的相應(yīng)最近點(diǎn) r(ukvk)的距離之和，用公式表示為

2.2.2 光順項(xiàng)的確定[4-5]

為求得光順項(xiàng)表達(dá)式，由彈性力學(xué)中的薄板彈性變形方程可寫(xiě)出該曲面的能量函數(shù)

式中：ru，rv，ruu，rvv分別為曲面 r(u，v)沿 u，v方向的一、二階偏導(dǎo)矢；ruv為混合偏導(dǎo)矢；αij和βij(i，j=0，1)為給定常數(shù)，與材料特性有關(guān)；在彈性變形方程中，f(u，v)代表形體所受的力，即外載荷．

這些參數(shù)對(duì)曲面的影響見(jiàn)文獻(xiàn)[4]和文獻(xiàn)[5]．計(jì)算時(shí)，可令 f(u，v)=0，取 α11=α12=α22=0 β11=β22=1，β12=2，可計(jì)算出能量函數(shù)Er，取光順因子α=0.0001，則可寫(xiě)出評(píng)價(jià)函數(shù)J

3 主要計(jì)算步驟

(1)輸入散亂數(shù)據(jù)點(diǎn) Pi(i=1 2 … p)及其他初始參數(shù)(m，n，k，l，Tol，T)．m 和 n 分別為沿矢量 u，v 方向的控制點(diǎn)個(gè)數(shù)，所以共有控制頂點(diǎn)mn個(gè)，k和l分別為沿矢量u，v方向的樣條次數(shù)，Tol為容差，T為m與n的差值．

(2)由散亂數(shù)據(jù)點(diǎn)按 B樣條曲面描述生成控制頂點(diǎn)．

(3)利用遺傳算法，生成優(yōu)化曲面．

①確定遺傳代數(shù)、種群數(shù)目、交叉概率、變異概率等參數(shù)．

②種群初始化．隨機(jī)生成各控制點(diǎn)權(quán)值并進(jìn)行編碼操作，從而生成遺傳個(gè)體，進(jìn)而生成整個(gè)種群．

③求解評(píng)價(jià)函數(shù)和適應(yīng)度函數(shù)．取式(4)為評(píng)價(jià)函數(shù)．

為求取 J的最小值，并防止分母為零，適應(yīng)度函數(shù)取為

④約束條件．取 w0,0，w0,n，wm,0，wm,n均大于 0，其余 wi,j(i=0，1，…，m；j=0，1，…，n)均不小于 0．

⑤求出此種群中各個(gè)體的適應(yīng)度，選取此代中的最優(yōu)個(gè)體，并與全局最優(yōu)個(gè)體的適應(yīng)度進(jìn)行比較，將適應(yīng)度大者保留為全局最優(yōu)個(gè)體．

⑥對(duì)全局最優(yōu)個(gè)體和遺傳代數(shù)進(jìn)行判斷，若最優(yōu)個(gè)體適應(yīng)度為 1，則輸出結(jié)果，程序結(jié)束．若遺傳代數(shù)達(dá)到設(shè)定值，則轉(zhuǎn)至步驟④，否則轉(zhuǎn)至步驟⑦．

⑦進(jìn)行染色體基因遺傳、交叉及變異操作．

⑧生成新一代種群，遺傳代數(shù)加1，轉(zhuǎn)至步驟③．

(4)計(jì)算所生成的曲面容差，并與給定的容差相比較，若大于給定容差Tol，則進(jìn)行下一步，否則，輸出結(jié)果，程序結(jié)束．

(5)增加控制頂點(diǎn)數(shù)目，n=n+1并轉(zhuǎn)至步驟②，若仍不滿(mǎn)足容差條件，則m=m+1，轉(zhuǎn)至步驟②．

4 實(shí)例仿真

圖1為散亂數(shù)據(jù)點(diǎn)的 NURBS曲面擬合優(yōu)化結(jié)果，其中“*”表示給定散亂點(diǎn)，擬合數(shù)據(jù)點(diǎn)數(shù)為238，初始參數(shù)取 m=3，n=3，k=3，l=3，Tol=0.9，T=5，交叉率為 0.9，變異率為 0.15，最大遺傳代數(shù)為 100．?dāng)M合后，m=6，n=9，所以擬合曲面共有控制頂點(diǎn) 54個(gè)，此時(shí)Tol=0.857 6．

圖1 散亂數(shù)據(jù)點(diǎn)的NURBS曲面擬合優(yōu)化

5 結(jié) 論

以遺傳算法為工具，通過(guò)種群規(guī)模的合理設(shè)定，恰當(dāng)?shù)剡x擇遺傳因子和評(píng)價(jià)函數(shù)以完成對(duì)散亂數(shù)據(jù)點(diǎn)的曲面擬合．仿真結(jié)果表明，此方法可以進(jìn)行散亂數(shù)據(jù)點(diǎn)的 NURBS曲面擬合優(yōu)化，優(yōu)化后曲面符合容差條件，光順性較好，且曲面表述簡(jiǎn)單，有利于提高此類(lèi)曲面數(shù)控加工的速度和精度．

［1］ Galleily J E. An overview of genetic algorithms[J]. Kybemetics，1992，21(6)：26-30．

［2］ 趙 巍. 數(shù)控系統(tǒng)的插補(bǔ)算法及加減速控制方法的研究[D]. 天津：天津大學(xué)，2004.

［3］ 李德信，謝 敬，賈 杰. NURBS曲面權(quán)因子及其應(yīng)用研究[J]. 西安理工大學(xué)學(xué)報(bào)，2004，20(2)：154-159．

［4］ 穆國(guó)旺. 逆向工程中 NURBS曲面重構(gòu)[D]. 北京：北京航空航天大學(xué)，2001.

［5］ YIN Zhong-wei. Reverse engineering of a NURBS surface from digitized points subject to boundary conditions[J]. Computers and Graphics，2004，28(2)：207-212.

［6］ 宋德軍. 基于能量?jī)?yōu)化的曲線曲面造型理論及應(yīng)用研究[D]. 北京：北京航空航天大學(xué)，1998.

［7］ 房 京，李世杰. NURBS自由曲線、曲面的等距算法及其在數(shù)控加工中的應(yīng)用[J]. 河北工業(yè)大學(xué)學(xué)報(bào)，2002，31(5)：50-54．