改进遗传算法在箱体零件加工路线优化中的应用

刘持平，董 成

(贵州大学机械工程学院，贵阳 550003)

改进遗传算法在箱体零件加工路线优化中的应用

刘持平，董 成

(贵州大学机械工程学院，贵阳 550003)

研究了加工路线优化问题和遗传算法在此问题中的运用。在此基础上添加惩罚函数来改进适应度函数，添加自适应策略并修改选择算子来改进算法流程。最后以箱体零件为例，用VC++编程实现该算法的加工路线优化，对结果进行分析，验证了其可行性和有效性。

加工路线优化;惩罚函数;遗传算法;工艺约束;CAPP

0 引言

计算机辅助工艺设计(Computer Aided Process Planning，CAPP)是联接设计和制造的纽带，其目的是提高工艺设计的质量和效率，减少工艺人员从事的烦琐重复性劳动。随着现代集成制造技术的迅猛发展，以及多品种、小批量的生产越来越占主导地位，CAPP系统的研究与开发显得尤为重要。工艺路线决策是CAPP的重点和难点之一。工艺路线的确定(主要是加工路线的排序)是工艺设计合理与否的关键，它直接影响CAPP系统的实用程度［1］。箱体零件不同于具有相识性的回转体类零件，难以建立成组工艺，所以其工艺路线决策更加困难。

加工路线的确定实际上是一个带约束的非线性规划问题，因为它不仅受机床、刀具和夹具等因素的影响，而且受工艺约束的制约。文献［2-8］研究了遗传算法在工艺路线优化中的应用，获得了较好的加工工艺。本文在研究原有理论的基础上对适应度函数进行改进，引入惩罚函数，综合考虑机床、刀具、夹具因素和工艺约束限制的问题，并添加自适应策略、修改选择算子来改进算法流程。最后以箱体零件为例，用VC++编程实现了该算法的加工路线优化，并对结果进行分析。

1 问题描述

对于加工路线优化这种带约束的非线性规划问题，很难用传统的优化算法来解决。遗传算法是将生物进化中自然选择的法则用于解决科学研究和工程实际中遇到的各种优化问题。运用遗传算法，需要先将零件的每个特征按加工要求生成加工方法，例如:特征“平面”，设计公差IT=8、表面粗糙度Ra为3.2的加工方法为:粗铣—精铣，由两个加工元组成。将所有特征的每个加工元组成链，生成加工链。然后利用遗传算法中的交换和变异等算子对加工链进行迭代优化，最终生成最优加工路线。

2 改进遗传算法

利用遗传算法解决加工路线排序优化问题，技术已经比较成熟。关于基因编码、初始种群的生成、交叉算子和变异算子，这里不再重复论述。本文中基因编码和初始种群的生成采用文献［4］的方式进行，但对种群中的个体不直接按照加工元的约束关系进行调整。交叉算子和变异算子采用文献［5］的方式进行，但对子代个体不直接进行违反约束集的淘汰处理。下面对本文的改进遗传算法进行详细的论述。

2.1 工艺约束的制约问题和惩罚函数

一个合理的加工路线排序必须满足加工方法之间的优先关系约束，包括以下几个方面:①定位约束;②基准约束;③装夹约束;④非破坏性约束;⑤先主后次约束;⑥特征属性自身决定的严格先后顺序。违反任何一种约束的个体，其代表的加工路线都是不合理的，都是不可行解。由于特征加工链中约束条件很多，不可行解空间远远大于可行解空间，所以不能像传统方式那样将不可行解直接剔除。该算法引入惩罚函数，不用像文献［4-6］对个体进行违反约束集的调整、验证和剔除，也不用像文献［7-8］对个体计算优先权系数来生成大致符合约束集的个体。这样将大大加快运算速度。

确定惩罚函数首先建立约束集合［5］，将加工元之间的先后关系用工艺约束矩阵表示，即用矩阵M［n］［n］(其中n等于加工链的长度)来表示。

