基于遗传算法的工艺路线决策与优化

范顺成 王进峰② 李世杰

(①河北工业大学机械工程学院，天津 300130;②华北电力大学机械工程系，河北保定 071003)

工艺路线决策是指利用所有的加工资源设计出从毛坯到零件的详细加工过程，包括确定加工方法、选择机床和刀具、计算切削用量、优化加工路线、装夹工件等方面内容。计算机辅助工艺规划是指利用计算机模仿经验丰富的工艺设计人员完成工艺路线规划，是一个典型的多目标决策和优化过程。随着人工智能技术的发展，遗传算法、蚁群算法等智能算法逐渐应用于工艺路线规划问题的研究，为获得最优或者接近最优的工艺路线提供了理论和技术支持［1－2］。目前的研究大部分着重于工艺路线染色体的交叉、变异算法设计，对于工艺知识表达方法、基因编码规则等基础性工作讨论较少。

本文在工艺路线决策优化研究的基础上，确定了基于特征的工艺知识表达方法，构建基于工艺约束的工艺路线决策空间，建立了多目标优化函数，通过遗传算法对工艺路线进行优化。

1 工艺知识的表达

一个典型工艺路线决策一般通过以下步骤。

(1)选择定位基准。

(2)选择加工方法:1个零件被若干具有加工意义的加工特征所描述，例如孔、槽、倒角等。对于每一个加工特征，寻找所有能够得到加工特征属性(形状、尺寸、公差和表面粗糙度)的加工方法。

(3)划分加工阶段。

(4)选择机床、刀具、夹具:根据加工方法和制造资源能力，选择机床和刀具。

(5)选择切削用量:根据加工余量等，选择合理的切削用量。

(6)加工方法排序:根据工艺约束、加工成本、效率、质量等指标对加工方法排序，形成工艺路线。

CAPP系统中利用计算机完成上述工艺路线的决策。而工艺知识表达方法直接影响工艺路线标准化、规范化和工艺路线的决策水平。在CAPP系统中，工艺知识表达就是将工艺知识通过某种数据结构结合到计算机系统的程序设计过程，是工艺知识的模型化和形式化。

实践表明工艺知识粒度大小和关键工艺知识直接影响工艺知识的表达。工艺知识划分越细，其所表达的知识量就越大［3］。据此原则，CAPP系统中将工艺知识划分为工艺路线、工步、特征表面、加工阶段、加工方法、刀具、夹具、机床和切削用量9个方面，每种工艺知识可通过相应特征向量表达。因此，某零件的工艺路线可以表示为:

i是该零件包含的工步数，OPi是构成该零件的第i道工步，可表示为7维特征向量。

式中:P为加工表面;S为加工阶段，分为粗加工、半精加工、精加工;M为加工方法，分为车、铣、刨、磨、钻、扩、镗、铰等;D为定位基准;R为切削用量;E为机床;C为刀具;J为夹具。

OPi中每一个特征向量又可表示为相应的特征向量。譬如，切削用量特征向量为

式中:ID为顺序号，对于每一种零件工艺路线需要确定的切削用量统一编号，用以唯一确定每次选择的切削用量;v为切削速度，m/s;f为进给量，mm/r或者mm/z;ap为背吃刀量，mm。

加工表面特征向量为

式中:ID为顺序号，构成零件的每一个表面统一编号，用以唯一确定加工表面;PT为特征类型，包括平面、外圆、孔、键槽等。

CAPP系统中的其他工艺知识也可表述为相应的特征向量，由工艺路线、工步、加工表面等9种工艺知识向量能够准确地表达复杂零件的工艺路线。在工艺路线决策过程中，零件的加工表面是工艺路线决策的依据，根据加工表面的特征，譬如尺寸、位置、形状精度和表面层的物理机械性能进行定位基准、加工方法的确定，加工阶段的划分。为了能够实现加工表面的技术要求，决策合理的工艺路线，必须遵循加工表面间的优先关系，即工艺约束［4］。在CAPP系统中，工艺约束称之为关键工艺知识。关键知识影响工艺路线的决策过程。通常关键工艺知识包括以下内容:

(1)优先加工主要表面 当某个表面和其他表面存在形位公差时，确定该表面为主要表面，优先加工。当某个表面的加工影响到其他表面的装夹时，确定该表面为主要表面，优先加工。零件的辅助表面应安排在主要表面之后加工。譬如对于独立于其他工序的辅助工艺孔、槽、倒角等，应安排在主要表面之后加工。

(2)优先加工平面 先加工平面，再以平面定位加工孔。既能保证加工时孔有稳定可靠的定位基准，又有利于保证孔与平面间的位置精度要求。

(3)先粗加工，后精加工，粗精分开 一个零件各表面的加工一般都需要分阶段进行，粗加工工序应安排在精加工工序之前。

