混沌螞蟻群優化求解自由節點B樣條曲線擬合

徐善健，郭有強，戚曉明，夏偉

蚌埠學院計算機科學與技術系，安徽蚌埠 233000

混沌螞蟻群優化求解自由節點B樣條曲線擬合

徐善健，郭有強，戚曉明，夏偉

蚌埠學院計算機科學與技術系，安徽蚌埠 233000

B樣條曲線擬合問題中，將節點作為自由變量可大幅提高擬合精度，但這就使曲線擬合問題轉化為求解困難的連續多峰值、多變量非線性優化問題，當待擬合的曲線是不連續、有尖點情況，就更為困難。針對這一問題，基于混沌螞蟻群優化算法CASO，提出了一種新的B樣條曲線擬合算法CASO-DF。該算法結合B樣條曲線擬合原理，通過蟻群中螞蟻個體的混沌行為，調整自由節點位置，通過蟻群的自組織行為自適應地調整內部節點數目，解決了B樣條曲線擬合問題。仿真結果表明了CASO-DF算法能夠有效實現自由節點B樣條曲線擬合，且性能優于其他同類算法。

曲線擬合；混沌螞蟻群優化算法；節點放置；B樣條

1 引言

在測試數據處理、逆向工程和圖像處理等工程領域中，B樣條曲線擬合技術應用較為廣泛[1-2]。B樣條曲線擬合問題是指：給定一組有序數據點，尋找一條B樣條曲線通過或逼近這些數據點。B樣條具有較好的逼近能力和強大的數學性質（局部修改，投影不變性等），可以非常靈活地表示種類繁多的形狀。合適地產生B樣條參數是獲最優近似解的前提條件，特別是節點數目和位置選擇對數據擬合精度有很大影響。

B樣條曲線擬合問題已經引起眾多學者關注，國內外的研究都取得了一定的進展。國內學者周明華、汪國昭[3]提出了基于遺傳算法的B樣條曲線，并解決了Bézier曲線擬合，表現較好的性能。郭改文、黃卡瑪[4]提出一種模擬自然樹生長的競爭優化算法，并將其應用在曲線擬合中。通過與遺傳算法和經典最小二乘法對比兩條經典的函數曲線擬合的結果，顯示其算法的有效性。國外一些學者，采用固定節點數[5-7]，將B樣條最小二乘擬合轉化為簡單的線性優化，擬合精度較低。Satoshi M等[8]提出一種新思想，采用自由節點（Free knot）代替固定節點，樣條曲線的平滑程度由節點位置和節點的多樣性來靈活調整。這種靈活性能抓住待擬合曲線的結構變化和適應分段曲線。因此，自由節點樣條對非平滑數據擬合時，可以大幅度提高樣條函數逼近程度，減少擬合誤差。處理方法是：采用一定數量的自由節點，在迭代中修改自由節點數量，使之滿足預定的誤差界限[9]。該方法通常需要主觀決策參數[10-11]（如誤差容忍、平滑因子、代價函數和節點的初始位置），不能自動產生較好的節點向量，很難得到平滑的曲線。Lindstrom[12]進一步提出了克服主觀決策的弱點，但其方法不適用于不連續、有尖點的擬合曲線。另一方面，從自由節點位置出發，Li 等[13]提出一個自適應節點放置（knot placement）方法，能夠有效地自動選擇合適的節點位置，但其僅適用于可微函數，并且很大程度上依賴于特征點（如曲率極值點和拐點）的信息，但有時很難獲得這些信息。一個非常有希望的研究路線是基于元啟發式算法放置節點。Yoshimoto等[14]將連續非線性、多變量優化問題轉化為離散的組合優化問題，通過遺傳算法解決。ülker等[15]采用人工免疫算法代替遺傳算法，得到較好結果。Zhao 等[16]采用隨機優化方法逼近，通過高斯混合分布和聚類技術分布式評估獲得節點，但該算法局限于封閉曲線。

綜上所述，將B樣條的節點作為自由變量，數據擬合精度會大幅度提高[17]，但是亟需克服以下困難：（1）采用自由節點時，B樣條不是線性，而是線性與非線性參數的混合，形成較難的非線性最小二乘優化問題；（2）采用自由節點受最優節點位置解析式難以表達和最小二乘目標函數存在多局部最優等問題困擾；（3）采用自由節點向量包含節點數量和位置選取，若選取不當，可能導致繪制曲線不光滑，特別是不連續、帶尖點的曲線。

