基于STEP-NC 加工工步序列的优化

周杨 钟建琳

摘要：研究了基于精英选择遗传算法的加工工步序列优化技术。传统的加工工艺路线是以工序为制造单元，

而在基于STEP-NC的加工中，是以加工工步为制造单元，并且面向数控加工（中心）的一种加工过程。本文以由加

工工步变换所带来的零件转位、刀具更换等所消耗的辅助加工时间为最短作为优化目标，来进行加工工步序列的优

化，并对加工工步序列的优化算法进行了验证。

关键字：工步序列优化遗传算法STEP-NC

Abstract:

Genetic algorithm based on elite choice for the oPtimization of working stepsSequence was developed. In

the conventional manufacturing the working procedure is used as machining unit, While under the application of STEP-NC

the working step is as machining unit and the machining is numerical control machining center-oriented.The Optimization

goal is to find the best working steps sequence according to the least assistant machining time consumed by the part location

transform and tool replacing, and the algorithm for optimization of working steps sequence was tested in this prototype

system.

Keywords: OptimizationofworkingstePssequenc, Genetic Algorithm, STEP-NC

引言：作用而导致当前群体的最佳个体在下一代的丢失，De

Jong[4] 提出了精英选择（elitist seleetion）策略。从GA

非线性工艺设计是生成众多条工步序列( 从种工艺

的整个选择策略来讲，精英选择将解决群体收敛到优化

方案)，通过对工序排序约束规则和工步序列的有效化

处理，排除N 个工步序列中的许多无效工步序列，但

的问题。

是剩下的有效工步序列的数目仍然是庞大的。在传统的

原理：如果下一代群体的最佳个体适应值小于当

设计中，操作人员经常依赖于经验来进行决策，由于操

前群体最佳个体的适应值，则将当前群体最佳个体或者

作人员知识水平的不一致和生产实践经验的局限性，往

适应值大于下一代最佳个体适应值的多个个体直接复制

往不能考虑到影响排序的各方面因素，因而编排的工艺

到下一代，随机替代或替代最差的下一代群体中的相应

路线往往不是最佳方案。因此，工序的自动排序和优化

数量的个体。

技术已成为CAPP 系统集成化、智能化的瓶颈之一。许

多学者都进行了大量的研究，人们曾采用了基于导数的

解析方法、枚举法和其它启发式搜索方法来进行工序排

序的优化，但由于这些优化方法大部分都是基于局部的

搜索，因此很难达到一个全局的最优解，而枚举法虽然

能求出精确的最优解，但是当集合空间较大时，该方法

的求解效率比较低，有时甚至最先进的计算工具上都无

法求解。

由于工艺约束优化过程与其它数值化的优化问题

不同，首先，它的优化量不是数值，而是排列顺序；其

次，没有明确的优化目标，适用度函数难以表达。遗传

算法（Genetic Algorithm，简称GA）由于其具有以编码、

基因重组和变异为基础的全局搜索优点，近年来受到了

广泛的重视和研究，遗传算法被越来越多地应用到加工

工步排序的优化领域中[1~3]，本文利用基于精英选择

模型的遗传算法来进行工步序列的优化。

一、基于精英选择模型的遗传算法原理

为了防止由于选择误差，或者交叉和变异的破坏二、加工工步序列的优化过程

1. 基因编码（Gene encoding）

基因编码是GA 方法应用的第一步，本文采用自然

数字链进行基因编码。在STEP-NC 数据模型中，一个

加工工步主要包含了刀具的安全平面（its_secplane）、

工件特征（its_feature）以及加工该特征所对应的加工操

作（its_operations）等信息，而在加工操作元素中，除

了包含加工工艺（its_technology）、加工机床参数（its_

machine_functions）等信息外，还包括了与加工行为密

切相关的刀具信息（its_tool）。因此为了充分反映特征

和所对应的加工等信息，每一个基因由四部分组成，它

们分别是：加工方位代码、制造特征代码、加工操作

（加工方法）代码和加工刀具代码，每一个基因对应于

SETP-NC 中的一个加工工步。在生成基因代码之前，

