量子免疫算法求解汽车零件切割路径规划

Quantum Immune Algorithm for Automotive-Parts Cutting Path Planning

摘要: 汽车制造过程需要使用激光对汽车零件切割，为了提高激光切割的效率，对激光切割路径规划进行研究。文章首先建立激光切割路径规划数学模型，然后使用一种改进的量子免疫算法求解该模型，最后将提出的优化算法进行仿真实验并与传统免疫算法、遗传算法和蚁群算法、量子进化算法对比，对比结果表明，改进量子免疫算法在求解该问题时可以有效缩短切割路径的空行程，提高切割效率。

Abstract: In order to improve the efficiency of laser cutting, the path planning of laser cutting is studied. Firstly, the mathematical model of laser cutting path planning is established, and then an improved quantum immune algorithm is used to solve the model. Finally, the proposed optimization algorithm is simulated and compared with traditional immune algorithm, genetic algorithm, ant-colony algorithm and quantum evolutionary algorithm. The comparison results show that the improved quantum immune algorithm can effectively shorten the empty travel of cutting path and improve cutting efficiency when solving this problem.

1. 引言

汽车智能制造关键环节包括汽车零件排样、对排样后各零件的切割。本文主要研究排样后的零件切割路径规划问题，即默认所有待切割零件已被合理排布。对多个汽车零件进行切割时，不同的零件轮廓切割顺序以及每个轮廓始切割点决定激光头走过的路径长度，例如下图1所示对4个零件切割的两种路径。始切割点指切入轮廓的第一个点，一般零件的所有顶点都可以成为该零件的始切割点，因此本文将零件所有顶点叫做候选点，从候选点中选出的顶点叫做始切割点。传统方法都是根据经验人工指定轮廓切割顺序以及始切割点，该过程耗时而且切割效率低下。

Figure 1. Schematic diagrams of two cutting methods

图1. 两种切割方式示意图

如今计算机技术蓬勃发展，使用智能优化算法优化轮廓切割顺序以及切割点可以提高加工效率。文献 [1] [2] [3] [4] 都将切割路径规划与智能优化算法相结合。文献 [1] 使用一种改进的量子进化算法(IQEA)优化轮廓切割顺序以及轮廓始切割点，并与帝国竞争优化算法(IMA)、文化基因算法(MA)、差分进化算法(DEA)对比，选取10个测试用例进行算法测试，有7个的实验结果优于上述三种优化算法。文献 [2] 使用改进禁忌表的蚁群算法优化切割顺序以及始切割点，实验表明使用该种优化算法的结果是合理的、有效的。文献 [3] 对于复杂轮廓的切割，先使用最小包络矩形对复杂轮廓进行包络以简化轮廓，然后使用遗传算法求取轮廓的切割顺序以及始切割点。文献 [4] 使用了一种离散人工蜂群算法优化多轮廓的切割路径，文中将该算法与A*算法以及遗传算法比较，结果表明离散人工蜂群算法的性能更优越，而且将该算法用于实际服装裁剪路径规划当中，运行结果可靠，比未规划的工艺路线平均提高效率33.7%。

量子进化算法 [5] (QEA)受量子计算启发，借鉴量子计算的部分概念以及理论而形成的概率进化算法。QEA的量子编码具有多样性并且其概率模型能够自适应调整，具有很强的全局寻优性能。人工免疫算法 [6] 受人体免疫学原理启示而提出的算法，其免疫操作中的克隆再变异具有很强的局部寻优能力。针对此，本文提出一种改进的量子免疫算法来求解切割路径规划问题，文章首先建立切割路径规划的数学模型，以切割总路径最短为目标函数，使用量子免疫优化算法求解该目标函数。

实际汽车零件切割生产当中，零件可能含有一个或者多个内轮廓，为了保证对汽车零件完整切割，在外部轮廓从汽车板材上掉落前，必须保证该外部轮廓的所有内轮廓都已经被切割。关于内部轮廓的切割顺序以及始切割点的确定会在第二部分进行介绍。另外，零件的边可能是曲线或者弧，这时需要在曲线或者弧上选取等分点作为零件的候选点，对于不含有曲线或者弧的零件，选取零件的所有顶点作为该零件的候选点。

2. 多零件切割路径规划数学建模

多零件激光切割路径规划可以归结为一类广义的旅行商问题(GTSP)，每个待切割零件可以看成是一个节点的子集，零件中的任何一个顶点可以看成是激光切割的始切割点。激光切割过程，激光从激光原点出发切割完所有轮廓后再回到激光原点。因此，对于切割N个零件的路径规划问题可以转化为寻找经过N + 1个顶点的最短回路。