惩罚函数:

2.2 适应度函数的确定

综合考虑换机床次数、换刀次数、装夹次数的因素和违反约束集的问题，本文的适应度函数由两部分组成:f1和惩罚函数fpunish。f1又由换机床得分、换刀得分、装夹得分组成。

f1=w1fm+w2ft+w3fp(w1、w2、w3为0 ～ 1;w1+w2+w3=1);指定 w1、w2、w3的值可以确定机床、刀具和夹具的权重，一般w1＞w3＞w2。

最终的适应度函数:F=f1×(1-w4)+w4fpunish;对于惩罚系数w4，一般大于0.5，这样突出了特征的加工元顺序约束的重要性。

2.3 自适应策略

本文的变异概率pm采用自适应调整，不是用F来调整，而是f1(换机床得分、换刀得分与装夹得分的总和)来进行调整:

pm1、pm2为0 ～1，f1max和f1avg分别为f1的最大值和平均值。这样有利于个体向着换机床次数最少，换刀次数最少，装夹次数最少的方向进化发展。对于算法的交叉概率pc取固定值，取值通常在0.5～0.9之间。

2.4 改进选择算子

本文对算法的选择操作采用“父代种群参与竞争的联赛选择”的方式，将父代复制之后再进行交叉变异，避免了把某个中间步骤中得到最优解丢失的弊端，这样将大幅度提高运算速度。在此基础上本文还选择其中适应度F最大的前N×K3个(取整)个体作为子代(N为种群规模，K3一般取50% ～100%之间)，再随机生成个体补充种群规模到N。这样保证了种群的个体异性，搜索到全部解空间。

2.5 算法流程

改进选择算子和加入自适应策略，最终改进的算法流程如下:

(4)当t等于Tmax时，输出结果X，算法结束。否则t=t+1，返回步骤(3)。

3 运行实例

下面对VC++编制的系统进行论述。示例零件为离合器壳，铸造成毛坯，材料为铸铁，加工特征数一共为30个，如图1～图3所示。

图1 零件示意图1

图2 零件示意图2

图3 零件示意图3

对各个特征进行分析后，将最终生成的加工链载入系统，一共29个加工元，则个体基因为X［29］。如图4，图5所示。

图4 零件加工链(上)

图5 零件加工链(下)

3.1 GA参数输入

遗传算法的参数输入界面如图6所示，机床系数、刀具系数与装夹系数分别为 0.65、0.05、0.3，惩罚系数、参数 k1、k2分别为 0.7，0.4，0.6，交叉变异率参数 pc、pm1、pm2分别为 0.8、0.8、1，种群大小确定为80，迭代200代。

3.2 约束集输入的改进

对于约束集M［n］［n］的输入问题，特征属性自身决定的严格先后顺序，系统能自动识别。约束集的其它输入，笔者采用如图7所示的输入方式:

(1)包括工艺孔在内的重要定位特征 f1、f25、f26、f27、f28 先加工，之后是其它特征，最后 f16、f17、f25 的攻丝，对应序号:1，2，21，22，23，24，25，26 ＞ 3，4，5，6，7，8，9，10，12，13，14，15，16，17，18，19，27，28，29 ＞ 11，20;

(2)特征f26、f27面加工后才能加工工艺孔f1:22，23，24，25 ＞ 1，2;

(3)特征f20端面先加工，之后是f22孔，最后是f30 的孔:13，14 ＞ 17，18 ＞ 28，29;

(4)特征f17的面先于f2～f9孔加工:9＞3;

(5)特征f21的面先于f10～f16孔加工:15，16＞ 4，5，6，7，8;

(6)特征f19的端面先于f18的螺纹孔加工:12＞ 10，11;

(7)特征f28的端面先于f16、f17的螺纹孔加工:13，14 ＞ 19，20。

一共7组，每一组用“;”号隔开区分，系统能对其自动识别并填充 M［n］［n］。

