基于改进遗传算法的激光切割协同作业路径规划

周锐 马汉武

摘  要：多激光切割机同时进行同一块板材的加工作业，不仅能够提高效率，还能够应对大规模定制的要求。但是由于加工路径规划不恰当，会使激光头受损，成本大幅增加，效率也并未提升，因此，研究激光切割协同作业的路径规划具有十分重要的意义。文章以总路径最短作为规划目标，考虑空行程切割和切割冲突两种情况，建立激光切割协同作业路径的多旅行商模型，提出了一种改进遗传算法。结果表明，与传统遗传算法相比，引入局部算子的遗传算法能够在相应约束条件下求出最优路径，而且收敛更好，计算时间更快。

关键词：路径规划;遗传算法;激光切割;协同作业

中图分类号：F273    文献标识码：A

Abstract： The use of multiple laser cutting machine at the same time for the same piece of plate processing operations， not only can improve efficiency， but also to deal with the requirements of mass customization. But the processing path planning is not appropriate， the laser head will be damaged， and the cost increased significantly， the efficiency has not been improved. Therefore， the study of laser cutting collaborative operation path planning has very important significance. In this paper， the planning objective is to minimize the total path， and considering the two situations of empty stroke cutting and cutting conflict. A multiple traveling salesman model is established to plan the collaborative work path of laser cutting， and an improved genetic algorithm is proposed. Compared with the traditional genetic algorithm， the genetic algorithm with local operators can find the minimize path under the corresponding constraints， and has better fitness and faster calculation time.

Key words： path planning; genetic algorithm; laser cutting; cooperative operation

0  引  言

近些年来，我国开始着力开发高质量、高精度和高创新的制造系统[1]。激光切割技术已经逐渐成为一种常见的切割加工方式，相较于目前企业运用较广的几种切割方法，激光切割具有加工范围广、速度快、精度高等优势[2]。随着激光切割技术的民用化，激光切割车间应运而生，而多台激光切割机的协同作业可以更快地完成板材零件的加工任务，便于企业应对顾客大规模定制的需求。多机作业时需要确保每一台激光切割机的加工路径最短，并且在作业过程中不会出现“碰刀”的情况[3-5]。如何规划激光切割车间的切割机协同作业路径，节省加工成本，减少加工时间，提高加工效率是需要解决的问题。

目前，对于激光切割路径规划的研究主要集中在单机作业和智能算法优化两个方面，取得了一定的成果。刘会霞等[4]在保证有效切割零件和切割零件质量的基础上，提高激光切割的生产率，基于图论学理论，建立了激光切割路径规划的数学模型，给出了最优行程规划。杨建军[5]将激光切割路径优化归纳为TSP问题，并改进了遗传算法。提高了算法的优化性能，改进了交叉操作与变异操作，有效地对激光切割路径进行了优化。Hajad[6]提出了一种模拟退火算法与自适应大邻域搜索（ALNS）相结合的方法，以优化激光切割过程中的路径。该优化算法基于广义旅行商问题（GTSP），可以较好地解决数据库中的多个数据集问题，在路径距离和计算时间之间取得最优解。王娜[7]为了进一步优化切割路径，缩短切割时间，基于广义旅行商问题（GTSP），采用双向蚁群算法进行激光切割的路径优化，针对激光切割过程中，根据切割路径的特殊性，设计了不同搜索方向的引导问题，从而避免了“碰刀”的情况发生，与原来的算法相比，行程变短，时间减少，具有优势。以上的研究均从智能算法的角度成功对激光切割路径进行了优化，减少了切割路径，缩短了切割时间，提高了切割效率。但是，还存在着一些不足：只考虑了单机加工的问题，没有考虑过多机协同加工模式下的路径规划问题。

在多机协同作业的研究中，Senthilkumar[10]利用生成树算法对机器人的协同探索作业进行了研究，但是得到的結果中，重复路径过多。Seyyedhasani[11]通过禁忌算法对3台拖拉机的协同作业路径进行了优化，提高了工作效率，但并未处理路径冲突问题。罗志远[12]利用分布遗传算法解决了多无人清洁车的协同作业全局规划，成功将这种路径规划问题转化为多旅行商（MTSP）问题，但是对于路径冲突问题依然没有研究。

