GA在Beta樣條曲線光順中的應用

李彥紅 郭 增

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

0 前 言

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

1 光順準則

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

2 基于GA的三次Beta樣條曲線的光順算法

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

2.1 編碼方案

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

并稱這個二進制串為染色體,L為染色體長度.s1子串對應形狀參數(shù)β1,s2子串對應形狀參數(shù)β2.

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

2.2 適應度函數(shù)

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

2.3 GA算子

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

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

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

2.4 算法描述

Step1.用鼠標輸入待插值的型值點.

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

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

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

Step5.計算Step4中插值曲線的光順度,從而得到種群P中各個染色體的適應度值.

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

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

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

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

3 實 例

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

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

4 結(jié)束語

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

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

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

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