成 彬，景冰雪

（1.西安建筑科技大学理学院，陕西西安710055；2.西安建筑科技大学机电工程学院，陕西西安710055）

计算机辅助工艺规划（computer aided process planning，CAPP）作为连接设计和制造的纽带，其合理性很大程度上决定了成品质量和生产成本。在顾及加工方法和加工资源时，满足工艺约束的工序排序优化呈现受多重约束且具有多样性的特点，是生产决策中的重要环节［1-2］。

近年来，国内外众多学者对工艺路线的决策问题进行了深入研究。Dou等［3］通过适当的编码和更新可行的操作序列来满足各操作之间的优先关系，利用离散粒子群优化算法中的均匀和贪婪突变操作改进机床、刀具的每一个操作和刀具进刀方向（tool approach direction，TAD），最终得到加工成本最低的工艺路线；Milica等［4］提出一种混沌粒子群算法，并验证了该算法对工艺路线优化的灵活性与优越性；安相华等［1］提出一种直觉模糊集合与第2代强度Pareto相结合的优化算法，来求解考虑加工资源更换成本的工艺路线优化多目标函数；Luo等［5］利用免疫原理来保持遗传算法的多样性，实现多个目标集成的工艺规划的优化；窦建平等［6-7］提出一种面向可行工序序列的新型遗传算法，进行工序排序优化，通过引入精英参与的新型交叉策略与自适应的交叉概率和变异概率，提高收敛速度和全局寻优能力；黄风立等［8］将工艺路线的优化问题转化为对制造特征的排序，提出将禁忌制造特征动态更新方法与Ant-Cycle模型的蚁群相结合的算法；Hu等［9］为实现工艺约束与操作序列的组合优化，采用一种基于操作优先图的蚁群优化算法，提高了蚁群算法的全局搜索能力。由以上研究可知：在工艺优先关系处理方面，主要采用直觉模糊集、动态禁忌算法及对可行性工序序列进行编码。通过比较可知，可行性工序序列（拓扑优先顺序）在视觉及搜索空间上都具有一定的优势。在优化算法方面，改进粒子群（particle swarm optimization，PSO）算法、Pareto最优解算法、遗传算法（genetic algorithm，GA）与蚁群优化（ant colony optimization，ACO）算法被广泛应用。基于拓扑优先顺序的工艺路线规划，在正反馈、随机性、禁忌搜索等方面较蚁群算法有优势［10］。

本文针对在工艺路线规划中存在的多重约束问题，提出一种细菌觅食和蚁群优化（bacteria foraging ant colony optimization，BFACO）算法：一方面，通过拓扑优先顺序补充蚁群算法的初始信息素，提高蚁群算法的应用性，并满足加工工艺约束；另一方面，针对蚁群算法易出现局部收敛且计算速度慢的问题，引入细菌觅食算法中的复制操作和趋向操作，提高蚁群算法的计算速度及跳出局部收敛的局限，最终求解最优加工序列。

1 工艺路线规划问题的描述

1.1 加工元间的优先关系

在机械加工过程中，针对零件的同一特征须进行一系列确定的加工操作。将形成加工操作的各基本元素定义为加工元（machining element，ME）［11］，数学上可描述为一个五元组：

式中：ME表示加工元；Fm、Ms、Er、Pm、Al分别表示零件特征、加工阶段、加工方法、加工阶段所需的资源及加工余量。其中，加工阶段包括粗加工、半精加工和精加工，加工方法一般包括车、铣、刨、磨和镗，加工阶段所需的资源包括机床、装夹和刀具等。

根据零件特征在几何和加工上的相互约束及有关技术要求，为保证零件加工精度，加工元的排序须遵循基准先行、先面后孔、先粗后精、聚类加工及其他工艺准则。对在以上工艺准则下形成的加工元的优先顺序，可通过构建拓扑优先顺序图来求解满足要求的最优解，具体如图1所示［9］。

