基于改进PSO算法的B样条曲线拟合*

李轩宇, 张兆军, 许钊雄

(江苏师范大学 电气工程及自动化学院,江苏 徐州 221116)

0 引 言

现代工程设计中经常需要从测量的数据点中获取最合适的曲线或曲面表达,但这些数据点往往由于各种因素的影响存在误差,所以待求的曲线或曲面不必严格地经过每一个数据点,可以用拟合的方法逼近数据点。由于B样条曲线具有较好的逼近能力以及局部修改等优秀的数学性质[1],可以灵活表示各类曲线及曲面的形状。因此,在测试数据处理、逆向工程和图像处理[2,3]等工程领域中,B样条曲线拟合技术得到了广泛的应用。

国内外学者对于B样条曲线拟合问题已经做了大量的研究。Bo P等人[4]在充分考虑曲线形状特征的基础上提出一种基于图形的平面相交B样条曲线拟合方法。Deng C等人[5]使用渐进迭代逼近的方法求解数据点数量较大的拟合问题,具有较好的保形效果。利用各种智能算法求解曲线拟合问题是一个新的研究方向。胡良臣等人[6]提出一种基于二进制遗传算法的B样条曲线拟合方法,可以在满足法向约束条件的同时生成误差较小的拟合曲线。Uyar K等人[7]采用杂草优化方法选择最优节点进行B样条曲线拟合,实验结果表明了较好的拟合效果。节点向量的选择对于曲线的拟合效果具有重要影响,合适的节点向量可以减小曲线拟合误差。粒子群优化(particle swarm optimization,PSO)算法[8]在求解曲线拟合问题时存在早熟收敛,易于陷入局部最优等缺点。

本文结合遗传算法(GA)[9]和天牛须搜索(BAS)策略[10]对标准PSO算法进行改进,提出一种基于GA-BAS策略的改进粒子群优化(genetic-beetle PSO，GBPSO)算法用于求解带法向约束的3次B样条曲线拟合问题。

1 问题描述

1.1 数学模型

一条p次B样条曲线可以表示为

(1)

式中p为B样条曲线次数,本文取p=3；Pi为控制顶点；Ni,p(u)为p次B样条在节点向量U上的基函数,定义如下

(2)

p≥1

(3)

式中 规定0/0=0；ui,i=0,1,…,n+p+1为节点向量U{ui}中的元素,u的范围一般取[0,1]。

给M+1定个数据点dk和法向约束条件lk,找到一条曲线C来逼近数据点dk的同时要满足数据点处的法向约束条件lk。文献[6]中将此类问题转化为带等式约束的最小化问题,即

式中tk为数据点dk所对应的参数值；‖·‖为平方范数；C′(tk)为曲线在tk处的一阶导数。

对于优化模型式(4),利用罚函数方法将其转换为无约束最优化问题,建立适应度函数如下

(5)

式(5)为本文最终所要优化的适应度函数,并利用GBPSO算法对其进行优化求解。

1.2 数据点参数化方式

求解曲线拟合问题时首先要将数据点进行参数化,不同的参数化方法会影响曲线最终的拟合效果。均匀参数化、向心参数化和弦长参数化是三种常用的参数化方法。本文中拟合曲线会面临数据点急剧变化的情况,因此选择向心参数化,该方法在处理此类问题时效果更好。参数tk与数据点dk的关系如下

(6)

2 算法介绍

2.1 PSO算法原理简介

PSO算法首先初始化产生N个粒子,每个粒子代表优化问题的一个潜在解。粒子i的速度和位置分别用d维向量vi和xi表示。粒子通过迭代更新自己的速度和位置,更新方式如下

(7)

(8)

2.2 BAS算法[10]简介

BAS算法是一种新型智能优化算法[10]。天牛在觅食过程中不知道食物的确切位置,仅依靠两个触须探测食物气味并通过判断左右须气味浓度大小来决定下一步的走向。如果左须气味强于右须,则向左移动,反之向右移动,直至找到食物。其数学模型如下：

1)随机天牛的搜索方向并标准化

(9)

式中 rands(·)为随机函数；n为空间维度。

2)计算左右须坐标

(10)

式中xlt和xrt分别为天牛左右须在t时刻的位置；d0为两须之间的距离。

3)根据两须对应的函数值,决定天牛下一步位置

(11)

式中δt为t时刻的步长；f为目标函数；sign(·)为符号函数；f(xlt)>f(xrt)时取-1,反之为1。

BAS算法仅仅通过单一个体进行寻优,具有较好的局部搜索能力,但也因此缺乏个体之间的信息交互,导致算法的全局搜索能力较弱。

2.3 GBPSO算法流程

由于标准PSO存在易于陷入局部最优的缺点,而BAS算法在局部搜索方面具有优势。本文首先结合两种算法的优点,将BAS策略引入到PSO算法之中,提高单个粒子的寻优能力帮助算法跳出局部最优,然后通过交叉和变异操作提高子代种群的多样性,增强算法的全局搜索能力,基于此提出一种改进的粒子群算法GBPSO。

