基于改進(jìn)PSO算法的B樣條曲線擬合*

李軒宇, 張兆軍, 許釗雄

(江蘇師范大學(xué) 電氣工程及自動化學(xué)院,江蘇 徐州 221116)

0 引 言

現(xiàn)代工程設(shè)計(jì)中經(jīng)常需要從測量的數(shù)據(jù)點(diǎn)中獲取最合適的曲線或曲面表達(dá),但這些數(shù)據(jù)點(diǎn)往往由于各種因素的影響存在誤差,所以待求的曲線或曲面不必嚴(yán)格地經(jīng)過每一個數(shù)據(jù)點(diǎn),可以用擬合的方法逼近數(shù)據(jù)點(diǎn)。由于B樣條曲線具有較好的逼近能力以及局部修改等優(yōu)秀的數(shù)學(xué)性質(zhì)[1],可以靈活表示各類曲線及曲面的形狀。因此,在測試數(shù)據(jù)處理、逆向工程和圖像處理[2,3]等工程領(lǐng)域中,B樣條曲線擬合技術(shù)得到了廣泛的應(yīng)用。

國內(nèi)外學(xué)者對于B樣條曲線擬合問題已經(jīng)做了大量的研究。Bo P等人[4]在充分考慮曲線形狀特征的基礎(chǔ)上提出一種基于圖形的平面相交B樣條曲線擬合方法。Deng C等人[5]使用漸進(jìn)迭代逼近的方法求解數(shù)據(jù)點(diǎn)數(shù)量較大的擬合問題,具有較好的保形效果。利用各種智能算法求解曲線擬合問題是一個新的研究方向。胡良臣等人[6]提出一種基于二進(jìn)制遺傳算法的B樣條曲線擬合方法,可以在滿足法向約束條件的同時生成誤差較小的擬合曲線。Uyar K等人[7]采用雜草優(yōu)化方法選擇最優(yōu)節(jié)點(diǎn)進(jìn)行B樣條曲線擬合,實(shí)驗(yàn)結(jié)果表明了較好的擬合效果。節(jié)點(diǎn)向量的選擇對于曲線的擬合效果具有重要影響,合適的節(jié)點(diǎn)向量可以減小曲線擬合誤差。粒子群優(yōu)化(particle swarm optimization,PSO)算法[8]在求解曲線擬合問題時存在早熟收斂,易于陷入局部最優(yōu)等缺點(diǎn)。

本文結(jié)合遺傳算法(GA)[9]和天牛須搜索(BAS)策略[10]對標(biāo)準(zhǔn)PSO算法進(jìn)行改進(jìn),提出一種基于GA-BAS策略的改進(jìn)粒子群優(yōu)化(genetic-beetle PSO，GBPSO)算法用于求解帶法向約束的3次B樣條曲線擬合問題。

1 問題描述

1.1 數(shù)學(xué)模型

一條p次B樣條曲線可以表示為

(1)

式中p為B樣條曲線次數(shù),本文取p=3；Pi為控制頂點(diǎn)；Ni,p(u)為p次B樣條在節(jié)點(diǎn)向量U上的基函數(shù),定義如下

(2)

p≥1

(3)

式中 規(guī)定0/0=0；ui,i=0,1,…,n+p+1為節(jié)點(diǎn)向量U{ui}中的元素,u的范圍一般取[0,1]。

給M+1定個數(shù)據(jù)點(diǎn)dk和法向約束條件lk,找到一條曲線C來逼近數(shù)據(jù)點(diǎn)dk的同時要滿足數(shù)據(jù)點(diǎn)處的法向約束條件lk。文獻(xiàn)[6]中將此類問題轉(zhuǎn)化為帶等式約束的最小化問題,即

式中tk為數(shù)據(jù)點(diǎn)dk所對應(yīng)的參數(shù)值；‖·‖為平方范數(shù)；C′(tk)為曲線在tk處的一階導(dǎo)數(shù)。

對于優(yōu)化模型式(4),利用罰函數(shù)方法將其轉(zhuǎn)換為無約束最優(yōu)化問題,建立適應(yīng)度函數(shù)如下

(5)

式(5)為本文最終所要優(yōu)化的適應(yīng)度函數(shù),并利用GBPSO算法對其進(jìn)行優(yōu)化求解。

1.2 數(shù)據(jù)點(diǎn)參數(shù)化方式

