随着市场竞争的日益激烈,企业的响应速度成为在竞争中占据优势的关键,对此,各企业采用各种技术手段以提高自身的竞争力.由于企业中存有大量的设计信息、制造信息等历史数据,丰富的产品知识蕴含于其中,对产品知识的挖掘与重用已成为企业所采用的重要手段之一^[1].

在众多的知识挖掘工具中,关联规则挖掘在产品的知识挖掘中常被采用,包括产品族设计知识的挖掘,产品设计与制造的映射关系识别,生产过程中质量控制规则的挖掘,以及工艺序列知识的挖掘^{[2, 3, 4, 5]}等.Apriori算法是关联规则挖掘的经典算法,但在挖掘过程中会产生大量的候选集，要对数据库进行多次读取,当数据量较大时效率低.为提高效率,遗传算法、粒子群算法等方法被引入关联规则的挖掘算法中^[6,7].此外蚁群优化算法和FP-growth算法也是频繁模式挖掘的常用算法^[8,9],前者在数据量大时会出现迭代次数多、效率低的问题;FP-growth算法只对数据库扫描两次,不产生大量的候选集,但该算法用于文本关联规则挖掘时,在时间和空间的效率不理想^[10].

卫星典型件是指在各型号卫星上都经常使用且结构功能相似的典型零部件,如结构板、管路等.目前我国的卫星发射任务激增,典型件需求量巨大,当前对典型件的工艺设计仍采用传统的方式,工作量巨大且设计效率低.由于卫星典型件结构相似,其工艺过程基本一致,为提高工艺知识的挖掘效率,本文将采用基于二进制粒子群的关联规则挖掘算法,从卫星典型件的历史工艺数据中抽取其工艺知识以支持卫星典型件的快速工艺设计.

在工艺数据库中存在大量的工艺对象,包括零件类型、材料、零件特征、加工方法、设备、刀具等,这些工艺对象之间存在着关联关系,如零件特征与加工方法、材料与刀具等.这些关联关系中比较典型的或工艺设计人员经常采用的都可作为工艺知识.这些工艺知识可以根据其必要性和适应性分为硬知识和软知识,其中硬知识是显而易见的、必要的或强制性的,而软知识则与工艺人员的经验、企业制造能力、客户要求等相关^[6].因此,软知识是工艺知识挖掘的主要目标.

对工艺知识挖掘而言,给定一事务集T={t₁,t₂,…,t_n},该事务集是某类型零部件的工艺的集合,t_i是每个事务的数据,X称为数据项,每个工艺过程(工序工步)都是一个数据项.事务集中的所有数据构成数据项集I={i₁,i₂,…,i_k}.关联规则是形如X⇒Y的逻辑蕴含式,其中X⇒I,Y⇒I,且X∩Y=,X称为前项,Y称为后项,如机加工艺规程中“先粗后精”的加工顺序即可作为一条工艺知识规则“粗加工⇒精加工”.

项集X和项集Y中所包含的项在事务集T中同时出现的概率记为关联规则的支持度Sup(X⇒Y),是对关联规则重要性(或适用范围)的衡量.

在包含项集X的事务中,出现项集Y的条件概率记为关联规则的置信度Conf(X⇒Y),是对关联规则准确度的衡量,用以度量关联规则的强度.

设定最小支持度min-Sup和最小置信度min-Conf两个阈值,若项集的支持度大于或等于最小支持度min-Sup,则称为频繁项集;若频繁项集的置信度大于或等于最小置信度min-Conf,则该频繁项集称为强规则.因此,挖掘事务数据库中关联规则的问题可以划分为以下两个过程:①找出所有满足最小支持度的项集,即获得频繁项集;②通过频繁项集产生强关联规则.

关联规则挖掘的经典算法是Apriori算法,该算法要对数据库作多次遍历,对小规模的数据库该算法完全能够满足,而对数据量大的数据库该算法效率低、耗时多.对此,引入粒子群优化算法以提高大数据量数据库的关联规则挖掘的效率^[8].

粒子群优化(particle swarm optimization,PSO)算法是由Kennedy等于1995年提出的一种群体智能演化算法,最初用于模拟鸟群觅食的过程,如图 1所示,后来经过不断地改进成为一种很好的优化工具,在多目标优化、模式识别、决策支持、数据挖掘等领域得到广泛应用.

图 1(Figure 1)

Fig. 1

图1 种群跟随最优的粒子移动到目标 Fig. 1 Swarm following the best particle to move to the goal

PSO算法包括3个步骤:生成粒子的初始位置和速度、粒子速度更新、粒子位置更新.在PSO算法中,每个被称为粒子的个体或优化问题的可能解在搜索空间中都有一个运动速度,该速度根据这个粒子自身的经验和相邻粒子的经验或者群体的经验来动态调整,粒子i的速度迭代公式和位置迭代公式为