加工元拓扑优先顺序图包含的2个元素分别为节点与指向节点的边，而拓扑优先顺序图排序的主要依据为各节点的入度。图论中节点的入度为指向该节点的边的数量，本文所指的入度为自起点指向节点的路径连接边的最大条数。加工元可按入度的大小进行排序，入度越大的越后加工。当指向节点的路径不止1条时，以入度最大的路径为准。如图1（b）中：无指向ME1的边，则ME1的入度为0；指向ME10的路径至少存 在 2 条（ME1→ME18→ME7→ME8→ME9→ME10；ME1→ME5→ME4→ME8→ME9→ME10），这 2条路径连接边的条数均为5，则ME10的入度为5。由此可知：拓扑优先顺序是以入度为0的节点为起点，入度越大，则排序越靠后；若加工元存在顺序并行状态，则可随机穿插在某一加工路线中，但须保证加工工艺约束，为后续研究考虑加工资源更换率的加工元排序提供有利条件。

图1 零件加工元的拓扑优先顺序图示例Fig.1 Example of topological priority diagram of part machining elements

1.2 加工元多目标函数的建立

在规划工艺路线时，除工艺约束外，另一个保证加工质量与节约生产成本的关键因素是加工资源（机床、装夹和刀具）更换率。对优化模型所涉及的各项加工资源进行定义：机床集合Ms={M1，M2，…，Md}；加工装夹集合Js={J1，J2，…，Je}；刀具集合 Ts={T1，T2，…，Tf}。在加工过程中，通过加工资源可加工的加工元集合判断是否须更换加工资源。如果进行下一工序时，所加工的加工元不属于上一工序的加工资源集合{Mi，Ji，Ti}，则须更换加工资源。在考虑加工资源更换成本的情况下，构建机床、刀具和装夹的目标函数［8］：

式中：Mc、Jc、Tc分别为机床、装夹和刀具的更换成本；λM、λJ、λT分别为机床、装夹和刀具更换成本的权重；n为零件加工元个数；i为加工元；η为机床、装夹和刀具的更换函数。

在整个机械加工过程中，考虑加工资源更换成本的总目标函数Gc为：

2 基于细菌觅食和蚁群算法的工序优化模型及其应用流程

蚁群算法具有正反馈机制与分布式优化的特点，适合基于工艺约束的拓扑优先顺序的搜索，但存在局部收敛且计算速度慢的问题。针对蚁群算法的局限性，本文采用具有全局分布式优化优势的细菌觅食算法，求解加工资源更换率最小的加工元序列。

2.1 蚁群优化算法模型

本文对加工元拓扑优先顺序采取两次蚁群优化（twice ant colony optimization，TACO）算法，优化加工元序列及选择合理的加工资源［12-13］。首先，在保证信息素浓度的前提下随机搜索加工元序列，进行全局搜索；其次，依据第1阶段搜索的加工元序列再进行加工资源的搜索，求解加工资源更换率最小的最优解。

1）加工元序列搜索信息素的积累。

在不考虑加工资源选择的情况下，对拓扑优先顺序进行初始信息素的积累，完成多个加工元序列的搜索。其搜索公式如下：

式中：pij为从加工元i到j经过n只蚂蚁后积累的信息素浓度；r1为迭代次数；pkij为第k只蚂蚁经过边ij所积累的信息素浓度，其大小代表了加工序列蚁群搜索经过边ij的概率；Is为特征拓扑优先顺序中前s个加工元入度，其值均为1，保证了随机选择起点时入度为1的加工元排在序列前面；δ为路径上信息素蒸发系数；θ为信息素的质量系数；Nde为完成一次路径搜索后的加工资源更换成本，其值在加工资源路径搜索中确定。

2）加工资源搜索信息素的积累。

当加工元存在多个加工资源时，为实现加工资源更换率最小的目标，须选择合理的加工资源。因此提出在加工序列搜索的基础上实现对加工资源的选择，形成确定加工元序列的加工资源序列。其搜索公式为：

经过以上迭代过程，对任一加工元序列，理论上均可通过蚁群算法得到针对该路径的最优解。但当依赖上一节点选择当前节点合理的加工资源时，会存在选择失误的情况，此时仅依赖加工资源的蚁群搜索，可能会存在局部收敛与速度慢的问题。因此，须借助细菌觅食算法返回上一节点重新选择适当的加工资源，加快收敛速度。

2.2 基于细菌觅食的工序优化模型

1）细菌觅食优化算法。

细菌觅食优化算法（bacterial foraging optimization algorithm，BFOA）是由Passino提出的一种基于大肠杆菌群体觅食行为的生物启发式智能随机搜索算法［14］，解决了连续搜索域中的大量问题并已成功应用于全局优化算法［15-16］。该算法模拟了细菌在觅食过程中单位时间内获得最大能量的方式。当细菌搜索到优质食物源时，会释放信号与附近的其他细菌进行交流，并通过趋向操作和复制操作移动位置。实时计算、比较细菌最小适应度函数，当最小适应度值不再改变或达到设定的细菌个体迁移步长的临界值时，该最小适应度值为该次搜索的最优解［17］。

