基于計(jì)算幾何和遺傳算法的直線度誤差評(píng)定*

李　彬　趙惠英　趙則祥　席建普　任東旭

(1.西安交通大學(xué)， 西安 710049；2.中原工學(xué)院，鄭州 450007)

0　引言

隨著現(xiàn)代計(jì)算機(jī)計(jì)算速度的提高和計(jì)算幾何算法的成熟，計(jì)算幾何算法在形狀誤差的評(píng)定中已經(jīng)得到廣泛的應(yīng)用和研究。形狀誤差雖然被劃分為低頻誤差，但在對(duì)其進(jìn)行評(píng)定時(shí)，公稱尺寸均被引入到評(píng)定計(jì)算中，因此具體的評(píng)定實(shí)際轉(zhuǎn)化為一個(gè)尺寸計(jì)算問(wèn)題。形狀誤差的評(píng)定原來(lái)均是采用優(yōu)化算法進(jìn)行處理，如最小二乘法、最速下降法和遺傳算法等[1-3]。

對(duì)于最小區(qū)域法直線度誤差的評(píng)定，國(guó)內(nèi)外已進(jìn)行了廣泛地研究，除了直接用優(yōu)化方法評(píng)定外，計(jì)算幾何[4]評(píng)定方法在采樣點(diǎn)數(shù)較少時(shí)亦常被采用，擬合凸多邊形法即是這類方法之一。要使用該方法來(lái)評(píng)定最小區(qū)域直線度，首先要根據(jù)(平面內(nèi)的)被測(cè)點(diǎn)建立其相應(yīng)的凸多邊形。建立平面內(nèi)一組點(diǎn)的凸多邊形是計(jì)算幾何中一個(gè)關(guān)鍵問(wèn)題。

1　最小區(qū)域直線度誤差定義

平面內(nèi)直線度公差的定義為：在給定平面內(nèi)，公差帶是距離為公差值t的兩平行直線之間的區(qū)域。評(píng)定時(shí)首先用兩條平行直線包容被測(cè)實(shí)際要素，當(dāng)其中一條直線至少有兩點(diǎn)與被測(cè)實(shí)際要素接觸，另一條平行直線至少有一點(diǎn)與被測(cè)實(shí)際直線接觸且該接觸點(diǎn)位于上述兩接觸點(diǎn)之間，則由上述兩平行直線形成的區(qū)域即為最小包容區(qū)域。

對(duì)于平面內(nèi)被測(cè)量的一組數(shù)據(jù)，首先建立起它的平面坐標(biāo)系，其坐標(biāo)表達(dá)式為(Xi，Yi)，i=1，…，n，然后根據(jù)這些測(cè)量點(diǎn)擬合出參考直線，參考直線的方程表達(dá)式為

Y(X)=aX+b

(1)

式中，a為參考中線的斜率；b為參考中線的截距。

則最小區(qū)域直線度誤差的優(yōu)化函數(shù)定義為：

(2)

式(2)中，m為采樣點(diǎn)數(shù)；

表1　素線直線度的測(cè)量數(shù)據(jù)X：μm，Y：mm

續(xù)表

2　最小區(qū)域直線度的計(jì)算幾何算法評(píng)定[4]

為說(shuō)明計(jì)算算法的實(shí)施步驟，采用表1所示的直線度測(cè)量數(shù)據(jù)。該算法的步驟如下：

1)根據(jù)被測(cè)點(diǎn)的X(測(cè)量長(zhǎng)度)坐標(biāo)(Z向位移)進(jìn)行排序；

2)連接首尾兩點(diǎn)得到一條中線，以該中線為界將被測(cè)點(diǎn)劃分到兩個(gè)區(qū)域中，如圖1所示；

3)將兩個(gè)區(qū)域分別為‘上區(qū)’和‘下區(qū)’，若點(diǎn)在中線下方，則點(diǎn)歸類為下區(qū)；反之，則歸類為上區(qū)，如圖1所示。據(jù)此所有被測(cè)點(diǎn)被劃分成了上下兩組數(shù)據(jù)；