為此，本文提出CASO-DF（Chaotic Ant Swarm Optimization for Data Fitting）算法，自適應地解決自由節點數量和位置選取問題。CASO-DF算法借助混沌螞蟻群優化算法CASO[18]的非線性搜索能力，根據給定的數據特點自動產生多個自由節點、克服不連續和尖點帶來的困難。實驗結果表明提出的CASO-DF非常有效，不僅可以計算出最佳內部節點（Internal knot）數，而且可以得到最佳內部節點數目的最優擬合。

2 B樣條數據擬合

k次B樣條曲線B(t)可表示為[5-6]：

式中pi為控制點（Control point），i=1，2，…，n；Ni，k(t)為k次B樣條在節點向量u={u0，u1，…，un+k}上的基函數，節點向量是區間[a，b]上的非減實數值節點。節點向量u的第一個和最后一個節點的重復度為k：u0=…=uk-1=a，un+1=…=un+k=b。不失一般性，假設[a，b]=[0，1]。Ni，k(t)是Cox-de Boor的遞歸函數[15]：

式中k=1，i=0，1，…，n+k-1。

式中k＞1，i=0，1，…，n。式（3）中，節點存在分子、分母，表明B(t)是節點的非線性函數。

不失一般性，假設待擬合的數據可以寫成：

其中F(t)為數據的未知函數；εj為測量誤差。式（4）運用最小二乘法，通過殘差的平方之和Q決定B樣條曲線B(t)的控制節點pj(j=0，1，…，n)：

顯然，目標函數Q依賴于B樣條基函數和控制點。這樣，求Q的過程就是解決連續的多峰值非線性最小化問題。

根據上述解釋，目標函數式（5）和它的變量是B樣條系數和內部節點。B樣條系數是線性參數，而內部節點是非線性參數。顯然這個最小化問題是一多峰值的最優化問題。

3 混沌螞蟻群優化算法

混沌螞蟻群優化算法（Chaotic Ant Swarm Optimization，CASO）基本原理源于螞蟻個體的確定性混沌行為和蟻群的周期性自組織行為。CASO算法受螞蟻混沌行為啟發，基于動力學和最優值理論而設計。CASO是一種全局搜索算法，在求解函數優化[19]、參數識別[20]、聚類[21]等問題表現出較好的性能。CASO算法搜索范圍與問題的搜索空間一致。設蟻群由M只螞蟻組成，搜索空間RD是D-維實數連續空間。在螞蟻的搜索空間S中，求函數f:S→R的最小值。因此，空間S中的每個點都是一個合法解。螞蟻m的位置表示一個變量zm=(zm1，zm2，…，zmD)，m=1，2，…，M。CASO算法數學模型為[18]：

式中τ為當前迭代，(τ-1)為上一次迭代；ym(τ)為螞蟻m當前迭代的組織變量，其初始值通常為ym(0)=0.999；rm為螞蟻m的組織因子，它影響CASO的收斂速度。因為需要螞蟻個體隨時間演化有小的差異，所以選擇rm值范圍為0≤rm≤0.5，如rm=0.01+0.2×rand(1)；zmd(τ)是螞蟻m第d維，d=1，2，…，D；qmd(τ-1)為螞蟻m及其鄰居在(τ-1)次迭代內發現的最優位置；a為較大的正數，可取a=200；b為常數0≤b≤2/3。ψd決定了變量的第d維的搜索區間[0，ψd]。文獻[18]完整地討論了式（6）中的參數與優化效果的關系。

在CASO算法中，螞蟻鄰居被定義為：在搜索空間中某螞蟻周圍一定距離內的有限只螞蟻。文獻[18]以歐氏距離作為判定鄰居的依據。在搜索空間中，兩只螞蟻的位置分別為(zm1，zm2，…，zmD)和(zl1，zl2，…，zlD)，那么，這兩只螞蟻之間的距離為：

其中，m≠l，m，l=1，2，…，M。

為便于理解CASO-DF算法，圖1給出混沌螞蟻群優化算法CASO算法的流程圖。由圖1可以看出，CASO算法步驟：