求解曲線擬合問題時首先要將數(shù)據(jù)點(diǎn)進(jìn)行參數(shù)化,不同的參數(shù)化方法會影響曲線最終的擬合效果。均勻參數(shù)化、向心參數(shù)化和弦長參數(shù)化是三種常用的參數(shù)化方法。本文中擬合曲線會面臨數(shù)據(jù)點(diǎn)急劇變化的情況,因此選擇向心參數(shù)化,該方法在處理此類問題時效果更好。參數(shù)tk與數(shù)據(jù)點(diǎn)dk的關(guān)系如下

(6)

2 算法介紹

2.1 PSO算法原理簡介

PSO算法首先初始化產(chǎn)生N個粒子,每個粒子代表優(yōu)化問題的一個潛在解。粒子i的速度和位置分別用d維向量vi和xi表示。粒子通過迭代更新自己的速度和位置,更新方式如下

(7)

(8)

2.2 BAS算法[10]簡介

BAS算法是一種新型智能優(yōu)化算法[10]。天牛在覓食過程中不知道食物的確切位置,僅依靠兩個觸須探測食物氣味并通過判斷左右須氣味濃度大小來決定下一步的走向。如果左須氣味強(qiáng)于右須,則向左移動,反之向右移動,直至找到食物。其數(shù)學(xué)模型如下：

1)隨機(jī)天牛的搜索方向并標(biāo)準(zhǔn)化

(9)

式中 rands(·)為隨機(jī)函數(shù)；n為空間維度。

2)計(jì)算左右須坐標(biāo)

(10)

式中xlt和xrt分別為天牛左右須在t時刻的位置；d0為兩須之間的距離。

3)根據(jù)兩須對應(yīng)的函數(shù)值,決定天牛下一步位置

(11)

式中δt為t時刻的步長；f為目標(biāo)函數(shù)；sign(·)為符號函數(shù)；f(xlt)>f(xrt)時取-1,反之為1。

BAS算法僅僅通過單一個體進(jìn)行尋優(yōu),具有較好的局部搜索能力,但也因此缺乏個體之間的信息交互,導(dǎo)致算法的全局搜索能力較弱。

2.3 GBPSO算法流程

由于標(biāo)準(zhǔn)PSO存在易于陷入局部最優(yōu)的缺點(diǎn),而BAS算法在局部搜索方面具有優(yōu)勢。本文首先結(jié)合兩種算法的優(yōu)點(diǎn),將BAS策略引入到PSO算法之中,提高單個粒子的尋優(yōu)能力幫助算法跳出局部最優(yōu),然后通過交叉和變異操作提高子代種群的多樣性,增強(qiáng)算法的全局搜索能力,基于此提出一種改進(jìn)的粒子群算法GBPSO。

GBPSO算法中,每個粒子都被當(dāng)成一個個的天牛進(jìn)行尋優(yōu)。與標(biāo)準(zhǔn)PSO相同的是,粒子的初始位置采用隨機(jī)初始化策略,速度使用式(7)進(jìn)行更新。不同之處在于,粒子的位置更新中結(jié)合了BAS策略,按式(12)更新

(12)

增量函數(shù)ξ的計(jì)算公式如下

(13)

式中δk為天牛在第k次迭代時的步長；Xld和Xrd為天牛的左右須坐標(biāo),其更新公式如下

(14)

步長δ隨著迭代衰減,本文初始步長設(shè)為1,δ和搜索距離s之間有如下關(guān)系

δk=eta·δk-1

(15)

sk=δk/T

(16)

常量eta和T的值根據(jù)經(jīng)驗(yàn)進(jìn)行調(diào)整,本文取eta=0.95,T=2。

本文選擇交叉方式為均勻交叉,交叉概率pc=0.5。變異方式選擇高斯變異,變異概率pm=0.05。

算法的具體步驟如下：

Step1 初始化種群和速度并設(shè)置相關(guān)參數(shù)。

Step2 計(jì)算每個粒子(天牛)的適應(yīng)度值。

Step3 對每個粒子,比較其當(dāng)前適應(yīng)度值和pbest的大小,如果當(dāng)前解更小,則更新pbest。

Step4 對每個粒子,比較其當(dāng)前適應(yīng)度值和gbest的大小,如果當(dāng)前解更好,更新gbest。

Step5 通過式(7)對粒子的速度進(jìn)行更新。

Step6 根據(jù)式(14)得到天牛左右須坐標(biāo),并計(jì)算左右須的適應(yīng)度值。

Step7 根據(jù)式(13)更新增量函數(shù)ξ,并結(jié)合式(12)更新粒子位置。

Step8 對子代個體進(jìn)行交叉和變異操作,經(jīng)過篩選得到更加優(yōu)秀的子代個體。

Step9 若滿足中止條件則退出算法,否則返回Step2。

2.4 基于GBPSO的B樣條曲線擬合算法