(4)其他工艺约束，譬如基于加工效率最高、成本最低等表面优先加工约束。

2 工艺路线的决策

选择合理的工装设备、切削用量、加工方法和顺序是工艺路线决策的重要内容。在CAPP系统中，通过工艺约束，在相关工艺知识表达的基础上，能够初步确定工艺路线。但是，该工艺路线往往不是当前生产环境下最优的工艺路线，譬如，最低成本的工艺路线［5］、最高效率工艺路线等［6］。因此，工艺路线决策时，除了能够满足基本的设计要求外，还需要针对不同目标优化工艺路线。实际上，工艺路线决策是一个带约束的非线性优化问题，即

式中优化变量x是工步顺序，由n个7维工步向量组成的工艺路线;hi(x)、gj(x)是约束函数。所谓最优工艺路线，是指在满足约束函数前提下，目标值最小。工艺路线进行优化决策的目标是使加工过程或者成本最低、或者质量最好、或者效率最高。

传统加工方式下，这3者往往是相互影响的。工程实践表明，频繁地装拆工件、刀具，更换机床会导致效率降低，成本升高，对于加工质量也有一定的影响。因此，本文以机床、刀具、工件的更换次数最少作为优化目标，关键工艺知识作为约束函数［7］。为了进一步明确优化目标，采用传统的多目标优化函数处理方法，针对具体的生产环境，为上述三种优化目标分别设置权重系数，然后求和，作为优化目标。多目标的优化问题转为单目标的优化问题。

3 基于遗传算法的工艺路线优化

遗传算法是一种全局搜索优化算法，将优胜劣汰的自然选择法则应用到目标寻优过程中。它通过对包含可能解的种群反复应用基于遗传学的操作，生成新的种群，从而使问题的解不断进化，获得满足要求的最优或接近最优解。种群的基本单位为染色体。在遗传算法中，主要存在以下5种操作。

(1)基因编码:由二进制或十进制数字构成的链表构成染色体，链表中的每一位数字或者每一组数字对应染色体中的一个基因。

(2)种群初始化:选择具有较好目标函数的染色体，构成第一代种群。

(3)复制:选择具有较好目标值的染色体进行复制，在下一代中代替具有较差的目标值的染色体。

(4)交叉:在一定交叉率下，选取一定数量的染色体按照规则两两交换，形成新的子代染色体。

(5)变异:在一定变异率下，选择一定数量的染色体，进行自身基因交换，形成新的子代染色体。

通过复制、交叉和变异生成的染色体将代替具有较差的目标函数的染色体，形成新的子代，这个过程被反复进行，直至达到优化目标或者规定的次数，然后停止搜索。下面以图1所示零件为例详细说明基于遗传算法的工艺路线决策和优化过程。

3.1 基因编码

基因编码方式对于工艺路线决策空间和遗传算法的搜索能力有重要影响。对于工艺路线决策和优化而言，染色体对应零件的工艺路线，基因对应构成工艺路线的每一道工步。设零件的工艺路线由n道工步组成，那么一个染色体中就有 n个基因，可以表示为{G1，G2，…，Gi，…，Gn}，基因 Gi表示第 i道工步。工艺路线决策以机床、刀具、工件的更换次数最少作为优化目标，通过对不同优化目标设置权重，将多目标优化问题转化为单目标优化问题，因此，基因编码需要包含机床、刀具、工件等的信息。根据第1节的论述，确定基因编码为5位十进制数字码，分别是加工表面码、机床码、刀具码、第一定位基准(表面)码，加工阶段码，其中前4个码位的值域为1～n，分别对应为相应特征向量的ID顺序号，加工阶段码的值域为数字1～3，分别代表粗加工阶段、半精加工阶段、精加工阶段。图1所示零件的基因编码如表1所示。

表1 基因编码

3.2 初始化种群

一般情况下，根据基因编码规则和染色体长度随机初始化种群，作为工艺路线的决策空间。但是工艺约束的存在，要求严格按照关键工艺知识的规则进行种群初始化。按照关键工艺知识的规则，图1所示零件加工表面间的优先级关系如表2所示。

表2 加工表面的优先级关系

CAPP系统中，根据关键工艺知识，初始化种群的算法可采用循环遍历法，对种群中的每一个染色体进行检查。从染色体的最后一个基因开始，遍历整个染色体，逐个判断每个基因是否满足关键工艺知识规则，不满足，则退出该染色体检查，如果满足，则从倒数第二个基因开始，遍历该基因以前所有基因，进行判断，依次类推，直至遍历该染色体的每一个基因。经过关键工艺知识检验的染色体构成了工艺路线决策空间，使遗传算法的搜索空间减小，避免了缺陷染色体的出现。初始化种群的算法如图2所示。对于初始种群的大小，实际应用中只能依据经验或实验确定，一般建议的取值范围是20～100。图3是生成的两个有效染色体。

