混沌螞蟻群優(yōu)化求解自由節(jié)點(diǎn)B樣條曲線擬合

徐善健，郭有強(qiáng)，戚曉明，夏偉

蚌埠學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系，安徽蚌埠 233000

混沌螞蟻群優(yōu)化求解自由節(jié)點(diǎn)B樣條曲線擬合

徐善健，郭有強(qiáng)，戚曉明，夏偉

蚌埠學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系，安徽蚌埠 233000

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

曲線擬合；混沌螞蟻群優(yōu)化算法；節(jié)點(diǎn)放置；B樣條

1 引言

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

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

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

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

2 B樣條數(shù)據(jù)擬合

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

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

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

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

不失一般性，假設(shè)待擬合的數(shù)據(jù)可以寫成：

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

顯然，目標(biāo)函數(shù)Q依賴于B樣條基函數(shù)和控制點(diǎn)。這樣，求Q的過程就是解決連續(xù)的多峰值非線性最小化問題。

根據(jù)上述解釋，目標(biāo)函數(shù)式（5）和它的變量是B樣條系數(shù)和內(nèi)部節(jié)點(diǎn)。B樣條系數(shù)是線性參數(shù)，而內(nèi)部節(jié)點(diǎn)是非線性參數(shù)。顯然這個(gè)最小化問題是一多峰值的最優(yōu)化問題。

3 混沌螞蟻群優(yōu)化算法

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

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

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

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

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

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

（2）計(jì)算每只螞蟻的當(dāng)前目標(biāo)函數(shù)值f(xi)，即適應(yīng)值。

（3）計(jì)算每只螞蟻及其鄰居的最優(yōu)位置pi。

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

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

圖1 CASO算法流程圖

4 基于CASO的數(shù)據(jù)擬合算法

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

4.1 方案描述

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

圖2 螞蟻編碼表示

圖2中，每只螞蟻的初始維數(shù)在L內(nèi)隨機(jī)產(chǎn)生，在混沌演化過程中，螞蟻的維數(shù)可以根據(jù)鄰居螞蟻的適應(yīng)值，調(diào)整其維數(shù)。螞蟻的一個(gè)“空位”表示此維不需要，即內(nèi)部節(jié)點(diǎn)數(shù)少1。

螞蟻每維數(shù)值z(mì)md(τ)有其混沌行為產(chǎn)生，根據(jù)螞蟻的自組織行為更新其編碼信息。終止條件為固定迭代次數(shù)Iter，經(jīng)過多步迭代，每只螞蟻逐步收斂到最優(yōu)值。

4.2 適應(yīng)函數(shù)

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

其中N是待擬合數(shù)據(jù)點(diǎn)數(shù)；Q由式（5）計(jì)算得到。由式（8）（9）可得，兩個(gè)表達(dá)式很相似，但BIC較AIC應(yīng)用了大量的懲罰。然而，不同點(diǎn)是對(duì)不連續(xù)、有尖點(diǎn)的函數(shù)，AIC可能產(chǎn)生不必要的冗余節(jié)點(diǎn)，因此，BIC更適用于自由節(jié)點(diǎn)數(shù)據(jù)擬合問題。

AIC和BIC的優(yōu)勢(shì)在于它們不需要主觀參數(shù)，如誤差邊界、平滑因子。同時(shí)它們提供了一個(gè)簡(jiǎn)單和直觀的過程決定最好的模型，AIC和BIC的值越小，適應(yīng)值越好。于是可用它們選擇最好的計(jì)算結(jié)果。

4.3 CASO-DF算法

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

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

輸入：B樣條次數(shù)k和待擬合的有序數(shù)據(jù)序列

5 實(shí)驗(yàn)結(jié)果及分析

5.1 仿真環(huán)境

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

