基于改进遗传算法的自由曲面测量路径优化＊

2022-06-13徐传法王士军李建宏齐娜

制造技术与机床 2022年6期

徐传法王士军王冉李建宏齐娜

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

随着科学技术的不断进步，机械产品的结构越来越合理，复杂曲面类零件被广泛的应用在动力能源、航空航天和工业等领域，其形状误差对其所构成产品的质量和性能起着直接的决定性作用，研究高效率、高精度的测量技术具有重要的理论意义和实际应用价值[1]。在对大型复杂曲面测点检测时，曲面需要被检测的点是非常多的，为了提高检测效率，需要找到一条最优的检测路径，既能不重复的走过所有的点，还要使其走过的路径最短。

国内外学者对于路径优化问题方面做了许多的研究。高延峰等将遗传算法运用到求解自由曲面测量路径优化问题上，把该问题简化成旅行商问题，试验证明遗传算法结构简单而且具有很强的优化能力[2]；高国军等提出了贪婪选择杂交算子，有效地提高了大规模路径优化的收敛速度和稳定性，并且对遗传算法过程中的控制参数进行了优化，给出了适合不同规模路径优化问题的控制参数取值[3]；Tuncer D 等提出了改进的变异算子，避免早熟的同时提高了算法的效率[4]；Srinivas M 等提出了自适应算法，个体的交叉概率能够随个体的适应度发生改变，防止陷入局部最优的同时提高了算法的效率[5]；石红国等提出一种 Hopfield 神经网络与归约方法相结合求解TSP 路径优化的方法，使Hopfield 神经网络不再只适用于求解小规模城市路径优化问题[6]。

文献[2]中，把遗传算法运用到自由曲面测量路径优化问题中，但并未对遗传算法收敛速度慢、易陷入局部最优解等问题做更深入研究，基于以上问题，本文设计了改进的遗传算法，实验结果表明，改进的遗传算法能够更高效且优质地完成自由曲面测量路径优化问题。

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

三坐标测量机测点检测过程中测头的具体运动过程如图1 所示。首先测头快速定位到A点，再以检测速度沿路径AB往B点移动，当检测完B点后，再以回退速度移动到C点，然后测头再快速定位到D点重复刚才的运动过程。无论检测路径如何变化，AB段（a段）与BC段（b段）的运动过程总是固定不变的，为简化求解过程，不考虑测量过程a与回退过程b这种固定不变的路径，只计算c这种影响总路程的路段，此时的测点检测过程就被简化成了类旅行商（TSP）问题。

图1 局部检测路径示意图

自由曲面测点检测过程与旅行商问题的主要区别在于：

（1）当测头检测完最后一个测点时，测头不需要回到初始测点。

（2）旅行商问题中用到的城市坐标是二维坐标，而自由曲面测点的坐标是三维的。

2 遗传算法简介

遗传算法（genetic algorithm，GA）最早是由美国的 John Holland 于20 世纪70 年代提出，该算法效仿大自然“物竞天择，适者生存”的演化规律来求解各类问题。遗传算法把问题参数编码为基因，把问题的解编码为染色体，然后对各个染色体进行选择、交叉和变异等操作，通过迭代来不断优化各个染色体中的信息，以优胜劣汰的方式最终生成一条较优的染色体作为问题的解。

3 改进遗传算法的设计

3.1 编码方式

采用自然编码方式，每个自然数表示1 个要检测的测点，例如一个染色体的基因串为26 379，则表示测头从2 号测点出发，顺序经过6、3、7、9号测点完成该条路径的检测。

3.2 适应度函数

遗传算法在寻求最优解的过程中仅依据适应度函数来选择优质解和淘汰劣质解，算法的求解质量和求解效率与适应度函数的选取密不可分。由于影响总路程变化的只有像c这样的路径段，所以求得的目标函数为，目标函数越小，优化的结果越好，轮盘赌选择算子个体适应度值越大，被选择的概率越高，所以对目标函数做了一次倒数转换，转换后用作适应度函数

3.3 选择算子

采用轮盘赌选择算子，轮盘赌算法的基本思想是：各个个体被选中的概率与其适应度函数值大小成正比，它是为了防止适应度数值较小的个体被直接淘汰而提出的。它的实施步骤为：

（1）计算种群中各个个体的适应度。

（2）通过式（2）与式（3）分别计算各个个体的被选择概率和累计概率。

