基于改进差分进化算法的自由曲面测量路径优化

王冠中 王士军 冉川东

（山东理工大学机械工程学院，山东 淄博 255000）

随着社会的不断进步，应用于动力机械、航海航空和其他工业等领域的机械零件呈现结构精细、曲面复杂等特点，而零件的形面精度直接决定了它所构成的产品质量和性能，因此，高效率、高精度曲面测量技术的研究与开发具有十分重要的理论意义，其对生产制造也有实际应用价值。自由复杂曲面的计算机建模过程中，需要使用到曲面测点检测技术，该技术所用到的主要设备为三坐标测量机。在计算机中，曲面由许多密密麻麻的测点组成，为了提高检测效率，就需要找到一条既能让测头扫过曲面全部，又能使测头移动的总距离最短的检测路径，并且能够不重复地走过曲面上需要的所有点[1]。

国内外学者对于路径优化问题方面做了许多的研究，白芸等学者通过试验表明，差分进化算法在解决旅行商问题时的收敛逐步优化，最大程度排除旅行商问题内部存在的动态误差，具有较强的优化能力，但差分进化算法收敛速度慢，容易陷入局部最优化问题[2]；李中伟等学者提出了改进反序-杂交算子应用于差分进化算法[3]，该算子使算法在搜索后期，能够有效地改善差分进化算法收敛速度慢的问题，同时避免了原来逆转操作中对基因位置的限制；梅觅等学者则提出了一种新的交叉操作——刘海交叉操作[4]，这种交叉操作方法取代了常规的遗传交叉算子，包括顺序交叉、循环交叉等，这些交叉操作后出现的子代有一些缺点，例如不能很好地保留父代的优秀基因，而子代需要做些改动才能保留。新的交叉操作则弥补了传统遗传算法随机生成初始种群的不足；而张敬敏等学者提出了改进差分进化算法用于求解JSP 问题，算法中通过改进算法中的变异算子以及缩放因子，来提高算法的运行效率和种群的多样性[5]。

以上文献所述都是基于求解TSP 问题的差分进化算法的改进，通过延伸和拓展，差分进化算法也可应用于求解自由曲面的测点检测路径规划问题，但有所不同的是：TSP 问题是一个二维平面求解路径规划问题，而自由曲面测点坐标检测路径规划问题则是一个三维问题。本文设计了改进的差分进化算法，并经过实验验证表明，改进的差分进化算法能够高效、稳定地完成自由曲面测点检测路径优化问题。

1 自由曲面的测点检测过程

三坐标测量机是自由曲面测点检测过程中使用到的最主要设备，自由曲面测点检测过程主要分为三段：第一段为测头定位到曲面测点上方的A点，然后以固定的检测速度沿着检测路径a移动到曲面测点B点；第二段为当B点检测完成后，测头以固定的回退速度沿着b到达C点；第三段为测头从曲面上方C点以固定速度移动到下一个检测点E点上方的D点；最后重复第一段的运动，直到全部测点检测完成，如图1 所示。

图1 局部检测路径示意图

2 差分进化算法简介

差分进化算法（differential evolution algorithm）属于一类基于群体差异的启发式随即搜索算法，这类算法具有高效性。该算法最初由Store R 和Price K 提出，用于求解Chebyshev 多项式。其演化流程与传统的遗传算法非常接近，基本包括变异、交叉和选择操作，然而具体的定义又有所不同，其基本思想为：首先，随机产生一个初始种群，计算在种群中随机选择的两个不同个体的向量差，并将这个向量差与第三个个体相加，以此来产生新的个体；然后，产生的新个体会与当代种群中相对应的个体进行适应度值的比较，若新个体的适应度值高于当前个体，在下一代中，新个体将会取代旧个体，否则将保留旧个体进入下一代的循环，直至达到最高迭代次数。通过这样的演化过程，不断保留优秀个体，淘汰劣质个体，引导搜索逐步接近最优解。

3 差分进化算法的设计与改进

3.1 编码方式

在解决TSP 问题时，有多种编码方式可供选择，其中之一是对经过每个城市的顺序进行逐次编码，即采用整体离散化编码，例如当编码为3271456 时，表示测头从3 号点出发，依次经过点2、7、1、4、5、6，完成该条路径的检测。