點(diǎn)的劃分方法如下：首先連接首尾兩點(diǎn)，得到中線Lm，其方程式為：

Y=ax+b

(3)

圖1　數(shù)據(jù)分區(qū)

圖2　上凸多邊形

4)被測(cè)點(diǎn)的分割完成后，就要分別在上下兩區(qū)內(nèi)進(jìn)行凸多邊形擬合了。擬合過(guò)程實(shí)際上就是保留凸頂點(diǎn)，舍去內(nèi)點(diǎn)。下面以下區(qū)擬合為例進(jìn)行說(shuō)明，設(shè)其包含n個(gè)點(diǎn)，首先連接Pn-1和Pn+1，其連線為L(zhǎng)n，根據(jù)Pn與Ln的關(guān)系來(lái)判斷Pn點(diǎn)是否為凸頂點(diǎn)，判斷條件為：若Pn在Ln的下方，則為臨時(shí)凸頂點(diǎn)；若在上方，則其必為內(nèi)點(diǎn)，可舍棄。所建立的上半凸面如圖2所示，進(jìn)而可以得到下半凸面，如圖3所示。

5)得到凸多邊形后就可以求解最終的最小區(qū)域直線度誤差，如圖5所示。求解方法為：設(shè)所求得的凸多邊形的邊數(shù)m，則其凸頂點(diǎn)的個(gè)數(shù)為m個(gè)。設(shè)邊Li的直線方程為Y=Ai+BiX，求出各頂點(diǎn)與該邊的距離(不包括該邊的兩個(gè)端點(diǎn))，挑選出最大值，根據(jù)式(2)中的判別準(zhǔn)則，最小區(qū)域直線度誤差可以表示為：

(4)

圖3　下凸多邊形圖

圖4　凸多邊形及最小區(qū)域包絡(luò)線

算法流程如表2所示。

表2　計(jì)算幾何算法評(píng)定直線度流程

3　最小區(qū)域直線度的遺傳算法評(píng)定

為了驗(yàn)證計(jì)算幾何算法對(duì)最小區(qū)域直線度評(píng)定的優(yōu)勢(shì)，作者使用了遺傳算法[5]來(lái)進(jìn)行比較。采用的數(shù)據(jù)仍然是表1所示的測(cè)量數(shù)據(jù)。

采用的遺傳算法如下：

1)首先利用最小二乘法擬合被測(cè)數(shù)據(jù)的參考直線參數(shù)a0，b0，所需優(yōu)化的目標(biāo)函數(shù)為式(2)。

2)由于最優(yōu)解與最小二乘解的偏差很小，選擇解搜索區(qū)間為(-a0，-b0)～(2a0，2b0)，以最小二乘解為初始值。

3)考慮到二進(jìn)制編碼、解碼操作簡(jiǎn)單，交叉、變異等遺傳操作便于實(shí)現(xiàn)，因此選擇二進(jìn)制編碼。為保證精度，優(yōu)化參數(shù)的有效數(shù)字保留到小數(shù)點(diǎn)后14位。由于優(yōu)化參數(shù)的數(shù)值較小，分別將此四個(gè)量乘以1014，分別用二進(jìn)制數(shù)表示，得到所需要的編碼長(zhǎng)度分別為nxi，i=1:N。

大量試驗(yàn)表明執(zhí)行代數(shù)m1和群體個(gè)數(shù)n1可以分別選擇為30和50，若選擇更大的進(jìn)化代數(shù)和群體個(gè)數(shù)并不會(huì)得到更優(yōu)解，只會(huì)影響效率。

4)生成初始群體。令T=rnd(1)，若T≥0.5，則選擇代碼1，若T≤0.5，則選擇代碼0。分別根據(jù)編碼長(zhǎng)度nxi，i=1:N，生成群體個(gè)數(shù)為50的初始種群。