通過罰函數(shù)方法將帶法向約束的B樣條曲線擬合問題轉(zhuǎn)化為無約束最優(yōu)化問題。算法流程如圖1所示。

圖1 B樣條曲線擬合流程

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

3.1 擬合曲線選擇

本文選擇了4個不同類型的算例,其表達(dá)式以及定義域如表1所示。

表1 算例詳細(xì)信息

每個算例的取點(diǎn)間隔為0.05,則例1的取點(diǎn)個數(shù)為80,例2～例4的取點(diǎn)個數(shù)均為126。例4中參數(shù)a=1,b=1/2,h=1。

3.2 實(shí)驗(yàn)說明

本文選擇4個算例驗(yàn)證所提GBPSO算法的擬合效果,并通過與標(biāo)準(zhǔn)PSO[8]和另外兩種改進(jìn)PSO算法—結(jié)合BAS的PSO(beetle PSO，BSO)[11]、和結(jié)合GA的PSO(GAPSO)[12]對比來證明其有效性。每組實(shí)驗(yàn)在相同條件下獨(dú)立運(yùn)行20次,以適應(yīng)度值為擬合效果的評價標(biāo)準(zhǔn),統(tǒng)計(jì)20次實(shí)驗(yàn)結(jié)果的最大值、最小值、平均值和方差。

GBPSO算法與3種對比算法的參數(shù)設(shè)置見表2。表2中sizepop表示種群規(guī)模,maxgen表示算法的最大迭代次數(shù)。

表2 算法參數(shù)設(shè)置

3.3 實(shí)驗(yàn)結(jié)果與分析

圖2所示為GBPSO算法優(yōu)化節(jié)點(diǎn)向量的曲線擬合效果圖。由圖2可以看出,本文所提GBPSO算法對所有4個算例都具有較好的擬合效果。

圖2 4個算例的擬合效果圖

圖2(a)中曲線形狀較為簡單,GBPSO算法在處理此類問題時可以達(dá)到較好的效果。圖2(b)和圖(d)中曲線的數(shù)據(jù)點(diǎn)分布較為均勻,且圖2(d)存在曲線交叉的情況,可以看出GBPSO算法對解決此類問題也是可行的。圖2(c)中曲線不僅存在交叉的情況,而且在局部有著較為尖銳的變化。可以看出,GBPSO算法不僅在處理平滑曲線時有較好的效果,而且在面對曲線形狀急劇變化的復(fù)雜情況時,依然能夠得到理想的擬合曲線。擬合仿真實(shí)驗(yàn)結(jié)果表明,所提GBPSO算法在面對一般的情況時,不僅可以得到誤差較小的擬合曲線,且能夠滿足數(shù)據(jù)點(diǎn)處的法向約束條件。

為了進(jìn)一步說明本文改進(jìn)算法的有效性,GBPSO算法與三種對比算法對以上4個算例的數(shù)值實(shí)驗(yàn)結(jié)果見表3,加黑數(shù)值表示算法在相應(yīng)算例上的最優(yōu)結(jié)果。

表3 數(shù)值實(shí)驗(yàn)結(jié)果

由表3可以看出,對于所給的4個算例,本文所提GBPSO算法的優(yōu)化結(jié)果都要優(yōu)于標(biāo)準(zhǔn)PSO算法,同時在例2～例4三條曲線的表現(xiàn)上優(yōu)于BSO和GAPSO兩種算法。對于算例1,由圖3可以看出該曲線形狀較為簡單,因此,所提算法與GAPSO算法在尋優(yōu)結(jié)果上差別很小,都在同一數(shù)量級,而從最小值的統(tǒng)計(jì)結(jié)果來看,所提GBPSO算法有一定的能力找到比GAPSO更好的解。

4 結(jié) 論

本文基于遺傳算法和天牛須搜索策略提出了GBPSO算法用于求解數(shù)據(jù)點(diǎn)帶法向約束的B樣條曲線擬合問題。不同于標(biāo)準(zhǔn)PSO算法,GBPSO中通過BAS策略更新粒子位置,并結(jié)合GA中的交叉和變異操作保證子代種群的多樣性,增強(qiáng)算法的全局搜索能力。通過罰函數(shù)的方法將帶法向約束的B樣條曲線擬合問題轉(zhuǎn)換為無約束最優(yōu)化問題,然后利用GBPSO對節(jié)點(diǎn)向量的位置進(jìn)行優(yōu)化。實(shí)驗(yàn)結(jié)果表明,本文算法生成的擬合曲線不僅誤差較小,而且能夠滿足數(shù)據(jù)點(diǎn)處的法向約束條件。