基于遗传算法的加工工艺规划研究
2011-02-20李梅竹
李梅竹
(陕西广播电视大学工程管理系， 陕西 西安 710119)
0 引 言
随着CAD技术的大量推广和应用以及制造业信息化工程的推进，制造业中越来越多的企业迫切地需要借助于CAPP来提高工艺设计的效率和水平，建立包括产品工艺信息在内的完整的企业产品信息，以提高自身快速反应市场的能力和竞争力.作为设计和制造的中间环节，CAPP系统的研制和开发工作并不顺利.究其原因，CAPP面临的困难与工艺设计的特点是分不开的[1].
本文致力于工艺规划系统的研究，建立了典型加工特征的工艺路线选取规则，对零件单个特征进行了工艺路线选择，再运用全局优化思想，考虑具体加工过程，对整个零件加工进行了工艺规划，实现了工艺排序关键技术.
在本文中应用遗传算法建立了零件加工方案组合优化的数学模型，并将该方法应用到具体零件的工艺排序决策过程中，通过编码、杂交、复制、变异等得到了满足零件要求的最优或接近最优的工艺路线[2].
1 零件典型特征加工方法
机械零件的结构形状是多种多样的，但它们都是由平面、外圆柱面、内圆柱面或曲面、成形面等基本特征组成的.每一种特征都有多种加工方法，具体选择时应根据零件的加工精度、表面粗糙度、材料、结构形状、尺寸及生产类型等因素，选用相应的加工方法和加工方案.
进行零件工艺规划，首先要确定零件主要特征最终工序的加工方法.下面先详细介绍一下平面这种典型特征的加工方法的选择[3-6].
平面的主要加工方法有铣削、刨削、车削、磨削和拉削等，精度要求高的还需要经过研磨或刮削加工.常见平面加工方式如下图1所示，其中尺寸公差等级是指平行平面之间距离尺寸的公差等级.
2 基于图的加工方法选择
图是一种比线性表和树更为复杂的非线性结构.在线性结构中，结点之间存在一对一的线性关系.在树形结构中，树中结点之间存在着明显的一对多的层次关系.而在图结构中，对结点(图中常称为顶点)的前驱和后继个数都是不加限制的，即任意两个结点之间均有可能相关，结点间可以存在多对多的关系[7,8].
图1 常见平面的加工方案
由于图的结构比较复杂，任意两个顶点之间都可能存在联系，因此很难用顺序存储结构来存放图.在实际应用中，是根据具体的图来设计适当的存储结构.常用的存储方法有两种：邻接矩阵表示法和邻接链表表示法[9].邻接表表示法是使用基本链表来链接每个顶点的邻接顶点的.每个顶点的结构如图2所示.
图2 邻接表结点结构
图1所示的加工方案图是有向图，按照图的存储结构，把它们分别转化成邻接表表示形式，见表1.
表1 常见平面加工方案邻接表
图 3 VertexInfo类的UML定义 图4 Digraph类的UML定义
想要存储这些顶点的信息，就要定义一个向量v[1]，v[2]，…，v[n]，每个元素对应加工方案图中的一个顶点.每个v[i]存储顶点i中的数据以及一个链表包含所有邻接于顶点i的顶点编号.而对于每个v[i]将采用一个类结构来对其定义，相关定义如下：
class VertexInfo
vector
其中类VertexInfo用来存储单个顶点信息，向量v用来存储所有顶点信息.对类VertexInfo采用UML建模，如图3所示.
这样采用邻接表表示法的加工方案图中信息的存储就转化成用程序对抽象出来的信息的读取，把类VertexInfo实例化为一个对象vi，顶点的相关信息(加工类型、邻接点、粗糙度等)存入相应的数据结构中，再把vi压入类向量v中，如此反复，直到把所有的顶点信息全部读完.
加工方案邻接表建立以后，首先要对加工方案进行遍历，对已存在的各种加工方案的加工类型、邻接点以及所能达到的粗糙度进行存储，以备后期操作的选取.
为了完成这项工作，定义了一个模板类Digraph，采用UML建模，如图4所示.
3 基于遗传算法的工艺路线生成
工艺路线设计是指拟定将毛坯制成所需零件的整个加工路线，是制定工艺规程的总体布局.在工艺路线设计时，应提出几个设计方案，从中加以分析比较，最后确定一个最为合理的方案.在本文中将采用自适应全局优化概率搜索算法——遗传算法来进行工艺路线生成的研究.
复杂零件的工艺特征之间存在着各种约束关系，按照实际要求的不同，可以将它们分为强制性约束和最优性约束.将强制性约束集记为Ra，最优性约束集记为Rb.
强制性约束集Ra在工艺实践中的表现为先后顺序上的约束，这是工艺路线中最重要的约束条件.必须考虑的几类关系有：(1)先基准面后其它.(2)先面后孔，先面后键槽.(3)先主后次.(4)非破坏性约束关系.(5)可访问性约束.(6)特征属性自身的严格的先后顺序[10].
最优约束集Rb一般出于对加工时间、精度和成本的考虑，通常包括：(1)尽量减少装夹次数,(2)尽量减少换刀次数,(3)聚类约束[10].
GA主要操作包括编码解码、适应度计算、遗传算子设计.首先确定求解问题的数学模型，生成原始种群，对种群个体进行编码和解码，然后对各代群体中个体的适应度进行计算，然后使用遗传算子完成选种、交叉和变异，繁衍后代种群，直至满足收敛条件，求得所需的最优解[11,12].图5是其基本工作流程.
图5 基于遗传算法的排序工作过程
3.1 编码
应用GA首先要对问题中的变量进行编码，编码的形式没有限制.常用的是二进制码链.对于工艺排序问题，自变量为特征加工单元，问题是求解特征加工单元排序问题，采用二进制编码不能解决.因此，在本文中选用自然数编码方式，基因编码如表2所示.
表2 基因编码
3.2 始群体的产生
一般采用随机方法产生一系列初始码链，构成原始群体.GA的任务是从这些原始群体出发，模拟进化过程，汰劣存优，最后得出优秀的群体与个体，满足优化的要求.
3.3 适应度计算
遗传算法中以个体适应度的大小来评定各个个体的优劣程度，从而决定其遗传机会的大小.
设计适应度函数时，主要考虑装夹次数、换刀次数和聚类是否满足这3方面因素，因此适应度函数定义为：F=a1×Score1+a2×Score2+a3×Score3，其中，Score1、Score2和Score3分别表示装夹得分、换刀得分和聚类得分，每部分满分均为100，a1、a2和a3分别表示3部分的权重，取值：a1=0.5，a2=0.3，a3=0.2，适应度满分也为100.
(1)装夹得分(n个特征，k种装夹类型，Ns次装夹)
(1)
(2)换刀得分(n个特征，l种刀具，Nt次换刀)
(2)
(3)聚类得分.设存在k个聚类约束Cluster[1]，Cluster[2]，…，Cluster[k]，对于Cluster[i]，定义如果该约束能够满足则Φ(Cluster[i])=1，否则Φ(Cluster[i])=0，可得：
(3)
3.4 选种
选种就是从群体中随机的选取一对个体作为其繁殖后代的双亲.通常根据个体适应度，按照一定的规则或者方法，从第t代群体P(t)中选择出一些优良的个体遗传到下一代群体P(t+1)中.
3.5 交叉
交叉就是将群体P(t)内的各个个体随机搭配成对，对每一个个体以某种概率(称为交叉概率)选择一个断点，将双亲的基因码链在断点处断开，然后模拟自然交配过程进行交换其断开后的一部分.
3.6 变异
变异操作模拟生物在自然遗传环境中由于各种偶然因素引起的基因变异,其方法是以一定概率P(称为变异概率)从群体中选取若干个个体，对所选的每个个体随机的选取某一位或一些基因值，改变为其他的等位基因.
图6 系统功能图
4 系统运行实例
本课题所开发的系统主要分为以下两个功能模块：(1)特征加工方法生成模块,(2)工艺路线优化模块.图6所示为整个系统功能图.下面就以图7所示零件的加工实例来对整个系统的功能进行介绍.
图7 基于遗传算法的排序工作过程
该零件有6个加工特征，包括面(1)，孔(2，3，4)，槽(5，6)，括号内为特征编号.6个加工特征其粗糙度要求分别为面1为Ra3.2，孔2为Ra12.5，孔3和孔4都为Ra1.6，槽5和槽6都为Ra3.2.参照前面所提供的典型特征加工方案图和加工方案邻接表，采用图结构，可以获得每个待加工特征的所有可行加工方法.
图8 工艺参数输入 图9 孔3加工路线选择界面
得到零件几何特征并且通过工艺性评价之后，系统采用人机交互的方式输入加工工艺参数，如图8所示.加工工艺参数主要包括形状公差、定位公差、轮廓公差、跳到公差、定向公差和表面粗糙度.
零件特征的加工路线方法选择已经在前面进行了详细介绍，在此只给出孔3的加工方法选取作为示例.选择孔加工，表面粗糙度0.8，加工起点选择1.进入下一步可得到可行加工终点编号以及对应的可行加工路线，如图9所示，选择加工终点为8的加工路线来加工孔3，即孔3的加工方法是：钻孔—粗铰—精铰.同理可以获得其他几个加工特征的加工路线.
当零件所有特征加工方法选取完毕，如图10所示，就可以得到零件特征加工链.
再为零件的加工选择合适的机床，确定加工特征所需要的加工设备，如刀具、装夹等,如图11所示为刀具选择界面.
图10 孔3零件特征加工链 图11 刀具选择
为了验证该系统所采用的遗传算法的可行性，对加工该零件所需的加工资源进行理想化.选用数控机床，完成该零件的加工需要装夹2次，第一次装夹完成面1上特征的加工，第二次装夹完成孔2的加工；刀具的选择：面1、槽5和槽6的加工选择铣刀；孔的加工分别选用钻刀和铰刀.根据不同的加工阶段可能分为粗铣刀、精铣刀等，根据不同的加工特征又可能分为面铣刀、键槽铣刀等.
对特征的加工刀具进行合并，例如槽5和槽6，孔3和孔4，分别采用同一刀具进行加工，减少换刀次数，提高加工效率.合并之后总共需要7把刀具，分别用于粗铣面1、粗铣槽5和槽6、精铣面1、精铣槽5和槽6、钻孔、粗铰和精铰.
参照表2的编码方式进行编码，该零件编码长度为13.
表3 特征编码
面1：f1粗铣，f2精铣；孔2：f3钻孔；孔3：f4钻孔，f5粗铰，f6精铰；孔4：f7钻孔，f8粗铰，f9精铰；槽5：f10粗铣，f11精铣；槽6：f12粗铣，f13精铣.
特征加工单元集合为：F={f1,f2,…,f13}共13个特征加工单元，采用自然数实现编码，如表3所示.
建立强制约束集Ra：
(1)f1必须首先加工，作为基准面；
(2)f12必须在f4之前加工，因为特征孔3包含在特征槽6里面；
(3) 特征属性的严格顺序约束，一个表面的粗加工工序必须在精加工之前.
参照之前给出的理想化加工资源，分2次装夹和需要7把刀具用于零件的最后加工成型，给出优化约束集Rb：
(1) 装夹类型集：{SU1，SU2}，其中SU1={f1,…,f2,f4,…,f13},SU2={f3}.
(2) 刀具集：{T1，T2，T3，T3，T5，T6，T7},其中T1={f1}，T2={f10,f12}，T3={f2}，T4={f11,f13}，T5={f3,f4,f7}，T6={f5,f8}，T7={f6,f9}.
(3) 聚类约束集.孔3与孔4最好一起加工，槽5与槽6最好一起加工.
Rb用于确定适应度函数.F=a1×Score1+a2×Score2+a3×Score3,其中a1=0.5，a2=0.3，a3=0.2，Score1、Score2和Score3分别参照式(1)、式(2)和式(3)可得：
由表3可知该零件基因链长度为13位，根据前面介绍的遗传算法初始群体的介绍，为了程序能有效的运行初始群体数目的选择不应过多也不能太少，在这里选取种群大小为30.为保证初始群体中的每个个体的随机性，在程序编制时，每个个体都采用时间的随机函数产生一组编码.初始种群随机生成后，采用轮盘赌选择法进行选种，初步选取交叉率为0.7，变异率为0.2.
表4 加工码链及计算结果
所有参数确定以后，就可以进行遗传算法排序了.随机产生各个初始码链后，运用工艺约束条件产生的加工码链及计算过程如表4所示.
此时得到最优个体基因型：[1，10，12，3，4，7，5，8，2，11，13，6，9]，其表现型为{f1，f10，f12，f3，f4，f7，f5，f8，f2，f11，f13，f6，f9}，其中装夹次数3，换刀次数7，满足聚类约束，其适应度为95.5.
把该工艺路线与实际结果相比较，发现基本符合该零件的加工要求，在假定的加工环境下，满足特征间的约束关系，所以说该结果是合理可行的.
5 结束语
工艺规划即工艺路线设计是工艺设计过程中最重要内容之一.在实际工艺规划中，由于零件特征的多种加工链方案中包含的加工方法不同、加工链长短不同，直接影响加工路线排序、工序划分、机床选择等决策活动.本文致力于工艺规划系统的研究，建立了典型加工特征的工艺路线选取规则，对零件单个特征进行工艺路线选择，再运用全局优化思想，考虑具体加工过程，采用遗传算法对整个零件加工进行工艺规划，实现了工艺排序关键技术.
参考文献
[1
[2] 秦宝荣,姜少飞,王宁生.基于遗传算法的零件多加工方案组合优化方法[J].中国机械工程，2005,16(12):1 076-1 078.
[3] 徐宏海.数控加工工艺[M].北京:化学工业出版社,2004:78-91,125-132.
[4] 蔡 兰,王 霄.数控加工工艺学[M].北京:化学工业出版社,2005:53-57.
[5] 刘长青.机械制造技术[M].武汉:华中科技大学出版社,2005:218-255.
[6] 周世权.机械制造基础[M].武汉:华中科技大学出版社,2005:160-197.
[7] 张 勇,杨喜权,刘君义.数据结构[M].北京:中国林业出版社,北京希望电子出版社,2006.
[8] Ellis Horowitz,Sartaj Sahni,Sanguthevar Rajasekaran.计算机算法(C++版)[M].冯博琴,叶 茂,高海昌,等译.北京:机械工业出版社,2006：184-187.
[9] Larry R.,Nyhoff. C++ An Introduction to Data Structures[M].陈佩佩,李东国,黄达明,译.北京:清华大学出版社,2005:516-523.
[10] 徐 正.三维CAPP中零件特征提取及基于遗传算法的工艺排序研究[D].武汉：华中科技大学硕士论文,2005:1-5.
[11] Chen,Yuming. Management of water resources using improved genetic algorithms[J].Computer and Electronics in Agriculture,1997,(8):117-127.
[12] Gabor Renner,Aniko Ekart.Genetic algorithms in computer aided design[J]. Computer-Aided Design，2003,(7):709-726.