依据上述分析激光切割路径规划问题的数学模型可以描述为：假设待切割零件序列为 $P=\left\{P_1,P_2,\cdots ,P_n\right\}$，n为待切割零件数，零件的候选点集合为 $V=\left\{v_1,v_2,\cdots ,v_s\right\}$，s为对应零件的候选点数。从第i个零件到第 $i+1$ 个零件的激光头所走的空行程表示为 $Length\left(P_i\left(v_i\right),P_{i+1}\left(v_{i+1}\right)\right)$。通过上述分析，整个切割路径规划的数学模型如下：

$\begin{array}{l}Len=\min \left(L_{set}\right),\\ L_{set}=\left\{L|L={\displaystyle {\sum }_{i=1}^{n-1}Length\left(P_i\left(v_i\right),P_{i+1}\left(v_{i+1}\right)\right)+Length\left(O,P_1\left(v_1\right)\right)+Length\left(P_n\left(v_n\right)\right)}\right\}\end{array}$ (1)

上式(1)中 $Len$ 为目标函数， $L_{set}$ 为所有可能切割路径长度的集合，即在集合 $L_{set}$ 中寻找最小值切割的路径长度。n为待切割零件数，O表示激光原点。

3. 改进量子免疫算法(IQEA)求解多零件加工问题

3.1. 量子编码

与常见的优化算法不同，量子进化算法(QEA)采用量子比特的编码形式，一个量子比特可表示为：

$|\psi \rangle =\alpha |0\rangle +\beta |1\rangle$ (2)

上式中 $\alpha ,\beta$ 为复数，分别表示状态0和1的相位幅。 $\alpha ,\beta$ 满足 ${\alpha }^2+{\beta }^2=1$， ${\alpha }^2$ 和 ${\beta }^2$ 表示量子为 $|0\rangle$ 和 $|1\rangle$ 的概率。一个量子染色体有由多个量子比特构成。如果量子染色体的每位基因具有n位量子比特，那么一个含有m个基因的染色体表示如下：

$\left[\begin{array}{c}{\alpha }_{11}\\ {\beta }_{11}\end{array},\begin{array}{c}{\alpha }_{12}\\ {\beta }_{12}\end{array},\cdots ,\begin{array}{c}{\alpha }_{1n}\\ {\beta }_{1n}\end{array}\begin{array}{c}|\\ |\end{array}\begin{array}{c}{\alpha }_{21}\\ {\beta }_{21}\end{array},\begin{array}{c}{\alpha }_{22}\\ {\beta }_{22}\end{array},\cdots ,\begin{array}{c}{\alpha }_{2n}\\ {\beta }_{2n}\end{array}\begin{array}{c}|\\ |\end{array},\cdots ,\begin{array}{c}|\\ |\end{array}\begin{array}{c}{\alpha }_{m1}\\ {\beta }_{m1}\end{array},\begin{array}{c}{\alpha }_{m2}\\ {\beta }_{m2}\end{array},\cdots ,\begin{array}{c}{\alpha }_{mn}\\ {\beta }_{mn}\end{array}\right]$ (3)

上式中 ${\alpha }_{ij}^2+{\beta }_{ij}^2=1$， $1\le i\le m$， $1\le j\le n$。

针对激光切割路径规划，染色体的编码分为两段，第一段表示零件编号序列，第二段表示每个零件的始切割点。对于第一段编码，假设对N个零件进行切割，必然存在一整数M，满足 $M=\lceil {\log }_{2}N\rceil$ ( $\lceil \rceil$ 表示向上取整)，则染色体的第一段分长度为 $N\ast M$，例如N = 8，则M = 3，第一段染色体长度为24。第二段编码用于指定每个零件的始切割点，因为每个零件可选取的始切割点数量不一，为了便于对量子比特解码，以候选点最多的零件为基准对染色体第二段进行编码。例如图1中，候选点数最多的是零件1，有12个候选点，因此第二段编码使用4位量子比特编码一位基因。因此对于N个零件的切割，每个零件最多含有M个候选点，则采用量子比特编码的染色体长度为 $N\ast \lceil {\log }_{2}N\rceil +N\ast \lceil {\log }_{2}M\rceil$。

