基于特征分层拓扑排序和改进蚁群算法的工艺路线研究*

冯 羚，黄海松，姚立国

(贵州大学 现代制造技术教育部重点实验室，贵阳 550025)

0 引言

工艺路线是指零件从毛坯到成品状态转变中，企业根据其材料、结构、设计信息等按照一定的最优准则完成的加工过程。由于零件的多样性、加工设备的局限性、生产环境的复杂性，使得对工艺路线决策较为复杂。工艺路线是毛坯和成品的连接纽带，很大程度决定了成品的质量和企业的效益，合理安排工艺路线在产品制造方案中显得尤为重要。近年来，一些启发式的算法常被用来解决工艺路线决策这一类问题。李聪波等[1]以车间高效低碳为目标建立机械加工工艺模型，应用遗传算法对模型求解，并用机床电动机基座加以验证模型的实用性。夏然飞等[2]考虑加工中心工件加工时间最短，采用和声搜索算法，引入刀具、工作台转位约束矩阵，对工艺生成方案进行求解。范孝良等[3]针对复杂零件工艺规划效率低，质量差的问题，采用蝙蝠算法，设计蝙蝠编码解码策略对工艺路线问题进行求解。付晓东等[4]采用基于神经网络的专家系统，将零件信息转换为特征矩阵作为输入，自适应BP算法训练网络模型，得到轴类零件的工艺规划。

与这些算法相比，蚁群算法具有正反馈、随机性、禁忌搜索等特点，在求解工艺决策问题时表现良好。文献[5]以双螺杆压缩机端盖加工工艺规划为目的，用“或”型工艺约束，针对决策问题编制了加工要素选择模块，并采用启发式要素选择规则，改进了蚁群算法的结构。Shi Gang Wang等[6]在CAD/CAM集成系统中，对路径优化问题采用蚁群算法与LK算法融合的智能算法，对孔组钻具工艺路径进行了优化，实现CAD/CAM的多个特征优化。黄风立等[7]提出一种禁忌特征动态更新与蚁群算法结合求解工艺路线的方法，解决方案设计中刚性约束问题，并通过实例验证算法的可行性。常志勇等[8]提出以约束矩阵表征加工元之间的加工顺序，建立制造资源目标函数，应用自适应蚁群算法对工艺路线进行求解。上述研究，较多是通过智能算法在约束条件下求解最优目标函数问题，但因为约束过多，搜索范围大，存在效率低，甚至运行多次才能得到可行解的问题。基于此，本文提出了一种基于特征分层拓扑排序和改进蚁群算法的工艺路线优化方法，构建分层拓扑顺序工序元序列表征工序元之间的加工顺序关系，蚂蚁搜索这些拓扑序列，缩小可行解的范围，以解决搜索效率和解的可行性等问题。

1 零件特征描述

零件特征是指包含零件一定的结构形状、加工精度、装配要求等一系列信息的结合，是组成零件的基本单元。零件特征一般可以分为以下两类。①主要特征：构建零件几何拓扑结构且无法进行二次拆分的特征，例如：平面、孔等。②辅助特征：辅助主要特征的局部特征，可以进行二次拆分，例如：螺纹、键槽等。

假设某零件Α一共有m个特征，则该零件可以表示为：

Α=(φ1,φ2,…φi…,φm)

(1)

式(1)中，φi表示第i个加工特征，i=1，2，……，m。

φi=(ω1,ω2,…ωj…,ωn)

(2)

式(2)中，ωj表示第j个工序元，j=1，2，……，n。

在零件加工中，每个工序元对应的加工资源有所不同，加工资源主要指机床、刀具、夹具等。因此，工序元可以看做一个加工资源的集合。设机床集合为x={x1,x2,…,xo}，刀具集合为y={y1,y2,…,yp}，夹具集合为z={z1,z2,…,zq}，其中o，p，q为加工制造部门机床、刀具、夹具的总和。对于零件Α，特征φi中的ωj工序元有：

ωj=(xα,yβ,zγ)

(3)

式(3)中xα,yβ,zγ分表表示制造加工工序元ωj所需要的机床、刀具、夹具。其中1≪α≪o，1≪β≪p，1≪γ≪q。

2 基本问题

2.1 基于特征分层拓扑顺序工序元序列

零件在进行工艺路线设计时，首先要遵循的工艺准则[9]如先粗后精、基准先行、聚类加工以及一些特定的准则，例如螺纹，一般安排在外圆精车后，粗精磨外圆之前。

