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

□ 張 鑫 □ 南 余榮

浙江工業大學 信息工程學院 杭 州 3 10023

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

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

1 問題的提出

設：P1，P2， …，Pn為給定的 n 個控制頂點，ω1，ω2，…，ωn為相應控制頂點的權，U=｛u0≤…≤uk≤…≤un+1≤…≤uk+n｝為節點序列，由這些控制頂點、權和節點定義的 k 次（k+1 階）NURBS 曲線的參數方程為［4］：

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

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

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

要使降階后的曲線和原曲線逼近，就要使h的值盡量小。因為NURBS曲線受到控制頂點、權以及節點向量的影響，為了減少計算量，同時又保持曲線的端點不變，在降階時對降階后的NURBS曲線的節點向量稍作改動。如果是降一階，將降階前節點序列的第一個和最后一個點刪除作為降階后的節點序列，相應的曲線控制頂點也要比降階前少一個。因此，NURBS曲線降階問題的實質就是找出一組控制頂點、權以及節點向量，使由它們確定的NURBS曲線盡可能逼近原曲線。所以降階問題轉化為如下帶約束條件的優化問題：

式中：R為實數。

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

2.1 粒子群算法

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

式中：ω 為慣性權重；c1、c2為學習因子；rand （）、Rand（）為兩個在［0，1］范圍內獨立均勻分布的隨機數。

標準粒子群算法的算法流程如下：

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

2）計算每個粒子的適應值。

3）對于每個粒子，將其適應值與它所經歷過的最好位置pbest的適應值進行比較，如果較好，則將其位置作為它自身當前的最好位置pbest。

4）對于每個粒子，將其適應值與全體粒子所經歷的最好位置gbest的適應值進行比較，如果較好，則將其位置作為當前群體的最好位置gbest。

5） 根據方程（6）、（7）對每個粒子的速度和位置進行更新。

6）如果終止條件（通常為足夠的適應值或達到一個預先設置的最大代數Gmax）滿足則停止，否則轉到第二步。

2.2 遺傳算法

遺傳算法跟其它智能算法一樣，也是通過模擬自然進化過程來搜索最優解。它求解問題的基本方法是：從當前種群出發，待優化的目標函數解釋為生物種群對環境的適應性，生物個體對應優化變量，利用選擇、復制、雜交和變異操作來生成新的種群。重復這個過程，直到出現滿足要求的種群或者達到了規定的進化限制。

遺傳算法的主要運算過程［8］如下。

1）編碼：編碼的方法主要有二進制編碼、符號編碼和浮點數編碼3大類。

2）初始群體的生成。

3）適應度值評估監測：適應度函數表明個體或解的優劣性。

4）選擇：常用的方法有輪盤賭選擇、錦標賽選擇、隨機競爭等。

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

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

7）終止條件判斷有3種情況：給定一個最大的遺傳代數，算法迭代到最大遺傳代數時停止；給定問題一個下界的計算方法，當進化中達到要求的偏差時，算法終止；當監控得到的算法再進化已無法改進解的性能即適應度無法再提高時，此時停止計算。

3 遺傳粒子群混合算法在曲線降階中的應用

粒子群算法收斂速度快，但易陷入局部最優；遺傳算法把握全局的能力好，但收斂速度慢，本文將遺傳算法融入到粒子群算法中，以充分利用各自的優點，形成即收斂速度快、又能收斂到全局最優的算法，并應用于NURBS曲線降階中。由于遺傳算法運算時間長的主要原因是其編碼解碼操作，本文提出的算法拋棄編碼解碼，直接對pbest和gbest進行交叉和變異。因為粒子是通過跟蹤pbest和gbest來更新自身的速度和位置的，pbest和gbest一旦改變，粒子的速度和位置會跟著改變，而pbest和gbest的變化是通過遺傳操作來實現的，遺傳操作是一種導向式的操作，它能使pbest和gbest向有利于收斂的方向變化，從而使粒子的速度和位置也向著有利于收斂的方向進行更新。

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

式中：MaxIter為最大迭代次數，Iter為當前迭代次數。

算法的具體步驟如下。

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

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

3）種群初始化：在解的可行域隨機確定400個（可能解）。

4）計算每個粒子的適應度，適應度函數取為：

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

5）取適應度高的直接進入下一代，而適應度低的另一部分進入遺傳池進行遺傳。遺傳直接對粒子的pbest進行操作，以避免費時的編碼解碼操作。

6）更新個體最好位置pbest和群體最好位置gbest。

7） 根據方程（6）、（7）對粒子的速度和位置進行更新，學習因子 c1、c2則根據方程（8）、（9）進行更新。

8）判斷種群是否達到最大進化代數，如未達到，則轉向步驟3），否則給出最優解和最優目標函數。

4 實驗仿真

用MATLAB7.0編程實現此算法。為描述簡單，只在平面內畫二維圖像，即讓控制頂點第三坐標軸取零。

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

表1 NURBS曲線降階結果

5 總結

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

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

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

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

［4］ 王國勛，王宛山，王軍，等.實時快速NURBS直接插補技術［J］.中國機械工程，2013，24（5）:617-622.

［5］ Les Piegl,Wayne Tiller著，趙罡，穆國旺，王拉柱譯.非均勻有理B樣條［M］.北京：清華大學出版社,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］.軟件學報，2004，15（10）:1522-1527.