f1(t)是一個(gè)除t=0.4之外都是連續(xù)光滑的，在t=0.4時(shí)，函數(shù)發(fā)生階躍的函數(shù)。f2(t)是一個(gè)富有挑戰(zhàn)性的函數(shù)，在t=0.6處非連續(xù)，且此點(diǎn)兩側(cè)函數(shù)增減性不同。f3(t)在t=0.5時(shí)有尖點(diǎn)，是一種比較好的、適用于評(píng)價(jià)CASO-DF的函數(shù)。

仿真實(shí)驗(yàn)的硬件環(huán)境是CPU Intel Core 2 Duo 2.4 GHz，內(nèi)存2 GB，軟件環(huán)境是W indow s XP，以M atlab 7.0作為實(shí)驗(yàn)工具。CASO-DF算法最大進(jìn)化代數(shù)為200，蟻群規(guī)模為20。其他相關(guān)參數(shù)按式的要求設(shè)置。

5.2 仿真結(jié)果及分析

表1 測(cè)試函數(shù)

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

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

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

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

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

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

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

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

具體看，圖4（c）f1(t)的結(jié)果與文獻(xiàn)[14]一致，表明CASO-DF算法擬合效果較好。圖5（a）表明f2(t)的適應(yīng)值A(chǔ)IC、BIC有相同的特征，都隨內(nèi)部節(jié)點(diǎn)數(shù)從1到7增加而急劇減少，內(nèi)部節(jié)點(diǎn)數(shù)為8時(shí)有最小值。隨內(nèi)部節(jié)點(diǎn)數(shù)增加，適應(yīng)值A(chǔ)IC、BIC緩慢增大。圖6（a）中，內(nèi)部節(jié)點(diǎn)數(shù)從1到4，f3(t)的適應(yīng)值A(chǔ)IC、BIC急劇下降，最好的內(nèi)部節(jié)點(diǎn)數(shù)為5。隨內(nèi)部節(jié)點(diǎn)數(shù)增加，適應(yīng)值A(chǔ)IC、BIC緩慢增大。圖4～6（c）表明了CASO-DF算法能夠?qū)B續(xù)、非連續(xù)、有尖點(diǎn)函數(shù)進(jìn)行數(shù)據(jù)擬合。為體現(xiàn)圖4～6（c）中CASO-DF算法自動(dòng)放置能力，表2給出三個(gè)函數(shù)的內(nèi)部節(jié)點(diǎn)數(shù)目及放置的橫坐標(biāo)。

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

圖4 （a）函數(shù)f1(t)的AIC、BIC適應(yīng)值與內(nèi)部節(jié)點(diǎn)數(shù)之間的關(guān)系

圖4 （b）函數(shù)f1(t)的BIC適應(yīng)值和內(nèi)部節(jié)點(diǎn)數(shù)隨迭代次數(shù)演化過程

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

圖5 （a）函數(shù)f2(t)的AIC、BIC適應(yīng)值與內(nèi)部節(jié)點(diǎn)數(shù)之間的關(guān)系

圖5 （b）函數(shù)f2(t)的BIC適應(yīng)值和內(nèi)部節(jié)點(diǎn)數(shù)隨迭代次數(shù)演化過程

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

圖6 （a）函數(shù)f3(t)的AIC、BIC適應(yīng)值與內(nèi)部節(jié)點(diǎn)數(shù)之間的關(guān)系

圖6 （b）函數(shù)f3(t)的BIC適應(yīng)值和內(nèi)部節(jié)點(diǎn)數(shù)隨迭代次數(shù)演化過程

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

表2f1(x)、f2(x)、f3(x)最優(yōu)內(nèi)部節(jié)點(diǎn)數(shù)及位置

5.3 與其他算法的比較

