基于粒子群算法和分割逼近法的復(fù)雜曲面輪廓度誤差計(jì)算

廖 平

中南大學(xué),長沙,4100831

0 引言

復(fù)雜曲面在現(xiàn)代機(jī)械制造業(yè)中的應(yīng)用越來越廣泛,在工程實(shí)際中,針對(duì)復(fù)雜曲面的高效率、高精度的測(cè)量要求也越來越高。最小區(qū)域法是我國和ISO評(píng)定復(fù)雜曲面輪廓度誤差的標(biāo)準(zhǔn)。但是,復(fù)雜曲面輪廓度誤差的求解是一個(gè)復(fù)雜非線性尋優(yōu)問題[1-5],目前采用的大多是傳統(tǒng)的近似求解方法,因此,基于最小區(qū)域法的復(fù)雜曲面輪廓度誤差的計(jì)算仍然是一個(gè)難題。

美國學(xué)者Kennedy等[6]于1995年提出了粒子群優(yōu)化(particle swarm optimization)算法,該算法具有高效并行優(yōu)化、流程簡單、不需要梯度信息、容易實(shí)現(xiàn)等特點(diǎn),對(duì)求解復(fù)雜曲面輪廓度誤差非線性優(yōu)化問題具有獨(dú)到之處。

本文提出了基于粒子群算法和分割逼近法的復(fù)雜曲面輪廓度誤差的計(jì)算方法。

1 粒子群優(yōu)化算法的基本原理

粒子群優(yōu)化算法是一種基于群智能方法的演化計(jì)算技術(shù),其思想來源于對(duì)鳥群捕食行為的模擬[6-7],采用速度—位置搜索模型,在優(yōu)化問題的D維空間隨機(jī)產(chǎn)生一個(gè)粒子數(shù)為m的初始種群,并賦予每個(gè)粒子一個(gè)隨機(jī)速度。更新粒子的速度和位置可表示為

式中,Vti為粒子i第t次迭代速度矢量;ω為慣性因子,ω≥0;c1、c2為學(xué)習(xí)因子;r1、r2為均勻分布在(0,1)區(qū)間的隨機(jī)數(shù);Xti為粒子i第t次迭代位置矢量;Pti為粒子最好位置;Gti為種群當(dāng)前最好位置。

假設(shè)求函數(shù)f(X)的最小值,那么粒子i的個(gè)體最優(yōu)位置為

則群體粒子的領(lǐng)域最優(yōu)值和對(duì)應(yīng)的位置為

2 復(fù)雜曲面NURBS描述及其輪廓度誤差的定義

2.1 基于NURBS描述復(fù)雜曲面

在CAD/CAM/CAGD中,形狀復(fù)雜、不規(guī)則的曲線輪廓一般以一組離散坐標(biāo)點(diǎn)和相應(yīng)控制參數(shù)表示,坐標(biāo)測(cè)量機(jī)對(duì)輪廓進(jìn)行測(cè)量時(shí)得到的也是一組離散坐標(biāo)點(diǎn)。對(duì)于這些離散的坐標(biāo)點(diǎn)一般用參數(shù)樣條曲面進(jìn)行擬合。而NURBS曲面具有局部性、變差縮減性、凸包性、在仿射與透視變換下的不變性、參數(shù)連續(xù)性,以及權(quán)因子的調(diào)形性等一系列優(yōu)良性能,在航空、航天、造船、汽車及模具工業(yè)的計(jì)算機(jī)輔助設(shè)計(jì)和輔助制造過程中得到廣泛應(yīng)用。一個(gè)k次NURBS曲面可以表示為多片有理多項(xiàng)式矢函數(shù)形式[8]:

式中,di,j為矩形域上特征網(wǎng)格控制點(diǎn);ωi,j為相應(yīng)控制點(diǎn)的權(quán)因子,規(guī)定四角點(diǎn)處用正權(quán)因子,即 ω0,0,ωm,0,ω0,n,ωm,n ＞0,其余 ωi,j≥0;Ni,k(u)、Nj,l(v)分別為u向k次和v向l次規(guī)范B樣條基函數(shù),它們分別由節(jié)點(diǎn)矢量U=(u0,u1,…,um+k+1)與V=(v0,v1,…,vn+l+1)由De Boor—Cox遞推公式?jīng)Q定。

2.2 復(fù)雜曲面輪廓度誤差的定義

按最小區(qū)域法來評(píng)定復(fù)雜曲面輪廓度誤差,其誤差值是包容被測(cè)輪廓的兩理論輪廓等距面的最小距離,如圖1所示。

