李彥紅 郭 增

1.河北建筑工程學(xué)院;2.張家口職業(yè)技術(shù)學(xué)院

0 前 言

曲線曲面造型的描述與控制在飛機(jī)、船舶、汽車以及家用電器等外形的計(jì)算機(jī)輔助設(shè)計(jì)中有著重要的意義,所以人們對(duì)曲線曲面造型新方法的探索永無止盡.為了使構(gòu)造的曲線曲面具有良好的性質(zhì),如曲線曲面滿足光順性的要求等,優(yōu)化技術(shù)被廣泛的應(yīng)用于曲線曲面造型中.GA(genetic algorithm)作為一種實(shí)用、高效、魯棒性強(qiáng)的優(yōu)化技術(shù),發(fā)展極為迅速,已引起國內(nèi)外CAD領(lǐng)域?qū)W者們的高度重視.GA在曲線曲面造型應(yīng)用中已經(jīng)取得了一定的發(fā)展,但就目前實(shí)際而言,關(guān)于GA在曲線曲面造型中的研究還是很不足的.本文將GA應(yīng)用到Beta樣條曲線中,采用樣條曲線的光順能量作為適應(yīng)度函數(shù),從而得到更為光順的插值Beta樣條曲線,為曲線造型技術(shù)又提供了一個(gè)更為簡單有效地曲線光順方法.

1 光順準(zhǔn)則

給定曲線的n+1個(gè)控制頂點(diǎn)陣列di(i=0,1,…,n),設(shè)為相鄰兩控制頂點(diǎn)連線的單位折線向量,li=‖di-di-1‖為相鄰兩控制頂點(diǎn)連線的折線長度,‖ei+1-ei‖表示相鄰兩控制多邊形折線di-1di和didi+1方向的變化量,則稱為曲線X的光順度.對(duì)于曲線上任一控制多邊形,如果值較大,表明所對(duì)應(yīng)的曲線段的法向曲率變化較大,則曲線在該處的光順性就差;反之,法向曲率變化較平緩,曲線在該處的光順性就好.據(jù)此,光順準(zhǔn)則可定義為:如果EX＜EY,則曲線X比曲線Y更光滑.

2 基于GA的三次Beta樣條曲線的光順?biāo)惴?/h2>

三次Beta樣條曲線除了具有G2連續(xù)性,還提供了額外的形狀參數(shù),可以對(duì)曲線的性質(zhì)實(shí)現(xiàn)進(jìn)一步的控制.但是,如何確定這些參數(shù)能夠使曲線具有良好的光順性,目前的文獻(xiàn)中還沒有談及,所以使得Beta樣條曲線在實(shí)際中的應(yīng)用受到了限制.本文將采用GA對(duì)三次Beta樣條曲線的光順度進(jìn)行優(yōu)化確定其形狀參數(shù),從而得到具有較小光順度的插值光滑曲線.

2.1 編碼方案

本算法采用二進(jìn)制編碼,將三次Beta樣曲線中的形狀參數(shù)β1和β2編碼為二進(jìn)制串

并稱這個(gè)二進(jìn)制串為染色體,L為染色體長度.s1子串對(duì)應(yīng)形狀參數(shù)β1,s2子串對(duì)應(yīng)形狀參數(shù)β2.

對(duì)于初始種群,我們?cè)O(shè)其種群規(guī)模為K,每個(gè)染色體的基因初值均按事先設(shè)定的節(jié)點(diǎn)率R隨機(jī)地賦值0或1,R為初始時(shí)期望的染色體中1和0出現(xiàn)的比率.

2.2 適應(yīng)度函數(shù)

顯然,這樣得到的適應(yīng)度函數(shù)值越大,染色體越優(yōu).當(dāng)算法收斂時(shí),某個(gè)染色體的適應(yīng)度值達(dá)到最大,即得到優(yōu)化問題的解.

2.3 GA算子

對(duì)于選擇算子,本文采用杰出策略將當(dāng)前最優(yōu)的染色體個(gè)體直接傳給下一代,其余染色體采用輪盤賭的方式作出選擇.

對(duì)于交叉算子,本文采用兩點(diǎn)交叉,同時(shí)將交叉產(chǎn)生的兩個(gè)子代染色體和兩個(gè)父代染色體的適應(yīng)度作比較,選出適應(yīng)度較大的兩個(gè)染色體傳給下一代.

對(duì)于變異算子,根據(jù)變異概率,進(jìn)行0、1變異,而且同樣選擇出變異前后適應(yīng)度較大的染色體傳給下一代.

2.4 算法描述

Step1.用鼠標(biāo)輸入待插值的型值點(diǎn).

Step2.輸入GA的各個(gè)控制參數(shù).

Step3.根據(jù)給定的種群規(guī)模和節(jié)點(diǎn)率,建立初始種群P.

Step4.根據(jù)P中每個(gè)染色體所表示的β1和β2的值,構(gòu)造插值三次Beta樣條曲線.

Step5.計(jì)算Step4中插值曲線的光順度,從而得到種群P中各個(gè)染色體的適應(yīng)度值.

Step6.對(duì)種群進(jìn)行選擇、交叉、變異操作,產(chǎn)生新種群P′.

Step7.檢驗(yàn)算法是否收斂:若收斂,則轉(zhuǎn)入Step8;否則,令P=P′,轉(zhuǎn)入Step4.

Step8.找到種群P′中的最優(yōu)染色體S,根據(jù)編碼規(guī)則得到它所表示的形狀參數(shù).

在Step7中檢驗(yàn)算法收斂的方法有以下幾種:①規(guī)定算法的迭代次數(shù),超過該次數(shù)則停止迭代;②當(dāng)種群中最大的適應(yīng)度值經(jīng)過g次迭代后均不再發(fā)生變化時(shí),則說明算法已經(jīng)收斂.

3 實(shí) 例

種群規(guī)模K=50,R=0.6,交叉概率Pc=0.8,變異概率Pm=0.8.圖為用本文給出的算法確定出的光順三次Beta樣條曲線.由此可以看出本文的方法確實(shí)有效,具有一定的可行性.

圖1 最優(yōu)染色體對(duì)應(yīng)的插值曲線

4 結(jié)束語

本文將GA應(yīng)用到三次Beta樣條曲線中,采用樣條曲線光順度的函數(shù)作為適應(yīng)度函數(shù),實(shí)例驗(yàn)證了此方法可以得到更為光順的插值Beta樣條曲線,具有一定的實(shí)際應(yīng)用價(jià)值.這又將推動(dòng)GA在曲線曲面造型應(yīng)用領(lǐng)域的研究向更深層次的發(fā)展.

[1]施法中.計(jì)算機(jī)輔助幾何設(shè)計(jì)與非均勻有理B樣條.北京:高等教育出版社,2001

[2]朱心雄.自由曲線曲面造型技術(shù).北京:科學(xué)出版社,2000

[3]陳國良,王熙法,莊鎮(zhèn)泉等.遺傳算法及其應(yīng)用.北京:人民郵電出版社,1996