收稿日期:2009-09-09
基金项目：辽宁省科学技术基金(2005400610)
行必果作者简介：王铁伟,1981年出生，硕士研究生，主要从事数控加工工艺方面的研究㊂E-mail:
蚁群优化算法在加工工艺知识发现中的应用
王铁伟 于 金 王明海
(沈阳航空工业学院机电工程学院，沈阳 110136)
文 摘 针对加工工艺数据复杂㊁庞大㊁多变的特点，为解决加工工艺知识的匹配与推理的关键性技术，将模拟生态系统的模糊聚类算法应用于加工工艺知识库㊂提出了基于蚁群算法的工艺知识发现的概率查询方法，并建立加工工艺知识库的数学模型㊂通过输入关键词运行蚁群算法，描绘出索引地图，提取分析所需要的加工工艺序列㊂最后以铣加工工艺为例进行实例验证，结果表明，基于蚁群算法的工艺知识发现高效全面地优化了工艺序列㊂
关键词 知识发现，蚁群优化，规则，聚类，索引地图
An Ant Colony Optimization Method for Knowledge Discovery in
Processing Technology
Wang Tiewei Yu Jin Wang Minghai
(School of Mechanical and Electrical Engineering ,Shenyang Institute of Aeronautical Engineering ,Shenyang 110136)
Abstract Processing technology is much more complex ,usually large in size ,and continuously changes.Aiming
to solve a ries of key technologies during the matching and reasoning of discovery ,a clustering algorithm that imitates the ecosystem taking into account the features of processing technology data was prented.A method of processing knowledge discovery is implemented by using of an Ant⁃Colony clustering algorithm and probable query ,baed on the method ,the mathematical model of processing knowledge is establid.By inputing process data ,Ant⁃Colony algorithm can be operated ,the index map can be described ,the process procedure can be drawn.Finally ,an instance is verified bad on the process information table of the milling.The result proves that the knowledge discovery bad on the Ant⁃
Colony clustering algorithm model optimizes the process quence comprehensively and efficiently.Key words Knowledge discovery ,Ant⁃Colony optimization (ACO ),Rule ,Clustering ,Index map
0 前言
在加工工艺系统开发中，有很多因素影响加工方法的选择㊁工艺路线的排序㊁定位基准的决策㊁加工设备的选择㊁切削参数的选择㊁切削刀具的选择㊁加工余量的选择等㊂知识库系统采用文件管理系统的模式，将各种知识以文件形式存储于计算机中㊂但是由于工艺数据数量巨大，知识存储结构不清晰，造成使用效率低，并且不利于查询㊂
紫田网络
工艺知识发现过程是一个多目标㊁多组合优化的工艺过程，常见的获取知识的方法是归纳学习法和信息融合法，但由于工艺信息案例库的复杂性和不确定性，往往使得条件属性归类可能包含于多个分类中,
无法获得确定性的关联规则㊂本文提出基于蚁群算法的加工工艺知识系统，针对加工工艺的特点，在文献[1]的基础上，通过模拟蚂蚁群体智能来处理数据挖掘中的查询㊁表示方法和检索方法等问题新的解决方法㊂主要包括以下两点㊂
(1)采用分布式并行计算和正反馈机制，与数据
库相结合，将蚁群算法在聚类中的应用到加工工艺知识库系统㊂通过信息素的不断更新达到查询中的最优解㊂
(2)模拟社会性昆虫搜索机制，应用概率算法从
结构中分析并提取出所需要的序列，建立加工工艺数据库模型㊂
1
1 加工工艺特征的信息模型
加工工艺特征包括材料的选择㊁工艺要求㊁刀具的选择㊁设备的选择等㊂利用加工工艺特征参数作为信息模型的基本单元，并把特征参数的描述与加工工艺的数据库相结合，通过加工对象集合进行分类㊂如图1所示，建立了3个基础数据库：工艺和材料参数库㊁实例库和规则库㊂工艺参数库的数据主要包括毛料尺寸等，主要来源于仿真与试验结合所产生的工艺设计与分析参数数据㊂实例库的数据来源于实际生产中已加工的成型的产品㊂规则库的数据则来源于加工工艺手册[2]㊂规则库由语言规则以及连接词构成，对蚁群搜索起到了链接作用，基于特征的参数统一的规则描述，更有利于在搜索中降低复杂工艺问题的难度，提高工艺知识的发现概率孔圣人
㊂
图1 知识库的结构图
Fig.1 Structure of knowledge ba
2 蚁群算法的原理
人们受蚂蚁等昆虫的启发，设计了一系列蚁群算
法[3]，模拟蚂蚁的群体智能来处理数据挖掘中的问题，根据数据对象的相似性度量出表达式㊂
首先引入如下记号:m 蚁群中蚂蚁数量;b i (t ) t 时刻位于结点i 的蚂蚁个数,m =∑i =1
男士内裤广告b i (t);d ij 两结点i 和j 之间的距离;
ηij 边(i ,j )的能见度，反映由结点i 转移到
结点j 的启发程度，这个量在蚂蚁系统的运行中不变;
τij 边(i ,j )上的信息素轨迹强度;
Δτij 蚂蚁k 在边(i ,j )上留下的单位长度轨
迹信息素量;
P k ij
蚂蚁k 的转移概率,j 是未访问的结点㊂每只蚂蚁都具有如下的特征:
(1)在从结点i 到结点j 的运动过程中和在完成一次循环后，蚂蚁在路径(i ,j )上释放一种信息素的物质，称为信息素轨迹;
(2)蚂蚁通过概率选择下一个将要访问的结点，这个概率是两个结点间距离和连接两个结点的路径上存有的轨迹量的函数;
(3)为了满足知识搜索的约束条件，在完成一次循环以前，不允许蚂蚁选择已经访问过的结点㊂
蚁群算法的流程如图2所示
㊂
图2 蚁群优化算法流程图
Fig.2 Flow chart of Ant⁃Colony optimization
初始时刻，各条路径上的信息素量相等，设
τij (0)=C (C 为常数)㊂蚂蚁k (k =1,2,3, ,m )在搜索过程中根据各条路径上的信息素量决定着方向㊂蚂蚁系统所使用的状态转移规则被称为随机比例规则，它给出了位于结点i 的蚂蚁k 选择移动到结点j 的概率㊂在t 时刻，蚂蚁k 在结点i 选择结点j 的转移概率P k ij (t )为
P k ij (t )=ταij (t )ηβ
ij (t )∑s ∈allowe
d k
ταis (t )ηβis
(t ),j ∈allowe d k
ìî
íïïï
ï0 otherwi (1)
2
其中,allowe d k ={0,1 ,n -1}表示k 下一步允
许选择的结点㊂由公式(1)可知，转移概率P k ij (t )与
ταij (t )ηβij (t )成正比㊂ηij 为能见度因数,α和β为两个
参数，分别反映了蚂蚁在运动过程中所积累的信息和启发信息在蚂蚁选择路径中的重要程度㊂与真实蚂蚁不同的是人工蚁群系统具有记忆功能㊂为了满足蚂蚁必须经过所有n 个不同结点这个约束条件，为每只蚂蚁都设计了一个数据结构，称为索引地图(Index Map)，索引地图记录了在t 时刻蚂蚁已经走过的结
点，不允许该蚂蚁在本次循环中再经过这些结点㊂经过n 个时刻，蚂蚁完成一次循环，各路径上信息素量根据公式(2)(3)调整
τij (t +1)=ρτij (t )+Δτij (t ,t +1)(2)Δτij (t ,t +1)=∑k =1
Δτk ij (t ,t +1)
(3)
其中,Δτk ij (t ,t +1)表示第k 只蚂蚁在时刻(t ,t +
1)留在路径(i ,j )上的信息素量㊂路径越短，信息素释放的就越多;Δτij (t ,t +1)表示本次循环中路径(i ,
j )的信息素量的增量㊂一只蚂蚁在经过路径(i ,j )上释放的信息素量为每单位长度Q /d ij ㊂从而
Δτk ij
(t ,t +1)=Q d ij 若第k 只蚂蚁经过路径(i ,j )0ìî
íïïï否则(4)
文献[4-6]中在数据结构和知识发现方面进行了研究，设索引地图中由n 个结点，其结点值分别为d ，并用自然数编号为1,2, n ㊂为了存储索引地图，首先用一个长度为n 的一维数组D (1:n )存放图中各数据结点的信息，再用一个n 阶的二维数组R (1:n ,1:n )存放图中各结点的关联信息㊂其中二维数组R 称为图的关联矩阵(邻接矩阵)㊂在R 中，每一个元素R (i ,j )(1≤i ≤n ,1≤j ≤n )的定义如下:
R (i ,j )=
1 d i 是d j 的前结点
0 d i 不是d j {
的前结点
(5)
因此关联矩阵可表示为R ㊂
关联矩阵只表示了索引地图的结构，对两个结点之间的值运算需要求值函数，另外还需要用求值矩阵V 来存储㊂
最近邻列表令d i 是从结点i 到所有结点j 的距离组成的数列,j =1, ,n 且i ≠j ㊂令数列d i 以非递减的顺序排列，得到一个有序数列d 'i ，值相等的项可以按顺序编排工序㊂
3 蚁群算法的在知识库中的实现
要把蚁群优化算法应用到工艺加工知识库中，需进行以下4个步骤[7]:(1)载入输入的数据，包括初始化数据;(2)执行蚁群算法创建索引地图，索引地
图显示了蚂蚁的运动搜索轨迹;(3)处理数据挖掘中的聚类问题和评价函数;(4)输出工序序列㊂本文重点描述索引地图和处理数据阶段㊂
3.1 蚂蚁的实现过程
在文献[8]中每只蚂蚁是一个基本计算单元，它负责构建待解问题的一条路径，并可能向它所经过的边释放一定量的信息素∨τ㊂这样，每只蚂蚁必须能够:(1)存储它至今所构建的部分路径;(2)确定每个结点可能的相邻结点;(3)计算并存储它构建的解的目标函数值㊂
3.1.1 初始化过程设t :=0;N c :=0;∥t 时间计数器,N c 循环次数计数器τij (t ):=C ;∥为每条路径(i ,j )设一个轨迹强度的初始值Δτij =0；轨迹强度增量的初值设为0扁豆角炒肉的做法
ηij =1/d ij ;∥ηij 由某种启发式方法确定index k =∅;∥在初始阶段，索引表为空
设置s :=1∥s 为索引表的索引，将各蚂蚁的初始结点置于当前索引地图中
for k :=1to n do for k :=1to b i (t )do index k (s )=1；以概率P k ij (t )选择结点j ;∥重复直到索引表满为止
将选择的结点j 加到index k 中;Δτij (t ,t +1):=Δτij (t ,t +1)+
Q
d ij
；对于每一个路径(i ,j )，根据方程(2)计算Δτij (t ,
t +1);
3.1.2 记录到目前为止的最优路径
If N c <N c max 设置s :=s +1index k (s )=1;∥一次循环后蚂蚁又重新回到初始位置设t :=t +1对于每一条路径(i ,j )，设置Δτij (t ,t +1):=0
el 输出序列
3.2 蚁群算法创建索引地图
为了把ACO 算法应用到加工工艺知识库问题中，把它看做组合的优化问题，它通过图形来表示㊂把加工工艺知识库问题看作对于一定数量的规则，它就是一种涉及到用最优判据来给每个规则分配结论的方法㊂
将会得到一些规则与工序㊁刀具的选择和加工精度等之间的相似之处㊂每个规则所对应的可能的结论集合是不同的，而且也不可能为超过两个的规则分配一个结论㊂
3
黄豆发芽观察日记
为了构造索引地图，采取以下步骤㊂
3.2.1 确立规则
工艺知识表达方式应具有可解释性，因此对工艺知识的处理不能脱离工艺语言本身的固有特征，而且还要考虑灵活的数学描述处理方式㊂下面是对几种常见类型的工艺规则的预处理方法㊂
例如，一个规则R i,i=1,2 ,N r由前提组合来定义为R i=IF X1is A i1and and X n is A in Then Y is B j(6)其中,X1, ,X n和Y分别是输入，输出语言变量;A i1 A in和B j均为由集合所定义的语言变量㊂这个规则当且仅当存在
∃e l=(x l1, ,x l n,y l)∈E使得
μA
in(x l1) μA in(x l n)≠0(7)才起作用㊂即，在规则前提所定义的子空间中，至少存在一个满足条件的样本㊂具体的加工工艺数据规则预处理方法如下[9]:
(1)对区间型工艺规则的处理包括连续区间和离散区间的处理㊂典型的离散区间型工艺规则如表面粗糙度Ra㊂连续区间型的工艺样本如材料直径大小，处理方法是将连续区间进行模糊离散化处理㊂区间型
的工艺规则主要采用二次等价关系进行处理㊂(2)对于集值型工艺规则的处理主要是加工精度，如{IT6,IT8}，集值型的工艺特征是属性值可以进行选择，处理方法是根据集值元素逐一细化㊂(3)对于字符型工艺规则的处理主要是加工材料，加工设备等㊂对于工艺规则值空缺的工艺信息决策表采用量化容差关系进行处理，这里对这种情况暂不予考虑，只考虑完备工艺信息决策表的情形㊂工艺样本间的关系是等价关系㊂
总之，对工艺属性的预处理方法关键要看工艺属性的特征要求，然后选择合适的二元关系㊂
3.2.2 连接规则和结论
当且仅当下面条件满足时，规则R i才和结论B j(j=1, ,N c)连接起来㊂
∃e l=(x l1, ,x l n,y l)∈E使得μA
in(x l1) μA in(x l n)μB j(y l)≠0(8)其中,e l和E代表输入和输出数据集(表示待解决问题的行为),μ是规则的前提和输入的匹配度，即语言变量A in的隶属函数㊂
也就是，至少在输入模糊子空间有一个样本，被这样一个结论所包含㊂
3.3 评价函数
评价函数决定了解的质量，用支持度函数和置信度函数来评估[10]㊂
定义1序列A在序列数据库D中的支持度为
σ(A/D)=S A S
B
×100%(9)式中σ为支持度函数;σ(A/D)为序列数据库D 中包含A的序列所占的百分比;S A为D中支持A的序列数;S B为D中的总序列数㊂
定义2数据库D中的序列规则是如下形式的一种:A→B，其中A⊂I,B⊂I,I为构成项目的集合，且A∩B=∅，指在数据库D中所有支持序列A的序列中，有c%的序列同时也支持B,c%称为序列规则A →B的置信度
φ(A→B)=σ[(A∪B)/D]
σ(A/D)×100%(10) 4 实验验证
以铣刀加工工艺规则为例，对初始工艺规则集作数据处理，得到表1所示的初始加工工艺参数表㊂
表1 加工工艺参数表
Tab.1 Parameters of processing technology 序号
工艺条件，输入规则
R1R2R3R4
加工精度表面粗糙度/μm材料加工直径1IT60.08~0.63钢中
2IT70.08~0.63铜中
3IT80.16~1.25铝小
4IT9 2.5~10.00钢大
表2 加工工艺决策表
Tab.2 Decision of processing technology 序号
工艺序列，输出结论
B1B2B3
台风前
粗铣半精铣精铣
Y1B1→B3→B2→B3
Y2B1→B2→B3→B3
Y3B1→B2→B3→B2
Y4B1→B2→B3
图3有2个输入变量x1和x2,4个规则R1㊁R2㊁R3和R4,3个输出B1㊁B2和B3划分的一个简单工艺处理过程:(1)每个规则对应的可能结论集合;(2)索引图里除了η13㊁η31㊁η41㊁η42为0，其他的ηij≠0;(3)可能采取的12条不同的路径，也就是，结论组合成的索引地图㊂
周坊集团图3是系统具有4条规则，每个输入变量有2个条件，每个输入变量有3个结论的一个例子㊂在图3 (a)中，给出了对每个前提组合的结论㊂为了构造完全的解决方法，一个蚂蚁反复地检查每个规则，然后依据支持度信息σij㊁置信度信息φij和试探信息ηij来选择可能的结论，如图3(b)所示㊂选择规则的次序
4
是不相关的㊂在图3(c)中，可以看到在一个指定的例子里一个蚂蚁可能采取的各种路径㊂图3(d)为第
三种组合的规则决策表
㊂
图3 工艺处理生成的索引地图
Fig.3 Index map of processing knowledge discovery
对于表面粗糙度R a 为离散区间，因此R 2的取值范围t 1∈[a 1,b 1],t 2∈[a 2,b 2](1)如果a 2⩾b 1，则Y is B 1，如果a 1⩾b 2，则Y is B 2;
(2)如果b 2⩾b 1,a 2⩾a 1，则Y is B 1;(3)如果a 1⩾a 2,b 1⩾b 2，则Y is B 1;(4)如果t 1⊆t 2，则Y is B 1，反之,Y is B 2；可以推断例子中Y is B 1㊂根据公式(7),
R 1=IF X 1is M and X 2is S Then Y is B 1R 2=IF X 1is S and X 2is M Then Y is B 2R 3=IF X 1is M and X 2is M Then Y is B 2R 1=IF X 1is L and X 2is S Then Y is B 3因此，从第五组合就得到的一个规则㊂
相应的加工工序见表3㊂
表3 加工工艺工序表
Tab.3 Process quence of processing technology
编号
加工工序
1粗铣→粗铣→半精铣→精铣2粗铣→粗铣→精铣→精铣
3粗铣→半精铣→半精铣→精铣4粗铣→半精铣→精铣→精铣5
粗铣→精铣→半精铣→精铣 所获得的加工工序规则覆盖了原始过程中工艺决策表中的所有工艺流程[11]，将隐含的工艺数据信息中的决策信息也表达出来，与要求的加工工艺过程相符，可以将其作为工艺人员的参考㊂
5 结论
从蚁群优化算法来解决加工工艺知识库中知识
5
