张银娟 王永科

(许昌学院电气信息工程学院1，河南 许昌 461000;许昌恒源发制品股份有限公司技术中心2，河南 许昌 461000)

0 引言

在科学数据的处理过程中，参数化技术给科学数据的处理带来了极大的便利。非均匀有理B样条(non-uniform rational B-splines，NURBS)曲线以其优良的性能受到广大计算机辅助设计(computer aided design，CAD)工作者的青睐。NURBS曲线法通过操纵控制顶点和权值的方式，为曲线形状调整提供了充分的灵活性;同时NURBS曲线的修正也引起了业界的广泛重视。Piegl从NURBS曲线的数学定义出发［1］，提出了基于权因子的曲线形状修正方法。众多科技工作者分别从几何角度分析了一个权因子和两个权因子的变化对NURBS曲线曲面形状的影响［2－6］。

由于权因子的不合理应用可能导致精度不足的曲线拟合，甚至破坏曲线的结构，因此，在曲线拟合过程中引入遗传算法。由于遗传算法计划将字符串推广到计算机程序［7］，尤其是采用符号回归技术直接对数学表达式进行操作，能够建立描述复杂系统的数学表达式模型，这就使得将遗传算法引入到权因子对NURBS曲线的拟合精度控制成为一种可能。通过遗传算法的全局并行搜索方式，搜索到权因子变化空间中的最优个体，从而对拟合函数的参数值进行优化。

1 权因子对NURBS曲线的影响

一条控制顶点为Vi(0≤i≤n)的NURBS曲线P(u)可表示为:

式中:wi(0≤i≤n)为依附于相应控制顶点Vi(0≤i≤n)的权因子，一般约定首末权因子w0和wn≥0，其余权因子wi＞0(1≤i≤n－1)，以防止表达式方程分母为0，保证了曲线的凸包性质，并避免曲线因为权因子的取值而退化为一点这类现象的发生;Ni，k(u)为第i个k次规范B样条基函数，它定义在节点矢量U={u0，u1，…，un+k+1}上;Ri，k(u)为权因子 w 和基函数Ni，k(u)的表达式，它表示的是曲线P(u)计算过程的一个中间运算式。

为分析权因子wi的几何意义，可以假设只有wi发生变化，其他变量均不变，同时设定B、N、B(i)分别为 wi=0、wi=1、wi∈(0，1)∪(1，∞)的对应 NURBS曲线上的点。权因子影响示意图如图1所示。

图1 权因子影响示意图Fig.1 The effects of weight factors

由图1和式(2)可以得出权因子wi对NURBS曲线形状的影响，具体介绍如下。

①当增大(减小)权因子wi，曲线被拉向(推离)控制顶点V(i)。

②当wi=0时，此时控制顶点V(i)对曲线没有控制作用;当 wi趋于无穷大时，曲线经过控制顶点V(i)。

③ 当wi连续变化时，B(i)点随之连续变化，轨迹为一条直线。

考虑到权因子对曲线的形态的影响，权因子选择不当可能导致误差较大的NURBS曲线拟合，本文采用最小二乘性能指标来表征NURBS曲线的拟合精度。当随机给定权因子 w=［3.5，1.7，2.2，6.5，0.9，1.5，4.9，2.5］时，NURBS 曲线拟合的最小二乘性能指标为1.3007，此时权因子和控制顶点也能大致反映控制顶点数据的结构。为了更精确地反映控制顶点的曲线趋势，下文将引入遗传算法。随机权因子NURBS拟合曲线如图2所示。

令 α=Ri，k(u;wi=1)和 β=Ri，k(u)，则有 N=(1 －α)B+αV(i);B(i)=(1－β)B+βV(i)，得到如下恒等式:

图2 随机权因子NURBS拟合曲线Fig.2 NURBS curve fitting with stochastic weight factors

2 遗传算法原理

遗传算法以自然选择和遗传理论为基础，它是一种将生物进化过程中适者生存规则与群体内部染色体的随机信息交换机制相结合的高效全局寻优搜索算法。目前，遗传算法得到迅速的发展，其主要的应用领域有生命的遗传进化、人工智能、生产规划、模式识别、图像特征提取、滤波器设计、机器人控制和防避导弹控制等领域;同时，遗传算法也成为求解优化问题的有力工具之一。

遗传算法的应用过程是将问题域中的可能解看作群体的一个个体或染色体，并将每一个个体编码成符号串的形式，模拟达尔文的遗传选择和自然淘汰的生物进化过程，对群体反复进行基于遗传学的操作［8－9］;同时，根据预定的目标适应度函数对每个个体进行评价，依据适者生存、优胜劣汰的进化规则，不断得到更优的群体，并采用全局并行搜索方式来搜索优化群体中的最优个体，求得满足要求的最优解。

遗传算法的应用步骤如下。

①确定个体的表现型X和问题的解空间;

②确定目标函数的类型及数学描述形式或量化方法;

③确定个体的基因型及遗传算法的搜索空间;

④确定个体基因型x映射到个体表现型X的对应关系或转换方法;

⑤确定目标函数值f(x)映射到个体适应度F(X)的转换规则;