本文研究了激光切割协同作业的路径规划，充分考虑作业冲突问题，建立了激光切割协同作业的多旅行商问题（Multiple Traveling Salesman Problem， MTSP）数学模型，提出了带有局部算子的遗传算法，在满足各种约束条件的前提下，缩短切割路径并减少切割时间。

1  问题描述与建模

1.1  问题描述

激光切割钣金零件，切割区域是由直线、曲线、圆和圆弧组成的闭合轮廓，如图1所示，我们将这个闭合轮廓定义为闭环（Loop），如果这个闭环内还存在其他轮廓，则称外部闭环为父环（FatherLoop），而内部闭环则称为子环（SonLoop），构成这些闭环的线段为边（E），这些边的端点称作顶点（V）。

图2为一块待加工钣金，由四个待切割零件构成，其中有五个闭环，定义闭环集合L：

L=L，L，…，L， k=0，1，2，3，4，5                                      （1）

特征点的集合V：

V=V， k=0，1，2，3，4，5， i=0，1，2，…，n                                  （2）

單机激光切割的过程是从机床原点出发，快速抵达第一个闭环的特征点，完成切割后，快速移动到下一个闭环的特征点，依次往复，直至切割完所有待切割零件，最后返回机床原点。激光切割协同作业的过程可以看作是多个激光头同时对材料进行加工，如图2所示，激光器1对零件1和零件2进行切割，为避免激光头在移动过程中经过已切割区域，从原点出发，抵达

V开始对零件2进行切割，再到V对零件1进行切割，最后返回原点;激光器2对零件3和零件4进行切割，为防止含有子环的零件因为重力掉落，从原点出发，抵达V对零件3进行切割，再到V对零件4的子环进行切割，然后到V对零件4的父环进行切割，最后返回原点。

根据上文所述的激光切割过程，激光切割协同作业路径规划问题，就是在满足约束条件的前提下，使总加工路径和总加工时长最短。

1.2  数学建模

将激光器看作多旅行商问题中的旅行商，待加工零件上的初始特征点为城市，一个零件上的所有特征点构成一个城市集合。求激光切割协同作业的路径规划问题就转化为求解MTSP问题，定义如下：给定m个激光器，n个待加工零件，使所有激光器的总切割路径最小，每个零件只会有一个激光器到达。所有的激光器从同一个原点出发，然后返回同一个原点（原点不记作城市）。每个切割器至少需要切割一个零件，最多P个零件。

其中，特征点和切割路线可以用无向完全图表示G=V，E，V表示所有特征点的集合，V表示机床原点，E表示特征点之间距离的集合。将整个钣金看作一个坐标系，则每一个特征点V都可以用一个坐标x，y进行表示，E表示从特征点V到V的路径，距离记作S。定义一个二进制变量X表示从特征点V到V的路径状态，如果E在选中的路径中，则X=1，否则，X=0，因此，本文的问题可以建模为：

D=minCX                                            （3）

条件约束为：

X∈0，1， E∈E                                            （4）

X=m                                                （5）

X=m                                                （6）

X=1    j=1，2，…，n-1                                       （7）

X=1    i=1，2，…，n-1                                       （8）

u-u+PX≤P-1， 1≤i≠j≤n-1                                      （9）

式（5）和式（6）確保有m个激光器从原点出发并且返回，式（7）和式（8）确保每个特征点只有一个激光器通过，式（9）是子闭迹消去约束[14]，用来防止没有机床原点的情况下生成路径，u表示任何一个激光器抵达一个特征点的数量。

2  带有局部算子的遗传算法

为了求解多旅行商问题，提出带有局部算子的遗传算法进行求解。设计两个新的局部算子：分支定界算子和交叉消除算子，以加快搜索过程的收敛速度，提高解的质量。

2.1  传统遗传算法

遗传算法（Genetic Algorithm， GA）是基于达尔文进化论和遗传学理论，根据大自然中生物体进化规律而设计提出的。是模拟自然选择和生物进化过程的一种数理模型，是一种通过模拟演化自然进化过程来解决最优解问题的方法。经过优胜劣汰的自然选择，适应环境能力比较强的个体或者基因，会被保留下来，而适应能力比较弱或者完全无法适应的个体或者基因就会被淘汰[15-16]。

遗传算法通过一系列选择、交叉和变异的过程，不断重复这些流程，最终得到一个比较优秀的解。具体步骤如下：

步骤1：确定个体编码的方式，并且设定好遗传参数;

步骤2：写出适应度函数;

步骤3：以问题为导向，设计遗传算子;

