摘 要 针对现有模糊Petri网的规则推理算法存在的不完善问题,提出并开发了优化的推理算法。该算法适用于大部分基于规则的推理系统,正确直观的仿真从出发命题开始到目标命题的推理过程。详细阐述了模型和算法,对具体的算例进行分析并与已有的算法进行比较突出其优点。
关键词 模糊Petri网;基于规则;推理;知识表示
1 引言
模糊Petri网(Fuzzy Petri Net,FPN)作为一种适合于描述异步、并行、模糊数据的计算机系统模型,被广泛的应用在基于规则的模糊推理系统中。伴随FPN的发展,相应模型的顺向推理算法以及逆向推理算法也在不断发展与完善。Looney最早给出了只适合于简单PN结构的顺向推理算法[3]。其后,Chen又给出了具体且精确的FPN数学定义,并优化了原有算法[1]。Li 等人提出了一种具有自适应能力的FPN[4],不但可以实现知识推理,同时具有类似神经网络的自我学习能力。
我们发现,现有的这些算法对于较简单的模型结构比较有效,当推理系统对应的FPN模型具有较复杂的结构时,则存在一定的问题,譬如:
(1)一些从始发命题到结论命题的推理路径并未充分考虑,如文献[1]。 (2)不适合并行推理,如文献[1][3]。 (3)对于一些库所,即使在推理中得到了它们的令牌值(Token),但在后续过程中不能被涉及到,如文献[1]。 (4)在文献[4]中,当一个变迁被允许发生后,其输入库所全部被删除,这部分被删除掉的库所有可能包含了其它库所的输入库所,造成整个推理无法正常进行。 因此,文本在以往研究的基础上,提出一种更具有灵活性和适用性的基于模糊Petri网的顺向规则推理算法。2 基于Petri网的模糊推理
一个模糊Petri网包含两种节点:库所(Place)和变迁(Transition)。有向弧可以从库所指向变迁或从变迁指向库所。在图形表示中,库所由圆形节点表示,变迁由方形节点表示。将FPN应用于规则系统中,每条规则表示为一个变迁,该规则的前提命题和结论命题则表示为该变迁的输入库所和输出库所。每个库所都有可能包含令牌值(Token)用来描述该库所对应的命题的可信度(Degree of Truth)。每个变迁对应一个确信因子(Certainty Factor,CF)用来表述对应规则的确信度。实例一:假设有如下规则: 假如A is B,则C is D。 该规则包含一个前提命题和一个结论命题,命题d1,d2用对应的库所P1,P2表示,规则用变迁t1表示,则该规则可用如图1的FPN表述。图1 基于实例一规则的FPN 根据文献[1]中的定义,一个基于规则系统的FPN可以被定义为一个六维量:FPN=(P,T,I,O,F,W)。其中, P={P1,P2,...Pn}为有限的库所集合,对应命题; T={t1,t2,...tn}为有限的变迁集合,对应规则; I:T→P为映射变迁到其所有输入库所的输入方程; O:T→P为映射变迁到其所有输出库所的输出方程; F:T→[0,1]为映射变迁到其确信因子的方程; W:P→[0,1]为映射库所到其令牌指的方程。 如果一个变迁 满足条件:对于任何Ps∈I(ti),有W(Ps)≥λ,λ为介于0和1之间的阈值,则该变迁将被点燃(Fired),其输入库所的令牌值将被复制,并通过一定的点燃机制为该变迁的输出库所产生令牌值。 例如,根据FPN的定义,实例一中的规则可被规范化为FPN1=(P,T,I,O,F,W),其中P{P1,P2},T{t1},I(t1)={P1},O(t1)={P2},F(t1)=0.75,F(P1)=0.9,F(P2)=空。若令λ=0.5,则t1点燃,根据图2的点燃机制,可得到输出库所P2的令牌值为0.675。 当然,实际的规则不可能像实例一中那样简单,在其命题中有可能包含类似“与(AND)”或“或(OR)”连接符。我们将这样的组合式规则及其对应的模糊FPN结构归结为以下三种类型:图2 实例一的FPN点燃结果 类型一:假如命题1(d1)与命题2(d2)与 …… 与命题m(dm)成立,则命题z(dz)成立,CF=μ。对应FPN结构及点燃机制如图3所示。 类型二:假如命题1(d1)成立,则命题a(da)与命题b(db)与 …… 与命题z(dz)成立,CF=μ。对应FPN结构及点燃机制如图4所示。 类型三:假如命题1(d1)或命题2(d2)或 …… 或命题m(dm)成立,则命题z(dz)成立,CF=μ。对应FPN结构及点燃机制如图5所示。图3 类型一FPN结构和点燃机制图4 类型二FPN结构和点燃机制图5 类型三FPN结构和点燃机制 令pi,tk为FPN中的任一库所和变迁,如果Pi∈I(tk),则称Pi是tk的最近逆向库所(Nearest Backward Place,NBP),变迁tk所有的NBP的集合称为SNBP(tk)。如果Pi∈O(tk),则称Pi是 tk的最近前向库所(Nearest Forward Place,NFP),变迁tk所有的NFP的集合称为SNFP(tk)。若存在流关系,从变迁tk连向库所Pi,则称Pi为变迁tk的向前库所(Forward Place,FP),变迁tS所有的FP集合称为 SFP(tk)。 实例二:如图6所示的FPN结构中,每个变迁的SNBP,SNFP及SFP如表1所示。图6 实例二中的FPN结构表1 实例二中每个变迁的SNBP,SNFP及SFP3 基于Petri网的前向推理优化算法 本节将给出一个优化的基于Petri网的前向推理算法。首先引入下面几个定义: 定义1 种子库所(Seed Place):对于一个FPN中的库所Pi,若不存在tk,使得Pi∈SNFP(tk),则Pi为种子库所。 在推理过程中,要求种子库所的令牌值是已知的或由用户给出。通常推理过程都是由种子库所开始,因此也被称为起始库所(Starting Place)。 定义2 目标库所(Goal Place):在一个FPN中我们通过流推理最终得到其令牌值的库所。 定义3 节点(Node):节点ni=(Pi,W(Pi)),其中W(Pi)是库所Pi的令牌值。 定义4 已知节点集(Known Node Set,KNS):若节点ni中的库所Pi的令牌值已知,则ni∈KNS。一个变迁点燃的前提条件是该变迁的SNBP能够在KNS中找到其对应的节点。
[8]电大学习网.免费论文网[EB/OL]. /d/file/p/2024/0424/fontbr /> 定义5 等待变迁集(Waiting Transition Set,WTS):尚未被点燃,正待点燃的变迁集合。
4 具体实例
用实例来对上节算法进行进一步阐述和校验。 实例三:令d0,d1,...,d6为规则中的命题,在一个基于规则的系统中,包含以下模糊规则: R1:IF d0,THEN d1(CF = 0.90); R2:IF d0,THEN d2(CF = 0.85); R3:IF d2,THEN d3(CF = 0.95); R4:IF d1 AND d4,THEN d5 (CF = 0.80); R5:IF d3,THEN d4 (CF = 0.90); R6:IF d3 AND d5,THEN d6(CF = 0.75); R7:IF d0,THEN d6 (CF = 0.90); 根据以上规则,我们建立相应的FPN结构实际如图6所示,命题d0,d1,...,d6用对应的库所 p0,p1,...,p6表示,规则R1,R2,…,R7用对应的变迁t0,t1,...,t7表示。设p0为初始库所,W(p0)=0.90,求W(p6)。根据第三节的算法,具体推理步骤为: 由于p6∈SFP(ti),i=1,2,3,4,5,6,7,则UFTS={t1,t2,t3,t4,t5,t6,t7},KNS={(p0,0.90)}。 以下,进入DO-WHILE循环: (1) t1,由于SNBP( t1)={p0}⊆KNS, t1点燃,生成节点(p1,W(p1)),其中W(p1)= W(p0).F(t1)=0.90.0.90=0.81。将节点(p1,W(p1))加入KNS,从UFTS中删除t1。完成后: UFTS={t2,t3,t4,t5,t6,t7},WTS = , KNS={(p0,0.90),(p1,0.81)}。 (2) t2,步骤同 t1相似。完成后: UFTS={t3,t4,t5,t6,t7},WTS = , KNS={(p0,0.90),(p1,0.81),(p2,0.77)}。 (3) t3,步骤同t1,t2相似。完成后: UFTS={t4,t5,t6,t7},WTS = , KNS={(p0,0.90),(p1,0.81),(p2,0.77),(p3,0.73)}。 (4) t4,由于SNBP(t4)={P1,P4},其中P4KNS且P4不是种子库所,所以将t4加入WTS,从UFTS中删除t4。完成后: UFTS={t5,t6,t7},WTS = {t4}, KNS={(p0,0.90),(p1,0.81),(p2,0.77),(p3,0.73)}。 (5)t5,步骤同t1,t2,t3相似。完成后: UFTS={t6,t7},WTS = {t4}, KNS={(p0,0.90),(p1,0.81),(p2,0.77),(p3,0.73),(p4,0.66)}。 (6)t6,由于SNBP(t6)={P3,P5},其中P5KNS且P5不是种子库所,所以将t6加入WTS,从UFTS中删除t6。完成后: UFTS={t7},WTS = {t4,t6}, KNS={(p0,0.90),(p1,0.81),(p2,0.77),(p3,0.73),(p4,0.66)}。 (7)t7,步骤同t1,t2,t3和t5相似。完成后: UFTS=,WTS = {t4,t6}, KNS={(p0,0.90),(p1,0.81),(p2,0.77),(p3,0.73),(p4,0.66),(p6,0.81)}。 (8)复制WTS到UFTS,则UFTS={t4,t6},清空WTS。 (9) t4,由于SNBP(t4)={P1,P4}⊆KNS,t4点燃,生成节点(p5,W(p5)),其中W(p5)=MIN(W(p1)),W(p4).F(t4)=0.66.0.80=0.53。完成后: UFTS={t6},WTS =, KNS={(p0,0.90),(p1,0.81),(p2,0.77),(p3,0.73),(p4,0.66),(p6,0.81),(p5,0.53)}。 (10)t6,由于SNBP(t6)={P3,P5}⊆KNS,t6点燃,生成节点(p6,W(p6)),其中,W(p6)=MIN(W(p3)),W(p5).F(t6)=0.53.0.75=0.40。由于KNS中已经存在p6对应的节点(p6,0.81),且0.81>0.40,故保持原有节点。完成后: UFTS=,WTS =, KNS={(p0,0.90),(p1,0.81),(p2,0.77),(p3,0.73),(p4,0.66),(p6,0.81),(p5,0.53)}。 至此,目标库所p6的令牌值W(p6)成功推出。5 结论
本文在总结现有算法的基础上,提出了一种基于模糊Petri网的规则向前推理优化算法。该算法避免了以往算法可能出现的不足,在一定程度上是对基于模糊Petri网的规则向前推理算法的一种完善。具有灵活性和适用性,对于较复杂的FPN结构也能成功的进行推理。参考文献
[1] S. M. Chen,J. S. Ke,J. F. Chang,“Knowledge Representation Using Fuzzy Petri Nets,” IEEE Trans. Syst. Man. Cybern.,Vol. 20,1990,pp. 311‑319.[2] M. M. Gao,M.C. Zhou,Y. Tang,“Intelligent Decision Making in Disassembly Process Based on Fuzzy Reasoning Petri Nets”,IEEE Trans. Systems,Man and Cybernetics,Part B,Vol. 34,no. 5,2004,pp. 2029-2034.[3] C. G.. Looney,“Petri Fuzzy Nets for Rule-based Decision Reasoning,” IEEE Trans. Syst. Man. Cybern.,Vol. SMC-18,1988,pp. 178‑183.[4] X. Li,F. Lara-Rosano,“Adaptive Fuzzy Petri Nets for Dynamics Knowledge Representation and Inference,” Expert System with Applications,Vol. 19,2000,pp. 235-241.[5] R. Yang,L.W.Shan,P. A. Heng,et al,“Improved Algorithm on Rule-based Reasoning Systems Modeled by Fuzzy Petri Nets”,Proc. 2002 IEEE Intern. Conf. Fuzzy Systems.
[8]电大学习网.免费论文网[EB/OL]. /d/file/p/2024/0424/fontbr />
相关文章:
网络攻击过程的形式化描述方法研究04-26
基于HTML标签的信息隐藏模型04-26
在当前网络环境下地方文献的组织管理探索04-26
基于对手思维建模的分布式入侵检测模型04-26
数字农业时空信息管理平台04-26
基于Verilog HDL的模型优化04-26
单点登录系统集成应用子系统的方法探讨04-26
基于Windows XP的PVM的实现04-26
基于J2EE的手机短信平台的设计与实现04-26