5)解碼計(jì)算每個(gè)個(gè)體的適應(yīng)度值。將二進(jìn)制表示的個(gè)體轉(zhuǎn)化為十進(jìn)制數(shù)，并分別乘以10-14，代入到式(4)中得到各自的適應(yīng)度值。

6)各個(gè)個(gè)體的適應(yīng)度值進(jìn)行尺度變換，采用線性變換法。

7)選擇操作采用按比例的適應(yīng)度分配法進(jìn)行。

8)以0.25的交叉概率進(jìn)行交叉操作。

9)以0.05的變異率進(jìn)行變異操作。

10)將此時(shí)的個(gè)體利用二進(jìn)制數(shù)表示，并重新回到步驟5)開(kāi)始，繁殖到50代結(jié)束。

11)挑選所有個(gè)體的適應(yīng)度最大值及其對(duì)應(yīng)的xi，i=1:N值。適應(yīng)度最大值即是要求的目標(biāo)函數(shù)的優(yōu)化值。

4　算法比較結(jié)果

4.1　計(jì)算幾何和遺傳算法的計(jì)算結(jié)果

采用文中所述的兩種算法分別對(duì)表1所示的直線度測(cè)量數(shù)據(jù)進(jìn)行了處理，得到了圖5所示的兩個(gè)包絡(luò)線。以及表3所示的結(jié)果比較表。由表3可以看出，遺傳算法和計(jì)算幾何法的評(píng)定結(jié)果非常相近。

圖5　計(jì)算幾何算法和遺傳算法的直線度誤差

表3　三種素線直線度誤差比較表　(單位：μm)

4.2　計(jì)算幾何和遺傳算法的計(jì)算結(jié)果和效率比較

圖6　三種算法的計(jì)算結(jié)果比較

為了比較兩種算法的計(jì)算結(jié)果和效率，采用了20組數(shù)據(jù)進(jìn)行比較，20組數(shù)據(jù)的點(diǎn)數(shù)從100到2000，計(jì)算結(jié)果和效率比較見(jiàn)圖6和圖7。圖6還包含了最小二乘法的計(jì)算結(jié)果。由圖7可以看出，計(jì)算幾何算和遺傳算法的計(jì)算結(jié)果相近；另隨著測(cè)量數(shù)據(jù)的增加，三種算法的計(jì)算結(jié)果更加接近，這說(shuō)明隨著提取要素?cái)?shù)量的增加，測(cè)量結(jié)果將更趨近于被測(cè)要素的實(shí)際情況。由圖7可以看出，遺傳算法的計(jì)算效率隨采樣數(shù)量的增加而降低，而計(jì)算幾何算法的變化較小，即使測(cè)量點(diǎn)達(dá)到2000點(diǎn)，計(jì)算時(shí)間仍然小于1s。

5　結(jié)論

本文建立了基于計(jì)算幾何的最小區(qū)域直線度評(píng)定算法，編寫(xiě)了相應(yīng)的VB評(píng)定和圖形顯示模塊，并將該算法與遺傳算法的計(jì)算結(jié)果及計(jì)算效率進(jìn)行了對(duì)比，比較結(jié)果和圖形顯示表明，兩種算法的結(jié)果相近，但計(jì)算幾何算法效率更高。

[1]羅英俊，李彬.最小區(qū)域平面度的計(jì)算幾何評(píng)定算法研究，制造技術(shù)與機(jī)床，2009(1)：92-94

[2]Jyunping Huang.An efficient approach for solving the straightness and flatness problems at large number of data points[J].computer-aided design，35(2003):15-25

[3]康敏.求解“最小條件”直線度誤差值的精確算法，計(jì)量技術(shù)，1992(02)

[4]Mark de berg.Computational geometry algorithm and application.London: Springer-Verlag london Limited，1997

[5]王小平.遺傳算法:理論應(yīng)用與軟件實(shí)現(xiàn),西安交通大學(xué)出版社,2007