PSO算法最初用于解决连续空间内的优化问题,而实际的工程应用问题多是离散的或组合优化问题,为此二进制粒子群优化(binary particle swarm optimization,BPSO)算法被提出并应用于实际的工程问题中^[7].BPSO算法中粒子速度迭代公式与实际PSO算法中的速度迭代公式形式上是相同的,但意义完全不同.粒子位置迭代公式如下:

基于BPSO的关联规则挖掘算法包括两个部分:数据准备和规则挖掘.数据准备部分主要是计算粒子群的适应度,将数据库中的数据转化为二进制格式并保存;然后利用PSO算法进行关联规则挖掘.首先对粒子群进行编码,然后根据适应度生成特定群体,最后启动搜索程序直到满足约束条件,即找到最优粒子.该粒子的支持度和置信度即为最小支持度和最小置信度,用于后续的关联规则挖掘.

首先将事务集中的数据转换成二进制格式,即每条数据的记录和存储都用“0”或“1”表示.这种方法可以加快数据库的扫描速度,而且支持度和置信度的计算也更加简单方便.这种变换方法可通过一个例子进行说明,如图 2所示.在原始数据库中有从T₁到T₅共5条记录,每条记录都可以转换为二进制形式,并以二进制形式进行存储.例如,在数据库中一共有5种不同的工艺对象,每条工艺路线都有5个单元,以B₂为例,在这条工艺路线中有3个工艺对象分别为I₁,I₂和I₃,因此与之对应的单元中都是“1”,而其他单元为“0”.

图 2(Figure 2)

Fig. 2

图2 数据的二进制转换 Fig. 2 Binary transformation of data

由于遗传算法在规则产生领域有成功的应用,参照其中规则的编码方法,针对工艺知识的特点,采用密西根方法(Michigan approach)对关联规则进行编码.

假如数据库中存在N个项目,每个项目包括两个部分,每个部分有两个可能值“0”或“1”.对于第一部分而言“1”表示该项目在某条规则中出现,“0”则表示该项目没有在规则中出现.第二部分的值表示该项目是否属于某规则的前项或后项,如果值为“1”则表示该项目出现在某规则的前项中,如果值为“0”则表示该项目出现在某规则的后项中.由此可见,每个粒子的维数为2N,在BPSO算法中关联规则的编码如表 1所示.

表1

Table 1

表1(Table 1)

表1 关联规则在BPSO算法中的编码 Table 1 Association rule encoding in BPSO algorithm I1 I2 … IN V11 V12 V21 V22 … VN1 VN2

表1 关联规则在BPSO算法中的编码 Table 1 Association rule encoding in BPSO algorithm

在PSO算法中,适应度这个概念是用来评价每个粒子在优化计算中可能达到或有助于找到最优解的重要性,适应度越高则粒子的位置越好,因此,适应度最大的种群可作为原始种群.每个粒子的适应度来源于适应度函数,适应度函数必须要有效地反映每个粒子与最优解之间的距离,适应度函数的确定直接影响PSO算法的搜索性能与计算效率,根据工艺数据库中工艺规则的特点,本文中关联规则X⇒Y的适应度函数表示为

基于BPSO的关联规则挖掘算法基本流程如图 3所示.该过程包含两部分:数据预处理和规则挖掘.数据预处理主要涉及数据二进制转换、适应度计算等步骤;规则挖掘部分首先通过规则编码和粒子适应度确定原始种群,然后应用PSO算法进行搜索,获得粒子的全局最优位置,该位置粒子的支持度和置信度即可作为关联规则挖掘的最小支持度与最小置信度.同时给出PSO算法的基本实现过程.

图 3(Figure 3)

Fig. 3

图3 基于BPSO的关联规则挖掘算法流程 Fig. 3 BPSO based association rule mining process

PSO算法:

输入: n(粒子规模),m(粒子维数),c₁,c₂(学习因子),w(权重)

输出:PGbest(全局最优位置)

//初始化粒子的位置和速度

For i=1 to n

For j=1 to m

X[i][j]=Llimit+(Ulimit-Llimit)×r

V[i][j]=0

End

End

//初始化全局和局部适应度 fitness_Gbest=inf

For i=1 to n

fitness_Lbest[i]=inf

End

Fitness_X=evaluate_fitness(X)

//更新局部最优位置和适应度

For i=1 to n

If(fitness_X(i)<fitness_Lbest(i))

fitness_Lbest[i]=fitness_X(i)

For j=1 to m

X_Lbest[i,j]=X[i,j]

End

End

End

//更新全局最优位置和适应度 [min_fitness,min_fitness_index]=min(fitness_X(i))