GBPSO算法中,每个粒子都被当成一个个的天牛进行寻优。与标准PSO相同的是,粒子的初始位置采用随机初始化策略,速度使用式(7)进行更新。不同之处在于,粒子的位置更新中结合了BAS策略,按式(12)更新

(12)

增量函数ξ的计算公式如下

(13)

式中δk为天牛在第k次迭代时的步长；Xld和Xrd为天牛的左右须坐标,其更新公式如下

(14)

步长δ随着迭代衰减,本文初始步长设为1,δ和搜索距离s之间有如下关系

δk=eta·δk-1

(15)

sk=δk/T

(16)

常量eta和T的值根据经验进行调整,本文取eta=0.95,T=2。

本文选择交叉方式为均匀交叉,交叉概率pc=0.5。变异方式选择高斯变异,变异概率pm=0.05。

算法的具体步骤如下：

Step1 初始化种群和速度并设置相关参数。

Step2 计算每个粒子(天牛)的适应度值。

Step3 对每个粒子,比较其当前适应度值和pbest的大小,如果当前解更小,则更新pbest。

Step4 对每个粒子,比较其当前适应度值和gbest的大小,如果当前解更好,更新gbest。

Step5 通过式(7)对粒子的速度进行更新。

Step6 根据式(14)得到天牛左右须坐标,并计算左右须的适应度值。

Step7 根据式(13)更新增量函数ξ,并结合式(12)更新粒子位置。

Step8 对子代个体进行交叉和变异操作,经过筛选得到更加优秀的子代个体。

Step9 若满足中止条件则退出算法,否则返回Step2。

2.4 基于GBPSO的B样条曲线拟合算法

通过罚函数方法将带法向约束的B样条曲线拟合问题转化为无约束最优化问题。算法流程如图1所示。

图1 B样条曲线拟合流程

3 实验仿真

3.1 拟合曲线选择

本文选择了4个不同类型的算例,其表达式以及定义域如表1所示。

表1 算例详细信息

每个算例的取点间隔为0.05,则例1的取点个数为80,例2～例4的取点个数均为126。例4中参数a=1,b=1/2,h=1。

3.2 实验说明

本文选择4个算例验证所提GBPSO算法的拟合效果,并通过与标准PSO[8]和另外两种改进PSO算法—结合BAS的PSO(beetle PSO，BSO)[11]、和结合GA的PSO(GAPSO)[12]对比来证明其有效性。每组实验在相同条件下独立运行20次,以适应度值为拟合效果的评价标准,统计20次实验结果的最大值、最小值、平均值和方差。

GBPSO算法与3种对比算法的参数设置见表2。表2中sizepop表示种群规模,maxgen表示算法的最大迭代次数。

表2 算法参数设置

3.3 实验结果与分析

图2所示为GBPSO算法优化节点向量的曲线拟合效果图。由图2可以看出,本文所提GBPSO算法对所有4个算例都具有较好的拟合效果。

图2 4个算例的拟合效果图

图2(a)中曲线形状较为简单,GBPSO算法在处理此类问题时可以达到较好的效果。图2(b)和图(d)中曲线的数据点分布较为均匀,且图2(d)存在曲线交叉的情况,可以看出GBPSO算法对解决此类问题也是可行的。图2(c)中曲线不仅存在交叉的情况,而且在局部有着较为尖锐的变化。可以看出,GBPSO算法不仅在处理平滑曲线时有较好的效果,而且在面对曲线形状急剧变化的复杂情况时,依然能够得到理想的拟合曲线。拟合仿真实验结果表明,所提GBPSO算法在面对一般的情况时,不仅可以得到误差较小的拟合曲线,且能够满足数据点处的法向约束条件。

为了进一步说明本文改进算法的有效性,GBPSO算法与三种对比算法对以上4个算例的数值实验结果见表3,加黑数值表示算法在相应算例上的最优结果。

表3 数值实验结果

由表3可以看出,对于所给的4个算例,本文所提GBPSO算法的优化结果都要优于标准PSO算法,同时在例2～例4三条曲线的表现上优于BSO和GAPSO两种算法。对于算例1,由图3可以看出该曲线形状较为简单,因此,所提算法与GAPSO算法在寻优结果上差别很小,都在同一数量级,而从最小值的统计结果来看,所提GBPSO算法有一定的能力找到比GAPSO更好的解。

4 结 论

本文基于遗传算法和天牛须搜索策略提出了GBPSO算法用于求解数据点带法向约束的B样条曲线拟合问题。不同于标准PSO算法,GBPSO中通过BAS策略更新粒子位置,并结合GA中的交叉和变异操作保证子代种群的多样性,增强算法的全局搜索能力。通过罚函数的方法将带法向约束的B样条曲线拟合问题转换为无约束最优化问题,然后利用GBPSO对节点向量的位置进行优化。实验结果表明,本文算法生成的拟合曲线不仅误差较小,而且能够满足数据点处的法向约束条件。