郝博，傅士栗，王建新，王明阳，闫俊伟
(1.东北大学机械工程与自动化学院，辽宁沈阳 110819；
2.东北大学航空动力装备振动及控制教育部重点实验室，辽宁沈阳 110819)
在计算机辅助工艺过程设计(Computer Aided Process Planning，CAPP)解决的问题中，加工工序规划是一个非常重要却又复杂的部分，不仅加工方法、刀具、机床等加工资源的选择会对工序规划产生影响，而且工艺约束也会对工序的排序产生制约。仅仅使用传统的方法，比如梯度下降法、图论法和仿真方法实现路线优化，在解决复杂的零件工序规划问题上效率很低，只能完成结构较简单的零件或复杂零件的某一部分工序排序规划的内容[1]。加工工序优化在某些重要领域，比如汽车制造、航空航天、装备现代化生产等行业的大规模生产中起到了重要的作用[2]。近年来，智能算法作为主要研究手段被广泛应用于工序规划的研究中。郑永前、郑开元、曹振、黄伟军等[3-6]采用遗传算法，针对工序排序问题，以成本最低或最大完工时间最少为优化目标，完成对应编码与解码解决方案。刘伟等人[7]运用蚁群算法，以海明距离反映任意两加工单位之间的相似程度，并在约束条件和禁忌准则的限制下对解空间进行搜索。刘敏等人[8]把模拟退火算法引入到传统遗传算法中，解决了加工中心的工步优化问题。姜存学等[9]将模拟退火算法与蚁群算法结合，建立零件工步优化过程模型，将之应用于以加工中心为主要加工设备的创成式CAPP中。但是，目前针对零件工序规划问题所采用的遗传算法存在一些不足：(1)没有考虑到在实际车间生产中，对于某类加工特征，通常存在几种加工方案，并且对于一个工步的加工，有多台机器可供选择；
(2)现有算法采用间接编码方式，对解的信息表达不直观，解码复杂度高，影响了算法的效率；
(3)现有遗传算法研究中对于种群的优化方法和进化导向使得算法的全局搜索能力不强，在运行过程中产生的新种群多样性逐渐降低，易使搜索进入局部收敛甚至发生停滞。
针对上述不足，本文作者设计分层多算子遗传算法(Hierarchical Multi -Operator Genetic Algorithm，HMO-GA)，其编码分为特征层、工序层、机器层、刀具层、方向层以及选择层，每一层对应工艺规划的一个维度，使得染色体中包含的决策信息更加丰富且直观，降低解码难度，减少算法求解时间，提高效率。对于每一个搜索维度，针对性采用不同的遗传优化算子，提高算法的全局和局部搜索性能，避免发生局部最优。采用面向加工资源使用的变异算子代替随机变异算子，从而改善全局平衡，增加繁殖更好的个体概率；
选择层编码设计对算法的性能有很大帮助，选择层的基因突变使得特征加工方法选择方案改变，实现柔性加工的灵活性。
1.1 工步信息表示
零件加工的单元为工步，工序排序就是将所有工步进行排列组合，而工步的选择制定面向的是零件的加工特征。一般来说，复杂的零件加工特征基本可以由面(外圆柱面、圆锥面、平面)、凸台、槽(环槽、方形槽、键槽、通槽)、肋、孔(普通孔、螺纹孔、沉头孔、盲孔)等构成。在零件加工特征排序问题上把每一个加工特征称为加工元。所有的加工元的集合就构成了零件的加工特征，通过工艺知识库的查询，为每一个特征选择合适的加工方法。若一复杂零件由n个加工元构成，则零件特征可表示为集合：
F={f1,f2，…，fn}
(1)
其中：fi为该复杂零件的第i个加工元。同一个加工元，根据加工精度的需要以及车间加工资源的限制，可能存在多种加工手段。例如，对于外圆面的加工，有粗精车→半精车→磨削、粗车→半精车→粗磨等多种不同的加工方式。对于内孔的加工，有钻→扩→镗、钻→扩→铰等不同的加工方式。所以对于每一个加工元根据实际需求以及车间资源可能存在多种加工方法，即一个加工元由多条加工链构成：
fi={OL1,…,OLi,…,OLm}
(2)
式中：OLi为加工元fi的第i条加工链。加工链是由工步经过线性排列组合而成，分为单个工步或多个组合工步。加工链可以表示为
OLi={OP1,OP2,…,OPk}
(3)
式中：OPi表示为加工链OLi的第i个加工工步。
为对加工特征进行更详细准确的描述，用基于工步的三维工步矩阵存储特征信息。其中：a为工步编码的维度，分别为加工序号、加工特征、加工方法、加工精度、可用机床集合、可用刀具集合以及进刀方向，包含工步的特征信息以及加工所用到的资源信息；
c为零件加工各特征的总工步数；
b为每一特征可能选取不同加工方法的工步表示，将同一特征加工精度相同的工步存放在三维工步矩阵的不同层。图1所示为三维工步矩阵。
图1 三维工步矩阵
1.2 工艺约束
将零件制造特征所选择的加工工步集合进行排列组合，在不违反工艺约束的情况下，得到最优目标值的工步序列，这个计算寻优过程就叫加工工序优化。假设一个零件有N个待加工特征，从排列组合的角度来看，就会产生N！组工步序列，假设不存在其他的限制条件，则会存在N！个可行解[10]。由于加工零件特征具有具体的精度需求，并且要满足设计的形位公差要求，所以加工顺序的排列就不能是所有的可行解，必须要遵循在零件设计前提下加工工艺的限制。加工工序决策优化的前提是确保零件加工精度，使加工完毕的零件符合设计的标准，否则无用的工序排序对加工规划而言毫无意义。所以，设计加工工序路线首先要满足工艺的约束，包括以下几个方面：
(1)几何拓扑关系。即工件在加工过程中各特征的先后顺序关系，如先面后孔，加工两个相关联的特征面和面上的孔时，工序排序必须满足面在孔之前的约束。
(2)先基准后其他准则。作为加工基准的加工特征表面应该先于其他表面先加工，因为后续特征表面的加工需要以它作为定位基准保证精度。
(3)先主要后次要，先粗后精准则。精基准加工完毕之后再对精度有更高要求的表面进行加工，精度特别高的还需进行光整加工。主要表面的精加工放在最后阶段进行，次要表面先进行加工或者穿插在主要表面加工工序之间。
通过对工艺约束的制定，结合具体零件的相关几何参数和加工信息建立工步约束矩阵CS：
(4)
式中：CS为n×n矩阵；
n表示所有工步个数；
元素rij表示第i个工步和第j个工步之间的先后约束关系，定义规则如下：①根据工艺约束原则，若工步i在工步j之前加工，则rij=1，反之rij=-1；
②若工步i和工步j相互之间没有加工约束关系，则rij=0。
1.3 工序方案评价方法
加工工序优化的目标是在现有加工资源的条件下得到最优的加工方案，使得加工时间、消耗成本等目标值达到预期满意的结果。工艺优化评价指标通常有最大完成时间、加工能量损耗、加工成本消耗等。文中用加工成本作为评价目标来对工序规划过程进行优化，评价函数定义为
(5)
式中：α、β、γ、θ为权值系数；
Mj为机床j单位时间内使用成本；
Tk为刀具k单位时间内使用成本；
Ti为加工第i个工步所耗费的时间；
si为第i个工步的加工是否用到机床j，若si=1，则表示加工过程用到机床j,反之则没有；
ti为第i个工步的加工是否用到刀具k，若ti=1，则表示加工过程用到刀具k，反之则没有；
Ai(n)为加工链A的第i个工序的第n位编码内容；
Cmc为更换机床成本；
Ctc为更换刀具成本；
φ(X,Y)为工序X和Y之间是否更换机床；
φ(X,Y)为工序X和Y之间是否更换刀具。
2.1 编码与解码
遗传算法的编码和解码方法很大程度上决定了算法的可行性和效率，是解决问题的关键，也是实现算法计算机编程的必要条件。之前用遗传算法解决工序规划问题的研究多采用双重编码的方法，单个加工特征独立编码，每个基因包含多项加工内容，存在染色体表示不直观、解码复杂度高、效率低、局部搜索能力差等问题。为解决遗传算法在工序排序问题上的不足，提出分层多算子遗传算法。用多层编码的方式映射6个独立的决策层，分别是特征层、工序层、机器层、刀具层，方向层以及选择层，它们之间相互关联，共同影响着目标函数。
图2所示为分层多算子遗传算法染色体编码实例。第一层为特征层编码，实数表示特征编号，其相对位置反映加工顺序的优先级关系，同一数字重复次数表示该特征加工工序数量。第二层为工序层编码，其数字与后面几层一一对应，位置反映了加工特征工步之间的先后顺序关系。机器层和刀具层中显示的数字代表在车间中对应可选工步的加工资源。加工方向层表示刀具的进给方向，结合具体实例，根据需要，设定初始方向和各进刀方向。第六层为选择层，用于选择零件各特征采用的加工方法，即加工链的构成，体现在工序的选择上。所有染色体通过选择层实现了特征的加工方案，数字1表示该工序被采用，否则未被采用。
图2 分层多算子遗传算法编码示例
分层多算子遗传算法的解码方式相对简便。首先，将特征层、工序层、机器层、刀具层以及方向层中的数字以前五层的编码顺序和指定形式全部列出。随后，将选择层中编码为0的基因列删除。图2所示的零件加工工序排序方案解码输出结果为
F1(OP1,M1,T2,TAD2)→F3(OP2,M2,T3,TAD3)→F1(OP3,M4,T2,TAD2)
→F2(OP1,M4,T4,TAD1)→F1(OP4,M3,T6,TAD1)→F1(OP2,M3,T2,TAD1)
→F2(OP2,M4,T5,TAD1)→F2(OP4,M6,T5,TAD2)→F3(OP3,M3,T3,TAD3)
→F1(OP6,M2,T3,TAD2)→F1(OP5,M5,T3,TAD2)
2.2 交叉与变异算子
2.2.1 交叉算子
交叉算子是产生新个体的主要方式，在很大程度上决定了智能算法性能的优劣。在交叉操作中，染色体的每一列都是作为位置转换的基本单元。当一列中的任何基因位置改变时，该列中的所有基因都以相同的方式改变它们的位置。对特征层、工序层、机器层(刀具层、方向层)分别采用不同交叉算子，从多个维度进行迭代搜索，具体操作如下：
(1)对于特征层编码交叉采用POX算子，该算子可以保证所有特征在父代和子代出现的次数一致，并保持任意特征工序之间的顺序约束关系。特征层POX编码交叉操作示例如图3所示，具体步骤为
步骤1，从一个种群中随机选择两条染色体，提取其特征层作为父染色体P1和P2,并初始化生成两条空染色体O1和O2作为子代；
步骤2，将特征集合F划分为两个非空集合F1和F2,并满足F1∪F2=F、F1∩F2=Ø；
步骤3，将P1中属于集合F1的特征对应的基因复制到O1相同的基因位置，然后在P2中删除O1中已确定的基因并将余下的基因从左到右依次填充到C1的空基因位置上；
步骤4，把P1、P2位置互换，再按照步骤3中同样操作步骤得到C2。
图3 特征层POX交叉示意
(2)对于工序层采用两点交叉算子，保证在交叉完成后生成的子染色体工序层序列的完整，避免重复或者遗漏，符合实际。该算子为局部操作，作用在两条随机染色体对应同一特征的工序层基因之间，如图4所示，具体操作过程如下：
步骤1，从种群中随机选取两条染色体作为交叉操作的父染色体，记为P1和P2。分别提取两条染色体的工序层基因，记为PP1和PP2，生成一条空的工序层基因作为子代，记为OP1；
步骤2，标记选择层代码为1的工序操作；
步骤3，随机选取两个交叉点位置，从左到右分别记为Pos1和Pos2；
步骤4，将PP1中Pos1左侧基因和Pos2右侧基因按照对应的位置复制到OP1两侧；
步骤5，在PP2筛选出不含PP1已复制到OP1中的基因，逐一插入到OP1中空缺位置；
步骤6，根据步骤1的记录调整OP1中选择层的编码，使选择层OP1编码为1的基因与PP1相同；
步骤7，将得到的OP1基因插入到染色体P1中PP1的原始位置，获得新的子代染色体。
图4 工序层两点交叉示例
(3)对于机器层、刀具层以及方向层均采用类似子图交换的交叉操作。如图5所示，将机器层交叉作为示例，随机选择两条父代染色体用作交叉操作。具体步骤如下:
步骤1，从种群中随机选取两条染色体作为父代染色体，分别提取同一特征对应的工序层和机器层基因，记为PM1和PM2，生成空基因层OM1；
步骤2，将PP1的工序层复制给OM1；
步骤3，随机产生特征工序层的n个位置用作交叉，将PM1机器层对应n位置的基因复制给OM1，将PP2对应剩下OM1中工序编号的机器层编号复制到OM1中；
步骤4，将OM1插入到PM1基因原位置的父染色体P1中，获得新的子代染色体。
图5 机器层两点交叉示例
2.2.2 变异算子
设计从多个维度对染色体进行变异，针对每个维度选择不同的变异算子。特征层变异，改变不同特征的加工先后次序；
工序层变异，改变同一特征的加工工序次序；
机器层(刀具层、方向层)变异，使作业加工资源发生变化；
选择层变异，改变特征采取的加工方式。与交叉操作一样，染色体的每一列都是变异操作中位置转换的基本单元。
(1)特征层的变异，采用如图6示例所示的方法,具体步骤如下:
步骤1，在染色体P中随机选择两个位置Pos1和Pos2,如果两个位置的编码所代表的特征相同，则重新选择两个位置，直到编码号不同，并记录为P1和P2；
步骤2，分别在Pos1和Pos2之间的染色体片段中标记P1和P2的所有基因位置；
步骤3，用第一个P2基因列覆盖第一个P1基因列，然后将片段中剩余的P2基因列向左移动，并逐个填充空缺，将Pos2位置留空；
步骤4，将P1最右边的基因列填充到Pos2的位置，然后将P1剩余的基因列向右移动，依次填充空缺，得到特征层突变后的个体O。
图6 特征层变异示例
(2)工序层变异，采用位置互换的方法，如图7所示,具体步骤如下:
步骤1，随机选择一个染色体进行突变，标记为PO；
步骤2，提取PO的工序层基因，标记其基因位置；
步骤3，在染色体中随机选择两个位置，将两个位置处的基因进行交换作为突变；
步骤4，确定变异后的工序序列是否满足约束矩阵的要求；
步骤5，若满足约束要求，则将其插入到PO染色体原位置,否则，使用约束矩阵对序列进行调整，再插入到PO中。
图7 工序层变异示例
(3)机器层、刀具层、方向层的变异均采用单点突变的方式。以机器层为例，对机器利用频率最高的基因实施变异。图8所示为机器层变异示例,具体步骤如下:
步骤1，计算机器利用率,机器利用率等于机器加工时间除以完工时间
步骤2，提取利用率最高的机器Mi在编码中的所用位置，并记录下来；
步骤3，随机选取步骤2中记录位置所含编码基因进行突变。
图8 机器层变异示例
(4)选择层的变异，采用多点变异的方式。随机选择一条染色体，提取一个特征的选择层进行变异。选择层变异如图9所示，具体步骤如下：
步骤1，随机选择一个特征进行基因突变，记为F；
步骤2，提取F中选择层的基因，并标记其位置；
步骤3，在特征F的可选加工方案中选择与当前方案不同的加工链；
步骤4，根据选择的加工链中包含的工步信息生成新的选择层代码；
步骤5，将步骤4得到的选择层基因替代F中原位置处的基因，生成新个体。
图9 选择层变异示例
2.3 改进遗传算法实现步骤
传统的工序规划遗传算法编码复杂，增加了解码的难度和时间。搜索算子的设置比较单一，导致算法在搜寻最优解的能力方面不足。本文作者对遗传算法进行改进，提出分层多算子遗传算法，提高了工序排序问题的全局搜索能力，将工序选择灵活性、工序排序灵活性、加工资源选择灵活性集成到单个阶段。具体步骤如下：
(1)根据工艺约束矩阵的约束，使种群中包含的个体加工顺序成为有效解；
(2)计算种群的个体适应度函数值，并根据所计算出来的适应度大小对它们进行排序；
(3)将种群中的染色体作为父代随机进行交叉和变异操作；
(4)根据各层的交叉概率，依次对选定的父个体进行特征层、工序层、机器层、刀具层以及方向层交叉，生成新个体；
(5)根据各层的变异概率，对新个体依次进行特征层、工序层、机器层、刀具层、方向层以及逻辑层变异，生成新个体形成后代种群；
(6)对新形成的种群中个体的适应度进行计算，并将其与父代染色体中优秀的个体结合，形成新的种群；
(7)判断结果是否满足算法终止条件。如果是，输出计算结果；
如果没有，返回步骤(3)。
为验证改进算法的有效性，选择如图10所示的箱体零件进行验证。该零件共有16个制造特征，加工这些特征共需要26个工步。关于零件加工的相关消息如表1—表3所示。
图10 某箱体零件
表1 机床使用成本 单元:元·h-1
表2 刀具使用成本 单位:元·h-1
表3 零件特征及加工信息
根据零件加工特征和加工方法以及制造资源之间的拓扑关系，可以得到工步三维矩阵。由于工步三维矩阵的平面可视化较为困难，用表4对其进行描述。
表4 工步三维矩阵
表4中的列对应工步三维矩阵列表示内容，序号表示元素在矩阵中的行数，括号内的数表示层数，即可选的加工方法。
用MATLAB完成分层多算子遗传算法编写。设置初始种群规模大小为M=100、交叉概率Pc=0.8、变异概率Pm=0.2、最大迭代次数为100。通过算法进行求解，得到如下结果：总成本为5 621.3元，机床更换了10次，刀具更换了11次，装夹方式更换了11次，得到最优加工工序规划为26→22→16→1→6→23→24→4(1)→2(2)→17(1)→11→18→12(1)→13→14→15→3→25→19→20→7→8→9→10→21→5。
为验证文中算法的有效性，将传统遗传算法、文献[5]中的遗传算法应用于该箱体示例作为比较，迭代过程如图11所示。可知：通过分层编码的方法，大大降低了解码的复杂度，提高了算法的效率；
引入多种交叉、变异算子，提高了算法的全局搜索能力，加快了收敛速度。
图11 改进遗传算法迭代过程
本文作者完善了评价函数模型，考虑到了在加工过程中因特征可选择的加工资源不同而导致的成本差异。在改进的算法中添加选择层，以动态的多加工链特征加工方法代替了传统的静态单一加工链，增加了加工过程中工艺路线的柔性。设计了分层多算子遗传算法，用分层的实数编码代替了双重编码，降低了算法解码的复杂度，减少了算法求解时间，使得效率大大提升。针对算法的不同维度引入有效的交叉、变异算子，全局搜索能力提升，从而高效地对最优的工序排序进行快速搜索。
将箱体零件作为实例对算法的有效性进行验证，结果表明：该算法在搜索结果和搜索效率上都有了明显提高；
在工序排序问题上与传统的遗传算法和模拟退火遗传算法相比，该算法有更好的寻优性能。