（1）設置蟻群規模為N、迭代次數τ、每只螞蟻的組織因子ri和位置xi。

（2）計算每只螞蟻的當前目標函數值f(xi)，即適應值。

（3）計算每只螞蟻及其鄰居的最優位置pi。

（4）采用式（6）更新每只螞蟻的組織變量yi和位置xi。

（5）判斷是否滿足終止條件，若滿足，則退出；否則，轉到步驟（2）。

圖1 CASO算法流程圖

4 基于CASO的數據擬合算法

根據第2章式（4），待擬合數據的未知函數可以用B樣條曲線逼近。由混沌螞蟻群優化算法CASO的特點，它是一種群體協同求解算法，在算法求解過程中，混沌個體的探索能力和群體的自組織能力相互結合，可以逼近任意的非線性函數[20]。于是，采用全局混沌螞蟻群優化算法自動搜索決定最好的內部節點（Internal knot）{uk，uk+1，…，un}。下面基于CASO，提出B樣條數據擬合獲得最優節點向量的方法。

4.1 方案描述

設內部節點數為L，L=[λN]，其中0≤λ＜0.5，λ稱為內部節點率，N是待擬合的節點數，0表示沒有內部節點，0.5表示內部節點數是N的一半。因此，L是可變參數，采用CASO進行數據擬合時，不同螞蟻處理的內部節點數不一定相同，也就是說，L對不同的螞蟻維數不同。于是，假設螞蟻m的維數L，每一維表示一個內部節點的實數值。圖2給出一個編碼實例。

圖2 螞蟻編碼表示

圖2中，每只螞蟻的初始維數在L內隨機產生，在混沌演化過程中，螞蟻的維數可以根據鄰居螞蟻的適應值，調整其維數。螞蟻的一個“空位”表示此維不需要，即內部節點數少1。

螞蟻每維數值zmd(τ)有其混沌行為產生，根據螞蟻的自組織行為更新其編碼信息。終止條件為固定迭代次數Iter，經過多步迭代，每只螞蟻逐步收斂到最優值。

4.2 適應函數

采用三個不同的適應函數。第一個是殘差之和Q，如式（5）所示，這種計算方法比較簡單：僅需計算誤差，不考慮計算模型的復雜度。因此，獲得最好的誤差需要犧牲大量的變量。考慮這個問題，采用其他兩個適應函數，A IC（Akaike Information Criterion）[22]和BIC （Bayesian Information Criterion）[23]。這兩個是懲罰信息論標準，通過簡單地平衡精度，發現最優逼近模型，它們包括兩項，第一項是模型函數的精度，第二項是最小化式中的自由參數數目的懲罰。AIC和BIC的表達式如下：

其中N是待擬合數據點數；Q由式（5）計算得到。由式（8）（9）可得，兩個表達式很相似，但BIC較AIC應用了大量的懲罰。然而，不同點是對不連續、有尖點的函數，AIC可能產生不必要的冗余節點，因此，BIC更適用于自由節點數據擬合問題。

AIC和BIC的優勢在于它們不需要主觀參數，如誤差邊界、平滑因子。同時它們提供了一個簡單和直觀的過程決定最好的模型，AIC和BIC的值越小，適應值越好。于是可用它們選擇最好的計算結果。

4.3 CASO-DF算法

由4.1節和4.2節，可得CASO-DF算法的偽代碼。

算法1 CASO-DF算法的偽代碼

輸入：B樣條次數k和待擬合的有序數據序列

5 實驗結果及分析

5.1 仿真環境

為清楚展現CASO-DF算法的性能，采用文獻[14]中的3個函數作為本文的測試函數，如表1。表1給出了函數的表達式和定義域。圖3給出了三個函數的圖像，顯示三個測試函數的特性。選擇這些函數的原因：首先，檢驗算法適用多樣性；其次，其他B樣條數據擬合算法常采用這些函數。函數包括連續平滑、不連續、有尖點三種類型。每個函數采樣201個數據點，n-k為內部節點數。這些點按照正弦函數g(t)=e2tsin(20t)的均勻隨機采樣U(0，1)。同時為了檢驗提出方法的魯棒性，對數據增加白噪音ξ，ξ符合正態分布N(0，σ2)，平均值為0，方差為σ2，三個函數的標準差為σ=0.1。

