基于NSGA-Ⅱ和最小二乘原理的加工轨迹拟合算法

瞿佳伟 张春雷 张 冀

（四川大学 制造科学与工程学院 成都 610065）

在现代机械加工零件的过程中，经常需要加工复杂非圆曲线。对于非圆曲线轮廓的加工，CAD/CAM系统常用连续微小直线段来逼近轮廓曲线，但是直线逼近的结果往往导致加工效果、形状精度不高，而且加工后表面粗糙度值大，特别是微线段不够短时线段间的转折更加明显；而当形状精度要求较高或加工图形过于复杂时，拟合线段数目将大大增加，导致加工时电机加减速频繁，大大降低了生产效率[1-2]。

由于圆弧能够较好地体现曲线曲率的变化且具有较低的计算复杂度,且目前大多数数控系统都具有圆弧插补指令，因此非常适合作为拟合的基本单元[3]。目前大多数基于最小二乘拟合算法，是将拟合点看做有序序列，逐次移位拟合，若拟合结果符合要求，则将拟合区间往后移一位重新拟合；否则将上次拟合结果保留，并以上次拟合终点作为新的拟合起点进行新一次的拟合，直至将所有轨迹点拟合完毕[4]。这种传统算法虽然简单快捷地实现了分段拟合，并得到了一种较优的拟合方案，但这种算法没有从整体考虑，因而得到的只是一种局部最优方案。

本文利用最小二乘法对用微线段逼近的加工轮廓进行圆弧拟合，并以拟合段数和拟合误差为目标，设计了一种基于NSGA-II的多目标遗传算法，找出拟合分界点，完成对加工轨迹的拟合。较传统的最小二乘拟合方法而言，设计的算法，在满足精度的前提下，可使拟合圆弧段数更少，并能够减小拟合误差、简化数值计算。

1 带精英策略的非支配排序的遗传算法简介

对于大多数多目标优化问题，其各个目标往往是相互矛盾，所以很难找到一个解使得所有的目标函数同时最优，也就是说，一个解可能对于某个目标函数最好，但对于其他目标函数并不是最好，甚至最差。因此，对于多目标优化问题,通常存在一个解集，这些解之间就全体目标函数而言是无法比较优劣的，这类问题的特点是:不能在改进任何目标函数的同时不削弱至少一个其他目标函数。这种解称作非支配解(nondominated soluitons)或Pareto最优解(Pareto optimal Soluitons)。

NSGA-Ⅱ是一种经典的多目标进化算法，由Kalyanmoy Deb等人于2002年在文章《A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-Ⅱ》中提出，是对1994年提出的NSGA的改进，相比于NSGA，NSGA-Ⅱ的改进有两点：(1)提出一种快速非支配排序，使得Pareto支配排序的时间复杂度由O(N3)优化到O(N2)；(2)提出一种拥挤距离来衡量解的分布性，并基于此选择种群中的合适的个体[5]。

NSGA-Ⅱ算法的基本思想：首先，随机产生规模为N的初始种群，非支配排序后通过遗传算法的选择、交叉、变异三个基本操作得到第一代子代种群；其次，从第二代开始，将父代种群与子代种群合并，进行快速非支配排序，同时对每个非支配层中的个体进行拥挤度计算，根据非支配关系以及个体的拥挤度选取合适的个体组成新的父代种群；最后，通过遗传算法的基本操作产生新的子代种群，依此类推，直到满足程序结束的条件。

NSGA-Ⅱ的提出，为多目标进化算法的一大进步，特别是其基于Pareto支配关系的框架被后来许多算法采用，如NSGA-Ⅲ，VaEA等。同时，NSGA-Ⅱ对于低维多目标优化问题效果是比较好的，但是对于高维多目标优化问题，其首先面对的是基于Pareto支配关系所导致的选择压力过小的问题；其次，是拥挤距离在高维空间不适用，计算复杂度也比较高。

2 最小二乘拟合原理

最小二乘法的基本思想：给定一组有序数据，以误差平方和最小的原则，找出这些数据的最佳匹配函数。但仅使用最小二乘法进行分段拟合时，显然不同段端点不一定会重合，由此引入端点约束条件改进最小二乘法。即固定起点和终点坐标对n个点进行圆弧拟合，设轨迹点坐标为(xi,yi)(i=1,2,3,…,n)，起点坐标为(x1,y1)，终点坐标为(xn,yn)，圆心坐标为(x0,y0)。拟合圆经过起点和终点，则圆心一定在起点和终点连线的中垂线上，可设该直线方程为y=k∙x+b则有：

拟合圆应满足以下条件：

由此即可求出拟合圆心坐标。

由于轨迹中可能也存在直线部分，这时计算机在进行圆弧拟合计算时，求出的圆心坐标将为非数（NAN），为方便处理，可以将这种结果的拟合圆弧用直线段代替。

3 算法设计

本文试图基于 NSGA-Ⅱ算法找出不同拟合段的分界点并利用最小二乘原理实现对不同拟合段的圆弧拟合。具体算法设计如下：

3.1 目标函数

本文以拟合段数最少和拟合误差最小作为目标函数，试图找出加工轨迹的最佳拟合方案，目标函数数学模型如下：

其中f1为拟合基元段数，N为原轨迹点数，f2为拟合误差，mi为第i段的拟合点数。 fi(x,y)为第i段拟合轨迹方程，P xij,yij为第i段第j个拟合点坐标。

3.2 编码与解码