3.2 初始化总体

3.3 适应度函数

从三坐标测量机测头检测过程的描述和示意图中可以看出：测头的单次运动路径D=La+Lb+Lc，测头的单次运行时间则为T=ta+tb+tc，而无论检测路径如何变化，AB段及BC段的运动过程总是固定不变的，即路径和运行时间不变，因此，在上述两个表达式中，只有Lc和tc影响表达式的结果，简化公式后，测点检测过程就简化为了三维状态下的求解TSP 问题。同遗传算法一样，差分近乎算法也是依靠适应度函数来判断解的优劣，即适应度函数是衡量解的质量或优劣的标准。目标函数可以定义为：（Lci表示为两个测点之间的测头移动距离），当D最小时，优化的结果最好。在差分进化算法中，通常会选择一定比例的个体进行变异操作，然后通过交叉操作产生新的个体，最后通过适应度函数来选择保留哪些个体，由目标函数可知，适应度函数的目标是最小化路径的总长度，因此适应度值越大，代表路径越短，个体越优秀，所以适应度函数确定为目标函数的倒数，即：

3.4 改进的适应性突变策略

传统DE 算法中的突变运算是从初始化的群体中随机选择两个不同的个体进行差分计算，然后与第三个不同的个体进行加权计算。该算法有不同的突变策略，其中最主流的策略[6]包括：

以上策略的提出在一定程度上都提高了差分进化算法的收敛速度和收敛性，而You X M 等学者提出了一种新的突变策略“DE/average/2”[7]，该策略的表达式为

这个新策略在仿真实验中的结果表明，与其他主流算法相比具有更强的求优能力，但是这个新策略存在收敛速度慢、迭代时间长、最优结果不稳定的问题。

为了提高算法求优能力的稳定性以及算法收敛速度慢的问题，在这里，我们提出一种新的突变策略，该策略的表达式为

新的突变策略以每代种群中最优秀个体以及两个随机的不同个体为基础，在此基础上分别求3 个个体的平均值，最优秀个体与随机个体的差值，差值并分别乘以一个适应度值F，依次来产生一个新的向量。其中适应度值F是一个动态调整的自适应因子，F的范围则是在均值为0，标准差为0.5 之间的随机数，这个随机数按照下面公式进行调整：

该公式使得算法在更新自适应因子时，如果个体当前的适应度值小于其历史适应度值，则自适应因子增加，使得个体具有更好的变异性；如果适应度值变大，则适应度自适应因子减小，使得个体更加倾向于利用当前已经找到的优解，这样可以在全局搜索和局部搜索之间进行更好的平衡。

基准误差是零件坐标系关于夹具坐标系的偏差，影响零件坐标系到夹具坐标系的实际转换矩阵，使实际转换矩阵在理想转换矩阵的基础上又增加了偏差转换矩阵。零件从工序k-1到k，将k-1的输出X(k-1)作为k的输入，X(k-1)由基准选择矩阵D(k)得到第k道工序的定位基准Da(k)，

3.5 重复启动策略

在差分进化算法中，重复启动策略是一种启发式技巧，在提高DE 算法的性能，尤其是处理复杂、多模态的优化问题时具有很好的效果。重复启动策略的运行机制如下。

（1）初始化种群：差分进化算法首先随机生成一个种群，每个种群代表一个潜在的解决方案，这些个体的参数值实在问题定义的范围内随机选择的。

（2）目标函数评估：对于每个个体，算法计算目标函数的值，这个值则衡量了该个体解决方案的质量，即优化路径长度的值。

（3）重复启动策略：在差分进化算法中，通常添加mutation、crossover 和selection 等操作来演化种群，以此来寻找更优的解。重复启动策略的核心思想是在不同的种群初始化条件下，多次运行差分进化算法。

（4）多次运行差分进化算法：差分进化算法会在不同的初始化条件下多次运行，每次运行都有独立的初始种群。

（5）选择最佳解：在每次运行结束后，都会选择最佳的个体作为该次运行的结果，最终，从多次运行中选择具有最佳目标函数值的个体作为全局最优解。