步骤4：初始化种群;

步骤5：计算适应度函数;

步骤6：通过选择部分染色体作为父代进行遗传操作;

步骤7：对选择出来的父代基因进行交叉;

步骤8：对选择出来的父代基因进行变异;

步骤9：不断进化，取一个合适的遗传代数，记录最优个体;

步骤10：更新种群，重复步骤5到步骤9;

步骤11：进化终止，得到最优解。

2.2  带有局部算子的遗传算法

（1）种群初始化编码

每条染色体由n+m-1个基因组成，前n-1个基因代表激光器抵达特征点的排列，剩下的m个基因表示每个激光器能够到达的特征点的数量。因为所有激光器必定从机床原点出发和返回，所以这个特征点不包括在染色体中，以节省内存。然后生成多个染色体，这些染色体组成初始种群。

（2）适应度函数的设计

遗传算法的适应度函数的设计，要考虑激光切割协同作业任务的均衡调度问题。这种问题相当于已经分组好的TSP问题，直接使每组的路径最短即可：

L=1                                     （10）

式（10）中，L为适应度值，x，y为各点的坐标。适应度值与各组点的距离之和成反比。

（3）变异操作

根据设计的染色体。染色体中第一部分中的特征点只能出现一次，第二部分的基因值之和必须等于特征点的总数。因为这些约束条件，所以采用优化的遗传算子改进进化机制。

染色体的第一部分，有两种变异操作方法，分别是随机交换和反向交换。随机交换就是选择两个不同的随机位置G和G，其中i≠j，这两个基因进行交换。反向交换就是选择两个随机的基因片段，片段内基因的位置颠倒。

染色体的第二部分，即每个激光器能够到达的特征点数，采用随机分布变异法。随机选擇两个不同的位置i和j，其中i

≠j，G增加1，G减少1，然后确保G≥1且G≤P。P为特征点的最大数目。

（4）交叉操作

利用边缘重组交叉算子[17]修改交叉染色体的第一部分。这种方法能够有效地解决MTSP问题。这个算子的交叉思路是，如果一条编码出现在双亲染色体上，它被认为是一个好的基因，并且有更高的机会出现在最优解中。

（5）局部算子操作

局部算子是使用局部搜索技术，引入贪婪染色体片段，为了防止早熟收敛，只对特定的遗传代数和种群中前五个个体进行操作。引入两个局部算子：交叉消除算子通过对激光器到达特征点顺序的重新排列，缩短总加工路径;分支定界算子为了从一条加工路径出发，为一部分特征点构成的集合选择最优路径。

交叉消除算子会积极搜索加工路径内部形成的交叉，并通过重新排列特征点顺序来消除交叉。激光协同加工中的交叉一般可以分成两个类型：单个激光器加工路径交叉和多个激光器加工路径交叉。为了得到最优解，建立一个包含所有解的列表，按降序形成求解序列，如图3（b）所示，交叉消除得到的结果可能会使路径变短，也可能像图3（c）一样变长。所以，需要经过几个周期（最多5个）的迭代或在没有明显改进时停止求解。

分支定界算子基于分支定界算法，用于求解离散组合优化问题，通过状态空间搜索，所有候选解形成一个集合，不断对集合的子集进行比较，得到最优解。利用分支定界法对所有特征点重新排序，将MTSP问题转化为TSP问题，得到局部最优路径，如图4所示。

2.3  算法流程

本文提出的带有局部算子的遗传算法，完整过程如图5所示：对多个激光器和带切割零件的特征点进行编码，成为染色体;计算整个流程的适应度;优先检查目前的加工零件是不是最优路径，是的话直接输出结果，否则，进行下一步;对个体执行选择、变异和交叉操作;因为激光切割的特殊性，为了防止空行程经过切割区域和“碰刀”现象，采用局部算子进行优化;根据终止的标准：达到一定的遗传代数，或者得到的结果不再有显著的改善;最后输出最优路径。

3  仿真实验与结果分析

根据本文的算法，采用MATLAB编程对多机激光切割协同作业的路径进行规划，实验对象为一块待切割板材，按照表1参数对切割路径进行规划，在计算时间和路径长度上，与现有的MTSP求解方法进行比较。电脑开发环境为：Win10、

Matlab2014b和I5-8400H。