零件由特征组成，每一个特征存在若干串行或并行关系。图1所示是由4个特征组成的工序元顺序关联关系。如特征1，工序元101在前，工序元102在后；特征2，工序元201、203、206，属于并行关系。工序元上方C1、C2等代表加工该工序元所需要的加工资源，0表示起点，1表示终点。一个有向无环图是由若干节点和弧组成的，且不存在闭合回路。对于图1此有向无环图，可以用弧线上的权值来对工序元节点进行拓扑排序[10]。定义弧尾工序元的入度为弧头入度加1，多条弧尾则取最大值。图1中，工序元205的入度为3，工序元401的入度为5。当工序元按照入度值从小到大排列，且相邻工序元之间入度值小于或等于1的时候，称为分层拓扑顺序工序元序列。

分层拓扑序列1(201,203,206,305,301,207,204,202,208,209,401,402)；

分层拓扑序列2(203,101,201,301,305,202,207,102,205,209，401,402)；

构建特征分层拓扑序列，可以表征工序元先后加工顺序，得到的分层拓扑序列包含了问题所需要的最优解。

图1 特征分层拓扑顺序有向无回图

2.2 加工资源最优模型

零件在进行工艺路线设计时，其次要遵循加工资源约束。一般而言，企业在对加工工艺路线进行设计的时候，会考虑多方面的问题，例如：加工成本、生产效率、产品质量等。需要一个量化的目标函数，考虑加工资源更换率最低。机床的更换率降低，加工基准不需要频繁更换，减少了因为基准更换带来的误差，提高了产品的加工精度；刀具的更换率降低，减少了换刀次数，生产效率得到提高；夹具的更换率降低，减少了装夹误差和装夹次数，质量得到保证。定义工序元i到工序元j之间的加工资源(机床、刀具、夹具)更换率为Cij。

Cij=λ1Eij+λ2Fij+λ3Gij

(5)

其中，λ1、λ2、λ3分别为机床、刀具、夹具的更换率加权系数，Eij、Fij、Gij分别为从工序元i到工序元j机床、刀具、夹具的更换次数。

(6)

(7)

(8)

3 工艺路线优化

3.1 基于改进蚁群算法工艺路线设计

本文采用双层蚁群算法来求解工艺路线设计中多约束问题，流程如图2所示。将求解过程划分为两个过程：一层蚁群算法从工序元中按加工顺序得到初始信息素浓度，二层蚁群算法按选择概率函数和初始信息素浓度找到工序元特征分层拓扑排序序列，在上述工序元序列中找到满足加工资源更换值最小的序列。期望值是根据企业现有的加工资源更换效率而定。

图2 工艺路线设计流程图

(1)为了将该方法描述清楚，以图1中的特征1、特征2、特征4为例。特征1所代表的的是端面，101102代表粗车精车；特征2所代表的是轴，201202代表粗车精车，203204205代表粗车精车粗磨，206207208209代表粗车精车粗磨精磨；特征4所代表的是槽，401402代表粗铣精铣，每个工序元对应的加工资源C1、C2、……有所不同。首先考虑加工顺序，先粗后精，聚类加工。一般蚁群算法用于求解优化问题的时候，初始信息素浓度定义各个单元相同。改进的蚁群算法，通过一层蚁群算法信息素更新，使得第二层蚁群算法的初始信息素浓度改变，并且和工序元之间加工顺序有关，一层蚁群算法信息素更新后，入度相同的特征元之间信息素浓度高于其他，如101、201、203、206之间入度均为1，信息素浓度肯定大于它们和其他工序元浓度。

(2)一层蚁群搜索使得满足分层拓扑顺序的工序元信息素浓度增加，蚂蚁在启动二层蚁群搜索的时候优先选择和自己入度相同或相近的工序元。随机选择起点工序元，这些序列都满足按入度从小到大排列规则，如图3所示，其对应的加工资源如表1。蚂蚁在启动二层蚁群搜索的时候，蚂蚁在这些序列中搜索满足加工资源更换最小的序列。

图3 入度排列关联图

工序元加工资源101、201、206C1102、204、207C2202C3203C4205、208M1209M2401X1402X2

3.2 改进的信息素更新规则

信息素更新采用蚁周系统，其具有随机性能保证全局搜索，更新规则如下：