f1(t)是一個除t=0.4之外都是連續光滑的，在t=0.4時，函數發生階躍的函數。f2(t)是一個富有挑戰性的函數，在t=0.6處非連續，且此點兩側函數增減性不同。f3(t)在t=0.5時有尖點，是一種比較好的、適用于評價CASO-DF的函數。

仿真實驗的硬件環境是CPU Intel Core 2 Duo 2.4 GHz，內存2 GB，軟件環境是W indow s XP，以M atlab 7.0作為實驗工具。CASO-DF算法最大進化代數為200，蟻群規模為20。其他相關參數按式的要求設置。

5.2 仿真結果及分析

表1 測試函數

為驗證CAS-DF算法的性能，對f1(t)、f2(t)、f3(t)適應值與內部節點數之間的關系以及它們隨迭代次數增加的演化收斂趨勢進行仿真和分析。在仿真圖中，‘x’點是根據仿真函數加入白噪音ξ后生成。

圖4的（a）（b）（c）分別給出了f1(t)的AIC、BIC適應值變化與內部節點數之間的變化趨勢，BIC適應值和內部節點數隨迭代次數的演化情況以及f1(t)的4階B樣條曲線擬合的最好仿真結果。

圖5的（a）（b）（c）分別給出了f2(t)的AIC、BIC適應值與內部節點數之間的演化趨勢，BIC適應值和節點數隨迭代次數的變化情況以及f2(t)的4階B樣條曲線擬合的最好仿真結果。

圖6的（a）（b）（c）分別給出了f3(t)的AIC、BIC適應值與內部節點數之間的演化趨勢，BIC適應值和節點數隨迭代次數的變化情況以及f3(t)的4階B樣條曲線擬合的最好仿真結果。

由圖4～6中可以看出，CASO-DF算法都能產生較好的B樣條曲線。圖4～6中的（a）顯示當內部節點數量少時，AIC和BIC相對較大。AIC和BIC隨內部節點數增加而減小，直至達到最小值，之后它隨內部節點數增加而增大，表明了f1(t)、f2(t)、f3(t)三個函數的最優內部節點數分別為4、8、5。圖4～6中的（b）表明了BIC和內部節點數隨迭代次數演化的收斂性。以三個函數的最優內部節點數，分別繪出圖4～6中的（c）4階B樣條擬合曲線。

圖3 （a）f1(t)的函數圖像

圖3 （b）f2(t)的函數圖像

圖3 （c）f3(t)的函數圖像

具體看，圖4（c）f1(t)的結果與文獻[14]一致，表明CASO-DF算法擬合效果較好。圖5（a）表明f2(t)的適應值AIC、BIC有相同的特征，都隨內部節點數從1到7增加而急劇減少，內部節點數為8時有最小值。隨內部節點數增加，適應值AIC、BIC緩慢增大。圖6（a）中，內部節點數從1到4，f3(t)的適應值AIC、BIC急劇下降，最好的內部節點數為5。隨內部節點數增加，適應值AIC、BIC緩慢增大。圖4～6（c）表明了CASO-DF算法能夠對連續、非連續、有尖點函數進行數據擬合。為體現圖4～6（c）中CASO-DF算法自動放置能力，表2給出三個函數的內部節點數目及放置的橫坐標。

由圖4（c）、圖5（c）、圖6（c）和表2可以看出，CASO-DF算法不僅能夠獲得三種函數的較好的數據擬合結果，而且能夠得到最優內部節點的位置，其原因在于CASO-DF算法的混沌行為可以搜索到內部節點的位置，而自組織行為可使蟻群選取到最少內部節點數目。

圖4 （a）函數f1(t)的AIC、BIC適應值與內部節點數之間的關系

圖4 （b）函數f1(t)的BIC適應值和內部節點數隨迭代次數演化過程

圖4 （c）函數f1(t)的4階B樣條曲線擬合結果

圖5 （a）函數f2(t)的AIC、BIC適應值與內部節點數之間的關系

圖5 （b）函數f2(t)的BIC適應值和內部節點數隨迭代次數演化過程

圖5 （c）函數f2(t)的4階B樣條曲線擬合結果

圖6 （a）函數f3(t)的AIC、BIC適應值與內部節點數之間的關系

