基于遺傳粒子群混合算法的NURBS曲線降階*

□ 張 鑫 □ 南 余榮

浙江工業(yè)大學(xué) 信息工程學(xué)院 杭 州 3 10023

在計(jì)算機(jī)圖形和計(jì)算機(jī)輔助幾何設(shè)計(jì)領(lǐng)域，非均勻有理B樣條（NURBS）曲線已經(jīng)成為設(shè)計(jì)和描述各種復(fù)雜曲線的標(biāo)準(zhǔn)，它能表示所有的自由曲線。由于在不同的數(shù)據(jù)模型中采用的曲線階數(shù)各不相同，為了提高計(jì)算效率以及穩(wěn)定性，實(shí)現(xiàn)不同階數(shù)曲線之間的數(shù)據(jù)交換和傳遞，必然要解決其降階問題。因此，NURBS曲線的降階問題不僅有著重要的理論價(jià)值，而且有著迫切的應(yīng)用需求。

近幾年對(duì)NURBS曲線降階問題有了很多的研究成果，文獻(xiàn)［1］采用遺傳算法實(shí)現(xiàn)一次對(duì)NURBS曲線降多階，得到的曲線為全局最優(yōu)或次優(yōu)。文獻(xiàn)［2］從最優(yōu)思想出發(fā)，把NURBS曲線的降階問題轉(zhuǎn)化為求最優(yōu)問題，并基于微粒子群算法給出了NURBS曲線降階的一種方法。文獻(xiàn)［3］利用NURBS曲線的顯式矩陣表示和多項(xiàng)式最佳一致逼近理論，得到了以顯式表達(dá)的NURBS曲線可退化的充要條件，給出了NURBS曲線降階的方法。本文提出了基于遺傳算法和粒子群算法混合的算法對(duì)NURBS曲線實(shí)現(xiàn)降階，采用該算法能夠更快速更精確地找到全局最優(yōu)的降階NURBS曲線。

1 問題的提出

設(shè)：P1，P2， …，Pn為給定的 n 個(gè)控制頂點(diǎn)，ω1，ω2，…，ωn為相應(yīng)控制頂點(diǎn)的權(quán)，U=｛u0≤…≤uk≤…≤un+1≤…≤uk+n｝為節(jié)點(diǎn)序列，由這些控制頂點(diǎn)、權(quán)和節(jié)點(diǎn)定義的 k 次（k+1 階）NURBS 曲線的參數(shù)方程為［4］：

其中，Nj，k（u）為 B 樣條基函數(shù)［5］，滿足：

實(shí)際上NURBS曲線的降階問題就是要找出另外一條 s（s＜k）次 NURBS 曲線：

使 f（u）盡量逼近 f（u），兩條曲線的逼近程度可以用其參數(shù)方程差的最大值來描述：

要使降階后的曲線和原曲線逼近，就要使h的值盡量小。因?yàn)镹URBS曲線受到控制頂點(diǎn)、權(quán)以及節(jié)點(diǎn)向量的影響，為了減少計(jì)算量，同時(shí)又保持曲線的端點(diǎn)不變，在降階時(shí)對(duì)降階后的NURBS曲線的節(jié)點(diǎn)向量稍作改動(dòng)。如果是降一階，將降階前節(jié)點(diǎn)序列的第一個(gè)和最后一個(gè)點(diǎn)刪除作為降階后的節(jié)點(diǎn)序列，相應(yīng)的曲線控制頂點(diǎn)也要比降階前少一個(gè)。因此，NURBS曲線降階問題的實(shí)質(zhì)就是找出一組控制頂點(diǎn)、權(quán)以及節(jié)點(diǎn)向量，使由它們確定的NURBS曲線盡可能逼近原曲線。所以降階問題轉(zhuǎn)化為如下帶約束條件的優(yōu)化問題：

式中：R為實(shí)數(shù)。

2 粒子群算法和遺傳算法的基本原理

2.1 粒子群算法

