基于遗传算法的散乱数据点的NURBS 曲面拟合与优化

张志强，李建军，赵 坚

(天津城市建设学院 能源与机械工程系，天津 300384)

基于截面数据点的 NURBS 曲面拟合优化问题的解决已比较成熟，但基于散乱数据点 NURBS曲面拟合优化问题的解决还不够完善．曲面拟合优化问题可以描述为：给定散乱数据点 Pi(i=1 2 …n)、对应的矢量参数及容差 Tol，求在给定容差下，以尽量少的控制顶点表示出逼近给定数据点Pi的样条曲面 r(u，v)，并要求曲面较为光顺．这样，可以对复杂曲面进行简洁表达，在数控加工过程中，能减少 NC代码输入长度，提高曲面加工速度和精度．

1 遗传算法与NURBS曲面表达

遗传算法是由美国 Michigan大学的 John Holland提出的自适应随机搜索算法[1-3]．遗传算法依据优胜劣汰和适者生存的自然法则，从初始种群出发，采用基于适应值比例的选择策略在当前种群中选择个体，使用杂交和变异来产生下一代种群．通过一代代的竞争淘汰，直到满足期望的终止条件．遗传算法广泛应用于函数优化等领域，从理论上讲，在不限制遗传代数的条件下，它以概率1逼近全局最优解．遗传算法最初用于求解无约束优化问题，经过改进，可以进行多目标，多条件约束优化问题的求解[4-6]．

NURBS方法表达自由曲线和曲面有很多优势，利用控制顶点、权因子和矢量函数可对曲面进行完全表述．NURBS曲面的表达式为[7]其中，wi,j(i=0，1，…，m；j=0，1，…，n)称为权或权因子(weights)，分别与控制顶点 di,，j相联系，di,j呈拓扑矩形阵列，形成一个控制网格．规定四角顶点处的权因子(w0,0，…，w0,n，wm,0，…，wm,n)均大于 0，其余wi,j≥0，以防止分母为零，保留凸包性质并保证曲线不致因权因子而退化为一点．Ni,k(u)(i=0，1，…，m)，Nj,l(v)(j=0，1，…，n)是分别由节点矢量 U=[u0，u1，…，um+k+1]，V=[v0，v1，…，vn+l+1]按 De Boor-Cox 递推公式决定的k，l次规范B样条基函数．

2 改变权因子优化NURBS曲面

2.1 遗传因子的选择

控制顶点、权因子和矢量函数一经确定，则曲线或曲面就可完全确定．如果将其全部设置为遗传因子，则计算量过于庞大．在控制顶点和权因子确定后，节点矢量求取有比较成熟的方法，如里森费尔德(Riesenfeld)方法和哈特利(Hartley)-贾德(Judd)方法，因此将节点矢量设置为权因子并不合适．由文献[2]和文献[3]可知，若权因子修改适当，它对曲面修改的效果与同时修改控制顶点和权因子的效果是相似的．基于以上考虑，利用 Hartley-Judd方法计算内节点矢量值，选择控制顶点的权因子作为遗传基因．基因编码方式主要有两种：二进制编码和真值编码．对于变量较多的优化问题，采用真值编码，可使用较高的交叉概率和变异概率，以提高优化的概率．因而对于该问题，采用参数真值编码．

2.2 评价函数的确定．

评价函数的确定基于以下思想，即曲面设计完成后，要求生成的曲面与给定的散乱数据点的容差不大于给定值，且比较光顺．进行控制顶点权值优化以达到采用尽量少的控制顶点来描述符合上述要求的曲面．因此，在评价函数中既有容差项，又有光顺项．

2.2.1 容差项的确定

容差的含义为所有各散乱数据点 Pi与所求得的曲面上的相应最近点 r(ukvk)的距离之和，用公式表示为

2.2.2 光顺项的确定[4-5]

为求得光顺项表达式，由弹性力学中的薄板弹性变形方程可写出该曲面的能量函数