設(shè)復(fù)雜曲面理論基準(zhǔn)點(diǎn)為(xtb,ytb,ztb),實(shí)際輪廓測(cè)得基準(zhǔn)點(diǎn)為(xb,yb,zb),輪廓測(cè)點(diǎn)坐標(biāo)為P={Pj=(xj,yj,zj)|j=1,2,…,m},其坐標(biāo)變換矩陣為

式中,Tp為測(cè)點(diǎn)平移坐標(biāo)變換矩陣;Tx為測(cè)點(diǎn)繞x軸旋轉(zhuǎn)θ后的變換矩陣;Ty為測(cè)點(diǎn)繞y軸旋轉(zhuǎn)φ后的變換矩陣;Tz為測(cè)點(diǎn)繞z軸旋轉(zhuǎn)ψ后的變換矩陣。

測(cè)點(diǎn)變換后的新坐標(biāo)為復(fù)雜曲面輪廓度誤差數(shù)學(xué)模型為

式中,dtj(Δx,Δy,Δz,θ,φ,ψ)為測(cè)點(diǎn)(xj,yj,zj)經(jīng)過坐標(biāo)變換后到理論輪廓的最小距離。

從復(fù)雜曲面輪廓度誤差數(shù)學(xué)模型理論可知:只有測(cè)點(diǎn)的位置位于最佳位置時(shí),才能保證包容全部測(cè)點(diǎn)的理論輪廓等距面之間的距離最小,這是一個(gè)非常復(fù)雜的非線性優(yōu)化問題[9-10]。

3 用分割逼近法計(jì)算測(cè)點(diǎn)到設(shè)計(jì)曲面輪廓的最小距離

設(shè)測(cè)點(diǎn)坐標(biāo)為(xk,yk,zk),如圖2所示,該點(diǎn)到用NURBS曲面描述的理論輪廓r(u,v)最小距離的數(shù)學(xué)模型為

要精確計(jì)算點(diǎn)到復(fù)雜曲面的最小距離,需要解決求解方法的選擇和算法的計(jì)算效率兩個(gè)關(guān)鍵問題。采用微分幾何方法求測(cè)點(diǎn)到理想輪廓的最小距離計(jì)算方法復(fù)雜,且工作量大,為此,本文提出一種快速數(shù)值求解法 ——分割逼近法。

(1)將NURBS曲面r(u,v)u向10等分、v向10等分,在曲面上形成11×11網(wǎng)格點(diǎn)r(ui,vj)(i=0,1,…,10;j=0,1,…,10)。

(2)計(jì)算測(cè)點(diǎn) pk到理論曲面網(wǎng)格點(diǎn)r(ui,vj)(i=0,1,…,10;j=0,1,…,10)上的距離dts

i,j,初始分割時(shí)取s=1。如圖 3所示。

(3)求測(cè)點(diǎn)到理論曲面上所有網(wǎng)格點(diǎn)距離的最小值:

繼續(xù)分割10×10等分,在曲面上形成11×11網(wǎng)格點(diǎn)r(us+1i,vs+1j)(i=0,1,…,10;j=0,1,…,10),轉(zhuǎn)到(2),繼續(xù)求解。

4 粒子群算法和分割逼近法相結(jié)合計(jì)算復(fù)雜曲面輪廓度誤差

(1)基本參數(shù)設(shè)置。c1=2,c2=2,ω=1,粒子群數(shù)量為n=30,最大迭代次數(shù)為tmax=100。

(2)粒子群初始化。在參數(shù)(Δx,Δy,Δz,θ,φ,ψ)允許的范圍內(nèi)隨機(jī)初始化粒子群體的位置:

隨機(jī)初始化對(duì)應(yīng)的速度:

每個(gè)粒子的初始最優(yōu)與初值相同,即

由式(4)求初始種群到達(dá)的最優(yōu)位置,即

(3)確定適應(yīng)值函數(shù)。選取復(fù)雜曲面輪廓度誤差的目標(biāo)函數(shù)為適應(yīng)值函數(shù),即個(gè)體(Δxti,Δyti,Δzti,θti,φti,ψti)所對(duì)應(yīng)的各測(cè)點(diǎn)到理論設(shè)計(jì)輪廓的最小距離中的最大值為

其中,eti為所有測(cè)點(diǎn)P={(xj,yj,zj)|j=1,2,…,m}經(jīng)過(Δxti,Δyti,Δzti,θti,φti,ψti)所對(duì)應(yīng)的坐標(biāo)變換后到理論設(shè)計(jì)輪廓的最小距離,eti采用分割逼近法求得。

(4)求出每一個(gè)粒子的最優(yōu)位置。首先計(jì)算每個(gè)粒子的適應(yīng)值 f(Δxti,Δyti,Δzti,θti,φti,ψti),然后求出每一個(gè)粒子的最優(yōu)位置:

