一种基于蝙蝠算法的工艺规划方法

范孝良， 吴学华， 赵爱林， 王进峰

(华北电力大学能源动力与机械工程学院，河北 保定 071003)

一种基于蝙蝠算法的工艺规划方法

范孝良， 吴学华， 赵爱林， 王进峰

(华北电力大学能源动力与机械工程学院，河北 保定 071003)

为了解决结构复杂零件工艺规划效率低、质量差的问题，设计了一种改进的蝙蝠算法用来进行复杂零件的工艺规划。在传统的特征-工序的工艺路线表达方法的基础上，设计了合理的蝙蝠编码、解码策略。建立了工艺路线和蝙蝠在搜索空间位置的映射矩阵，设计了蝙蝠种群的初始化方法。为了扩大搜索范围，改进了蝙蝠算法原有的局部搜索策略，对局部最优解进行移位和变异操作，从而增加了种群的多样性。仿真实验验证了该算法进行工艺规划的可行性。

工艺规划；蝙蝠算法；工艺约束；局部搜索

计算机辅助工艺规划(computer aided process planning，CAPP)是计算机集成制造系统(computer integrated manufacturing system，CIMS)的重要组成部分[1]，大大提高了工艺规划效率和质量。近年来，数控加工设备的应用日益广泛，可从事的工序类型远远超出了普通加工机床，许多传统的CAPP系统已经不能够满足新的加工环境要求。材料科学的不断发展，使得特种装备越来越多，其制造精度要求、尺寸要求、服役环境要求等也超出了传统的机械加工工艺要求。另外，大型、奇型、结构复杂的零件或者装备在航天航空、深海勘探等领域出现的越来越频繁，其加工工艺也变得日益复杂。为了解决上述问题，必须对传统的CAPP方法进行改进。近年来，越来越多的人工智能技术应用CAPP，用以解决当前制造环境下的工艺规划问题。

王忠宾等[2]通过同时考虑机床和刀具的选择，进行工艺路线的决策，并利用遗传算法决策基于工艺约束的工艺路线规划问题，同时考虑操作的选择和工序的排序等多重任务来实现整个工艺过程的全局动态优化。刘伟等[3]将被加工零件划分为若干特征元，由各个特征元的加工链得到该零件的加工元。在禁忌准则和约束条件的限制下，利用改进的蚁群算法求解工艺规划问题。Wang等[4]人将零件的工艺路线表示为二维的矩阵，通过将多种局部搜索算法结合进传统的粒子群优化算法，进行工艺路线的决策和优化。近些年来，除了应用智能搜索算法进行工艺规划以外，在CAPP的数学模型方面，也进行了大量的研究。张祥祥等[5]为了在三维模型上实现工艺信息标识，提出了一种基于模型定义(model based definition，MBD)技术和 GB/T 24734-2009的机加工工艺信息标识方法。王进峰等[6]考虑到作业车间的实际情况，进行工艺规划，获得某种作业零件的多个可替换工艺路线，将传统的工艺规划问题和车间作业调度问题转变为二者的集成问题。

CAPP问题一直是工业领域和学术界研究的热点问题，尤其是随着零件结构日益复杂，奇型、异构件越来越多，应用传统的方法进行工艺规划往往面临的解空间太大，导致算法不收敛或者收敛过慢，最后无法获得最优解。本文利用蝙蝠算法求解工艺规划问题，设计了合理的蝙蝠编码、解码规则和种群初始化的方法，并将两种局部搜索算法结合到蝙蝠的局部搜索算法中，从而提高了算法求解工艺规划问题的效率。

1　工艺路线的表达

在CAPP系统中，工序内容是针对零件需要加工的特征表面。所以，在工艺规划过程中，零件表面的加工特征首先要映射为相应的工序。考虑到车间的实际情况，有可能会出现同一加工特征映射成不同的可选工序，在这种情况下，工艺规划首先要解决工序的选择，然后对选择的工序进行排序。零件特征与工序的映射关系如图1所示。

如图1所示，同一特征可以由多种不同机床、夹具、刀具进刀方向组合的工序表示[7]。CAPP第一步是根据零件的特征选择工序进行加工。第二步，根据特征之间的结构关系，确定工序之间的工艺约束。在工艺规划过程中常见的工艺约束主要包括先主后次，先粗后精、基准先行、先面后孔等。根据工序间的工艺约束，对第一步确定的工序进行排序。表1为某个零件的工艺路线。

图1　零件特征与工序的映射关系

表1　可选择的工艺路线示例