式中：ru，rv，ruu，rvv分别为曲面 r(u，v)沿 u，v方向的一、二阶偏导矢；ruv为混合偏导矢；αij和βij(i，j=0，1)为给定常数，与材料特性有关；在弹性变形方程中，f(u，v)代表形体所受的力，即外载荷．

这些参数对曲面的影响见文献[4]和文献[5]．计算时，可令 f(u，v)=0，取 α11=α12=α22=0 β11=β22=1，β12=2，可计算出能量函数Er，取光顺因子α=0.0001，则可写出评价函数J

3 主要计算步骤

(1)输入散乱数据点 Pi(i=1 2 … p)及其他初始参数(m，n，k，l，Tol，T)．m 和 n 分别为沿矢量 u，v 方向的控制点个数，所以共有控制顶点mn个，k和l分别为沿矢量u，v方向的样条次数，Tol为容差，T为m与n的差值．

(2)由散乱数据点按 B样条曲面描述生成控制顶点．

(3)利用遗传算法，生成优化曲面．

①确定遗传代数、种群数目、交叉概率、变异概率等参数．

②种群初始化．随机生成各控制点权值并进行编码操作，从而生成遗传个体，进而生成整个种群．

③求解评价函数和适应度函数．取式(4)为评价函数．

为求取 J的最小值，并防止分母为零，适应度函数取为

④约束条件．取 w0,0，w0,n，wm,0，wm,n均大于 0，其余 wi,j(i=0，1，…，m；j=0，1，…，n)均不小于 0．

⑤求出此种群中各个体的适应度，选取此代中的最优个体，并与全局最优个体的适应度进行比较，将适应度大者保留为全局最优个体．

⑥对全局最优个体和遗传代数进行判断，若最优个体适应度为 1，则输出结果，程序结束．若遗传代数达到设定值，则转至步骤④，否则转至步骤⑦．

⑦进行染色体基因遗传、交叉及变异操作．

⑧生成新一代种群，遗传代数加1，转至步骤③．

(4)计算所生成的曲面容差，并与给定的容差相比较，若大于给定容差Tol，则进行下一步，否则，输出结果，程序结束．

(5)增加控制顶点数目，n=n+1并转至步骤②，若仍不满足容差条件，则m=m+1，转至步骤②．

4 实例仿真

图1为散乱数据点的 NURBS曲面拟合优化结果，其中“*”表示给定散乱点，拟合数据点数为238，初始参数取 m=3，n=3，k=3，l=3，Tol=0.9，T=5，交叉率为 0.9，变异率为 0.15，最大遗传代数为 100．拟合后，m=6，n=9，所以拟合曲面共有控制顶点 54个，此时Tol=0.857 6．

图1 散乱数据点的NURBS曲面拟合优化

5 结 论

以遗传算法为工具，通过种群规模的合理设定，恰当地选择遗传因子和评价函数以完成对散乱数据点的曲面拟合．仿真结果表明，此方法可以进行散乱数据点的 NURBS曲面拟合优化，优化后曲面符合容差条件，光顺性较好，且曲面表述简单，有利于提高此类曲面数控加工的速度和精度．

［1］ Galleily J E. An overview of genetic algorithms[J]. Kybemetics，1992，21(6)：26-30．

［2］ 赵 巍. 数控系统的插补算法及加减速控制方法的研究[D]. 天津：天津大学，2004.

［3］ 李德信，谢 敬，贾 杰. NURBS曲面权因子及其应用研究[J]. 西安理工大学学报，2004，20(2)：154-159．

［4］ 穆国旺. 逆向工程中 NURBS曲面重构[D]. 北京：北京航空航天大学，2001.

［5］ YIN Zhong-wei. Reverse engineering of a NURBS surface from digitized points subject to boundary conditions[J]. Computers and Graphics，2004，28(2)：207-212.

［6］ 宋德军. 基于能量优化的曲线曲面造型理论及应用研究[D]. 北京：北京航空航天大学，1998.

［7］ 房 京，李世杰. NURBS自由曲线、曲面的等距算法及其在数控加工中的应用[J]. 河北工业大学学报，2002，31(5)：50-54．