在激光切割中待切割的轮廓轨迹一般都是封闭图形，不同的封闭图形可以看作一个个独立的图元，切割时从一个图元切换到另一个图元的行程称之为激光头的空行程，此时激光头处于关闭状态。显然，减少空行程可以实现时间（与之相比软件计算的时间差可忽略）和能量的节约，这就涉及到激光切割路径优化问题，可以归结为旅行商问题（travelling salesman problem，TSP），待加工图形中的图元类似于TSP中的城市。但是，对于每个图元切割起点的选择不同，空行程的距离会不一样，由于每个图元的切割起点（也叫打孔点）可以是图形上的任一点，故此处有两个问题需要解决：图元（轮廓）间的路径规划问题以及图元内的切割起点的选择问题，该问题可归结为节点可变的广义旅行商问题（generalized travelling salesman problem， GTSP）［4］。
目前，对GTSP问题求解的智能算法有很多，文献［5］应用改进的蚁群算法，先用蚁群算法得到初始路径，再应用最近邻插入算法对路径进一步优化，其缺点是对每个轮廓的切割起点如何确定没有明确给出；文献［6］提出了基于双染色体遗传算法的切割路径规划方法，文献［7］对每个轮廓的交叉点预设了节点，作为切割起点的备选点，这样就可以对每个轮廓的节点之间的距离做优化处理。文献［8］建立了GTSP模型，对每个轮廓预设了一组节点，选最合适的节点作切割起点，再用蚁群优化算法解决最优问题，文献［6-8］的缺点是切割起点只选在预设的交叉点上，这样的方法限制了找到更好的优化路径的灵活性。文献 ［9-10］不仅在每个轮廓的交叉点放置一套预设的节点，而且还人为地在轮廓外围加了更多的节点作为备选的切割起点，这种方法扩大了搜索区域以找到更优路径。但是缺点是由于预设的切割起点是沿轮廓外围主观给定的，故方法不一致，不可复制。 因此，有必要探索一种选取切割起点的方法以及确定近优路径。本文从图元的特征点提取出发，提出一种基于双链基因的模拟退火算法来求解激光切割中的GTSP问题，仿真测试结果表明，此方法可以很好地优化路径，且耗时少，同时也避免了打刀现象。
1 激光切割问题的数学建模
在TSP中，各个城市的位置一般都在笛卡尔坐标下表示，而图元的表示意味着也必须放在笛卡尔坐标框架里，显然，每个图元的切割起点可以是任何位置。
1.1 图元在路径优化上的数学描述
为了对各个图元选取合适的打孔点，文献［6，11］根据图形的特点确定每个图元的特征点，即备选的打孔点。将封闭轮廓的基本几何曲线段定义为边，相邻边的交点定义为顶点。对于圆形的图元一般选择其若干等分点作为顶点。钣金件中的零件环数记为n，第i个环记为 Li，（i = 1，2，…，n），环Li的顶点数量记为mi，则第i个环的第j个顶点可记为pij，则环 Li 的特征点集合记为｛pij｝，图1给出了几种常见图形的特征点确定方法，各零件的切割起点从其特征点集合中进行选择。此种方法比较简单。显然此处对切割取点的选取，如果局限于轮廓的定点，会影响最优路径的结果。此处如果在轮廓上动态增加适量顶点，既可改善优化效果，又不至于大幅增加计算耗时。比如在各图元上可以根据图形的形状及位置特点随机增加特征点的个数，以提高获得更优路径的可能性。
<G:\武汉工程大学\2023\第3期\常翠芝-1.tif>
图1 不同特征的轮廓特征点的确定
Fig. 1 Determination of contour feature points
1.2 切割路径的描述
钣金件排样完成后可以开始切割，切割过程为：激光头从机床原点出发，依照程序给定的顺序对零件轮廓依次切割，完毕后激光头回到机床原点。如图1的不同轮廓之间的连线，就是一条完整的激光头行走的轨迹。如图2所示，其中｛ ｝ 内表示一个环的切割顺序，每个｛ ｝内第1个特征点为各图元的切割起点［6，11］。
此处直接将每个零件的切割起点确定在零件轮廓上，这种简化对路径的优化结果影响极小。每个轮廓在每次选取的切割路径上只有一个切割起点。见图1的连线。
1.3 切割路径规划的数学模型
激光切割路径优化问题优化目标为： 空行路程最小。若待切割的轮廓数记为n，第i次的切割路径空行程记为di，某个环的切割起点为 Pi （xi， yi），其下一个环的切割起点为 Pi + 1 （xi + 1，yi + 1 ），机床原点记为P0（x0，y0），则激光切割的总空行程为：
[di=i=0nxi -xi+12+yi-yi+12+x0 -xn2+y0-yn2] （1）
式中，优化的约束条件是：激光切割路径不能经过已经切割的区域，防止出现“打刀”现象而损坏激光头［12］。
2 模拟退火算法参数规划
2.1 模拟退火算法
模拟退火算法（simulated annealing，SA）的基本思想来源于物理退火原理［13-14］：从初始温度开始，在搜索空间上生成一个初始解，然后对温度进行更新，此时模拟粒子在一定温度下的移动状态，将更新后产生的新解与旧解进行对比，在Metropolis准则［15］下进行迭代。Metropolis准则定义了物体在某一温度下从状态i转移到状态j 的内能的概率，其表达式为：
[pTij= 1? ? E(j)≤E(i)exp-Ej-EiKT=e-ΔEKT? others ] （2）
式中：[E(i),E(j)]分别为粒子在状态 i、j下的内能，?E 为内能增量，K 表示玻尔兹曼常数，T为当前的温度，该式根据内能最低的原则去接受新的状态，即：以概率1接受更优解，但也会以某种概率接受较差解［16］，以此来跳出局部最优解，有效地避免收敛过快及精度不高的现象，显然T值越大，接受新解的概率越高。
2.2 模型的参数规划
路径的每次空行程值总和对应于粒子的内能，对每次的行程计算要尽可能跳出局部最优，由于模拟退火算法的近优解常出现在退火低温区，所以温度更新函数表达式改进为：
[Tk=αTk-1=αkT0] （3）
式中： T0为退火初始温度，[α]为退火常数，常取 0.80~0.99，k为模拟退火迭代次数，显然，T0通过快速退火方式，能够提升算法的运行速度，更快地得到近优解。
2.3 双链基因模拟退火算法规划
前文已经分析，激光切割路径规划面临两个问题：图元之间的路径规划问题和图元内切割起点的选择问题。为了解决这两个问题，本文采用双链基因模拟退火算法，同时算法要注意避免切割中的“打刀”问题。
算法的主程序包括两个循环：内循环和外循环，外循环是温度变化控制的循环，内循环设定了每个温度下一定的迭代次数以确保尽可能跳出局部最优。迭代次数的大小也称为马尔科夫链长度。
程序包含对待加工的多个图元按序编号并在相应的图元上标识；对每个图元取点（提取多个特征点）及坐标的信息存储；每个图元切割点的选取及初始路径的产生；路径更新；距离的计算等。
（1）图元切割点的存放：为了避免在同一轮廓多次取到切割点或者漏取，将轮廓序号和轮廓的坐标序号用元胞数组的形式存放，例如，第k个图元的特征点的坐标储存在第k个元胞里，对每个图元选取的特征点按序编号，依次存入。
（2）初始路径的生成：比如要对5个轮廓（cont_n=5）进行切割，利用随机函数生成一个序列。
（3）切割路径的表示：为了防止出现“打刀”现象，此处应用双链基因序列表示，比如生成的五个轮廓的切割顺序是4->5->2->1->3，在这5个轮廓上选取的切割点的序号分别是3，2，5，8，3。那么双链路径的表示为：[path=4 5 2 1 33 2 5 8 3]。
（4）路径的更新：分别设定交换法和位移法产生新路径的概率p1和p2，利用随机函数rand（1）生成的数值分别与两者比较，若rand（1）<p1，利用path0（2，i）=ceil（rand*dots），对每个轮廓随机取点；若rand（1）<p2，则随机选取路径中c1：c2的列，利用翻转函数fliplr（path），将路径按序左右翻转产生新路径。
2.4 算法的程序流程
基于模拟退火的算法原理和GTSP模型，本文制定了双链基因路径：给定算法参数，如初始温度T0，马尔科夫链长度，显然，初始温度越高，马尔科夫链越长，搜索就越充分，就越可能得到最优解，但是缺点是比较耗时，所以为了兼顾计算效率，设定每个温度下的迭代次数Lk，以及最大迭代次数maxgen，温度衰减系数alpha； 算法的程序流程如图3所示。
<G:\武汉工程大学\2023\第3期\常翠芝-3.tif>[图3 算法流程框图
Fig. 3 Algorithm flow diagram
][开始][生成初始路径path0，计算空行程距离][设定n（Tk），n=0][产生新路径path1，n=n+1，计算空行程距离
d1=dist（path1）计算Δd=d1-d0][Δd<0][Y][Y][N][N][N][Y][n>n（Tk）][k=k+1降温][k<maxgen][N][Y][停止][内循环][外循环][path0=path1
d0=d1][exp（-Δd/Tk）>ξ，ξ∈U（0，1）]
3 仿真实验与比较分析
3.1 仿真参数设置
基于 MATLAB R2021a版本进行路径规划的仿真实验。采用双链基因模拟退火算法进行实验运算。为了验证算法的普遍适用性，实验对象随机选取了一朵花，见图4，可以看出这朵花由多个不规则的封闭图元组成。综合考虑马尔科夫链长度和温度衰减系数及计算耗时对结果的影响，本文搜索参数设置为：maxgen = 2 000，退火初始温度T0=100，温度衰减系数α=0.98，切割的起点和终点为原始坐标点（0，0）。
3.2 仿真结果分析
对该花朵图案的图元进行编号：1~47；对每个图元动态取特征点并保存为元胞矩阵，从仿真结果图5和图6可以看出，在迭代次数大约为500的时候搜索到的优化路径为：［3 11 12 8 10 13 16 17 15 18 22 21 24 25 26 23 20 41 42 43 44 45 46 47 27 28 29 30 33 32 31 34 35 40 39 38 37 36 19 6 14 5 9 7 4 2 1 48；6 2 2 2 3 4 5 1 4 11 3 3 3 2 3 2 5 1 1 2 2 1 2 2 2 2 2 2 1 1 2 1 1 1 1 1 1 2 2 8 1 10 1 5 1 1 4 1］，此时最优值是：2.065 1×103像素，历时 23.309 037s。同时可以看出，优化路径没有激光头重复经过同一区域的现象，即有效避免“打刀”现象，且空行程值也相对比较小。
<G:\武汉工程大学\2023\第3期\常翠芝-5.tif>
图5 优化路径标识
Fig. 5 Marking of optimization path
<G:\武汉工程大学\2023\第3期\常翠芝-6.tif>[0 500 1 000 1 500 2 000
迭代次数 / 次][9 000
8 000
7 000
6 000
5 000
4 000
3 000
2 000][路径长度 / pik]
图6 迭代次数及最优目标值曲线
Fig. 6 Curve for iterations number vs optimal target value
3.3 优化加工路径与计算机辅助制造（computer-aided-manufacturing，CAM）加工路径对比
为了验证和对比优化效果，选择HANS_ G6020-C1PA8000/激光HANSIPG2500W的机型，其激光功率为2 500 W，X，Y轴的快移速度为100 m/min，机床的加速度为1.0 G；板材材质：Steel，板材尺寸：791.0 mm×880.0 mm厚度=3.0 mm，零件数量：1，零件尺寸：771.0 mm×860.0 mm。零件质量：6.880 kg，板材质量：16.29 kg。以相同的图案作为切割对象，本智能算法优化切割路径和CAM自带优化切割路径作对比，为了合理评估智能算法的优化效果，轮廓加工起点没有考虑在废料区选取，对比效果如图7所示。
<G:\武汉工程大学\2023\第3期\常翠芝-7-2.tif><G:\武汉工程大学\2023\第3期\常翠芝-7-1.tif>[ a ][ b ]
图7 模拟退火算法和CAM优化算法应用对比（无微链接）：（a）模拟退火算法优化的切割路径，（b）CAM带优化的切割路径
Fig.7 Comparison between SA algorithm and CAM
optimization algorithm （without microlink）： （a） optimized cutting path by SA algorithm，（b） cutting path by CAM
optimization algorithm
本SA算法对本次切割的空行程路径为4 687 mm，比CAM自带优化的切割空行程少了16.25%，并且没有穿过已切割区域，而CAM自带优化的路径有4次穿过已切割区域。
为了贴近实际切割情况，本文也考虑到增加微链接的实验对比，效果如图8所示，此处选择穿孔数为103。加了微链接后，所有空行程路径都有所增加，使用SA算法的空行程路径为6 978.2 mm，比使用CAM软件规划的路径空行程7 797.3 mm短了10.5%，模拟退火算法规划的路径仍然没有经过已切割区域，但是CAM自带优化软件规划路径经过已切割区域却有3次。
<G:\武汉工程大学\2023\第3期\常翠芝-8-1.tif><G:\武汉工程大学\2023\第3期\常翠芝-8-2.tif>[ a ][ b ]
图8 模拟退火算法和CAM优化算法应用对比（带微链接）：（a）模拟退火算法优化的切割路径，
（b） CAM带优化的切割路径
Fig. 8 Comparison between SA algorithm and CAM
optimization algorithm （with microlink）：（a） optimized
cutting path by SA algorithm ，（b） cutting path by CAM
optimization algorithm
5 结 论
以上数据表明了模拟退火算法在激光切割路径规划的优越性，可以看出本文的模拟退火智能算法优化的路径与CAM自带的优化软件规划的路径相比，都有很好的效果。
（1）未加微链接的情况下，本智能算法空行程明显减小。
（2）添加微链接后，意味着是每个轮廓的切割起点从废料区选取，增加的距离在两种路径下都是相等的，所以空行程的改善度看起来会降低一些，但是仍然有明显的改善。
（3）无论是否添加微链接，本文模拟退火算法均可完全消除经过已切割区域的现象，而CAM自带优化软件规划路径有多次交叉，且有多次经过已切割区域，显示智能性较差，存在损坏激光头的风险。
值得特别说明的是，如果待切割图形中有图元包含一个或者多个子图元的情况，在数据表示时，仍然可以采用子元胞数组的形式实现图元编号与特征点序列号的捆绑而不至于出现“打刀”现象。此外，此方法中，对于图元相对较多的案例（如本案例，选取的迭代次数在1 000~1 500效果较好），如果选择的最大迭代次数过小，则会影响较优路径的获取效果。反之，如果最大迭代次数较大，则耗时相对较长，此时可以用添加收敛系数的方法加速收敛。