粒子群算法屬于迭代算法的一種，從隨機(jī)解出發(fā)，通過迭代尋找最優(yōu)解，同時(shí)通過適應(yīng)度來評(píng)價(jià)解的品質(zhì)。在算法中，設(shè)有N個(gè)粒子組成一個(gè)粒子群，其中Xi（xi1，xi2，...，xin）為第 i個(gè)粒子的位置，它是優(yōu)化問題的一個(gè)潛在解；Pi=（pi1，pi2，...，pin） 為粒子 i所經(jīng)歷的最好位置（即具有最好的適應(yīng)值）；Pg（pg1，pg2，...，pgn）為群體中所有粒子經(jīng)歷過的最好位置；Vi=（vi1，vi2，...，vin）為粒子i的飛行速度，對(duì)于每一代t，每個(gè)粒子第d維（1≤d≤n）的速度和位置根據(jù)下列方程更新［6,7］：

式中：ω 為慣性權(quán)重；c1、c2為學(xué)習(xí)因子；rand （）、Rand（）為兩個(gè)在［0，1］范圍內(nèi)獨(dú)立均勻分布的隨機(jī)數(shù)。

標(biāo)準(zhǔn)粒子群算法的算法流程如下：

1）初始化群體規(guī)模為N粒子群，包括每個(gè)粒子的位置和速度。

2）計(jì)算每個(gè)粒子的適應(yīng)值。

3）對(duì)于每個(gè)粒子，將其適應(yīng)值與它所經(jīng)歷過的最好位置pbest的適應(yīng)值進(jìn)行比較，如果較好，則將其位置作為它自身當(dāng)前的最好位置pbest。

4）對(duì)于每個(gè)粒子，將其適應(yīng)值與全體粒子所經(jīng)歷的最好位置gbest的適應(yīng)值進(jìn)行比較，如果較好，則將其位置作為當(dāng)前群體的最好位置gbest。

5） 根據(jù)方程（6）、（7）對(duì)每個(gè)粒子的速度和位置進(jìn)行更新。

6）如果終止條件（通常為足夠的適應(yīng)值或達(dá)到一個(gè)預(yù)先設(shè)置的最大代數(shù)Gmax）滿足則停止，否則轉(zhuǎn)到第二步。

2.2 遺傳算法

遺傳算法跟其它智能算法一樣，也是通過模擬自然進(jìn)化過程來搜索最優(yōu)解。它求解問題的基本方法是：從當(dāng)前種群出發(fā)，待優(yōu)化的目標(biāo)函數(shù)解釋為生物種群對(duì)環(huán)境的適應(yīng)性，生物個(gè)體對(duì)應(yīng)優(yōu)化變量，利用選擇、復(fù)制、雜交和變異操作來生成新的種群。重復(fù)這個(gè)過程，直到出現(xiàn)滿足要求的種群或者達(dá)到了規(guī)定的進(jìn)化限制。

遺傳算法的主要運(yùn)算過程［8］如下。

1）編碼：編碼的方法主要有二進(jìn)制編碼、符號(hào)編碼和浮點(diǎn)數(shù)編碼3大類。

2）初始群體的生成。

3）適應(yīng)度值評(píng)估監(jiān)測(cè)：適應(yīng)度函數(shù)表明個(gè)體或解的優(yōu)劣性。

4）選擇：常用的方法有輪盤賭選擇、錦標(biāo)賽選擇、隨機(jī)競(jìng)爭(zhēng)等。

5）交換：交換（也叫雜交）操作是遺傳算法中最主要的遺傳操作。

6）變異：變異可以改善遺傳算法的局部搜索能力；維持群體的多樣性，防止出現(xiàn)早熟現(xiàn)象。

7）終止條件判斷有3種情況：給定一個(gè)最大的遺傳代數(shù)，算法迭代到最大遺傳代數(shù)時(shí)停止；給定問題一個(gè)下界的計(jì)算方法，當(dāng)進(jìn)化中達(dá)到要求的偏差時(shí)，算法終止；當(dāng)監(jiān)控得到的算法再進(jìn)化已無(wú)法改進(jìn)解的性能即適應(yīng)度無(wú)法再提高時(shí)，此時(shí)停止計(jì)算。