首先分别给加工方位、制造特征、加工方法和被选用刀

具进行顺次编号，考虑到在一次加工中可能含有多个工

步的情况，基因中的每一部分则由两位十进制数组成。

根据每一部分的编号，可以将各个组合分别表示成相应

的十进制代码，这样就完成了基因编码工作。所有工步

的基因按任意方式进行排列就组成了一条染色体。

2. 初始群体的产生（population Initialization）

通过工步约束规则和有效工步序列转换算法，将

那些无效工步序列逐一转化成有效工步序列，所有有效

的工步序列集就组成了初始群体。

3. 选种（selection）

选种是指从初始群体中选择出一些优良的个体进

行后代的繁衍和进化，种子个数控制在20~100 以内。

一般遗传算法都是依据染色体个体的适应值来进行选

择，即按照给定的适应度函数首先计算每个个体的适

应值，然后将适应值较高的个体作为种子生成交配池

（mating pool）。采用如下的方法进行：

（1）从初始群体中任意选择出一些个体作为第一

代的种子，虽然这些种子开始并不能保证是一些较好的

个体，但是它们都是有效的个体，而优良个体的选择可

以逐步通过后面的经营选择策略来实现；

（2）当选出第一代种子后，接着进行个体评价，

把适应值最大的个体作以标一记Amax 并把该最大适应

值赋予一个变量fmax 进行保存，以便和下一代种群中

的最大的适应值进行比较；

（3）进行交叉、变异操作，初步形成下一代种群；

（4）对下一代种群进行评价，并把适应值最小

的个体作以标记Bmin，同时把最大适应值赋给一变量

f‘max 且标记该个体( 具有最大适应值)Bmax；

（5）将上一代的最大适应值与本代（下一代）的

最大适应值进行比较，如果上代的最大适应值大于本代

的最大适应值，则将上一代的最大个体Amax 代替掉本

代适应值最小的个体Bmin，而本代中的其它个体保持

不变，这样就形成了本代最终的种群P（t+1）；如果

上代的最大适应值小于本代的最大适应值，则将本代的

最大适应值赋予变量fmax，即：fmax = f‘max，且将其

标记Bmax 换为Amax，而本代种群个体依旧保持不变。

重复上述的步骤（3）到（5），直到群体满足某一指标，

或者己完成预定的迭代次数，则优化算法结束。

4. 评价函数（适应函数，fitness evaluation）

由于适应值是群体中个体生存机会选择的唯一确

定性指标，所以适应函数的形式直接决定着群体的进化

行为。为了能够直接将适应函数与群体中的个体优劣度

量相联系，在遗传算法中适应值规定为非负，并且在任

何情况下总是希望越大越好。

在工艺设计中，评价指标是加工时间最短、加工

成本最低。我们以加工时间最短作为工步序列的优化目

标，数控加工中心中影响加工时间的主要是零件特征的

加工时间和零件转位、刀具更换等所占用的辅助时间，

在这里主要考虑辅助时间对整个零件加工的影响，因此

目标函数可以表达为：

g（x）=Min（f1，f2……fm）

其中m 为种群中染色体的个数，人为第i 条染色体

所对应的加工时间，即第i 条工步序列链条所对应的加工

时间。而每一条染色体其加工时间可通过下列等式计算：

上式中，n为染色体的长度( 即工步序列所包含的

工步个数)，t1[j] 为连续两道工步的转位时间，t2[j]为

连续两道工步的换刀时间，L[j]为第j 个工步所对应的

加工方位代码，T[j]为第j 个工步所对应的刀具代码。

对上式有下列的等式成立：

为了保证目标函数的优化方向对应于适应值增大

的方向，有必要建立适应函数与目标函数的映射关系，

保证映射后的适应值是非负的。由于上述目标函数是属

于最小化问题，因此对于适应函数f（x）和目标函数g（x）有以下的映射关系：

其中， 是一个理论最大值，设定最大的加工时间

为理论最大值，即假设每道工步都存在转位和换刀操作，

在这种情况下计算其加工时间即可得到最大理论值 。

5. 交叉运算（crossover）

交叉运算是进化算法中遗传算法具备的原始性的独