在CAPP系统中，通过工艺约束，在相关工艺知识表达的基础上，能够初步确定工艺路线。本文以生产成本最小化作为工艺规划的目标，并将生产成本分解为5个方面，即机床成本、刀具成本、装夹成本、机床更换成本和刀具更换成本[7-8]。

(1) 机床总成本TMC：

MCi表示机床Mi的成本。

(2) 刀具总成本TTC：

TCi表示刀具Ti的成本。

(3) 机床更换总成本TMCC：

MCC表示单次机床更换成本，Ω1(x,y)是判断函数：

(4) 刀具更换总成本TTCC：

式中TCC表示单次刀具更换成本，Ω2(x,y)是判断函数：

(5) 装夹总成本TSC：

式中SCC为单次装夹成本。

(6) 总加工成本TPC：

2　基于蝙蝠算法的工艺规划

2.1蝙蝠算法

自然界中，蝙蝠能够根据回声定位原理搜寻目标，避开障碍物。受蝙蝠回声定位行为的启发，Yang[9]提出了一种新型的元启发式算法-蝙蝠算法。所有的蝙蝠运用回声定位去感应距离，在搜索空间中蝙蝠i在位置xi以速度vi随意飞行，以固定频率f、可变波长λ和响度A0去搜索食物，并根据与目标物体的距离自动调节发射脉冲波长(或频率)，在靠近目标时调整脉冲发射频度ri。对于解空间搜索的蝙蝠 i而言，其位置 xi和速度 vi通过式(9)～(11)更新。

同时，脉冲发射的响度Ai和频度ri随着迭代过程而更新。

2.2编码

蝙蝠算法主要用于连续解空间的搜索，而工艺规划问题是离散的组合优化问题。因此，应用蝙蝠算法求解工艺规划问题，首先要进行工艺规划的编码和解码。工艺规划问题要解决工序选择和工序排序两方面的问题，因此，通过2×n的矩阵表示蝙蝠i在第t次迭代的位置。

第1行表示选择的工序，第2行表示已选择工序的排序。其中选择的工序可表示为：

其中，m_id、t_id、s_id分别代表工序n可选的机床编号、刀具编号和TAD编号。c可通过式(16)获得：

其中，NM、NT、NS分别代表加工本零件的机床、刀具、TAD的最大数量。对于表1所示的某条工艺路线可表示为表2所示的矩阵。

表2　工艺路线编码矩阵示例

在算法执行过程中，需要对蝙蝠的位置矩阵进行解码，以计算其所代表的工艺路线的总成本，从而衡量其优劣。对蝙蝠的位置编码矩阵xit1n解码可按照式(17)～(20)进行。

表3　示例编码矩阵的工艺路线

2.3初始化

蝙蝠种群初始化按照以下步骤进行：

步骤1. 参数初始化。包括种群规模Pmax，最大迭代次数Nmax，最大重复次数Rmax等。

步骤2. 按照2.2节所示的方法初始化蝙蝠种群的每一只个体的初始位置xi和速度vi。

步骤3. 解码每一只蝙蝠的位置矩阵，获得其工艺路线，并计算其TPC，获得当前全局最优的蝙蝠位置矩阵x*。

2.4迭代和局部搜索

(1) 根据式(14)～(16)，更新每一只蝙蝠的位置。

(2) 解码每一只蝙蝠的位置矩阵为响应的工艺路线，并计算其TPC。

虽然蝙蝠算法通过即时更新脉冲响度和频率的方式来进行局部搜索，但是实际进行复杂零件工艺路线优化的时候依然存在局部收敛或者收敛过慢的情况。因此，针对这两种情况，本文采用两种改进的局部搜索手段来进行工艺路线的优化。

在算法的执行过程中，早期阶段的非正常收敛依然时常发生。本文通过控制重复次数Rmax来避免过早的局部收敛，保持算法的稳定。如果连续Rmax次输出相同工艺路线，则重新启动算法。

当蝙蝠种群的循环迭代次数达到Nmax时，则算法结束。

3　实验验证

为了验证算法的有效性，以图2的零件为例进行说明[8]。该零件的加工特征和工序的映射和工艺约束如表4所示，成本信息如表5所示。

针对图2所示的零件进行了大量的重复性试验，试验结果表明在参数Pmax= 50，Nmax= 200，fmin= 0，fmax=1，A0= 1，α=0.9，γ = 0.9，w=0.75，pm=0.3，ps= 0.2 and Rmax=10的情况下，能够获得较好的工艺路线，最终的输出结果如表6所示。

图2　示例零件

表4　特征和工序的映射关系