在激光切割协同作业中，对于引入局部算子的优化曲线仿真如图6所示。其中x轴表示遗传代数，y轴表示路径总长度，正方形实线表示传统遗传算法的收敛，圆圈实线表示引入分支定界算子的收敛，正三角形实线表示引入交叉消除算子的收敛，倒三角形实线表示引入两种算子的收敛，可以看出引入两种算子的遗传算法随着解的规模越大，收敛越快。

5个激光头使用两种算法得到的路径如图7和图8所示。从图7中可以看出，得到的路径规划无法避免交叉点，即会出现“碰刀”或者是空行程经过已切割零件区域的情况，而图8引入交叉消除算子和分支定界算子之后，避免了这种情况的发生，在约束下找到了路径最优解。

通过分析可知，带有局部算子的方法能够在避免空行程切割和碰刀的约束条件下使激光协同作业的路径最短，但是从表2还可以看出，虽然算法的收敛程度很快，解决问题时间很快，在约束条件下的路径是最优的，但是相比于没有约束时遗传算法求得的路径长度，加入约束之后的路径变长了。

4  结  论

将多机激光切割协同作业路径规划问题转化为带有约束条件的多旅行商问题，基于避免空行程经过已切割区域、碰刀现象等工艺约束条件，引入两种算子优化遗传算法，能够很好地解决加工路径规划的问题。算法的收敛程度优秀，求解时间相对短，但是求得最优路径，相比无约束的切割路径是变长的。下一步针对如何再度计算更短的切割路径，研究通过引入其他算法，或者是提前对钣金待加工零件进行排样优化，进一步去缩短多机激光切割协同作业的路径。

参考文献：

[1] 周济. 智能制造——“中国制造2025”的主攻方向[J]. 中国机械工程，2015，26（17）：2273-2284.

[2] P A Hilton. The early days of laser cutting[C] // 11th Nordic Conference in Laser Processing of Materials， 2007：20-22.

[3] 张素云，杨勇生，梁承姬，等. 自动化码头多AGV路径冲突的优化控制研究[J]. 交通运输系统工程与信息，2017，17（2）：83-89.

[4] 肖珂，高冠东，马跃进. 基于Kinect视频技术的葡萄园农药喷施路径规划算法[J]. 农业工程学报，2017，33（24）：192-199.

[5]  Bochtis D D， S？覬rensen C G， Busato P. Advances in agricultural machinery management： A review[J]. Biosystems Engineering， 2014，126（39）：69-81.

[6] 刘会霞，王霄，周明，等. 共边排样件激光切割路径的规划[J]. 中国激光，2004（10）：1269-1274.

[7] 杨建军，刘保业，鞠录岩. 激光切割路径优化的双重编码改进遗传算法[J]. 解放军理工大学学报（自然科学版），2012，13（6）：684-687.

[8]  Hajad M， Tangwarodomnukun V， Jaturanonda C， et al. Laser cutting path optimization using simulated annealing with an adaptive large neighborhood search[J]. International Journal of Advanced Manufacturing Technology， 2019，103：781-792.

[9] 王娜，王海艳，姜云春. 激光切割工艺路径的双向蚁群算法优化[J]. 锻压技术，2020，45（11）：30-35.

[10]  Senthilkumar K S， Bharadwaj K K. Multi-robot exploration and terrain coverage in an unknown environment[J]. Robotics and Autonomous Systems， 2012，60：123-132.

[11]  Seyyedhasani H， Dvorak J S. Reducing field work time using fleet routing optimization[J]. Biosystems Engineering， 2018，169：1-10.

[12] 羅志远，丰硕，刘小峰，等. 一种基于分步遗传算法的多无人清洁车区域覆盖路径规划方法[J]. 电子测量与仪器学报，2020，34（8）：43-50.

[13] Liang M A. Artificial Ant Algorithm for Constrained Optimization[J]. 系统科学与系统工程学报（英文版），2001，10（1）：57-61.

[14]  C E Miller， A W Tucker， R A Zemlin. Integer Programming Formulation of Traveling Salesman Problems[J]. ACM， 1960，7（4）：326-329.

[15]  Prinetto P， Rebaudengo M， Reorda M S. Hybrid Genetic Algorithms for the Traveling Salesman Problem[M]. Artificial Neural Nets and Genetic Algorithms. Springer Vienna， 1993：559-566.

[16]  胡志伟，郄培，赵新超，等. 一种新的混合遗传算法求解旅行商问题[J]. 计算机与现代化，2010（11）：12-15.