基于遗传算法的加工操作排序及优化

刘 岩，段国林，蔡 瑾

(河北工业大学 机械工程学院，天津 300131)



基于遗传算法的加工操作排序及优化

刘 岩，段国林，蔡 瑾

(河北工业大学 机械工程学院，天津 300131)

针对加工操作排序是一个动态的、多约束的组合优化的过程，提出了基于遗传算法的加工操排序方法。以最小变化机床、装夹和刀具次数为目标，构建操作排序优化模型。根据加工规则建立工艺约束关系，生成操作优先关系矩阵，验证并调整加工操作确保排序有效。采用双层编码遗传算法将加工资源与操作相关联，分析操作优先关系矩阵划分加工阶段，减少无效解的求解空间。应用遗传算子选择、交叉和变异，并对算法进行了改进，采用进化逆转操作提高局部搜索能力，加快收敛速度。最后通过实例验证该算法的有效性和实用性。

CAPP; 操作排序；遗传算法; 操作优先关系矩阵; 工艺路线优化

0 引言

目前产品发展趋势是多品种、小批量、客户个性化、更新快，需要企业快速设计缩短产品开发和制造周期。产品实现过程中工艺设计是关键技术之一，决策和优化产品的工艺路线并且保证加工质量要求。传统的工艺设计是工艺设计人员根据自己的工作经验和工艺知识，制定一条工艺路线。该方案可以生产出符合加工要求的产品，但结果可能不是最优的，工艺决策过程非常耗时、费力导致工作效率低。当加工资源发生改变，上述的方法也就不再适用，还需要重新设计加工路线。所以，采用智能的工艺路线规划可快速而准确地生成符合要求的多条工艺路线，并从中选取最优解。研究人员应用蚁群算法优化工艺路线，以知识描述加工零件确定加工元，采用加权海明距离判断加工元的相识度[1]。文献[2]分析箱体加工的典型工艺，采用多色集合理论的层次递阶结构建立加工过程模型，选取零件的最佳工艺路线。而文献[3]运用该理论的合取运算对特征测量路径分组以蚁群算法规划子路径。一些研究者通过遗传算法寻求最优解，建立扩展加工元优先矩阵表示加工顺序[4]，加工中心为了减少刀具空走行程，提高孔群的加工效率分别采用遗传算法优化孔群的加工路线[5]和蚁群算法与相邻排序算法相结合来规化钣金零件上的孔群加工路线[6]。为了提高运算速度对遗传算法进行改进，采用自适应遗传算法优化加工中心的箱体工步排序[7]并根据约束规则描述加工序列的优化关系生成约束矩阵[8]。为了防止陷入局部优化，应用遗传算法和模拟退火算法相结合来优化复杂箱体加工顺序[9]。

本文将工艺知识和遗传算法相结合，在加工操作排序过程中引入热处理工序，有效的将加工操作分段，减少求解空间中的无效解。同时为了适应加工环境的动态变化，采用双层编码遗传算法，在加工操作编码时也考虑加工资源如机床，准确地从全局角度表达了问题的求解。在满足工艺约束的条件下，应用选择、交叉、变异等操作，优化工艺方案，将加工规则转换为操作优先关系矩阵，以最小机床、装夹和刀具的更换次数建立目标函数对加工操作排序及优化，快速选出适应产品的最优加工路线。

1 工艺排序优化问题的数学模型

工艺排序优化过程是将所有操作构成了整个求解空间的解，满足一定的工艺约束条件下，确定每个操作的加工先后顺序，构成了一系列有效的加工序列。根据生产需要设置目标值最小，得到最优加工操作排序。排序问题的约束条件不能由具体的解析式表达，是一个非线性规划的函数寻优，其数学模型如下：

其中x∈X，f(x)为目标函数，gi(x)和hj(x)是约束条件，x*=为满足工艺约束的有效加工操作的最优解。

2 工艺路线优化模型的建立

工艺优化过程是在一定的加工原则下，具有约束条件的多目标排序问题也是一个典型组合优化问题。加工操作需要符合工艺加工规则，如先基准、先粗后精和先主后辅等原则，确保求解的有效性[10]。