(5)求當(dāng)代種群中到達(dá)的最優(yōu)位置,即

(6)根據(jù)式(1)、式(2)更新每個(gè)粒子的位置和飛行速度。

(7)檢查更新粒子位置越限情況并進(jìn)行相應(yīng)處理。

(8)判斷迭代次數(shù)t是否到達(dá)設(shè)定值tmax,如未達(dá)到則繼續(xù)迭代;若達(dá)到則停止計(jì)算,此時(shí)得到的種群中最優(yōu)位置為Ptg,所對(duì)應(yīng)的適應(yīng)值即為復(fù)雜曲面輪廓度誤差。

5 計(jì)算實(shí)例

表1為一理論設(shè)計(jì)輪廓三次NURBS曲面特征頂點(diǎn),表2為實(shí)際輪廓測(cè)點(diǎn),其中:

U=(0,0,0,0,0.5,1,1,1,1)

V=(0,0,0,0,0.5,1,1,1,1)

采用粒子群算法和分割逼近法相結(jié)合方法計(jì)算得到的輪廓度誤差為0.073 788 109 106 757 8mm,采用最小二乘法計(jì)算的輪廓度誤差為0.095 179 980 162 99 9mm,從計(jì)算結(jié)果可以看出采用粒子群算法和分割逼近法相結(jié)合的方法計(jì)算輪廓誤差值比最小二乘法的計(jì)算結(jié)果小,說明最小二乘法獲得的不是最優(yōu)解,不符合最小區(qū)域法評(píng)定復(fù)雜曲面輪廓度誤差的標(biāo)準(zhǔn)。

表1 理論輪廓控制點(diǎn)坐標(biāo) mm

表2 測(cè)點(diǎn)坐標(biāo) mm

(續(xù)表)

6 結(jié)束語

本文采用粒子群算法和分割逼近法相結(jié)合的方法計(jì)算復(fù)雜曲面輪廓度誤差,其精確度非常高,可達(dá)到任意給定的精度值,理論上可以收斂于全局最優(yōu)解,完全符合最小區(qū)域法的評(píng)定標(biāo)準(zhǔn)。該算法簡單明了,易于計(jì)算機(jī)程序?qū)崿F(xiàn),為復(fù)雜曲面輪廓度誤差的數(shù)據(jù)處理開辟了新的途徑,尤其非常適用于三坐標(biāo)測(cè)量機(jī)、飛機(jī)型架三坐標(biāo)測(cè)量系統(tǒng)的復(fù)雜曲面輪廓度誤差的測(cè)量數(shù)據(jù)處理。

[1]侯宇,張競,崔晨陽.復(fù)雜線輪廓度誤差坐標(biāo)測(cè)量的數(shù)據(jù)處理方法[J].計(jì)量學(xué)報(bào),2002,23(1):13-16.

[2]郭慧,林大鈞.基于微粒群算法的復(fù)雜曲面輪廓度誤差計(jì)算[J].東華大學(xué)學(xué)報(bào)(自然科學(xué)版),2008,34(3):274-277.

[3]王伯平,曾建潮.一種自調(diào)整的空間面輪廓度誤差的評(píng)定方法[J].計(jì)量學(xué)報(bào),2002,23(2):106-108.

[4]Yu Yuan,Lu Jun,Wang Xiaochun.Modeling and A-nalysis of the Best Match in Free—form Surface Measuring[J].Mechanical Science and Technology,2001,20(3):19-20.

[5]Liu Yujun,Zhu Xiuli.Research on Curve Surface Fairing of Complicated Ship Hull Plate[J].Journal of Dalian University of Technology,2005,45(2):226-229.

[6]Kennedy J,Eberhart R C.Particle Swarm Optimization[C]//Proc.of IEEE International Conference on Neural Networks.Piscataway,New Jersey:IEEE Service Center,1995:1942-1948.

[7]Eberhart R C,Shi Y.Particle Swarm Optimization:Developments,Applications and Resources[C]//Proc.of Congress on Evolutionary Computation.Piscataway:IEEE Press,2001:81-86.

[8]Choi B K,Yoo W S,Lee C S.Matrix Representation for NURBS Curve and Surface[J].Computer—aided Design,1990,22(4):235-240.

[9]劉元朋,劉晶,張力寧.復(fù)雜曲面測(cè)量數(shù)據(jù)最佳匹配問題研究[J].中國機(jī)械工程,2005,16(12):1080-1082.

[10]Kyuseojin A,Akmoto Y.A New Method of Best—fitting on Curved Surface[J].SPIE,1993,2101:54-61.