一层蚁群搜索公式(13)～式(15)：

(13)

(14)

Ltabu=min(Cij，i，j=1，2…n)

(15)

rij为i，j经过m只蚂蚁后的信息素浓度，rijk为第k只蚂蚁在i，j边留下的信息素浓度，Q为信息素一个常量，Ltabu_s为禁忌列表中前s个工序元对应入度的大小，s为拓扑排序中入度为1的工序元个数，Lrudu_s是为了保证在第二层蚁群搜索中，随机选择起点加工元中入度为1的能排在前面。

二层蚁群搜索公式(16)～式(18)：

rie jf′(t+n)=ρrie jf′(t)+Δrie jf′

(16)

(17)

(18)

rie jf′(t+n)为经过n次迭代i，j加工资源更换路径上的信息素，Δrie jf′为p只蚂蚁经过后留在ie，jf路径上的信息素，Ltabu′为加工资源禁忌列表里面，蚂蚁完成一次遍历后得到的加工资源更换率。

4 仿真与分析

4.1 算法性能测试

为了验证本算法的性能，采用经典文献中的数据为样本，并与文献中的结果进行对比。数据来自于文献[8]，共有40个工序元，采用本算法得到加工路线如表2所示。

通过表2看出机床更换3次，刀具更换7次，夹具更换10次，Cmin=5.7，结果与文献得到的结果相差不大。图4为测试两例算法收敛情况，本文算法对特征包含的工序元进行分层拓扑排序，缩小蚂蚁搜索范围，在较短的时间内达到收敛，在收敛情况方面略优于文献[8]算法。

图4 算法收敛情况对比

序号加工内容位置加工资源更换加工资源次数机床刀具夹具1粗车5、6、8、92y2 t1 f1———2粗车1、2、3、48y2 t1 f113精车18y2 t2 f114精车92y2 t2 f115钻9-12y2 t5 f116钻1-18y2 t5 f117半精车2、3、4、2-18y2 t2 f2118半精车5、6、7、8、8-12y2 t2 f219粗磨5、6、7、8、5-1、6-1、7-12y5 t3 f311110粗磨2、3、4、2-2、3-18y5 t3 f3111精磨2、48y5 t4 f3112精磨6、7、82y5 t4 f3113铣键槽6-22、8y6 t1 f411114滚齿4-16y7 t8 f5111

表3 减速器传动轴特征属性表

4.2 实例仿真

以某企业生产的减速器传动轴为例，如图5所示，对该轴的特征进行分析，得到特征属性表3；该企业可用机床、刀具、夹具等可用加工资源信息如表4所示。

对该传动轴49工序元进行分层拓扑排序，如图6所示。算法参数设置如下：蚁群个数m=49，α=1，β=5，ρ=0.95，企业期望加工资源最小更换率ε=70%。通过算法求解，机床更换2次，刀具更换8次，夹具更换14次，得到工序元最佳加工顺序如图7所示，加工资源更换率为(0.55×2+0.15×8+0.3×14)×100%=65%，满足企业要求。

图5 某企业减速器传动轴设计图

工序元刀具机床类型ω3、ω7、ω11、ω14、ω17、ω25、ω29、ω36、ω40、ω4590°车刀1CA6136、CA6140ω2、ω6、ω10、ω13、ω16、ω24、ω28、ω35、ω39、ω4590°车刀2CA6136、CA6140ω5、ω23、ω32、ω3445°车刀1CA6136、CA6140ω4、ω22、ω31、ω3345°车刀2CA6136、CA6140ω8、ω12、ω15、ω18、ω26、ω30、ω37、ω41粗磨砂轮M1320-520ω9、ω19、ω27、ω38、ω42精磨砂轮M1432Aω1、ω44平头铣刀X62W、X6030ω20、ω21、ω43、ω44键槽铣刀X62Wω1、ω47麻花钻CA6136、CA6140

图6 传动轴工序元有向无环图

图7 传动轴加工路线

5 结束语

本文以特征为起点划分工序元满足了加工准则中“聚类加工”即相同的基准、特征上的加工元期望能排在一起加工。工序元按入度从小到大排序满足了加工准则中“先粗后精”的要求。定义了加工资源最优模型，通过对两层信息数更新规则的改进，提高了算法的效率和解的可行性。实验结果表明，文中提出的算法能很好的在加工准则约束和目标函数约束下求解，得到满足企业所期望达到的效果。