2.1 工艺约束及表达

工艺约束是满足加工规则的一种优先关系，是一个复杂的网状结构，同时加工元间的优先关系是有方向的，并且不可逆。加工质量要求较高或复杂零件的工艺路线需要划分加工阶段，在各个阶段按照图纸精度要求安排加工操作顺序。而热处理工序能够改善材料的加工切削性能和金属组织、消除内应力提高零件表面硬度，在加工阶段的划分起着重要的作用，粗加工在热处理前，半精加工等精度高的加工在其后[10]。在加工操作中引入热处理工序会节省很大求解空间，提高收敛速度。

为了确保加工排序合理性，以关系矩阵的方式来表达工艺规划中约束即工艺规则。例如完成零件的加工需要有n个加工操作，根据零件图中的技术要求和材料属性得知是否需要热处理工序，若需要设置为n+1道工序，生成操作优先关系矩阵A。设置该零件关系矩阵大小为A(n+1)(n+1)其中aij为矩阵A的元素，当aij=1时操作ai优先于aj。零件操作约束函数流程步骤如下：

Step1: 生成操作优先关系矩阵A(n+1)(n+1)。

Step2:根据矩阵A并对随机生成的染色体S划分操作阶段。

1)判断列全为0的操作，该操作为加工的开始，而机械加工的开始工序通常为粗加工阶段。假设为m个，将操作依次识别并放入S(n+1)的前m位置；

2)判断行全为0的操作，该操作通常为该特征加工的结束即在其后没有对该特征的加工操作。也为一些辅助特征如倒角、钻孔等操作，假设为d个将其识别放入一个存储空间S(n+1)的末端；

(3)插入热处理工序，设置为第(m+1)道工序。

Step3：根据优先矩阵的A,从i=(m+2)依次开始判断加工序列S(n+1)的有效性，若S(i)=b，则调用矩阵A，若abj=1，ab优先aj,且aj=r；若S(i)=b

Step4:i=i+1,直至i=n结束，生成的染色体S符合加工优先顺序。加工操作排序是否合理的验证过程如图1所示。

图1 约束函数流程图

2.2 优化目标函数

加工资源都已确定的情况下，装夹、刀具和机床的频繁变换，造成了加工效率的降低和加工成本的增加，也不利于保证加工精度[11]。本文以加工过程中最少机床变化、装夹和换刀次数为优化目标，该函数由机床、装夹和换刀次数三部分组成，通过权重分配将多目标优化问题转化为单目标优化问题。如公式(1)所示：

ObjV=ω1×f(x1)+ω2×f(x2)+ω3×f(x3)

(1)

式中: ω1，ω2, ω3分别表示加床、夹具和刀具变换次数的权重系数[3]，根据经验分别取ω1=0.5，ω2=0.3, ω3=0.2。

(2)

(3)

(4)

f(x1)f(x2)f(x3)分别为该零件加工时工序排列的机床、装夹和刀具变化次数。

O.Mi,O.Ft(i),O.Ti为该操作所需要的机器、夹具和刀具，函数g(x-y)为判断函数。

(5)

为了减少数据对分析结果的影响，将由公式(2)～(4)计算得到的数据进行数据归一化处理，使结果值映射到[0-1]之间。max为样本数据的最大值，min为样本数据的最小值，current为当前值，机床、装夹和刀具的变换数量进行转换，如表1所示。

表1 函数归一化处理

3 GA的加工操作优化排序

遗传算法是一种全局优化智能算法，其原理是模仿生物界的演化法则，将问题参数编码形成染色体，利用迭代的方法进行选择、交叉和变异算子来交换染色体信息，最终生成符合优化目标的染色体[12]。基于遗传算法的工艺路线优化方法的步骤如图2所示。

图2 遗传算法的工艺路线优化流程图

3.1 编码

由于工艺操作排序是一个非线性、动态的优化问题，采用双层编码遗传算法将染色体分两层编码，第一层表示零件加工的工序，第二层表示加工机床，并采用整数代码以解决排序问题。每一条染色体代表了一种工艺方案，其长度等于加工的操作数和每个操作所需的机床。