实验表明，多重启动策略通过多次独立运行差分进化算法，每次运行都能从不同的起点开始，增加了算法的全局搜索性能，在一定程度上克服了局部最优解的缺陷。同时，重复启动策略在一定程度上减轻了算法对于初始种群选择的依赖，提高了算法的求优稳定性。

3.6 改进差分进化算法结构

改进差分进化算法的流程图如图2 所示，基本流程如下：

图2 改进差分进化算法流程图

（1）生成初始种群。

（2）进行种群个体的适应度值评估。

（3）通过新的策略、交叉、变异操作得到新的个体。

（4）判定个体的适应度值是否大于上一代个体的适应度值。

（5）取适应度值好的个体进行下一轮迭代。

（6）基于历史适应度值更新自适应因子。

（7）判定迭代次数是否到达最大值，若是，则输出最优解；若否，则进行适应度值计算并继续进行步骤4。

4 实验研究

4.1 Matlab 仿真对比实验

为了验证新策略的运行稳定性和收敛速度较“DE/average/2”有所提升，任意设计一个自由曲面作为仿真对比试验中的实验对象，如图3 所示，该曲面的曲面表达式为Z=3x2+y2+6。

图3 Matlab 仿真实验自由曲面

在该曲面上随机选取50 个点作为测头移动路径的测点，取其中10 个点的坐标，见表1。

表1 三维坐标点

使用Matlab2021b 分别编写基于文献[7]中提到的策略“DE/average/2”和基于本文提到的新策略的两种差分进化算法，在两个代码程式中，初始种群数目均为10 000，种群元素值的上下限均为500和-500，初始变异因子为F0=0.6，交叉概率为CR=0.1，自适应参数为adaptF=F+rand()×0.1，分别用两种算法对50 个测点进行最优路径规划，同时使用重复启动策略对两种算法运行后的数据进行多次比较，优化轨迹和优化过程曲线如图4 和图5所示。

图4 使用 DE/average/2策略生成的优化路径和优化过程曲线

图5 使用新策略生成的优化路径和优化过程曲线

两种策略的最优路径长度和优化时间见表2。

表2 仿真对比实验数据

从表2 中可以看出，“DE/average/2”策略的三次仿真实验的平均路径长度为142.05 mm，平均优化时间为76 s，而本文提出的新策略的三次仿真实验的 平均路径长度为126.57 mm，平均优化时间为68 s，因此可以得出新策略相较于 “DE/average/2”策略在优化速度和收敛精度上都提高了10%左右。

而从图4 和图5 的仿真对比试验优化路径图和优化过程曲线中可以看出，“DE/average/2”策略在4 000 代之后曲线仍在收敛，且收敛精度保持在143 mm 左右，而新策略在4 000 代之后曲线趋于平稳，且收敛精度保持在128 mm 左右，说明新策略相较于“DE/average/2”策略在求优稳定性和收敛速度上要好。

4.2 实际检测对比实验

通过使用德国的ZEISS SPECTRUM 三坐标测量机来进行实验参数曲面的检测实验，在选择机器参数时，测球直径选择3 mm，固定的定位和回退距离设置为5 mm，测头的移动速度为10 mm/s，分别对使用“DE/average/2”策略的差分进化算法和优化策略后的差分进化算法的50 个测点进行最小路径检测，检测过程如图6 所示，在检测过程中，使用图3 曲面，并分别对两种策略算法进行计时，统计的实验结果见表3。

表3 实际检测实验对比数据表

图6 检测过程

从表3 的数据中可以看出，在实际的测点检测过程中，新策略求优的耗时和收敛精度相较于“DE/average/2”策略都减少了10%左右。

5 结语

在自由曲面测点路径优化问题上，使用新策略的差分进化算法在测量路径最小值求解的稳定性上有较好的提升；就求优速度以及最小值收敛精度两方面，无论是在仿真实验还是实际检验中，这两方面的数据结果都提升了约10%，大大提高了实际生产中的效率。虽然改进的新策略在稳定性方面要好于“DE/average/2”策略，但仍有较低的概率出现最优值过大的问题，需要进一步的改进。