0 引言
工艺路线规划是NP难度哈密顿路径问题[1]，在工程实践中受到许多工艺规则的限制。因此，在进行工艺规划时，首先要保证工艺路线满足工步排序规则的约束，其次将优化工艺路线的资源消耗尽量降低[2]。启发式算法中，破坏工艺路线可行性的主要步骤为初始工艺路线生成与工艺路线变异调整，为保证初始工艺路线满足规则约束，文献[3]利用边缘选择策略，文献[4]采用基于工步优先图的随机拓扑排序算法，文献[5]基于多色集合理论构建围道布尔矩阵的方式表示工步排序规则，根据规则生成初始工艺路线，上述方法均有效保证了初始种群的可行性。为保证工艺路线变异调整后依然满足规则约束，文献[6]采用可行性审查的方式，在算法每步迭代完成后，根据工步排序规则淘汰掉不符合要求的方案。文献[7]采用SEC(subtour exchange crossover)交叉变异方式，利用工艺路线的可行序列对变异进行指导，有效保证了子代的可行性。此外，为了更清晰地表达规则对工步序列的约束，文献[8]根据工步排序规则制定了优先级矩阵，使处理过程更加规范、简便。在对工艺路线优化方法的研究中，文献[9]将机床、刀具，以及进刀方向的更换次数及资源使用产生的消耗作为评价因子构建目标函数进行优化。文献[10]综合考虑了加工成本和时间成本，基于由特征、加工方法等约束建立起来的工艺约束矩阵进行方案的优化。文献[11]将影响工艺路线质量的众多因素的层次进行划分，并采用模糊综合评价的方法来实现决策优化。
上述文献主要考虑制造资源的更换引起的时间成本，讨论了特征在特定加工方法下制造资源的组合选优[12-13]，而实际工程中，某些特征的加工可能适应多种加工方法，而加工方法的不同会影响制造资源的选取与加工的时长。
因此，本文采用免疫遗传算法，讨论了加工特征相同而加工方法不同的工步的组织形式，在加工成本计算中考虑不同加工方法引起的制造资源与加工时长不同而产生的成本差异。在此基础上，对特征的加工方法与制造资源进行组合选优并对工步排序进行优化。文中，工艺路线即为免疫遗传算法中的抗体，工艺路线规划过程即为基于免疫遗传算法寻找最优抗体的过程。
1 基于免疫遗传算法的工艺路线规划
1.1 相关概念及模型建立
1.1.1 基于特征的工步分类及其编码方式
工艺路线规划是对各个工步进行排列，而工步面向的对象为特征，因此基于特征将工步分为四类：
(1)加工不同特征的工步。
(2)加工同一特征的若干道工步，即按照加工精度的不同进行排序，工步之间有确定的排列顺序，例如粗→半精→精。
(3)加工同一特征且加工精度相同，但加工方法或制造资源不同的工步，此类工步不能在工艺路线中同时出现。
(4)加工不同特征但加工方法和制造资源均相同的工步，这是第一类工步的一种特殊形式。
为了清晰地对工步进行整理，对工步编码并储存在三维工步矩阵中。工步编码包括工步的序号、工步对应的加工特征及其加工方法、加工精度、机床、刀具、进刀方向、采用该工步的预计加工时间共8项参数。
工步矩阵是m×n×p的三维矩阵，其中，第三类工步的行数与列数相同、层数不同，其余类型工步的列数相同、行数不同，层数可能相同。由于不同加工方法的工步数不一定相同，所以m为加工零件所有特征所需的最大工步数。以孔的两类典型加工方法“钻→半精镗→精镗”与“钻→扩→粗磨→精磨”为例来说明，实现精度相近的工步储存在同一行的不同层，即“半精镗”与“扩”、“精镗”与“精磨”，剩余的工步“粗磨”单独储存为一行，其中，采用“粗磨”工艺时，必须采用“钻→扩→粗磨→精磨”而不可采用“钻→半精镗→精镗”的加工方法，称“粗磨”与“扩”、“精磨”具有对应关系，“粗磨”为过渡工步。因此，m为定值，但零件不同工艺路线的工步数与选用的加工方法有关。工步编码的参数数量n=8。第三类工步中，不同行的层数不一定相同，令p为第三类工步中的最大层数。图1所示为一个三维工步矩阵。
图1 三维工步矩阵
Fig.1 Three-dimension process matrix
1.1.2 评价函数的定义
本文以工艺路线成本最小化为评价函数，主要考虑制造资源的使用成本与更换成本。首先定义两工步之间的广义距离：
Di,j=wddi,j+wTT+wFF+wMM
(1)
(2)
其中，Di,j为工步i与工步j之间的广义距离，Di,i=0；di,j为工步i与工步j对应加工特征之间的空间距离；(xi, yi, zi)为工步i对应特征的定位点坐标，即人为规定的可以表明特征位置的点，本文设置为特征三维建模时的草图原点；T、F、M取值为0或1，分别表示刀具、装夹方式、机床是否需要更换，其中，当工步i与工步j使用机床相同而进刀方向不同时，则认为装夹方式发生了更换[14]；wd、wT、wF、wM分别为d、T、F、M的权值。
此外，式(2)对dij的定义可使算法根据特征的空间距离计算出相对合理的刀具轨迹，避免刀具轨迹杂乱无章。
评价函数定义为
(3)
式中，W为工艺路线的加工成本；Mj为机床j单位运行时间产生的成本；Ai(n)为工艺路线A第i道工步的第n位编码信息；si表示第i道工步所用的机床是否为机床j；Tk为刀具k单位使用时间产生的成本；ti表示第i道工步所用的刀具是否为刀具k；vM、vT分别为机床使用成本和刀具使用成本的权值。
1.2 基于免疫遗传算法的工艺路线规划框架
1.2.1 基于前趋图的初始抗体生成
工艺路线需要符合工步排序规则，工步排序规主要有以下三种：
(1)先粗后精，若工步为第二类工步，则根据工步的加工精度由粗到精排序，其余类型工步不需考虑该规则。
(2)先主后次，即加工主要特征的工步优先于加工次要特征的工步。
(3)先基准后其他，即加工基准特征的工步优先于以该特征为基准的其他工步。
根据工艺排序规则构建前趋图，指导可行初始抗体的生成。工步前趋图为有向无环图，表示工步之间的优先级关系[15]。由于工步矩阵中，同一行工步实现的加工效果相同，因此在前趋图中，节点表示工步在工步矩阵中的行号，边表示所连接两工步之间的前趋关系。如果工步i可以通过任一路径达到工步j，则认为工步i是工步j的前趋，工步j是工步i的后继，即工步i必须于工步j前完成；若工步i既不是工步j的前趋，也不是工步j的后继，则认为工步i与工步j为并列关系。虚线边除表示前趋关系外，还表示对应关系，受加工方法选择的影响，虚线边及其连接的工步在工艺路线中不一定会出现。
前趋图的拓扑排序方法：每一步均遍历当前无前趋(入度为0)的节点，并随机选取一个节点与出边输出，输出一个节点之后，删除选中的节点以及节点的所有出边，然后选取第二个输出节点，反复进行，直到所有节点都被输出[16]。以图2所示的前趋图为例，说明初始抗体生成过程。
图2 基于前趋图的初始抗体生成
Fig.2 Generation of initial antibodies based on method of forward graph
1.2.2 自适应平行变换算子设计
若工艺路线中的某工步为第三类工步，则利用平行变换方式对其进行概率替换。在工艺路线优化的过程中，变异的概率决定了抗体的搜索面积和进化速度，变异算子越大，搜索面积越大，值越小，收敛越快。计算过程中，抗体时刻处于动态变化的状态。随着迭代次数的增加和抗体质量的提高，静态的变异算子往往不能满足抗体对变异概率的需求，导致进化减缓或陷入局部最优。因此引入自适应平行变换算子：
(4)
式中，PI为第I个抗体的自适应平行变换算子；aI为第I个抗体的亲和力归一化值；N为抗体总数；J为当前抗体按亲和度大小在总体中的排名；t为当前进化代数；T为最大进化代数；α、β、γ为控制变异力度收缩的参数；Pr为(0,1)区间的随机数，指导PI依概率取值。
自适应平行变换算子将变异的概率与抗体质量和进化代数联系起来，随着迭代次数的增加和抗体质量的提高，变异概率逐渐减小，有利于较优抗体的精细化搜索[17]。
图3为符合图2中前趋关系的工步矩阵，以图3为例阐述自适应平行变换算子产生新解的过程。抽象算法可描述为
Parallel-Transformation(A) ∥输入工艺路线A。
N=A.length；∥随机选取若干个节点进行变换。
for I=1 to N
根据式(6)计算平行变换算子PI的数值；
产生(0,1)区间的随机数r；
if(工步A(I)有多解 & PI> r) {
随机选择一组解将原始解替换；
if (新解含有对应关系) {
指定有对应关系的工步行的层数，并对过渡工步增加或删除；
}；
}；
return A；∥生成新解。
图3 平行变换过程
Fig.3 Parallel Transformation
1.2.3 免疫遗传算法流程
改进后的免疫遗传算法流程如图4所示。首先对工步编码，建立三维工步矩阵与评价函数的模型。设置初始抗体群数量为N，利用前趋法生成初始抗体群，通过抗体克隆、交叉变异与平行变换得到新的抗体群。对变异后的抗体群，根据评价函数计算成本并按升序排序，选择前N名抗体组成新的抗体群进入下一次迭代。反复执行克隆与变异操作，直到终止条件满足。抗体克隆与交叉变异方法可参考文献[18]与文献[7]。
图4 免疫遗传算法流程图
Fig.4 The flow chart of immune genetic algorithm
2 实验分析
2.1 实例验证
选取一种回转体零件对算法的有效性进行验证，如图5所示。首先要得到零件及加工资源的相关信息，如表1～表3所示。
根据零件特征与加工方法和制造资源之间的拓扑关系，可以得到三维工步矩阵。由于三维矩阵可视化表达比较困难，因此将其表示为表格(表4)。表4中的列即为三维矩阵的列，“序号”表示
图5 某回转体零件
Fig.5 The rotating part
表1 机床使用成本
Tab.1 The use cost of the machines元/h
机床号机床类型机床单位时间使用成本M1数控车床100M2数控铣床100M3数控镗床150M4数控磨床60
表2 刀具使用成本
Tab.2 The use cost of the tools 元/h
刀具号刀具类型刀具单位时间使用成本C1车刀10C2车刀15X1铣刀10X2铣刀15T1镗刀15T2镗刀20MD1磨刀8
表3 零件特征及加工信息
Tab.3 Part features and manufacturing information
特征编号特征名称位置加工方法精度要求F1密封台(0,0,690)车/铣精F2椭圆窗口(0,-800,200)铣粗F3外形(0,0,670)车精F4圆形窗口(497,568,146)铣粗F5大端面(0,0,0)车/铣精F6圆形窗口(-568,497,146)铣粗F7小端面内孔(0,0,670)镗/铣、磨精F8小端面(0,0,670)车/铣精F9大端面内孔(0,0,0)镗/铣、磨精F10大端内形(0,0,341)车/铣精F11中间孔(0,0,421)车/铣精F12小端内形(0,0,620)车/铣精
表4 三维工步矩阵表
Tab.4 The three-dimension process matrix
序号加工特征加工方法精度要求可用机床可用刀具可用进刀方向预计加工时间(h)1(1)F1车粗M1C1(0,0,-1)0.31(2)F1铣粗M2X1(0,0,-1)0.42(1)F1车精M1C2(0,0,-1)0.42(2)F1铣精M2X2(0,0,-1)0.53(1)F2铣粗M2X1(0,0,-1)0.44(1)F3车粗M1C1(0,0,-1)0.35(1)F3车精M1C2(0,0,-1)0.46(1)F4铣粗M2X1(0,0,-1)0.47(1)F5车粗M1C1(0,0,1)0.37(2)F5铣粗M2X1(0,0,1)0.48(1)F5车精M1C2(0,0,1)0.48(2)F5铣精M2X2(0,0,1)0.59(1)F6铣粗M2X1(0,0,-1)0.410(1)F7镗粗M3T1(0,0,-1)0.410(2)F7铣粗M2X1(0,0,-1)0.411(1)F7铣精M2X2(0,0,-1)0.512(1)F7镗精M3T2(0,0,-1)0.512(2)F7磨精M4MD1(0,0,-1)0.513(1)F8车粗M1C1(0,0,-1)0.313(2)F8铣粗M2X1(0,0,-1)0.414(1)F8车精M1C2(0,0,-1)0.414(2)F8铣精M2X2(0,0,-1)0.515(1)F9镗粗M3T1(0,0,1)0.415(2)F9铣粗M2X1(0,0,1)0.416(1)F9铣精M2X2(0,0,1)0.517(1)F9镗精M3T2(0,0,1)0.517(2)F9磨精M4MD1(0,0,1)0.518(1)F10车粗M1C1(0,0,1)0.318(2)F10铣粗M2X1(0,0,1)0.419(1)F10车精M1C2(0,0,1)0.419(2)F10铣精M2X2(0,0,1)0.520(1)F11车粗M1C1(0,0,1)0.320(2)F11铣粗M2X1(0,0,1)0.421(1)F11车精M1C2(0,0,1)0.421(2)F11铣精M2X2(0,0,1)0.522(1)F12车粗M1C1(0,0,1)0.322(2)F12铣粗M2X1(0,0,1)0.423(1)F12车精M1C2(0,0,1)0.423(2)F12铣精M2X2(0,0,1)0.5
元素在矩阵中的位置，括号外的数字表示元素在矩阵中的行号，括号内的数即为层号，例如“1(2)”，表示第1行第2层。进刀方向用向量表示，其中，特征F2、F4、F6的进刀方向虽然不同，但是其装夹方式相同，为方便更换成本的计算，按装夹方式将其处理为(0,0,-1)。实验零件的工步排序规则前趋图见图6。
图6 工步排序规则前趋图
Fig.6 Precedence graph of the process ordering rules
在MATLAB环境下编写免疫遗传算法，对工步模型进行计算。迭代过程如图7所示，此次计算结果如下：总成本为3244.319元，机床更换6次，刀具更换7次，装夹方式更换7次，工艺路线为7(1)→4(1)→3(1)→1(2)→13(2)→10(1) →20(2)→9(1)→6(1)→15(1)→22(1)→18(1)→8(1)→14(1)→5(1)→19(1)→12(1)→2(1)→23(1)→21(1)→17(1)。
图7 免疫遗传算法迭代过程
Fig.7 Iterative process of immune genetic algorithm
通过上述结果可以看出，该算法对工艺路线给出了符合工步排序规则的合理安排，完成了对整个工艺流程的路线规划，说明算法在计算过程中可以保证工艺路线的可行性。
2.2 对比实验
为验证本文改进算法的优越性，采用2.1节的实例，将改进的免疫遗传算法(improved immune genetic algorithm, IIGA)与传统的免疫遗传算法(immune genetic algorithm, IGA)、遗传算法(genetic algorithm, GA)进行比较，为避免偶然因素，连续进行10次对比实验并记录实验结果，其中，第一组迭代过程如图8所示， 10次计算结果如表5所示。
图8 各算法迭代过程
Fig.8 Iterative process of the algorithms
表5 计算结果对比
Tab.5 Comparison of calculation results
次数改进的免疫遗传算法传统免疫遗传算法遗传算法成本(元)计算时间(s)成本(元)计算时间(s)成本(元)计算时间(s)13 247.3626.766 93 622.7457.726 13 822.7226.586 523 422.7106.760 03 422.7116.561 83 246.0826.208 733 222.6506.966 33 642.7347.105 53 425.6556.338 043 240.9026.787 33 627.4117.274 73 646.0426.676 653 247.3796.756 33 421.3427.210 53 642.7035.775 963 045.5956.704 53 447.3797.265 43 645.6156.357 673 222.7276.785 93 447.3717.141 13 627.3876.192 583 247.3996.083 93 420.9916.441 23 821.3415.755 693 245.6926.721 13 440.9516.774 33 821.3176.264 6103 042.7116.445 13 424.3157.349 23 626.0185.760 0均值3 218.56.670 03 491.87.080 03 632.56.190 0成本区间(元)[3 042.7,3 422.7][3 421.3,3 642.7][3 246.1,3 822.7]耗时区间(s)[6.083 9, 6.966 3][6.441 2, 7.726 1][5.755 6, 6.676 6]
实验结果表明，改进的免疫遗传算法与传统的免疫遗传算法在计算时间上差距较小，而在寻优性能方面有较大提升，说明了自适应平行变换算子的有效性。此外，通过与遗传算法相比较，免疫遗传算法的克隆机制使计算速度略微下降，但对提高算法寻优能力有较大帮助。因此，改进的免疫遗传算法在处理工艺路线决策问题上有一定的优越性。
3 结论
(1)完善了评价指标，考虑了特征加工过程中，不同的加工方法导致的制造资源与加工时长不同而产生的成本差异。
(2)讨论了加工特征相同而加工方法不同的工步的关系，并在此基础上，完善了初始工艺路线的生成规则。
(3)设计了自适应平行变换算子，随迭代次数及抗体质量的变化动态调整变异概率，实现了加工方法和制造资源的动态调整。
将回转体零件作为案例对算法的有效性进行验证，实验结果表明，该算法在短时间内完成了工艺路线规划。与传统的免疫遗传算法和遗传算法的实验验证了该算法在处理工艺规划问题时有更好的寻优性能。
[1] JIMÉNEZ P. Survey on Assembly Sequencing: a Combinatorial and Geometrical Perspective[J]. Journal of Intelligent Manufacturing, 2013, 24(2): 235-250.
[2] 姜存学,蔡力钢,胡于进.基于约束矩阵与蚁群算法的CAPP加工工序优化排序[J].中国机械工程, 2009, 20(18): 2203-2206.
JIANG Cunxue, CAI Ligang, HU Yujin. Optimization Operation Sequence in CAPP Using an Ant Colony Algorithm Based on Constraint Matrix[J]. China Mechanical Engineering, 2009,20(18): 2203-2206.
[3] SU Y, CHU X, CHEN D, et al. A genetic Algorithm for Operation Sequencing in CAPP Using Edge Selection Based Encoding Strategy[J]. Journal of Intelligent Manufacturing, 2018,29(2): 313-332.
[4] HUANG W, LIN W, XU S. Application of Graph Theory and Hybrid GA-SA for Operation Sequencing in a Dynamic Workshop Environment[J]. Computer-Aided Design and Applications, 2016,14 (2):148-159.
[5] 刘雪梅,孟飞飞,李爱平，等. 基于多色集合理论和遗传算法的加工中心工步排序研究[J]. 中国机械工程, 2013,24(18):2437-2442.
LIU Xuemei, MENG Feifei, LI Aiping, et al. Research on Machining Step Sequencing of Machining Center Based on Polychromatic Sets Theory and Genetic Algorithm[J]. China Mechanical Engineering, 2013, 24(18): 2437-2442.
[6] SINGH S, DEB S. An Intelligent Methodology for Optimizing Machining Operation Sequence by Ant System Algorithm[J]. International Journal of Industrial and System Engineering, 2014,16(4):451-471.
[7] 窦建平,李俊,苏春. 基于可行工序序列遗传算法的工序排序优化[J]. 计算机集成制造系统, 2019, 25(8): 1981-1990.
DOU Jianping, LI Jun, SU Chun. A Feasible Operation Sequence Oriented Genetic Algorithm for Optimization of Operation Sequencing[J]. Computer Integrated Manufacturing Systems, 2019,25(8):1981-1990.
[8] WU Yujia, CAO Yan, WANG Qiangfeng. Assembly Sequence Planning Method Based on Particle Swarm Algorithm[J]. Cluster Computing, 2019, 22(1): 835-846.
[9] 
M, et al. Integration of Process Planning and Scheduling Using Chaotic Particle Swarm Optimization Algorithm[J]. Expert Systems with Applications, 2016, 64(1): 569-588.
[10] YILDIZ A R. A New Hybrid Differential Evolution Algorithm for the Selection of Optimal Machining Parameters in Milling Operations[J]. Applied Soft Computing Journal, 2013,13(3):1561-1566.
[11] WANG Guilian, WANG Yiqiang, ZHAO Ji, et al. Process Optimization of the Serial-parallel Hybrid Polishing Machine Tool Based on Artificial Neural Network and Genetic Algorithm[J]. Journal of Intelligent Manufacturing, 2012, 23(3): 365-374.
[12] 张中伟,唐任仲,陶俐言.非线性工艺规划的资源优化配置[J].计算机集成制造系统,2016,22(2):516-528.
ZHANG Zhongwei, TANG Renzhong, TAO Liyan. Optimal Allocation of Nonlinear Process Planning Resources[J]. Computer Integrated Manufacturing Systems, 2016,22(2):516-528.
[13] 张雷,赵希坤,蒋诗新，等.低碳低成本约束下箱体零件加工路线优化方法[J].中国机械工程, 2018, 29(23): 2836-2844.
ZHANG Lei, ZHAO Xikun, JIANG Shixin, et al. Optimization Method of Process Routes for Housing Parts under Low-carbon and Low-cost Constraint[J]. China Mechanical Engineering, 2018,29(23):2836-2844.
[14] 黄伟军,蔡力钢,胡于进, 等. 基于遗传算法与有向图拓扑排序的工艺路线优化[J]. 计算机集成制造系统, 2009,15(9):1770-1778.
HUANG Weijun, CAI Ligang, HU Yujin. et al. Process Planning Optimization Based on Genetic Algorithm and Topological Sort Algorithm for Digraph[J]. Computer Integrated Manufacturing Systems, 2009,15(9):1770-1778.
[15] KLINDWORTH H, OTTO C, SCHOLL A. On a Learning Precedence Graph Concept for the Automotive Industry[J]. European Journal of Operational Research, 2012, 217(2): 259-269.
[16] 冯羚,黄海松,姚立国.基于特征分层拓扑排序和改进蚁群算法的工艺路线研究[J].组合机床与自动化加工技术, 2019(2):123-126.
FENG Ling, HUANG Haisong, YAO Liguo. Process Routing Research Based on Feature Hierarchical Topological Sorting and Improved Ant Colony Algorithm[J]. Modular Machine Tool & Automatic Manufacturing Technique, 2019(2):123-126.
[17] 焦李成，杜海峰，刘芳，等. 免疫优化计算、学习与识别[M]. 北京：科学出版社，2006.
JIAO Licheng, DU Haifeng, LIU Fang, et al. Immune Optimization, Learning and Recognition[M]. Beijing: Science Press, 2006.
[18] 巫东凯,张凤斌,席亮.自适应混合变异克隆选择算法研究[J].计算机工程与应用,2018,54(21):78-83.
WU Dongkai, ZHANG Fengbin, XI Liang. Research on Clonal Selection Algorithm of Adaptive Hybrid Mutation[J]. Computer Engineering and Applications, 2018, 54(21):78-83.