表7对比了蝙蝠算法与遗传算法[8]、模拟退火算法[8]、禁忌搜索算法[10]和粒子群算法[11]的平均成本、最大成本和最小成本。从对比结果看，在表中所列举的3个评价指标下，蝙蝠算法都获得了最好的结果。

表5　机床、刀具成本表

表6　最优的工艺路线

表7　实验对比结果

4　结　论

本文改进了传统的蝙蝠算法用于复杂零件的工艺规划。设计了合理的蝙蝠编码、解码策略，建立了工艺路线和蝙蝠在搜索空间位置的映射矩阵，设计了蝙蝠种群的初始化方法。为了扩大搜索范围，改进了蝙蝠算法原有的局部搜索策略。对局部最优解进行移位和变异操作，增加了种群的多样性。针对典型零件的仿真试验验证了算法的有效性，对比试验结果表明在平均成本，最小成本、最大成本3个评价指标方面，蝙蝠算法都取得了最优秀的结果。

因为实际的车间运行状态直接影响着工艺规划的效率和结果，下一步的工作是将机床、刀具等装备的实时运行状态考虑到工艺规划的数学模型中，使工艺规划实时性更强。

[1] 邵新宇, 蔡力钢. 现代CAPP技术与应用[M]. 北京: 机械工业出版社, 2004: 5.

[2] 王忠宾, 王宁生, 陈禹六. 基于遗传算法的工艺路线优化决策[J]. 清华大学学报: 自然科学版, 2004, 44(7): 988-992.

[3] 刘伟, 王太勇, 周明, 等. 基于蚁群算法的工艺路线生成及优化[J]. 计算机集成制造系统, 2010, 16(7): 1378-1382.

[4] Wang Y F, Zhang Y F, Fuh J Y H. A hybrid particle swarm based method for process planning optimization [J]. International Journal of Production Research, 2012, 50(1): 277-292.

[5] 张祥祥, 陈兴玉, 程五四, 等. 基于模型的工艺信息标识方法研究[J]. 图学学报, 2012, 33(6): 146-150.

[6] 王进峰, 范孝良, 宗鹏程, 等. 一种改进的蚁群算法在工艺规划与车间调度集成优化中的应用[J]. 图学学报, 2014, 35(3): 396-401.

[7] Zhang F, Zhang Y F, Nee A Y C. Using genetic algorithms in process planning for job shop machining [J]. IEEE Transactions on Evolutionary Computation, 1997, 1(4): 278-289.

[8] Li W D, Ong S K, Nee A Y C. Hybrid genetic algorithm and simulated annealing approach for the optimization of process plans for prismatic parts [J]. International Journal of Production Research, 2002, 40(8): 1899-1922.

[9] Yang X S. A new metaheuristic bat-inspired algorithm nature inspired cooperative strategies for optimization (NICSO) [J]. Studies in Computational Intelligence, 2010, 284: 65-74.

[10] Li W D, Ong S K, Nee A Y C. Optimization of process plans using a constraint-based tabu search approach [J]. International Journal of Production Research, 2004, 42(10): 1955-1985.

[11] Guo Y W, Mileham A R, Owen G W, et al. Operation sequencing optimization using a particle swarm optimization approach [J]. Proceedings of the Institution of Mechanical Engineers B: Journal of Engineering Manufacture, 2006, 220(12): 1945-1958.

An Approach of Process Planning Based on Bat Algorithms

Fan Xiaoliang,Wu Xuehua,Zhao Ailin,Wang Jinfeng
(School of Energy, Power and Mechanical Engineering, North China Electric Power University, Baoding Hebei 071003, China)

An improved bat algorithm is employed to optimize the process planning for the complicated part to improve the efficiency and quality in process planning. A feasible bat encoding and decoding strategy is designed based on traditional process route representation method from the features to processes. The mapping matrix of process route and bat positions in the search space is constructed, and an initialized approach of bat population is designed. A modification for the local search of bat algorithms (BA) is executed to explore the search space. And displacement and mutation operation for local optimal solution are executed to diverse the population. Simulation experiments verify the feasibility of the proposed algorithm for process planning.

process planning; bat algorithm; operation constraints; local search

TP 301

A

2095-302X(2015)06-0856-06

2015-06-24；定稿日期：2015-07-31

中央高校基本科研业务费专项资金资助项目(13MS100，14ZD37)；国家自然科学基金资助项目(51301068)；河北省自然科学基金资助项目(E2014502003)

范孝良(1962–)，男，河北承德人，教授，硕士生导师。主要研究方向为计算机集成技术、现代制造信息系统、工业工程等。E-mail：wcx803@163.com