3.2 适应度函数

适应度函数表明染色体或解的优劣，是自然选择的唯一依据。而遗传算法中的适应度函数值越大越代表染色体最优。适应度函数由目标函数变化得到，而优化的目标是求最小化问题。所有将式(1)定义的优化的目标函数取倒数,使其转化为适应度函数。

3.3 初始化种群

遗传算法随机生成的种群，有可能不符合加工操作优先条件，是无效的加工序列。调用验证程序，验证并调整不符合要求的序列，直至初始种群中所有染色体都符合要求。该算法中种群数量是一定的，设置太小收敛速度快，但是容易出现早熟现象，值太大运算效率低。所以根据经验设置为N=20～100[9]。

3.4 选择

轮赌盘选择算子是适应度值越大的染色体被选中的概率越大，这样能使遗传算法往好的方向进化，有助于提高解的质量，如公式(6)所示计算染色体的适应度值选中概率。但是该算法不能保证最好的染色体遗传给下一代，对其进行改进使用“精英策略”将当前代最高适应度的染色体按比例直接选入下一代种群，防止在交叉、变异操作时将好的个体破坏。

(6)

3.5 交叉

种群采用整数交叉法获得新的染色体，从种群中随机选中两个染色体a和b，随机选中交叉位置r(r1～n-1)，交换该交叉点后的工序。交叉后新生成的染色体a1和b1会出现工序的缺失和多余，根据交叉前染色体a和b来调整使其合理。

3.6 变异

为了保护群体的多样性，避免问题局部优化，种群通过变异操作获得新的染色体。从种群随机选取变异染色体，选择变异位置r1和r2，把染色体中两位置的工序对换，生成新的染色体，通常变异率为0.01～0.1。

3.7 进化逆转操作

为了改善遗传算法的局部搜索能力，在选择、交叉、变异后引入连续多次的进化逆转操作，对遗传算法改进。运用进化逆转算子过程如图3所示。从种群中选择一条染色体，该染色体由10个基因组成，随机生成该个体的两个位置r1和r2,则该两位置间的基因相互交换。若取r1=4和r2=9，经过进化逆转操作后生成新的子代染色体。该算子具有单方向性，只有经逆转后，适应度值有提高的才接受，否则逆转无效。

图3 进化逆转操作后生成子代染色体

4 实例

以锤式破碎机锥套零件加工为实例，如图4所示。零件锥套是机械传动连接部件，精度高、结构紧凑，外圆柱面与大皮带相连接，内孔圆锥和轴相连接，传递动力驱动工件运转，所以该工件内孔和外圆的加工精度较高。

图4 锥套零件图

如表2所示该零件共有13个特征，包括6个主特征和7个辅特征。

表2 零件特征描述

为了减少计算时间将孔组合特征如(钻-绞)进行合并处理，该零件包括20个机加工操作，根据零件图得知需要热处理工序，设置为最后一个操作序号21，加工操作及遗传算法的编码，如表3所示。

表3 加工特征信息及遗传算法编码

续表

特征加工操作操作名称装夹面加工设备刀具编码F6⁃1Op16车倒角FS1M2T416F6⁃2Op17拉内孔键槽FS3M3T417F2⁃2Op18钻ϕ17．5孔FS4M4T818攻丝M4T9F2⁃3Op19钻ϕ20孔FS4M4T1019钻ϕ30孔M4T11锪倒角M4T12F4⁃2Op20钻ϕ21×40FS4M4T1320钻ϕ26×102M4T14攻丝40M4T15Op21热处理21

通过分析旋转件锥套的特征拓扑关系，根据工艺规则可以明确加工操作的优先加工关系。将表3中的各个加工操作处理得到表4的操作优先表，生成加工操作优先关系矩阵，用于验证和调整操作顺序以确保加工排序的有效性。

表4 加工操作优先表

设置遗传算法的初始参数，初始种群数量为40，选择代沟为0.9，交叉率概率为0.95，变异率为0.01，迭代次数200，运算最优的结果如下:

1→3→9→11→6→21→2→4→14→7→12

→10→13→16→5→8→15→18→19→20→17