⑥确定选择运算、交叉运算和变异运算等基本遗传算子的具体操作方法;

⑦问题解的解空间寻优过程，寻优过程完成后确定最优解。

3 最优权因子的求解

权因子对曲线形态有着重要影响，不合适的权因子会导致NURBS曲线失去意义。本文将遗传算法引入到权因子对NURBS曲线的拟合精度控制中，通过遗传算法的全局并行搜索方式，搜索到权因子变化空间中的最优个体，从而对拟合函数的参数值进行优化。

3.1 权因子求解步骤

最优权因子求解过程如下。

①建立优化模型，确定决策变量解空间范围和约束条件。

②确定编码方法，用长度为10位的二进制串码(b1，b2，…，b10)分别表示决策变量，其中10位二进制串码代表0～1023之间的1024个不同数值，同时将决策变量定义域离散化为1023个均等区域。根据解空间的取值范围，离散点0到离散点10.23依次分别对应二进制串码0000000000～1111111111之间的二进制串码。这些二进制串码构成了次优化问题的染色体编码。

③确定解码方法，解码时，根据编码方法和离散化方法，设定 bi∈(b1，b2，…，b10)，Umin和 Umax分别代表十进制串码的最小值和最大值，则每十位二进制串码分别映射到十进制的数值代码W的解码公式为:

④确定个体评价方法，针对曲线拟合的精度问题，运用最小二乘法。该问题的优化目标就是求解给定曲线和拟合曲线的最小二乘值最小。

⑤设计基本遗传算子，选择运算使用比例选择算子，交叉运算使用单点交叉算子，变异运算使用基本位变异算子。

⑥确定遗传算法的运行参数。

3.2 仿真试验

采用上述遗传算法步骤，设定群体大小为80，终止进化迭代数为500，交叉概率为0.60，变异概率为0.10，则迭代运算500步。算法迭代仿真试验完成后，最佳权因子NURBS拟合曲线和性能指标最小变化过程曲线分别如图3和图4所示。

从图4可以看出，遗传算法在运算开始的一段时间内，效果很明显。随着进化迭代次数的增加(进化过程的进行)，同时由于选择、交叉和变异机制的作用，群体中适应度低的一些个体被淘汰，而适应度高的一些个体则越来越多，并且都集中在所求问题的最优点附近。在迭代运算完成后，算法全局搜索到的最佳权因子样本为 ［0.41，8.64，3.45，3.81，10.11，3.22，4.13，1.79］，此时最小二乘性能指标仅为0.3276，相比随机权因子NURBS曲线拟合性能指标1.3007有了较大提高。因此，遗传算法全局搜索到的最优解使得曲线拟合精度有了较大的改善。

4 结束语

遗传算法摒弃了传统的搜索方式，模拟自然界生物进化过程，采用人工进化的方式对NURBS权因子空间进行随机全局搜索和优化;使用适者生存的原则，从潜在的解决方案种群中依次产生一个近似最优的方案，从而对NURBS曲线拟合的权因子进行优化。当然，遗传算法的NURBS曲线拟合还有很多需要改进的地方，如对参数的编码可以采用整数或字母排列的方式，对曲线和曲面的拟合也可以用熵性能指标作为适配值［10－12］。相信在不久的将来，通过对遗传算法进行改进和完善，使其有望在设计和工程运用中发挥更大的作用及优势。

［1］Piegl L，Tiller W.Curve and surface constructions using rational B-sphine［J］.Computer Aided Design，1987，19(9):485 －498.

［2］戴春来.样条曲线的参数化变形方法［J］.计算机辅助设计与图形学学报，2005，17(6):1207 －1212.

［3］龚晨.曲线的随机拟合及其自适应算法［J］.上海交通大学学报:自然科学版，2005，39(4):661 －664.

［4］陈国振，刘静华.B样条曲面自适应拟合算法［J］.北京航空航天大学学报:自然科学版，2007，33(2):210 －213.

［5］苏翩，林意，邱利琼，等.NURBS曲线的一种快速修正算法［J］.重庆大学学报:自然科学版，2007，30(4):118－120.

［6］孙玉文，吴宏基，刘健.基于NURBS的自由曲面精确拟合方法研究［J］.机械工程学报，2004，40(3):10 －14.

［7］张善文，刘建都，韩小斌.基于遗传算法的一种数据拟合方法［J］.空军工程大学学报:自然科学版，2007，8(1):66 －68.

［8］梁芳，王卫华，祝庆.改进的遗传算法在Logistic曲线拟合中的应用［J］.武汉理工大学学报:信息与管理工程版，2008，30(4):544 －547.

［9］周明华，汪国昭.基于遗传算法的B样条曲线和Bézier曲线的最小二乘拟合［J］.计算机研究与发展，2005，42(1):134 －143.

［10］吴景龙，杨淑霞，刘承水.基于遗传算法优化参数的支持向量机短期负荷预测方法［J］.2009，40(1):180－184.

［11］陈果.基于遗传算法的支持向量机分类器模型参数优化［J］.机械科学与技术，2007，26(3):347 －350.

［12］唐炜，张莉，陈涛.遗传优化支持向量机的传感器动态建模［J］.自动化仪表，2011，32(3):21 －23.