遗传算法在箱体零件CAPP数控加工工步排序决策中的应用研究

刘晓阳，刘恩福，方忆湘，李宗斌

LIU Xiao-yang1, LIU En-fu1, FANG Yi-xiang1, LI Zong-bin2

（1.河北科技大学 机械电子工程学院，石家庄 050024；2.西安交通大学 制造系统国家重点实验室，西安 710049）

0 引言

机械制造中，箱体零件由于品种多样、结构复杂、生产状态模糊和生产环境复杂，使得工序工步排序变成为极其复杂的决策过程。在现代数控加工中，一般工序数目较少，而一个工序内工步数目较多，此时工步排序则变得更复杂、更详细。本文使用遗传算法解决了CAPP中加工工步的优化排序，在文献[4]的基础上，目标函数由换刀时间、工作台转位时间和刀具在三个坐标轴方向快速移动到加工区域所需要的时间组成。并利用多色集合理论将工步排序的约束规则以围道布尔矩阵的形式存储，根据不同的加工对象，通过添加约束规则确保工步之间的约束顺序。

1 工步排序的数学模型

工步排序的数学模型可描述为[4]：

设S={s1,s2,…,sn}是某工件在加工中心上一次装夹的n(n>1)个加工工步的集合，S有n个元素， 所以存在n！种工步顺序，这n个工步构成某一种工序顺序x={o1,o2,…,on}。通过进行优化找一个最优的顺序x*，能够满足要求的约束规则，并且使换刀、工作台转位的辅助时间和刀具在三个坐标轴方向快速移动到加工区域所需要的时间最短。因此，目标函数f(x)由三部分组成：

每次换刀时间为tT，若顺序x中工步ai使用的刀具为Di，则顺序x的换刀时间f1(x)：

式中g(*)的取值如式(3)：

工作台转位90°需要的时间为t'i，若顺序x中相邻工步i和i+1之间工作台转过角度Ai，则顺序x的工作台转位时间f2(x)：

假设从工步oi到oi+1，刀具在3个坐标轴方向快速移动到加工区域所需要的时间ti,i+1，刀具快速移动的时间与刀具移动的距离有关，f3(x)可以表示为：

优化目标是寻找一种最优的工步顺序x*，使

2 加工中心上工步排序问题的约束模型

2.1 建立关系模型

多色集合理论（Theory of polychromatic Sets，TPS）[4,5]是俄罗斯的Pavlov V.V.教授于1995年提出的。它是一种新的信息处理工具。利用多色集合理论建立零件特征、工步排序的约束规则与加工工步、面孔属性之间的关系模型，如图1所示；零件特征与工步排序的约束规则之间的关系模型，如图2所示。前者把工步排序中的各个工步、面孔属性作为多色集合的设计元素，将加工零件特征和需要添加的约束规则作为多色集合的统一颜色，后者将工步排序的约束规则作为多色集合设计元素，将加工零件特征作为多色集合的统一颜色，建立了工步排序过程的网络数学模型，形成围道组成矩阵[A×F(A)]和[F(Ai)×F(Aj)]。

图1 围道组成矩阵[A×F(A)]

图2 围道组成矩阵[F(Ai)×F(Aj)]

假设一条加工路线由9个加工工步组成，分别是a1,…,ai,…,a9，面孔属性分别表示为b1 和b2，集合A数学表达式为：A=(a1,…,ai,…,a9,b1,b2)。

颜色集合F(A)由零件特征和添加的约束规则组成，假设某零件由有编号为1～20的特征，每个特征的加工工步链如下：通孔1、2、5、8、11、16、19：粗镗—精镗；平面4、7、10、13、15、17：粗铣—精铣；螺纹孔系3、6、9、12、14 、18、20：钻。

在图1中表示成ai和Fj对应的单元格中为“●”就表示了颜色Fj（A）和元素ai的颜色Fj（ai）。可查找 到具有“相邻约束”的工步类型并以表1的形式彼此之间可能存在约束关系。

表1 具有“相邻约束”的工步类型之间的约束关系

表1中●表示竖列和横列的工步类型之间存在关联，对应的横列的工步类型在前，竖列的工步类型在后。在表1中可以看到a1和a2之间存在“相邻约束”关系；在表中a5和a7也含有“相邻约束”关系，但只存在a5a7，并且a5和a7有先后的约束要求，也就说在加工过程中存在工步类型a5要先于a7进行加工。