由此可知该零件加工过程中换机器变换次数为 4次，装夹次数为6，刀具更换次数为14,适应度值为140，加工操作排序符合实际加工要求。

5 结论

采用遗传算法以旋转件锥套为例，在工艺约束的优先操作关系矩阵中引入热处理工序，分隔加工阶段减少了无效加工操作排序的求解空间，提高了计算收敛速度。为了解决随机生成工艺过程中选择、交叉和变异后对基因的破坏，设计验证算法确保工序的有效性。并对遗传算法进行了改进，引入连续多次的进化逆转操作，提高遗传算法的局部搜索能力，避免陷入局部最优解。由于加工制造资源是动态的、不确定的，采用两层基因编码考虑加工机床设备从全局的角度优化加工过程，可以增加生产制造的柔性。在得到次优解的同时还可以得到多种方案的工艺加工路线, 以备工艺人员选择，该方法非常适应于动态的加工环境。

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

[2] 祝天荣, 徐新盛, 陶西柱. 基于多色集合理论的机械零件加工路线方法研究[J]. 组合机床与自动化加工技术,2013(9):129-131.

[3] 王春梅,姜腾.基于多色集合的智能三坐标测量路径规划研究[J].组合机床与自动化加工技术,2014(12):88-90.

[4] 袁青,李迎光,王 伟,等. 基于遗传算法的飞机结构件加工特征排序[J].机械科学与技术,2011,30(1):86-92.

[5] 肖军民.一种改进遗传算法在孔群加工路径中的优化[J].组合机床与自动化加工技术,2015(2):151-153.

[6] 潘海鸿,刘晓琳,廖小平,等. 钣金激光切割加工CAD/CAM软件的孔群加工路径优化算法[J]. 组合机床与自动化加工技术,2013(11):110-113.

[7] 郑永前, 王 阳. 基于遗传算法的加工工艺决策与排序优化[J].中国机械工程,2012,23(1):59-65.

[8] 王军,孟庆智. 基于遗传算法与约束矩阵的工艺路线优化方法研究[J]. 制造技术与机床，2011(8):147-152.

[9] 徐立云,史楠,段建国, 等. 基于特征加工元的复杂箱体类零件工艺优化[J]. 中国机械工程, 2013,24(2):201-207.

[10] 李凯岭. 机械制造工艺学[M]. 北京:清华大学出版社,2014.

[11] 刘连发, 张振明, 田锡天, 等. 基于遗传算法的工艺过程优化决策方法研究[J]. 机械制造,2008,46(52):59-62.

[12] 玄关男,程润伟. 遗传算法与工程优化[M]. 北京:清华大学出版社,2004.

(编辑 李秀敏)

Operation Sequencing and Optimization Based on Genetic Algorithm

LIU Yan, DUAN Guo-lin, CAI Jin

(School of Mechanical Engineering,Hebei University of Technology, Tianjin 300130,China)

Aiming at processing operation sequencing is a dynamic combinatorial optimization problem with multi-constraints, a method based on genetic algorithm is presented. An operation sequence optimization model is built by taking the minimum number of changes machines, setups and cutting tools as the objective. Operation precedence relation matrix is generated according to the rules of process constraint and the process operations are verified and adjusted by using the matrix to ensure the process route is feasible. Hierarchic genetic algorithm was adapted to associate operation with processing resources, dividing the processing stages by analyzing operation precedence relation matrix to reduce invalid solutions. Genetic operators of crossover and mutation are applied and the algorithm was improved by using reverse evolution operator to enhance the local searching ability and accelerated the convergence speed. Finally, an example is given to testify the effectiveness and practicability of this algorithm.

CAPP; operation sequencing; genetic algorithm; operation precedence relation matrix; process route optimization

1001-2265(2016)11-0126-04

10.13462/j.cnki.mmtamt.2016.11.034

2016-01-10；

2016-02-18

河北省自然科学基金项目(E2010000052)

刘岩(1977—)，女，辽宁葫芦岛人，河北工业大学博士研究生，研究方向为CAD/CAPP/CAM，(E-mail)lyan092012400900@sina.com。

TH162;TG506

A