拟合的过程是将原始点列形成的轨迹用线段或圆弧组合的形式来表达，因此关键是找出每段（线段或圆弧）之间的分界点，这里采用二进制编码方法进行编码，即将原始点分为连续点和分界点，连续点用0表示，分界点用1表示。

对于个体进行评价时需要计算其适应度，解码时将两个分界点所有点看成一段，分别进行最小二乘拟合，并根据拟合结果分别计算每个点的拟合误差。

3.3 初始解的产生

遗传算法中，初始解的优劣影响着算法的收敛速度。在轨迹拟合的误差要求限制下，全体解空间中有许多无用解，因此，如何快速地产生一些可行的初始解便成了提升算法性能的关键。

产生的初始解包括编码和随机拟合两部分，随机拟合在计算机程序上使用递归方式进行实现。

步骤1：以原始的第一点和最后一点为分界点，两个分界点之间的所有点进行拟合，计算拟合误差；拟合误差不符合要求，转到步骤2，否则转到步骤3。

步骤 2：在原始轨迹中随机选择一个点为分界点，将原始轨迹分成两段新的需要拟合的轨迹；对两段新的轨迹分别递归调用函数本身，即转到step1，将两个函数返回的信息表组合成一个新的信息表并作为函数返回值。

步骤3：返回拟合信息表。

3.4 从种群中选出父代

计算种群中个体在不同目标函数下的适应度，对种群进行非支配排序，分成不同的帕累托前沿（Pareto front），计算不同前沿中同一前沿不同个体的拥挤距离，从种群中选出非支配等级高，拥挤距离大的一定数量个体参加锦标赛，从而通过锦标赛选出父代。

3.5 交叉变异算子

交叉算子，这里选择两点交叉。计算每个基因位上的拟合误差与0到1之间随机数的积，选出其中值最大的基因位作为交叉点，据此随机从父代中选出两个不同的染色体，并从两个染色体中分别选出两个交叉点，得到新的子代染色体。

变异算子，这里同等概率随机选择变异点，并将变异点的原有基因取反得到新的子代染色体。算法流程图，如图1所示。

图1 算法流程图

4 算法仿真及算法改进

本文算法已在Matlab平台上实现，图2为用来验证本文算法的测试图像数据点，是CAM软件对蜘蛛图像生成的 G代码中的轨迹点，总共有 1121个点。这里设置种群大小为50，迭代终止条件为连续 10代拟合段数最少个体的拟合段数或者迭代次数达到1000次。

图2 原始数据点

图3为最后一代pareto前沿中拟合段数最少的轨迹拟合图像，图4为拟合过程中第一代和最后一代的pareto前沿。图3由114条圆弧和6条线段（可视为半径为无穷大的圆弧）组成，拟合总误差为0.02134mm，原轨迹每个点到拟合曲线的误差均小于 0.01mm，拟合效果比较令人满意，但是对于本例，算法平均计算时间达到了几十分钟，这显然无法满足实际生产工作对效率的要求。因此需要对算法进行改进。

图3 拟合图像

图4 第一代及最后一代pareto前沿图

通过对本处案例的跟踪运行发现，算法花费时间最多的地方为交叉变异函数，因为染色体长度较长，经过交叉变异操作得到的个体有较大可能为非可行解，因此需要多次重复操作得到可行解，浪费了大量时间。经过实验发现，染色体越短，交叉变异得到可行解的概率越高，因此可以从这个角度考虑改进原算法。

改进后的算法考虑到实际情况中的加工轨迹可能有多个尖点，通过提前找出尖点，将一条加工轨迹分成几部分，对于每部分看成独立的轨迹分别调用拟合算法，可以有效地降低整条轨迹的拟合计算时间。使用改进算法对图2进行拟合，设置同样的种群大小及迭代终止条件。拟合时间对比原算法的数小时缩短到了50 s左右。拟合性能也有一定的提升。

NSGA2的最差时间复杂度为O(mn2)，其中，m为目标函数个数，n为种群大小。在本文中，假设一条轨迹由n个点组成，其中包含 1个尖点，改进算法将轨迹以尖点为分界线，分成两段小轨迹，点数分别为n1和n2，分别调用原拟合算法，因此改进算法的最差时间复杂度为 O 2n12+2n22小于原算法的最差时间复杂度O(2n2)，这也从理论上证明了改进策略的有效性。

为了具体比较说明本文算法及改进算法性能，下面通过使用不同算法对图5中的心型图形进行拟合，每种算法均运行100次，记录其平均性能如表1所示。

图5 心形轨迹图

表1 针对心形案例算法性能参数表

从表中可知，本文算法作为启发式进化算法，所求解趋近于全局最优解，因此所求解比传统算法往往更优，虽然计算效率有所下降，但在对加工轨迹精度要求更高的场合还是有其优势的。

5 结语

本文设计了基于 NSGA-Ⅱ的以圆弧为最小二乘基元的轨迹拟合算法，以较少圆弧与较小逼近误差为优化目标。实现算法时，为提高算法自适应性，设计了初始解生成算法，改进了交叉操作，自适应产生交叉概率，为了提高对复杂图形的拟合效率改进了拟合算法。

通过对CAM软件生成的微小线段表达的加工轨迹的拟合,可以有效减少加工时传输的数据，提高后续对加工轨迹的速度规划效率，从而提高加工速度。本文算法较传统算法，给出一系列Pareto最优解以供选择，同等拟合段数下的拟合轨迹更为逼近原始轨迹，但如何进一步完善，提高其收敛速度，减少计算量，还有待后续研究。