3 遺傳粒子群混合算法在曲線降階中的應(yīng)用

粒子群算法收斂速度快，但易陷入局部最優(yōu)；遺傳算法把握全局的能力好，但收斂速度慢，本文將遺傳算法融入到粒子群算法中，以充分利用各自的優(yōu)點(diǎn)，形成即收斂速度快、又能收斂到全局最優(yōu)的算法，并應(yīng)用于NURBS曲線降階中。由于遺傳算法運(yùn)算時(shí)間長(zhǎng)的主要原因是其編碼解碼操作，本文提出的算法拋棄編碼解碼，直接對(duì)pbest和gbest進(jìn)行交叉和變異。因?yàn)榱Ｗ邮峭ㄟ^跟蹤pbest和gbest來更新自身的速度和位置的，pbest和gbest一旦改變，粒子的速度和位置會(huì)跟著改變，而pbest和gbest的變化是通過遺傳操作來實(shí)現(xiàn)的，遺傳操作是一種導(dǎo)向式的操作，它能使pbest和gbest向有利于收斂的方向變化，從而使粒子的速度和位置也向著有利于收斂的方向進(jìn)行更新。

遺傳粒子群混合算法應(yīng)用于NURBS曲線降階時(shí)，把NURBS曲線的待求解（降階后的控制頂點(diǎn)、權(quán)因子向量以及帶點(diǎn)序列）看作是一個(gè)粒子，每個(gè)粒子的位置為待優(yōu)化問題中的一個(gè)潛在解。此混合算法將在遺傳算法的變異和粒子群算法中的學(xué)習(xí)因子中引入自適應(yīng)機(jī)制，在變異過程中引入自適應(yīng)的概念即發(fā)現(xiàn)算法有可能陷入了局部最優(yōu)時(shí)才進(jìn)行變異，而平時(shí)并不進(jìn)行變異，以節(jié)約運(yùn)算時(shí)間；在學(xué)習(xí)因子中引入自適應(yīng)是因?yàn)閷W(xué)習(xí)因子反映的是粒子的學(xué)習(xí)能力，學(xué)習(xí)因子大，粒子的學(xué)習(xí)能力就強(qiáng)，但在算法的早期粒子需要較強(qiáng)的學(xué)習(xí)因子以盡快找到全局最優(yōu)；而在算法后期，粒子的學(xué)習(xí)因子如果小一些，可以使粒子在全局最優(yōu)附近進(jìn)行精細(xì)搜索，從而得到盡可能精確的解。c1、c2的更新方式如下：

式中：MaxIter為最大迭代次數(shù)，Iter為當(dāng)前迭代次數(shù)。

算法的具體步驟如下。

1） 給出 pi，ωi和 Ti的可行解范圍，其中 pi為降階后的控制頂點(diǎn)分量，ωi為降階后的權(quán)因子，Ti為降階后的節(jié)點(diǎn)序列。為了保證端點(diǎn)的插值性，令：p0=p0，pn-m=pn。

2）確定粒子群算法的種群大小、慣性權(quán)重，學(xué)習(xí)因子，文中選取種群大小Popsize，慣性權(quán)重ω=0.675，學(xué)習(xí)因子 c1、c2根據(jù)方程（8）、（9）更新，最大迭代次數(shù)MaxIter為 1 000。

3）種群初始化：在解的可行域隨機(jī)確定400個(gè)（可能解）。

4）計(jì)算每個(gè)粒子的適應(yīng)度，適應(yīng)度函數(shù)取為：

▲圖1 四階降為三階的NURBS曲線與控制線

5）取適應(yīng)度高的直接進(jìn)入下一代，而適應(yīng)度低的另一部分進(jìn)入遺傳池進(jìn)行遺傳。遺傳直接對(duì)粒子的pbest進(jìn)行操作，以避免費(fèi)時(shí)的編碼解碼操作。

6）更新個(gè)體最好位置pbest和群體最好位置gbest。