If(min_fitness < fitness_Gbest) fitness_Gbest=min_fitness

For j=1 to m

X_Gbest[j]=X(min_fitness_index,j)

End

End

//更新粒子的位置和速度

For i=1 to n

For j=1 to m

V[i][j]=w×V[i][j] + c₁×r₁×(X_Lbest[i][j] -X[i][j])+c₂×r₂×(X_Gbest[j] - X[i][j])

X[i][j]=X[i][j] + V[i][j]

End

End

以卫星结构板为例,在其工艺编制过程中,很多工艺单元是重复使用的,将这些成熟的、相对固定的若干工序(工步)组成标准的工艺规程单元,即工艺知识中的硬知识,可直接应用于工艺编制中.根据结构板材料的不同，其研制流程涉及6～7种工艺,典型工序序列是多种工艺知识中有代表性的,因此,本文以复合材料结构板典型工艺序列的挖掘为算例.对某卫星制造企业CAPP数据库中的复合材料结构板成型工艺进行整理,形成如表 2所示的工艺路线数据集,为简化计算过程,只取10个工艺路线事务,直接用工序名称作为数据项,共135个数据项.从中可以看出,诸如“准备→备料”、“车铣→阳化”等工序序列可直接作为典型工序序列.

表2

Table 2

表2(Table 2)

表2 结构板成型工艺路线数据集 Table 2 Dataset of shaping process for satellite plate 序号 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 P1 准备 备料 试件 工装 试装 车铣 阳化 装配 固化 修整 理化 后装 胶钳 检 入库 P2 准备 备料 车铣 阳化 试装 车铣 阳化 装配 固化 修整 理化 胶钳 检 入库 — P3 准备 备料 试件 工装 试装 装配 封装 固化 修整 理化 胶钳 检 入库 — — P4 准备 备料 车铣 阳化 试件 试装 工装 装配 固化 修整 理化 胶钳 检 入库 — P5 准备 备料 试件 试装 车铣 阳化 工装 装配 固化 修整 理化 后装 胶钳 检 入库 P6 准备 备料 试件 工装 试装 装配 固化 修整 理化 胶钳 检 入库 — — — P7 准备 备料 试件 车铣 阳化 工装 装配 封装 固化 修整 理化 胶钳 检 入库 — P8 准备 备料 试件 试装 工装 装配 固化 修整 理化 后装 胶钳 检 入库 — — P9 准备 备料 工装 装配 封装 固化 修整 理化 后装 胶钳 检 入库 — — — P10 准备 备料 工装 试装 车铣 阳化 装配 固化 修整 理化 胶钳 检 入库 — —

表2 结构板成型工艺路线数据集 Table 2 Dataset of shaping process for satellite plate

用前文研究的算法对表 2中的数据进行典型工序序列的挖掘,通过计算得到全局最优位置处粒子的支持度Sup为0.58,置信度为0.62,取表 3中的三组支持度和置信度分别用Apriori算法和BPSO算法进行规则挖掘,结果如表 3所示.Apriori算法挖掘得到的规则数目多于BPSO算法,是因为BPSO算法是随机搜索算法,会导致规则挖掘不全,但可以得到大部分的规则,而Apriori算法与BPSO算法相比耗时多,因此BPSO算法在提高规则的挖掘效率方面优势明显.受限于篇幅,不再列出具体结果,之所以会出现如此多的强规则是因为多个工序不同的排列组合造成的,对工艺本身而言多数规则实质上是相同的,而且对典型件的工艺也是有效的.此外粒子群算法与遗传算法在关联规则挖掘效率方面的比较可参考文献^[11],本文不再赘述.

表3

Table 3

表3(Table 3)

表3 BPSO算法与Apriori算法挖掘结果比较 Table 3 Comparison of mining result between Apriori algorithm and BPSO algorithm 挖掘算法 支持度 置信度 规则数 耗时/s 0.6 0.6 4094 22010.3 Apriori算法 0.8 0.8 1535 606.7 1 0.8 510 78.2 0.6 0.6 3824 13097.2 BPSO算法 0.8 0.8 1302 438.5 1 0.8 479 65.7

表3 BPSO算法与Apriori算法挖掘结果比较 Table 3 Comparison of mining result between Apriori algorithm and BPSO algorithm

1) 关联规则挖掘算法可用于工艺知识的挖掘,而且工艺知识能较好地用关联规则进行表达.

2) 基于BPSO的关联规则挖掘算法可以有效提高工艺知识的挖掘效率.

3) 本文只用典型工序序列的挖掘对挖掘算法进行了验证,实际上工艺历史数据中所蕴含的知识更丰富;由于工艺历史数据的不规范性,为方便挖掘,在进行知识挖掘之前需要对其进行整理,此过程同样值得研究.