2）细菌觅食优化算法模型。

在细菌觅食优化算法中，趋向操作是使细菌能够翻转和游动。当加工元节点存在多个加工资源时，若选择了使加工资源更换率增大的加工资源，则采取翻转操作使细菌重返上一加工元节点重新选择，向使加工资源更换率减小的加工资源游动。细菌z的每一步趋向操作可表示为：

式中：σ（zg+1，h，f）是指细菌z在第g+1次趋向操作、第h次复制操作、第f次迁移操作后的位置；L（z）为细菌跨越加工元节点间的路径数；V（z）为细菌z趋向操作的随机的一个方向向量。

在细菌运动过程中，通过释放引诱剂与排斥剂发出信号，让其他细菌蜂拥而至。细菌间的信号传导过程如下所示：

式中：Jt[σa(g，h，f)，P(g，h，f)] 为添加了实际加工资源更换成本的时变加工资源更换成本，它随时间而变化，用以表示细菌在运动过程中引诱剂和排斥剂的释放情况；P（g，h，f）为群体中细菌所处加工元节点位置；a为细菌所处并行加工元节点位置的维度；b为搜索空间的变量数；e为自然对数的底；σmz，σmq分别为第z个细菌位置的第m个分量（行列式）和第q个细菌位置的第m个分量（行列式）；da，wa，hr和wr分别为吸引信号深度、吸引信号宽度、排斥信号高度和排斥信号宽度。

在计算实际加工资源更换成本后，令：

在进行复制操作时，需淘汰c/2（c为细菌总数量）个细菌。因数量变化导致其位置与跨越加工元节点间的路径数发生变化，可表示为：

2.3 基于细菌觅食和蚁群算法的工序优化模型的应用流程

将细菌觅食优化算法与蚁群优化算法进行组合，完成对加工元拓扑优先顺序的搜索，具体流程如图2所示。首先，利用蚁群优化算法搜索加工元序列，在此序列基础上搜索加工资源；其次，引入细菌觅食优化算法的复制与趋向操作。复制操作为：计算加工资源更换成本值Jt后，将其由小到大排序，淘汰后一半成本较高的细菌个体，复制保留前一半成本较低的细菌个体；趋向操作主要是实现细菌的翻转与游动，一般选择靠近的下一个加工资源。若加工元拓扑优先顺序图中2个节点间存在2条及以上路径，即存在路径并行的情况，则比较Jt值，若须翻转则返回至上一步，再进行一次趋向操作，从而达到加工资源更换成本最低的状态。细菌觅食算法结束的标志为搜索完此加工元序列的加工资源且细菌遍历结束，则最终返回蚁群算法进行第2次信息素积累。依次循环，直到获得加工资源更换成本最低的加工序列为止。

图2 基于细菌觅食和蚁群算法的工序优化模型的应用流程Fig.2 Application flow of process optimization model based on BFACO algorithm

3 BFACO算法验证实例

分别以图3（a）和图1（a）所示的零件为案例1和案例2进行研究，规划其工艺路线。在路线规划的第2阶段用蚁群优化算法搜索加工资源时融合细菌觅食优化算法，求解加工资源更换成本目标函数的最优解。分别用TACO算法和BFACO算法进行计算并对比，验证所提BFACO算法的有效性和优势。

图3 案例1的零件加工元拓扑优先顺序图Fig.3 Topological priority diagram of machining elements for case 1

3.1 工艺路线规划

案例1的加工资源信息如表1所示。

根据图3与表1可知，零件所属的34个加工元对应的加工资源集合为ME1={M1，J1，T1} ，ME2，ME17，ME19={M3，J3，T2} ，ME3，ME34={M4，J4} ，ME4，ME6，ME8，ME28，ME30={M1，J1，T3} ，ME16，ME18={M1/M5，J1/J9，T8} ，ME5，ME7，ME9，ME29，ME31={M3，J3，T5} ，ME10，ME12，ME13，ME15={M3，J6，T12} ，ME11，ME14={M3，J6，T13} ，ME20，ME21，ME22，ME23={M3/M4，J5，T14} ，ME24，ME26={M2，J2，T9} ，ME25，ME27={M5，J7，T10} ，ME32={M1，J1，T6} ，ME33={M3，J3，T7} 。