3.3 确定目标函数

根据第2节的讨论，多目标函数经过加权处理，转变为单目标函数。假设种群初始化后形成了染色体空间R，包含n条染色体，每条染色体包含14个基因，n条染色体构成了工艺路线的决策空间。目标函数可表示为

式中:x为染色体;SJ(x)为染色体x的装夹次数;SC(x)为染色体x的换刀次数;SE(x)为染色体x的机床变换次数;αJ、αC、αE为装夹次数、换刀次数、机床变换次数的权重;Gi(3)为基因i的第3码位，刀具码位;Gi(2)为基因i的第2码位，机床码位;Gi(4)为基因i的第4码位，基准码位。

λ(x，y)是一个判断函数，表示为

根据优化目标可知，Sx值越小，染色体则越接近最优，工艺路线越接近最优解。

3.4 复制、交叉、变异

复制是遗传算法的基本算子，将一代种群中目标函数值较小的染色体直接复制到下一代种群中，即精英染色体保留策略，同时，为了避免陷入局部最优，对于精英染色体中目标函数相同或者接近的染色体设置复制概率，一般为10% ～20%，使下一代种群既保留了精英染色体，又避免了陷入局部最优。交叉运算从种群中随机选择两个父代染色体，随机产生两个交叉位置，在一个父代染色体中取出两个交叉点之间的基因，杂交点外的基因保持不变，然后在另一个父代染色体中寻找交叉点外缺少的基因，按照原来的排列顺序插入到两个交叉点之间的位置，形成一个新的子代染色体。以上述的两个染色体为例，取染色体1的交叉点X=5和Y=9，经过交叉运算则形成一个新的染色体如图4所示。取染色体1的相应两个交叉点，经过交叉运算也可形成新的染色体。执行交叉操作的染色体个数一般取种群染色体个数的50% ～90%，经过交叉运算后生成的新染色体，需要经过关键工艺知识的检验，符合要求进入下一代染色体。变异操作一般是在一定的变异率下，选择一部分染色体，在单个染色体内部进行两个或多个基因交换，形成新的染色体符合关键工艺知识的规则，则直接形成新的子代，否则，放弃。在这个过程中，如果变异率过大，会破坏杰出群体而使解远离最优，变异率过小，则不会产生新的基因块。为了保护杰出群体，变异率取值范围为1% ～10%。

表3 最优工艺路线

复制、交叉、变异操作反复进行，经过若干次的迭代后，到达目标函数的最小值或者接近最小值，对应的工艺路线为最优的工艺路线。

上述示例零件，取20条染色体构成决策空间，复制概率10%，交叉概率80%，变异概率5%，αJ、αC、αE分别设置为0.2、0.2、0.6，迭代次数取100，最后得到最优染色体如图5，对应工艺路线如表3。

4 结语

在CAPP系统中，工艺路线的决策和优化是非常重要和复杂的。本文将遗传算法应用于工艺路线的决策和优化过程中，分析了基于加工特征的工艺知识表达方法，设计了目标函数和适应度函数，采用了基于十进制数的基因编码规则，通过选择、改进的交叉和变异算法反复作用于种群来优化工艺路线，从而获得最优或者接近最优的工艺路线。另外，工艺路线的优化是机加工工艺优化的一方面，切削参数的优化也影响工艺路线的决策和优化［8］。考虑到实际加工环境，工艺路线的优化还要考虑具体的车间作业任务等问题［9］。上述问题将在以后的工作中予以关注。

［1］刘晓芳，赵万生，迟关心，等.基于改进遗传算法的工艺过程优化设计［J］.中国机械工程，2003，14(2):137－140.

［2］田颖，江平宇，周光辉，等.基于蚁群算法的零件多工艺路线决策方法研究［J］.计算机集成制造系统，2006，12(6):882 －887.

［3］刘晨，殷国富，龙红能.制造工艺知识粒度描述方法与获取算法研究［J］.计算机集成制造系统，2008，14(10):1966－1973.

［4］胡于进，张正义，凌玲，等.基于工艺约束矩阵的加工序列优化［J］.中国机械工程，2009，20(9):1062－1066.

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

［6］王志红，杜平安，郭志龙，等.基于遗传算法与动态规划法的工艺过程优化［J］.电子科技大学学报，2007，36(1):146 －149.

［7］凌玲，王青青，张正义，等.基于改进遗传算法的箱体类零件加工路线优化问题研究［J］.组合机床与自动化加工技术，2009(1):75－80.

［8］蔡力钢，张建设，张正义，等.复杂零件工艺方案全局多层并行优化［J］.机械工程学报，2008，44(9).

［9］LEUNG C W，WONG T N，MAK K L，et al.Integrated process planning and scheduling by an agent－ based ant colony optimization［J］.Computers＆ Industrial Engineering，2010，54:166－180.