（3）在区间[0,1]随机选取1 个数x，x落在哪个个体的累计概率区间内，则该个体被选中。

3.4 自适应参数调节

交叉概率和变异概率对遗传算法的性能有着重要的影响，选择合适的交叉概率和变异概率，有利于提高种群的寻优效率和防止局部最优解的出现。在传统的遗传算法中，交叉概率和变异概率在算法迭代过程中是固定不变的，这样不利于遗传算法更好地发挥其性能。许多学者对参数的自适应调节做了研究[7-9]，在此基础上，本文对交叉概率和变异概率的自适应参数调节做了如下设置。

3.4.1 自适应交叉概率调节机制

在种群进化初期，种群个体的适应度比较分散，为增加新个体的产生速度，加快种群整体搜索效率，应该增大Pc的值；在种群进化后期，种群个体适应度比较集中，为使优良个体不被破坏，应该减小Pc的值；另外交叉算子有可能会破坏种群中的优良基因，为使交叉算子能够更好地工作，对适应度差的个体，给与较高的Pc值，使其能够更好地进化；对适应度高的个体，应该减小Pc的值，使优良的基因得以延续；文献[9]以迭代次数作为进化处于何种阶段的评判依据，对终止代数的选取是十分苛刻的，代数设置的太大会对自适应参数调节产生很大的影响。如图2 所示。

图2 优化过程

对50 个城市寻求最优路径，在遗传算法其他部分相同的情况下，算法a 未使用自适应调节机制，算法b 使用文献[9]的自适应调节机制，从图2a 与b 的比较可知，在终止代数为2 000 的情况下，优化过程已无明显差异，自适应参数调节机制几乎失去作用。基于以上考虑，本文在文献[9]的基础上做了以下改进。

式中：Pci为种群中个体i发生交叉运算的概率；Pcmax与当前种群的适应度有关；fmax和fmin分别为当前种群最优个体的适应度和最差个体的适应度；fi为个体i的适应度值；为当前种群的平均适应度值。从式（5）可以看出Pcmax与当前种群个体的适应度分布情况有关。

改进后的自适应调节机制在遗传算法其他部分与前面相同的情况下，对50 个城市寻求最优路径，如图3 所示。

图3 使用改进的自适应参数调节机制

改进的自适应调节机制在终止代数为2 000 的情况下，依然能稳定地发挥其性能，不会因终止代数设置过大而导致自适应调节机制失效。

3.4.2 自适应变异概率调节机制

选取合适的变异概率，有利于保持种群多样性和防止种群陷入局部最优。当种群中个体的适应度值没有太大差距时，种群多样性降低，易陷入局部最优，此时应该增大变异概率，通过变异增加种群多样性，跳出局部最优。另外在种群进化过程中，为延续较优个体，应给与较优个体小的变异概率。基于以上考虑，本文在文献[9]的基础上做了以下改进。

式中：Pmi为种群中个体i发生变异运算的概率；Pmmin与当前种群的适应度有关。

3.5 贪婪交叉算子

贪婪交叉算子能够充分利用染色体的局部信息指导遗传进化搜索。该算子在两条父代染色体的两个基因中使用局部贪婪策略得到一条新的染色体，这样的子代染色体缺乏多样性，容易陷入局部最优解。为防止局部收敛，另一条染色体由整体贪婪策略得到，增加群体多样性。

假如参与交叉运算的父代个体为L1和L2，生成的子代个体为l1和l2，随机产生的初始测点为Gstart。l1以Gstart为第一个监测点，分别计算父代中Gstart与与其右相邻的两个测点Gnext1与Gnext2之间的距离，若Gstart与Gnext1之间的距离小，则下一个测点选Gnext1，反之则选Gnext2，以此类推选出l1染色体上剩余的所有测点。l2的选取遵循整体贪婪策略的规则，以Gstart为第一个测点，计算Gstart与剩余所有测点之间的距离，选取与之距离最短的测点作为下一个测点，以此类推选出l2染色体上剩余的所有测点。

下面用7 个检测点为例，说明贪婪交叉算子的运行过程。7 个测点的坐标分别为：1：（10，12，20），2：（41，26，23），3：（25，58，63），4：（81，55，42），5：（72，31，66），6：（55，43，82），7：（61，28，53），7 个测点之间的距离如表1 所示。

表1 7 个测点之间的距离