如图7所示的三项最终填入内容为:

(1)先 加 工:1，2，21，22，23，24，25，26;13，14;22，23，24，25;9;15，16;12;13，14;

(2)后 加 工:3，4，5，6，7，8，9，10，12，13，14，15，16，17，18，19，27，28，29;17，18;1，2;3;4，5，6，7，8;10，11;19，20;

(3)最后加工:11，20;28，29;

相比传统矩阵式的输入方式，这将大大加快约束集输入的速度，节约大量的时间。

图6 算法参数的输入

图7 约束集的载入

3.3 结果分析

最终在200代后生成的加工路线结果:先对主要基准进行加工24＞21＞22＞26＞23＞25＞，再对工艺孔进行加工 ＞1＞2＞，最后以工艺孔和主要基准来定位加工 ＞15＞16＞9＞27＞7＞3＞8＞13＞14＞19＞4＞5＞6＞17＞18＞28＞29＞12＞10＞11＞20。换床6次、换刀25次、装夹10次、违反约束0次、适应度函数为97.3471，结果合理。如图8，图9所示。

图8 运行结果(上)

图9 运行结果(下)

系统中加入了适应度显示模块如图10，将F、f1、fpunish三者随进化代数的变化走势显示出来。从中发现在迭代初期，个体fpunish值比较低，严重违反约束集，但是这些个体包含很多有用信息，某些代的f1值比最终结果的f1值都要高。不用专门对这些个体进行违反约束集的调整，也不能直接将这些个体剔除，添加惩罚函数让这些个体参与迭代有利于算法最优结果的生成，提高了搜索的收敛效率，加快运算速度。

图10 适应度图

4 结束语

基于遗传算法的箱体零件加工路线排序优化，综合考虑机床、刀具、夹具因素和工艺约束限制的问题来改进适应度函数，并改进了算法流程，提高了算法的收敛速度和准确性。最终设计的加工路线优化系统，对CAPP系统的开发有一定的参考意义。

［1］王细洋，万在红.CAPP的关键问题及其对策［J］.制造业自动化，2000，22(2):25-29.

［2］Rocha J，Ramos C，Vale Z.Process planning using a genetic algorithm approach［A］.Proc of the 1999 IEEE Int Symp on Assembly and Task Planning［C］.Porto，Portugal:IEEE，1999:82-86.

［3］张冠伟，赵相松，李佳.基于遗传算法的工步优化排序方法［J］. 计算机集成制造系统，2005，11(2):242-246.

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

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

［6］刘伟，王太勇.基于遗传算法的工艺路线生成及优化［J］. 农业机械学报，2009，40(8):202-208.

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

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

［9］陈国良.遗传算法及其应用［M］.北京:人民邮电出版社，1996.

Optimization of Manufacturing Sequence Based on Improved Genetic Algorithm about Box Part

LIU Chi-ping，DONG Cheng
(School of Mechanical Engineering，Guizhou University，Guiyang 550003，China)

Researched on the problem of manufacturing sequence optimization and the application of genetic algorithms in this problem.On the basis，the paper added punish function to improve fitness function.Besides，the paper added adaptive strategy and modified Selection operator to improved flow of genetic algorithm，which can improve the velocity of convergence and veracity of genetic algorithms.Eventually，taken the box parts as the example to achieve the optimization of manufacturing sequence by programming with VC++and analyzed the result，which proves the algorithm's feasibility and effectiveness.

manufacturing sequence optimization;punish function;genetic algorithms;process constraint;CAPP

TH162;TP391

A

1001-2265(2012)01-0085-04

2011-06-13;

2011-07-12

刘持平(1954—)，女，江苏人，贵州大学机械工程学院教授，从事制造系统自动化、计算机辅助工艺过程设计、计算机辅助生产管理系统的研究，(E-mail)cpliu@gzu.edu.cn。

(编辑 李秀敏)