為了評(píng)估所提出的CASO-DF算法的節(jié)點(diǎn)自動(dòng)放置能力，將該算法與演化相關(guān)算法[14-16，24-25]進(jìn)行比較。Yoshimoto等[14]將數(shù)據(jù)擬合作為基于遺傳算法的離散組合優(yōu)化問題。ülker等[15]采用人工免疫算法處理數(shù)據(jù)擬合問題。Yoshimoto等[24]采用自適應(yīng)實(shí)數(shù)編碼的遺傳算法。Sarfraz等[25]采用基于遺傳算法和探測(cè)技術(shù)解決數(shù)據(jù)擬合問題。Zhao等[16]將高斯混合模型和k-均值方法結(jié)合，解決數(shù)據(jù)擬合問題。采用5.1節(jié)給出的測(cè)試函數(shù)，以M atlab7.0作為仿真工具，將CASO-DF算法與這些算法比較分析，相關(guān)算法的參數(shù)設(shè)置參考相關(guān)文獻(xiàn)。表3考慮它們的迭代次數(shù)、計(jì)算時(shí)間等因素，給出了比較結(jié)果?！啊北硎静淮嬖?。

表3 CASO-DF與相關(guān)算法的比較

從表3可以看出，CASO-DF算法較其他算法優(yōu)秀，適用于多種類型的函數(shù)，特別是計(jì)算速度快。究其原因是，CASO算法是基于螞蟻個(gè)體的混沌行為和整個(gè)蟻群的自組織行為設(shè)計(jì)，螞蟻個(gè)體的混沌行為探索能力較強(qiáng)，對(duì)內(nèi)部節(jié)點(diǎn)的位置搜索有較大幫助，而自組織行為能夠較好協(xié)調(diào)個(gè)體之間的最優(yōu)位置，加快了蟻群的搜索能力。因而CASO-DF算法的節(jié)點(diǎn)自動(dòng)放置能力強(qiáng)于其他算法。

由5.2節(jié)和5.3節(jié)的仿真實(shí)驗(yàn)可以看出，基于CASO算法設(shè)計(jì)的CASO-DF算法，有較好的性能，在計(jì)算精度和計(jì)算時(shí)間上優(yōu)于其他相關(guān)算法。

6 結(jié)束語(yǔ)

本文結(jié)合新型混沌螞蟻群算法，提出了基于混沌螞蟻群算法的B樣條曲線擬合算法CASO-DF，該算法將節(jié)點(diǎn)作為自由變量，把B樣條曲線擬合轉(zhuǎn)化為連續(xù)多峰值非線性優(yōu)化問題，應(yīng)用CASO自動(dòng)計(jì)算最優(yōu)內(nèi)部節(jié)點(diǎn)數(shù)，實(shí)現(xiàn)自由節(jié)點(diǎn)數(shù)目和位置自動(dòng)選擇。文中給出了混沌螞蟻群算法解決曲線擬合問題的具體方法及步驟。仿真結(jié)果表明了CASO-DF在計(jì)算精度和計(jì)算速度方面優(yōu)于相關(guān)算法。下一步的研究是將CASO-DF算法應(yīng)用于圖像邊緣檢測(cè)。

[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]周明華，汪國(guó)昭.基于遺傳算法的B樣條曲線和Bézier曲線的最小二乘擬合[J].計(jì)算機(jī)研究與發(fā)展，2005，42（1）：134-143.

[4]郭改文，黃卡瑪.模擬自然樹生長(zhǎng)的競(jìng)爭(zhēng)算法及在曲線擬合中的應(yīng)用[J].電子學(xué)報(bào)，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.

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

徐善?。?973—），男，講師，研究領(lǐng)域?yàn)閿?shù)字信息處理，信息檢索；郭有強(qiáng)（1966—），男，教授，碩士生導(dǎo)師，研究方向?yàn)榫W(wǎng)絡(luò)信息處理、智能控制和優(yōu)化算法；戚曉明（1975—），男，博士，副教授，研究方向?yàn)閿?shù)字信息處理，信息檢索；夏偉（1973—），男，博士，講師，研究方向?yàn)樾问交夹g(shù)及應(yīng)用，混雜系統(tǒng)理論及控制。E-mail：xiawei_0987@163.com

2012-09-26

2013-01-21

1002-8331（2014）16-0177-06

CNKI網(wǎng)絡(luò)優(yōu)先出版：2013-02-28,http://www.cnki.net/kcms/detail/11.2127.TP.20130228.1148.005.htm l