有特征。GA 交叉算子是模仿自然界中有性繁殖的基因重

组过程，其作用在于将原有的优良基因遗传给下一代个体，

并生成包含更复杂基因结构的新个体。在本文中，我们采

用两点交叉的方式进行交叉运算，具体步骤如下：

首先在种群中任意选取两个种子作为父辈类进行

交叉运算，假设两个父类分别为P1

和P2，在这两个父类中任意指定两个交叉点作为

交叉的位置，这样父类染色体被分成了三部分：左半部

分、中部右半部分。交叉运算分两步来进行：1）对于

下一代染色体个体Child1 的生成，首先将父类P1 的左

半部分和右半部分分别复制到子代Child1 的左右部分；

2）然后在父代P2 中依次寻找出与父代P1 中左半部分

和右半部分基因具有相同加工方位代码、制造特征代码

和加工操作（加工方法）代码的全部基因，并将它们划掉，

将父代P2 中剩下的基因按照它们原来的顺序依次复制

到子代Child1 的中间部分，这样子代Child1 就生成了，

采用同样的方法就可生成子代Child2，由于父代染色体

是有效的染色体，因此采用该交叉方法生成的子代染色

体也是有效的。

6. 变异算子（mutation）

变异操作是通过模拟自然界生物体进化中染色体上

某位基因发生的突变现象，从而改变染色体的结构和物理

性状。我们采用随机交换染色体中的两个基因代码的位置

来完成变异运算。由于交换基因代码后，会出现无效的染

色体，因此当完成位置交换后，还必须依据工步的约束规

则对染色体的有效性进行判断，如果出现了无效染色体则

需要将其转化为有效的染色体。转换方法同前述的方法，

只需要将位于两个交换点之间的基因序列进行有效性转化

即可，这是因为在交换位置以外的基因序列本身就继承了

染色体变异以前的合理性，因此只要保证交换点之间序列

的有效性就能保证整条染色体的有效性。

7. 循环终止条件 （100次后终止）

三、实例证明

1）精铣平面 2）钻孔 3）扩孔

4）粗铣型腔 5）精铣型腔

图2 零件加工工步图

利用VisualC++ 语言开发了一个STEP-NC 加工系统

[5] ，演示了非线性工艺设计的过程，并对上述提出的遗传

优化算法进行了验证。图2 为零件加工工步图，1）粗铣

平面2）精铣平面3）钻孔4）扩孔5）粗铣型腔6）精铣

型腔。为了验证本文提出的遗传优化算法的有效性和稳定

性，利用Matalab 软件对上述实例零件进行了不同参数情

形下的优化仿真计算，其收敛效果见图3 所示，运行参数

和结果见图4，假设零件平均转位时间为5s，平均换刀时

间为15s，优化结果得出的最短加工辅助约为130 秒。

图3 工步序列优化收敛图 种群大小交叉概率变异概率收敛次数最优值

50 0.8 0.08 60 130s

30 0.6 0.1 35 130s

40 0.7 0.09 50 130s

图4 遗传算法的参数表值

结论：

基于精英选择策略的遗传优化算法在工艺优化中，

该算法具有很好的有效性、合理性、稳定性，收敛性。

参考文献

[1]秦宝荣、柯文等，基于遗传算法的箱体零件加

工路线决策方法研究，中国机械工程，2002年13卷第

24期：2071-2075

[2]M.Shakeri ,IlnPlementation of an

automated oPeration Planning and oPtimum

oPeration sequencing and tool seleetion

algorithms，ComPuters in Industry，Volume54，

Issue3，August2004，Pages223-236

[3]D.Kritsis，K-P.Neuendorf and

P.Xirouehakis，Petri net teehniques for

Proees Planning cost estimation，Advanees

in Engineering Software，Volume30，Issue6，

June1999，Pages375-387

[4]李敏强、寇纪淞等，遗传算法的基本理论与应

用，北京:科学出版社，2002年3月，50~300

[5] 白丽, STEP-NC 数控系统整体规划及程序解

释器设计,2011年3月

注：文章内所有公式及图表请以PDF形式查看。