圖6 （b）函數f3(t)的BIC適應值和內部節點數隨迭代次數演化過程

圖6 （c）函數f3(t)的4階B樣條曲線擬合結果

表2f1(x)、f2(x)、f3(x)最優內部節點數及位置

5.3 與其他算法的比較

為了評估所提出的CASO-DF算法的節點自動放置能力，將該算法與演化相關算法[14-16，24-25]進行比較。Yoshimoto等[14]將數據擬合作為基于遺傳算法的離散組合優化問題。ülker等[15]采用人工免疫算法處理數據擬合問題。Yoshimoto等[24]采用自適應實數編碼的遺傳算法。Sarfraz等[25]采用基于遺傳算法和探測技術解決數據擬合問題。Zhao等[16]將高斯混合模型和k-均值方法結合，解決數據擬合問題。采用5.1節給出的測試函數，以M atlab7.0作為仿真工具，將CASO-DF算法與這些算法比較分析，相關算法的參數設置參考相關文獻。表3考慮它們的迭代次數、計算時間等因素，給出了比較結果。“—”表示不存在。

表3 CASO-DF與相關算法的比較

從表3可以看出，CASO-DF算法較其他算法優秀，適用于多種類型的函數，特別是計算速度快。究其原因是，CASO算法是基于螞蟻個體的混沌行為和整個蟻群的自組織行為設計，螞蟻個體的混沌行為探索能力較強，對內部節點的位置搜索有較大幫助，而自組織行為能夠較好協調個體之間的最優位置，加快了蟻群的搜索能力。因而CASO-DF算法的節點自動放置能力強于其他算法。

由5.2節和5.3節的仿真實驗可以看出，基于CASO算法設計的CASO-DF算法，有較好的性能，在計算精度和計算時間上優于其他相關算法。

6 結束語

本文結合新型混沌螞蟻群算法，提出了基于混沌螞蟻群算法的B樣條曲線擬合算法CASO-DF，該算法將節點作為自由變量，把B樣條曲線擬合轉化為連續多峰值非線性優化問題，應用CASO自動計算最優內部節點數，實現自由節點數目和位置自動選擇。文中給出了混沌螞蟻群算法解決曲線擬合問題的具體方法及步驟。仿真結果表明了CASO-DF在計算精度和計算速度方面優于相關算法。下一步的研究是將CASO-DF算法應用于圖像邊緣檢測。

[1]PARK H.An error-bounded approximate method for representing planar curves in B-splines[J].Computer-Aided Geometric Design，2004，21（5）：479-497.

[2]Li W，Xua S，Zhao G.Adaptive knot placement in B-spline curve approximation[J].Computer-Aided Design，2005，37（8）：791-797.

[3]周明華，汪國昭.基于遺傳算法的B樣條曲線和Bézier曲線的最小二乘擬合[J].計算機研究與發展，2005，42（1）：134-143.

[4]郭改文，黃卡瑪.模擬自然樹生長的競爭算法及在曲線擬合中的應用[J].電子學報，2008，36（9）：1839-1842.

[5]Jing L，Sun L.Fitting B-spline curves by least squares support vector machines[C]//Proc of the 2nd Int Conf on Neural Networks&Brain.[S.l.]：IEEE Press，2005：905-909.

[6]Park H，Lee J H.B-spline curve fitting based on adaptive curve refinement using dominant points[J].Computer-Aided Design，2007，39：439-451.

[7]Wang W P，Pottmann H，Liu Y.Fitting B-spline curves to point clouds by curvature-based squared distance minimization[J].ACM Transactions on Graphics，2006，25（2）：214-238.

[8]Burchard H G.Splines（with optimal knots）are better[J]. Applicable Analysis，1974，3：309-319.

[9]Lyche T，Morken K.A data-reduction strategy for splines with applications to the approximation of functions and data[J].IMA Journal of Numerical Analysis，1988，8：185-208.

[10]A lhanaty M，Bercovier M.Curve and surface fitting and design by optimal control methods[J].Computer-Aided Design，2001，33：167-182.

[11]Goldenthal R，Bercovier M.Spline curve approximation and design by optimal control over the knots[J].Computing，2004，72：53-64.

[12]Lindstrom M J.Penalized estimation of free-knot splines[J]. Journal of Computational and Graphical Statistics，1999，8（2）：333-352.