以图1为例，假设量子比特编码的染色体进行解码观测得到二进制解如下：[01001101, 0101101011101011]，第一段和第二段用逗号分割。将染色体第一段每2位划分为一小段得到[01, 00, 11, 01]，然后转化为十进制得到[1, 0, 3, 1]，按十进制的大小对下标排序，最小的元素对应1，次小对应2，以此类推得到零件切割顺序[ 2, 1, 4, 3]。染色体的第二段每4个为一小段[0101, 1010, 1110, 1011]，解码为[5, 10, 14, 11]，第一个元素为5，表示编号为1的零件将第6个候选点作为始切割点(候选点下标从0开始)，以此类推，元素10表示第二个零件的第1个候选点作为始切割点(10超过第二个零件的候选点数量，这时进行取余运算10%5 = 0)。

3.2. 量子旋转门

量子旋转门操作是量子进化算法的核心，该操作通过矩阵变换实现量子解的转移。量子旋转门的变换矩阵以及量子状态的变换公式一般如下所示：

$\begin{array}{l}U\left(\theta \right)=\left[\begin{array}{cc}\cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{array}\right]\\ \left[\begin{array}{c}{{\alpha }^{\prime }}_{ij}\\ {{\beta }^{\prime }}_{ij}\end{array}\right]=U\left({\theta }_{ij}\right)\left[\begin{array}{c}{\alpha }_{ij}\\ {\beta }_{ij}\end{array}\right]=\left[\begin{array}{cc}\cos {\theta }_{ij}& -\sin {\theta }_{ij}\\ \sin {\theta }_{ij}& \cos {\theta }_{ij}\end{array}\right]\cdot \left[\begin{array}{c}{\alpha }_{ij}\\ {\beta }_{ij}\end{array}\right]\end{array}$ (4)

上式中 $\theta$ 为旋转角度， $\left[\begin{array}{c}{\alpha }_{ij}\\ {\beta }_{ij}\end{array}\right]$ 为量子染色体的第i位基因的第j位量子比特， $\left[\begin{array}{c}{{\alpha }^{\prime }}_{ij}\\ {{\beta }^{\prime }}_{ij}\end{array}\right]$ 为更新后的量子比特。旋转角度 ${\theta }_{ij}=s\left({\alpha }_{ij},{\beta }_{ij}\right)\Delta {\theta }_{ij}$， $\Delta {\theta }_{ij}$ 为角度大小，决定算法收敛速度。 $s\left({\alpha }_{ij},{\beta }_{ij}\right)$ 为旋转方向，保证算法向指定方向收敛。

为了避免种群早熟，对QEA更新算子进行改进。传统QEA，个体每次都向种群最优解旋转，这在算法早期不利于个体差异，可以让个体概率性的向最优解转移，否则向种群平均解转移，旋转选择概率为 $P={\text{e}}^{t/T-1}$。t为当前迭代次数，T为总的迭代次数。上式表明P随t递增，算法前期种群大多个体会向种群平均解转移，随着迭代次数的增加，P增大，个体逐渐向最优解旋转。

3.3. 免疫操作

常见的人工免疫算法的免疫操作通过免疫选择得到种群中部分优良个体，然后对优良个体经过复制、变异，再对变异体进行再筛选，以实现充分局部搜索。本文在对所有个体进行量子旋转操作后，对种群个体进行解码得到十进制离散编码的个体，然后执行前述免疫操作。对于免疫选择以及免疫克隆，为了协调算法的运行效率以及收敛性能，本文采用一种自适应的选择和克隆方式，具体如下：