在图2中， F21、F22、F23表示成工步关联关系分别为oioj、om^on和(ol,ok)。 oioj表示oi和oj在工步排序中相邻，om^on表示om和on不相邻，(ol,ok)表示ol排在ok的前面，ol和ok不相邻约束。

2.2 基于关系模型获得相关联的工步

通过上面建立的关系模型，找到彼此之间相关联的工步并以布尔矩阵的形式进行存储，过程如下：

1）通过图2找到约束要求Fj对应的特征Fi。

2）通过如图1所示布尔矩阵找到约束要求Fj对应的工步类型ai。

3）通过Fi和ai可以找到工步oi，oi即为含有约束要求Fi的工步，同样可以找到与oi相关联的工步oj。

3 利用遗传算法进行工步排序

3.1 通过编码产生初始种群

编码采用实数编码的方式，通过编码产生初始种群。设有n个工步，则基因值为在1～n之间随机取值，且每个基因值不同。假设有u个特征，v种加工方法，w种约束规则。将类似图1的数据存入二维数组a[v][u+w]中，具体编码过程如图3所示。

图3 编码产生初始种群的流程图

按照图3进行编码得到的染色体都满足先粗后精、先面后孔的约束条件，每一条染色体代表一个合理的加工顺序。

3.2 交叉操作

设需要进行交叉操作的两个父代个体为A1、A2，它们交叉之后产生的子代个体为B。随机产生两个交叉位置e1、e2，设e1

交叉操作是GA产生新个体的主要方法，所以交叉概率一般应取较大值。但若取值过大又会破坏群体中的优良模式；若取值多小，产生新个体的速度又较慢。一般建议的取值范围是0.4～0.99。

3.3 变异操作

变异操作采用启发式互换式变异，即随机选取一个基因位置，判断该位置的基因能不能与前面或者后面的基因值互换，判断过程中需要利用约束模型。

变异概率是增加种群多样性的重要因素，太小则不会产生新个体，太大则使遗传算法成为随机搜索。由于本算法的变异操作具有非强制性，而是满足相应的条件才执行，所以变异概率不宜取太小，在0.2～0.9之间为宜。工步数目较少时，交叉概率和变异概率取较大值；反之，取较小值。

4 实例

图4是一个箱体类零件，基于建立的关系模型利用遗传算法对箱体零件的加工工步进行排序。该箱体零件需要加工20个特征，主要是孔系的加工，方位面分为后面、左面、前面、右面和顶面。

进行工步排序前，首先添加约束规则和参数的设置。获得零件特征所在方位面及对应的加工工步，进行约束规则的添加，获得添加约束的工步。取遗传算法运行参数的群体大小为101，交叉概率为0.75，变异概率0.85，最大进化代数为120。每次换刀时间为5秒，工作台转位90°所需时间为2秒，可通过工步排序取得最优解。所得结果满足工步排序受到的条件约束，即先粗后精、先面后孔，且能较快地得到较优的排序结果，能够较大程度地实现方位集中和刀具集中。

图4 箱体零件模型

5 结论

本文主要解决数控加工中心上箱体零件一次装夹下的工步排序优化问题。利用多色集合理论建立了加工中心上工步排序问题的约束模型，在进行工步排序过程中，能够根据零件的实际的加工要求灵活的添加约束规则，利用上述遗传算法寻求工步顺序的近优方案。本文所提出的方法同样可以解决其它零件工艺路线的决策问题。

[1] 蒲建,王先逵,吴丹.工艺规划中的组合优化问题[J].清华大学学报,1997,37(8)：69-71.

[2] 秦宝荣,王宁生.基于遗传算法的加工中心工步排序优化方法[J].中国机械工程,2002,13(18)：1531-1533.

[3] 秦宝荣,柯文,王宁生.基于遗传算法的箱体零件加工路线决策方法研究[J].中国机械工程,2002,13(24)：2071-2075.

[4] 郝建波,李宗斌,赵丽萍.加工中心上工步排序问题的约束模型及其遗传算法求解[J].西安交通大学学报,2008,7(7)：860-864.

[5] 李宗斌.先进制造中多色集合理论的研究及应[M].北京：中国水利水电出版社,2005.