[13]Li W，Xu S，Zhao G，et al.Adaptive knot placement in B-spline curve approximation[J].Computer-Aided Design，2005，37：791-797.

[14]Yoshimoto F，moriyama M，harada T.Automatic knot placement by a genetic algorithm for data fitting with a spline[C]//Proceedings of the International Conference on Shape Modeling and Applications.[S.l.]：IEEE Computer Society Press，1999：162-169.

[15]üLker E，Arslan A.Automatic knot adjustment using an artificial immune system for B-spline curve approximation[J].Information Sciences，2009，179：1483-1494.

[16]Zhao X，Zhang C，Yang B，et al.Adaptive knot placement using a GMM-based continuous optimization algorithm in B-spline curve approximation[J].Computer-Aided Design，2011，43：598-604.

[17]Molinari N，Durand J F，Sabatier R.Bounded optimal knots for regression splines[J].Computational Statistics&Data Analysis，2004，45（2）：159-178.

[18]Li L，Peng H，Wang X，et al.An optimization method inspired by chaotic ant behavior[J].International Journal of Bifurcation and Chaos，2006，16（8）：2351-2364.

[19]Ge F，Wei Z，Lu Y，et al.Disturbance chaotic ant swarm[J]. International Journal of Bifurcation and Chaos，2011，21 （9）：2597-2622.

[20]Peng H，Li L，Yang Y，et al.Parameter estimation of dynamical systems via chaotic ant swarm[J].Physical Review E，2010，81（1）.

[21]Wan M，Li L，Xiao J，et al.CAS based clustering algorithm for web users[J].Nonlinear Dynamics，2010，61：347-361.

[22]Akaike H.A new look at the statistical model identification[J].IEEE Transactions on Automatic Control，1974，19（6）：716-723.

[23]Schwarz G E.Estimating the dimension of a model[J]. Annals of Statistics，1978，6（2）：461-464.

[24]Yoshimoto F，Harada T，Yoshimoto Y.Data fitting with a spline using a real coded algorithm[J].Computer-Aided Design，2003，35：751-760.

[25]Sarfraz M，Raza S A.Capturing outline of fonts using genetic algorithms and splines[C]//Proc of Fifth International Conference on Information Visualization IV’2001.[S.l.]：IEEE Computer Society Press，2001：738-743.

XU Shanjian,GUO Youqiang,QI Xiaoming,XIA Wei

Department of Computer Science and Technology,Bengbu College,Bengbu,Anhui 233000,China

Data fitting through B-splines improves the accuracy of the solution dramatically if the knots are treated as free variables.However,in this case the problem becomes a very difficult continuous multimodal and multivariate nonlinear optimization problem,especially the unknown functions are discontinuous and cusps.To this end,a Chaotic Ant Swarm Optimization（CASO）based curve fitting with B-splines,called CASO-DF,is proposed to implement the smoothness fitting quickly.The approach is devised based on the curve fitting with B-splines using chaotic coordination of a single ant and self-organizing capacity of the whole ant colony.CASO-DF can adaptively adjust knots placement and choose the number of internal knots.Simulation results show that the proposed approach can perform effectively as well as efficiently,and this algorithm has better performance than other similar algorithms.

curve fitting;chaotic ant swarm optimization;knot placement;B-splines

A

TP18

10.3778/j.issn.1002-8331.1209-0312

XU Shanjian,GUO Youqiang,QI Xiaoming,et al.Chaotic ant swarm optimization in solving cu rve fitting with free knot B-sp lines.Computer Engineering and Applications,2014,50（16）：177-182.

安徽省自然科學基金（No.11040606M 151）。

徐善健（1973—），男，講師，研究領域為數字信息處理，信息檢索；郭有強（1966—），男，教授，碩士生導師，研究方向為網絡信息處理、智能控制和優化算法；戚曉明（1975—），男，博士，副教授，研究方向為數字信息處理，信息檢索；夏偉（1973—），男，博士，講師，研究方向為形式化技術及應用，混雜系統理論及控制。E-mail：xiawei_0987@163.com

2012-09-26

2013-01-21

1002-8331（2014）16-0177-06

CNKI網絡優先出版：2013-02-28,http://www.cnki.net/kcms/detail/11.2127.TP.20130228.1148.005.htm l