$fi{t}_{avg}\left(G\right)=\frac{fi{t}_G\left(p_i\right)}{pop},M\left(G\right)=\{\begin{array}{l}{p}_i,fi{t}_G\left(p_i\right)\ge fi{t}_{avg}\left(p_i\right)\\ \varnothing ,fi{t}_G\left(p_i\right)<fi{t}_{avg}\left(G\right)\end{array}$ (5)

上式(5)， $fi{t}_{avg}\left(G\right)$ 表示第G代种群的平均适应度， $fi{t}_G\left(p_i\right)$ 表示第G代个体 $p_i$ 的适应度，M(G)表示经免疫选择后被选择出的个体集合， $pop$ 表示种群大小。

$C\left(p_j\right)=\lceil \omega \times fit\left(p_j\right)/{\displaystyle {\sum }_{j=1}^{CL}fit\left(p_j\right)}\rceil$ (6)

上式(6)中 $C\left(p_j\right)$ 表示个体 $p_j$ 被克隆的数量， $fit\left(p_j\right)$ 表示个体 $p_j$ 的适应度，CL表示经免疫选择后被选择出的个体数量， $\omega$ 为克隆系数。

克隆后的变异：经过免疫选择以及克隆后的所有克隆体进行变异操作以实现局部搜索。本文变异主要包括对零件切割顺序的变异以及零件始切割点的变异。零件切割顺序变异即随机产生两个位置下标，交换两个下标位置的零件编号即可；零件始切割点变异采取随机产生一个位置pos，将染色体第二段pos位置处的始切割点编号随机更改。

3.4. 适应度计算

根据每条染色体所确定的切割顺序以及始切割点计算个体所代表的路径长度，在计算完种群所有个体表达的路径长度后，为了保证路径越短适应度越高，需要通过归一化操作计算每个个体适应度，归一化方式具体如下：

$fit\left(p_i\right)=\left(L_i-L_{\min }\right)/\left(L_{\max }-L_{\min }\right)$ (7)

上式中 $L_i$ 表示种群第i个个体所代表的路径长度， $L_{\min }$ 表示本次迭代种群中最短路径， $L_{\max }$ 表示本次迭代种群中最长路径， $fit\left(p_i\right)$ 表示种群中个体 $p_i$ 的适应度。

3.5. 算法步骤

step1: 初始化种群Q以及相关参数，对初始化种群Q进行测量得到一组状态P；

step2: 对状态P中的每个个体进行适应度评估，记录最优个体pBest；

step3: 判断是否满足终止条件，若满足输出种群最优解，否则进行步骤4；

step4: 依据种群最优个体，利用量子门U对中种群Q所有个体进行量子更新；

step5: 对更新后的所有种群个体进行测量得到一组新的状态P；

step6: 对P中每个个体进行适应度评估，并更新最优个体pBest；

step7: 进行免疫操作，依据式(5)进行免疫选择，将个体解码为十进制数据并依据式(6)对个体进行克隆，变异，选择，并更新种群最优个体pBest，并转步骤3。

3.6. 内轮廓的处理方式

调用本文算法求解得到外轮廓的切割顺序以及始切割点后，按切割顺序遍历外轮廓。假设遍历到第i个零件，如果该零件不含有内部轮廓则直接遍历下一个，否则对于含有一个或者多个内轮廓的零件，将该零件的始切割点设为激光原点，然后调用本文提出的量子免疫算法求解内轮廓的切割顺序以及始切割点，按求解得到的结果将内轮廓切割插入到第i − 1和第i个零件之间。

4. 算法验证

为了验证本文算法的可行性以及性能，本文选取ESICUP网站提供的服装样片数据集以及实际汽车零件数据进行测试，并选取免疫算法 [7] (IA)、遗传算法 [8] (GA)和蚁群算法 [9] (AA)、量子进化算法 [10] (QEA)对比。本文设置种群规模为100，最大迭代次数500次，经过测试，本文克隆系数 $\omega =30$。测试结果见表1。

表1选取了ESICUP网站的3个服装样片数据集。分别对每个数据集进行10次测试，记录最优路径长度以及10次的平均路径长度。上表Best表示最优路径长度，Avg表示平均路径长度。从上表可以看出：无论是10运行的最好结果还是平均结果，IQEA都要优于另外四种算法。

表2展示了两个汽车零件数据集实验结果。每个数据集同样测试10次，记录最优结果以及平均结果。从表中可以看出无论是最优结果还是平均结果都是IQEA最优。

Table 1. Comparison results of the five algorithms

表1. 五种算法对比结果

Table 2. Path planning results of auto parts (Unit: mm)

表2. 汽车零件路径规划结果(单位：毫米(mm))

5. 结论

汽车零件切割路径规划问题，本质上是一类广义的旅行商问题，本文提出一种改进的量子免疫算法求解该问题。对常规的量子旋转操作进行改进，使个体前期向种群平均解靠近，后期向种群最优解靠近，避免了算法的早熟现象；引入自适应免疫操作，增强了算法的局部寻优能力。最后选取ESICUP网站提供的服装样片数据集以及汽车零件数据集进行算法测试，并与传统的GA/IA/SA/QEA进行对比，对比结果表明本文算法的结果无论是最好解还是平均解，结果都要优于这四种算法，说明本文提出的算法是可行的、有效的。

基金项目

国家重点研发计划(2018YFB1306600; 2018YFB1306603)。