基于模糊Petri网的规则推理优化算法

1、基于模糊Petri网的规则推理优化算法         08-07-30 15:23:00     作者：杨蓉    编辑：studa0714 摘  要  针对现有模糊Petri网的规则推理算法存在的不完善问题，提出并开发了优化的推理算法。该算法适用于大部分基于规则的推理系统，正确直观的仿真从出发命题开始到目标命题的推理过程。详细阐述了模型和算法，对具体的算例进行分析并与已有的算法进行比较突出其优点。 &#

2、160;   关键词  模糊Petri网；基于规则；推理；知识表示  1  引言    模糊Petri网(Fuzzy Petri Net，FPN)作为一种适合于描述异步、并行、模糊数据的计算机系统模型，被广泛的应用在基于规则的模糊推理系统中。伴随FPN的发展，相应模型的顺向推理算法以及逆向推理算法也在不断发展与完善。Looney最早给出了只适合于简单PN结构的顺向推理算法3。其后，Chen又给出了具体且精确的FPN数学定义，并优化了原有算法1。Li 等人提出了一种具有自适应能力的FPN4，不但可以实现知识

3、推理，同时具有类似神经网络的自我学习能力。    我们发现，现有的这些算法对于较简单的模型结构比较有效，当推理系统对应的FPN模型具有较复杂的结构时，则存在一定的问题，譬如：    (1)一些从始发命题到结论命题的推理路径并未充分考虑，如文献1。    (2)不适合并行推理，如文献13。    (3)对于一些库所，即使在推理中得到了它们的令牌值(Token)，但在后续过程中不能被涉及到，如文献1。    (4)在文献4中，当一个变迁被允许发生后，

4、其输入库所全部被删除，这部分被删除掉的库所有可能包含了其它库所的输入库所，造成整个推理无法正常进行。    因此，文本在以往研究的基础上，提出一种更具有灵活性和适用性的基于模糊Petri网的顺向规则推理算法。2  基于Petri网的模糊推理    一个模糊Petri网包含两种节点：库所(Place)和变迁(Transition)。有向弧可以从库所指向变迁或从变迁指向库所。在图形表示中，库所由圆形节点表示，变迁由方形节点表示。将FPN应用于规则系统中，每条规则表示为一个变迁，该规则的前提命题和结论命题则表示为该变迁的输入库所和

5、输出库所。每个库所都有可能包含令牌值(Token)用来描述该库所对应的命题的可信度(Degree of Truth)。每个变迁对应一个确信因子(Certainty Factor，CF)用来表述对应规则的确信度。实例一：假设有如下规则：    假如A is B，则C is D。    该规则包含一个前提命题和一个结论命题，命题d1,d2用对应的库所P1,P2表示，规则用变迁t1表示，则该规则可用如图1的FPN表述。图1  基于实例一规则的FPN    根据文献1中的定义，一个基于规则系统的FPN可

6、以被定义为一个六维量：FPN=(P,T,I,O,F,W)。其中，    P=P1,P2,.Pn为有限的库所集合，对应命题；    T=t1,t2,.tn为有限的变迁集合，对应规则；    I:TP为映射变迁到其所有输入库所的输入方程；    O:TP为映射变迁到其所有输出库所的输出方程；    F:T0,1为映射变迁到其确信因子的方程；    W:P0,1为映射库所到其令牌指的方程。   

7、; 如果一个变迁 满足条件：对于任何PsI(ti)，有W(Ps)，为介于0和1之间的阈值，则该变迁将被点燃(Fired)，其输入库所的令牌值将被复制，并通过一定的点燃机制为该变迁的输出库所产生令牌值。    例如，根据FPN的定义，实例一中的规则可被规范化为FPN1=(P,T,I,O,F,W)，其中PP1,P2，Tt1，I(t1)=P1，O(t1)=P2，F(t1)=0.75，F(P1)=0.9，F(P2)=空。若令=0.5，则t1点燃，根据图2的点燃机制，可得到输出库所P2的令牌值为0.675。    当然，实际的规则不可能像实例一

8、中那样简单，在其命题中有可能包含类似“与(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

9、)或命题2(d2)或 或命题m(dm)成立，则命题z(dz)成立，CF=。对应FPN结构及点燃机制如图5所示。图3  类型一FPN结构和点燃机制图4  类型二FPN结构和点燃机制图5  类型三FPN结构和点燃机制    令pi,tk为FPN中的任一库所和变迁，如果PiI(tk)，则称Pi是tk的最近逆向库所(Nearest Backward Place，NBP)，变迁tk所有的NBP的集合称为SNBP(tk)。如果PiO(tk)，则称Pi是 tk的最近前向库所(Nearest Forward Place，NFP)，变迁tk所有的NFP

10、的集合称为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，使得PiSNFP（tk），则Pi为种子库所。    在推理过程中，要求种子库所的令牌值是已知的或由用户给出。通常推理过程都是由种子库所开始，因此也被称为起始库所(Starting Place)。    定义2  目标库所(Goal Place)：在一个FPN中我们通过流推理最终得到其令牌值的库所。    定义3