该案例中，取加工资源的成本权重λM=0.55，λJ=0.3，λT=0.15，蚂蚁数n=50，信息素的蒸发系数δ=0.5，信息素的质量系数θ=1。最终得到案例1的机床更换次数为4，装夹更换次数为6，刀具更换次数为12，最优解min Gc=0.55×4+0.3×6+0.15×12=5.8。具体的最优加工元顺序如表2所示。

表1 案例1的加工资源信息Table 1 Processing resource information for case 1

表2 案例1的最优加工元序列Table 2 The optimal sequence of machining elements for case 1

根据文献［9］所提供的案例2的加工资源信息，利用BFACO算法搜索并优化其加工元拓扑优先顺序，得到其最优加工元序列，如表3所示。

案例2与案例1的加工资源大致相同，因此可设置相同的加工资源的成本权重。最终得到案例2的机床更换次数为2，装夹更换次数为10，刀具更换次数为12，最优解min Gc=0.55×2+0.3×10+0.15×12=5.9。

表3 案例2的最优加工元序列Table 3 The optimal sequence of machining elements for case 2

3.2 算法验证

分别采用BFACO算法和TACO算法计算案例1和案例2加工元序列的加工资源更换成本，结果如图4和图5所示。案例1现有工艺路线加工资源更换成本min Gc=0.55×5+0.3×8+0.15×13=7.1［18］。通过比较可知，采用BFACO算法求得的加工资源更换成本较现有的加工资源更换成本下降18.3%，有效降低了零件加工过程的加工资源更换成本，同时拓扑优先顺序图的应用也保证了零件的加工精度。采用BFACO算法求得的案例2的加工资源更换成本较文献［9，19-20］得出的更换成本虽无降低，但在收敛代数方面有较大的改善。

图4 采用BFACO算法和TACO算法的案例1求解结果Fig.4 Solution results obtained by BFACO algorithm and TACO algorithm for case 1

在算法求解效率方面，如图4所示，BFACO算法在第65代已得到最优解，而TACO算法在第128代才得出最优解，由此可知BFACO算法可解决TACO算法局部搜索的缺陷，进行全局优化，提高求解速度。

图5 采用BFACO算法和TACO算法的案例2求解结果Fig.5 Solution results obtained by BFACO algorithm and TACO algorithm for case 2

为验证BFACO算法的总体优化效率，分别采用BFACO算法及改进的蚁群优化（modified ant colony optimization，MACO）算法［9］、粒子群优化（particle swarm optimization，PSO）算法［19］、遗传算法（genetic algorithm，GA）［20］、禁忌搜索（tabu search，TS）算法［20］以及模拟退火（simulated annealing，SA）算法［20］计算案例2的加工资源更换成本，结果如表4所示。由表3可知：在算法的质量方面，BFACO、TACO、MACO算法优于其他算法；在收敛代数方面，GA在第40代得出最优解，速度最快，但解的质量较差；在运行时间方面，BFACO算法比TACO算法的运行时间快。综合而言，BFACO算法的求解效果优于TACO、MACO、PSO、GA、TS及SA等算法。

表4 采用不同算法的案例2求解结果的对比Table 4 Comparison ofsolution resultsobtained by different algorithms for case 2

4 总结

针对工艺路线优化问题，提出一种基于细菌觅食的蚁群优化算法。首先，搜索满足工艺优先关系约束且包含加工方法和加工资源的加工元拓扑优先顺序，弥补了蚁群算法初始信息素匮乏的缺点；其次，在加工资源搜索阶段引入细菌觅食算法的复制和趋向操作，淘汰加工资源更换成本较高的一半细菌且复制成本较低的一半细菌以保持细菌群体的规模，当加工元节点存在多个可用资源时，进行趋向操作，返回上一节点重新选择加工资源；最后，由应用实例表明，BFACO算法较蚁群算法有较高的收敛速度，同时有效降低了加工资源更换成本，可为实际生产提供指导。

今后须将BFACO算法应用到更多的随机实例中，并和现有改进的其他智能算法进行系统对比。另外，BFACO算法还须扩展，以便应用于同时考虑多目标的工艺路线优化与调度集成优化问题。