7） 根據(jù)方程（6）、（7）對(duì)粒子的速度和位置進(jìn)行更新，學(xué)習(xí)因子 c1、c2則根據(jù)方程（8）、（9）進(jìn)行更新。

8）判斷種群是否達(dá)到最大進(jìn)化代數(shù)，如未達(dá)到，則轉(zhuǎn)向步驟3），否則給出最優(yōu)解和最優(yōu)目標(biāo)函數(shù)。

4 實(shí)驗(yàn)仿真

用MATLAB7.0編程實(shí)現(xiàn)此算法。為描述簡(jiǎn)單，只在平面內(nèi)畫二維圖像，即讓控制頂點(diǎn)第三坐標(biāo)軸取零。

設(shè)一條4次NURBS曲線，節(jié)點(diǎn)序列u=｛0，0，0，0，0.4，0.7，1，1，1，1｝,控制頂點(diǎn) p=｛（10，10，0），（41，88，0）， （84，115，0）， （178，9，0）， （231，30，0），（290，110，0）｝，權(quán)因子 ω=｛1，1，1，1，1，1｝。對(duì)此曲線分別用遺傳算法、粒子群算法和遺傳粒子群混合算法降一階所得控制頂點(diǎn)及權(quán)因子（見表1），所得曲線及相應(yīng)的控制頂點(diǎn)與原曲線和控制頂點(diǎn) （如圖1所示），圖中折線表示控制多邊形，曲線表示NURBS曲線，并對(duì)其中部分曲線進(jìn)行放大。從圖1可以看出，用遺傳粒子群混合算法降階后的曲線與原曲線基本重合，降階效果較遺傳算法、粒子群算法更好。

表1 NURBS曲線降階結(jié)果

5 總結(jié)

本文利用NURBS曲線的幾何性質(zhì)，并結(jié)合遺傳算法和粒子群算法，給出了NURBS曲線降階的一種新方法。利用粒子群算法收斂速度快、遺傳算法把握全局能力好的特點(diǎn)，將遺傳粒子群混合算法應(yīng)用于NURBS曲線的降階中。實(shí)驗(yàn)結(jié)果表明，本算法能在保留原曲線端點(diǎn)處幾何信息的前提下達(dá)到較好的逼近精度。本文的思想和方法可以方便地推廣到參數(shù)曲面上的降階逼近。

［1］ 劉彬.基于遺傳算法的NURBS曲線降階［J］.計(jì)算機(jī)工程，2008，34（14）:194-196.

［2］ 江明，羅予頻，楊士元.基于微粒群算法的有理Bezier曲線降階［J］.計(jì)算機(jī)應(yīng)用，2007，27（6）:1524-1527.

［3］ 程敏，王國(guó)瑾.基于顯示矩陣表示和多項(xiàng)式逼近論的NURBS 曲線降多階［J］.中國(guó)科學(xué)（E 輯），2003，33（8）:673-680.

［4］ 王國(guó)勛，王宛山，王軍，等.實(shí)時(shí)快速NURBS直接插補(bǔ)技術(shù)［J］.中國(guó)機(jī)械工程，2013，24（5）:617-622.

［5］ Les Piegl,Wayne Tiller著，趙罡，穆國(guó)旺，王拉柱譯.非均勻有理B樣條［M］.北京：清華大學(xué)出版社,2010.

［6］ A A A Esmin，G Lambert-Toores，A C Zambroni de Souza.A Hybrid Particle Swarm Optimization Applied to Loss Power Minimization ［J］.IEEE Transactions on Power Systems,2005,20（2）:859-866.

［7］ D I S Adi,S M B Shamsuddin，S Z M Hashim.NURBS Curve Approximation Using Particle Swarm Optimization［C］.2010 Seventh International Conference on Computer Graphics,Imaging and Visualization,Sydney,NSW,2010.

［8］ 康寶生，石茂，張景嶠.有理 Bezier曲線的降階［J］.軟件學(xué)報(bào)，2004，15（10）:1522-1527.