假设参加交叉运算的染色体L1和L2分别为（2 3 5 4 6 1 7）和（7 2 1 6 3 4 5），随机产生初始测点为3，右转动使3 成为初始测点。新生成L1'和L2'分别为（3 5 4 6 1 7 2）和（3 4 5 7 2 1 6），则l1的第一个基因为3，分别计算父代染色体中与测点3右相邻的两个测点的距离，得d35=54.29＜d34=59.89，则L1''和L2''分别为（3 5 4 6 1 7 2）和（3 5 4 7 2 1 6），l1的第二个基因为5，以此类推，得到的l1为（3 5 4 7 6 2 1）；l2由整体贪婪策略得到，计算测点3 与剩余所有测点之间的距离，d36＜d37＜d32＜d35＜d34＜d31，则l2的第二个基因为6，以此类推得到l2为（3 6 5 7 4 2 1）。

3.6 贪婪倒位变异算子

贪婪倒位变异算子是基于贪婪策略的倒位变异，首先在一条染色体上随机选取一个基因Gx，计算该基因与左右相邻两基因Gxleft和Gxright之间的距离d1、d2，若d1＞d2,则选Gxleft为待变异基因，反之则选Gxright为待变异基因，再从除Gx、Gxleft和Gxright以外剩余的基因中，选取距离Gx最近的基因Gclose作为另一个待变异基因，在不改变其他基因位置的情况下，交换两待变异基因位置，完成贪婪倒位变异运算。

以L1（2 3 5 4 6 1 7）为例，随机选取的测点为3。先计算测点3 与左右相邻两测点之间的距离d32、d35，d35＞d32则第一个待变异测点为5，再从除3、2 和5以外的剩余测点中选取距离3 最近的基因作为另一个待变异基因，经计算得该基因为6，交换两待变异基因的位置，得到变异后的染色体l1为(2 3 6 4 5 1 7)。

3.7 精英保存策略

为防止选择过程中最优解的丢失和交叉变异过程中最优解的破坏，实施精英保存策略。通过选择、交叉和变异后，复制子代中的最优个体并保存到下一轮的子代中，剩余子代继续下一轮的选择、交叉和变异，用复制的最优个体替代下一轮子代的最差个体。继续实施精英保存策略，直至迭代结束。

4 改进遗传算法结构

改进遗传算法的流程图如图4 所示，基本流程如下：

图4 改进遗传算法流程图

（1）生成初始种群。

（2）计算种群各个个体的适应度值。

（3）通过精英保存策略，复制适应度值最大的个体直接进入子代，其余个体继续进行选择、交叉和变异操作。

（4）判断是否达到最大迭代次数，若是，输出最优解，若否，则返回过程2，计算种群中各个个体的适应度值，用上一轮过程3 复制的最优个体替换这一轮父代中的最差个体，继续下面的迭代过程。

5 实验研究

5.1 仿真实验

设计一个参数曲面作为本次仿真实验的自由曲面，如图5 所示。在该曲面上随机生成100 个点作为路径测点，用Matlab2018a 编写算法程序，初始种群数为250，自适应交叉概率为Pci，自适应变异概率为Pmi，代沟GGAP=0.9，最大迭代次数传统遗传算法和改进遗传算法分别是1 200 和500 代。分别用传统遗传算法和改进遗传算法对这100 个测点求解最优路径，优化轨迹和优化过程如图6 所示，优化的路径长度和时间如表2 所示。

图5 参数曲面

图6 优化轨迹与优化过程

从图6a 与b，c 与d 的比较中可以看出，相比于改进的遗传算法，传统的遗传算法生成的最优路径拐角比较多，且优化代数比改进的遗传算法高很多，通过表2 可以得出，传统的遗传算法出现了过早收敛现象，而且工作效率远不及改进的遗传算法，在路径长度方面改进的遗传算法比传统的遗传算法路径长度缩短6.8%，在程序耗时方面改进的遗传算法比传统的遗传算法时间缩短了75%。

5.2 实际检测实验

参数曲面检测实验在意大利COORD3 三坐标测量机下进行，选择测球直径为3 mm，定位和回退距离为5 mm，触测和回退速度为0.55 mm/s，移动速度为10 mm/s，分别对用传统遗传算法和改进遗传算法优化后的100 个测点路径进行检测，检测过程如图7 所示，并对整个检测过程计时，实验结果如表2 所示。