改进的基于规则的逆向模糊推理算法.doc

第2期张稳等：改进的基于规则的逆向模糊推理算法105改进的基于规则的逆向模糊推理算法张稳1,2，张桂戌1(1. 华东师范大学 计算机科学技术系，上海 200062; 2.上海大学 理学院数学系，上海 200444)摘 要：给出了一种改进的基于规则的逆向模糊推理算法。该算法基于产生式知识表示的模糊Petri网（FPN）模型，适用于一类基于规则的系统。利用该算法可以有效地对该类系统的FPN模型进行相应的处理。对于任意指定的库所，通过该算法可以确定其模糊托肯值，即对应命题的模糊真值。通过对具体的算例进行分析并与已有的算法进行比较后发现，该算法不仅可以得到同样精确的结果，而且该算法使FPN的推理过程更类似于人脑的逻辑推导过程，比较缜密。关键词：模糊Petri网；模糊产生式规则；逆向推理；基于规则中图分类号：TP301.6 文献标识码：B 文章编号：1000-436X(2008)02-0101-05Improved rule-based backward fuzzy reasoning algorithmZHANG Wen1,2, ZHANG Gui-xu1(1. Department of Computer Science and Technology, East China Normal University, Shanghai 200062, China;2. Department of Mathematics, Science College, Shanghai University, Shanghai 200444, China)Abstract: An improved rule-based backward fuzzy reasoning algorithm was pointed. The algorithm is based on the fuzzy Petri net (FPN) which represents fuzzy production rules. The algorithm is also suit for a class of rule-based systems, i.e. it can deal with the fuzzy Petri net model which results from the real system. Via using the algorithm, one can calculate the tokens of any appointed places which correspond to the true fuzzy values of the relevant propositions. Through practical applications, the advantages of the proposed algorithm compared with those present results obtained by the existed algorithm. Key words: fuzzy Petri net; fuzzy production rule; backward reasoning; rule-based1 引言收稿日期：2005-12-31；修回日期：2007-12-11基金项目：国家重点基础研究发展计划（“973”计划）基金资助项目（2005CB321904）；上海市自然科学启明星计划项目（03QG14016）；上海市教委局管基金重点项目（04JG05063）Foundation Items: The National Basic Research Program of China（973 program）（2005CB321904）；The Natural Science Foundation of Shanghai of China(03QG14016); The Key project of Shanghai Education Committee Fund(04JG05063)最近几年，模糊Petri网（FPN，fuzzy Petri net）以其强大的并行处理能力和对于具有模糊行为系统的广泛适用性而越来越引起诸多学者和专家们的关注。伴随FPN的日益发展，如今它已被较多地运用于产生式知识表示中，相应模型的推理算法以及逆向推理算法也在不断地完善，这其中还出现了模糊推理Petri网。该领域主要的工作有CHEN等提出的采用FPN的知识表示及逆向模糊推理算法1 和相对应的正向算法2；GAO等提出的一种适用于模糊产生式知识表示模型的基于矩阵以及向量运算的推理算法3,4。可以说，这些算法对于特定的模型都相当有效，并且便于实现，当然也难免会存在一定的不足。比如文献2中的算法，在一些特殊情况下并未能充分考虑到所有与推理相关的库所或命题，而且也不太适于并行推理。文献1中提出的逆向推理算法，虽然比较直观，但必须要借助于与/或图，相对而言缺乏比较强的逻辑性，因此也具有一定的不足之处。本文力图在已有算法的基础上，提出一种改进的基于规则的逆向模糊推理算法，使其能够实现已有算法的功能，同时又能在一定程度上更加富有逻辑性，从而使算法更加完善。2 产生式知识表示的模糊Petri网模型在许多文献中给出过产生式知识表示的Petri网模型，相关的FPN模型也不难得到，为了本文后面讨论的方便，先给出模糊产生式规则知识表示的FPN模型及其相关的一些特性。令R是模糊产生式规则集， 。对于其中每个规则的定义为： IF dj THEN dk（），其中dj 和dk为命题，它们的真值是介于0和1之间的实数；为规则的模糊因子（CF，certainty factor），。不难看出越接近1，规则越可信。我们可以用以下表示模糊产生式规则的FPN模型来表示一个基于规则的系统。定义 FPN=（），其中是有限库所集；T是有限变迁集；为有限命题集；为输入函数，即从变迁集到库所集的一个映射；为输出函数，即另外一个从变迁集到库所集的映射；：，将每个变迁对应于一个0到1范围内的实数，即变迁的确信度；：，是库所与其托肯值之间的映射；：为库所与命题之间的对应关系函数。具体的解释如下：表示变迁的输出库所的集合；为的所有输入库所集合；，则的确信度为；表示的托肯值为；则表明库所与命题相对应。综合前面后两条，我们得到：如果，并且，则表示命题的确信度为。通常的模糊产生式规则有以下3种类型。类型1：IF THEN （）；类型2：IFORTHEN （=）；类型3： Ri IF di AND dj THEN dk()。3种类型规则的FPN模型分别如图1图3所示。图1 类型1的FPN模型图2 类型2的FPN模型图3 类型3的FPN模型3 逆向模糊推理算法逆向模糊推理算法的主要作用是根据已知条件推导未知命题的真值，即根据逆向模糊推理算法可以推导出FPN模型中任意一个指定库所的模糊托肯值。在本文中，主要考虑给出一种基于规则的逆向模糊推理算法。假定用户想要知道某一命题的真值，反映到FPN模型中，即要求出对应的库所的模糊托肯值。这里，或称为目标库所或目标命题。在算法中，需要用户输入必要的种子库所（在有些文献中称之为起始库所）的模糊托肯值。所谓的种子（起始）库所，即没有任何输入库所和输入变迁的库所。在文献5中，作者给出了一种得到与目标命题相关的所有库所和变迁集合的逆向推理算法，即用文中的算法可以推导出原FPN的一个子网，从而大大缩小了需要考察的范围，不足之处是算法没有进一步确定目标命题的真值，而本文中的算法将直接给出目标命题的真值。首先给出几个与算法有着密切联系的定义：变迁的紧后库所集（SNBP, set of nearest backward places）、紧前库所集（SNFP, set of nearest forward places）、节点、必须已知库所集、未知库所集、未知节点集、已知节点集。各定义具体如下：定义1 SNBP。变迁的紧后库所集为SNBP（），如果在FPN中存在直接从到的弧关系，即，且路径中不包含任何其他的库所和变迁，则所有这样的库所所组成的集合为SNBP（）。定义2 SNFP。变迁的紧前库所集为SNFP（），即所有满足条件的库所的集合，具体的条件为：在FPN中存在直接从到的弧关系，即，路径中间不含有任何其他的库所和变迁。定义3 节点（node）。节点的形式为：()，其中为的真值；为所有满足条件的变迁所组成的集合，即对于，均有，所有这样的变迁组成集合；为所有满足条件的变迁的集合，具体条件为：，。为了后面算法描述的需要，我们记为中元素的个数。定义4 必须已知库所集（MKPS, must known places set）：在算法的推理过程中，必须要得知模糊托肯值的所有库所的集合。定义5 未知库所集（UKPS, unknown places set）：在整个推理过程中，不知道具体模糊托肯值的所有库所的集合。定义6 未知节点集（UKNS, unknown nodes set）：如果节点中第二项的值未知，则所有这些节点所组成的集合为SUKN。定义7 已知节点集（KNS, known nodes set）：节点的第二项的值已知的所有节点所组成的集合。以上给出了一些相关的定义，下面我们将给出具体的算法步骤和算法的描述。算法的输入：欲得知其真值的目标命题di亦即对应的目标库所pi。算法的输出：的模糊托肯值亦即对应的的真值。具体的算法步骤如下。1) 建立节点（）。因为未知，所以先记为“”，并令为“”（实际上有可能是一个由已知库所组成的集合）。为目标库所，需要求的为。所以=（），将放入SUKN中，同时将放入SUKN中。2) 考虑SUKN中的节点（初始时只有一个与目标库所对应的节点），其中=( )，对于，求SNBP()。若 不是种子库所，建立节点=（ ），将放入SUKN中；若是种子库所，则需输入的值（如果已知则不必再提示用户输入），并建立节点=( )，将放入SKN中，如果SKN中已经包含，则SKN保持不变。然后将放入SMKP中。对所有的完成上述过程以后，如果SMKP中含有非种子库所，则将其中的非种子库所移动到SUKN中；否则（SMKP中全为种子库所），SMKP保持不变。对于SUKN中所有的节点（包括在推理过程中SUKN不断增加的各节点），重复上述过程，直到SMKP并且SUKN中不再增加新的节点为止。3) 假设SKN=，对于 ，=（）（若为种子库所，则应为“”，在这里，不用加以考虑），同时对于，=（），若，且对，则将从中删除，并将所有这样的变迁从相应的节点元素中删掉。如果=1（先处理中元素个数为1的节点），而且有n(=1)个节点，其中，=()，使得：，且，则置 ，其中为的模糊因子。若1，设=，则对于每一个，根据上面所述当=1时的算法，计算=,其中节点同前，且满足：，使得，并依次得到，然后利用公式（）计算出的值。计算以后，自然有=（），然后将放入SKN中，并将其从SUKN中删除。重复以上步骤，直至SUKN为空集为止，则步骤3结束，进入下一步推理。4) 在最终得到的SKN中找到与目标库所相对应的节点（），则其中的即为算法最终的输出结果。所以最后输出的值。以上是算法的具体过程，该算法可以看作是文献6中算法的一个逆算法，因为它使用了部分文献6中的定义，从而避免了已有算法中的一些不足之处。下面我们用该算法对文献1中的例子进行推导计算，并将最终得到的结果做一下比较。对于文献1中的例4.1，要求d4的真值，所以p4为目标库所，本例的FPN如图41所示。图4 FPN建立相应的模糊产生式规则：R1：IF THEN (CF=0.85)R2：IF THEN (CF=0.80)R3：IF THEN (CF=0.80)R4：IF THEN (CF=0.90)R5：IF THEN (CF=0.90)R6：IF THEN and (CF=0.95)R7：IF and THEN (CF=0.90)R8：IF THEN (CF=0.90)具体的推理过程如下。1) 建立节点，SUKN= ，SUKP=。2) 考虑集合，对于，SNBP（）=，不是种子库所，所以建立节点n2=(p2,t3,t1)，将n2放入SUKN中，将p2放入SMKP中。对于t6，SNBP(t6)=p6，p6也不是种子库所，所以建立节点n6=()，将n6放入SUKN中，将p6放入SMKP中。对于t8，SNBP(t6)=p7，p7不是种子库所，故建立节点n7=()，将n7放入SUKN中，并将p7放入SMKP中。此时，SMKP=，均为非种子库所，所以将它们都移动到SUKP中。这时，SUKN=，SUKP=，SMKP=。这时对于SUKN中增加的元素重复以上的过程。对于n2：SNBP(t1)=p1，p1是种子库所，要求输入其托肯值，我们取同样的模糊托肯值=0.8，建立节点n1=()，将n1放入SKN中，将p1放入SMKP中；SKN=n1。对于n6：SNBP(t5)=p1，p1是种子库所，因为节点n1=()已经在SKN中，所以SKN不变，并且SMKP也保持不变；对于n7:SNBP(t7)= ，p1是种子库所并在SMKP中，所以SKN和SMKP均保持不变；p8也是种子库所，为方便比较，我们仍取文献1中的值，即=0.7，建立节点n8=()，将n8放入SKN中，将p8放入SMKP中；SKN=，SMKP=，它们均为种子库所，所以SMKP保持不变，此时SMKP非空，且SUKN中没有增加新的节点，第二步到此结束。3) 至此，我们得到SKN=，=(t1, t5, t7,)，n8=()；SUKN=n4, n2, n6, n7,，n2=()，n6= ()，n7=()。根据算法规定，所以先从n2开始考虑。对于n2，按照规则它只对应于节点n1，所以=0.8=0.80.85=0.68，故n2=()，此时SKN= ，SUKN=；再看n6，它惟一对应于SKN中的n1，所以=0.8=0.80.9=0.72，故n6=()；然后考虑n7，它对应节点n1和n8，而，所以：=min(0.7, 0.8)=0.70.9=0.63，故n7=()。此时SKN=n1, n8, n2, n6, n7，而SUKN=n4。最后来考虑n4，此时它对应于SKN中的n2、n6和n7，所以根据算法的规定我们有：=max， =max(0.680.8,0.720.95,0.630.9)=max (0.544, 0.684, 0.567)=0.684，故最后得到 ，SKN=n1, ，SUKN=，算法结束。4) 由于，所以最后输出=0.684，即d4的真值为0.684。通过比较以上的结果可以发现，本文中最后得到的输出与现有的结果是一致的。由于SKN中的元素在推理过程中不断增加，所以对于一些已经推导出模糊托肯值的库所其对应的节点可以在后面的推导过程中充分地被考虑到，这是本算法的一个优点。对于该算法我们做简短的分析：该算法具有与现有的逆向推理算法一样的准确性，所不同的是本算法是完全基于规则的，并且引进了一些新的定义，给出了整体的模型结构。该算法使FPN的推理过程能够更加贴近人脑的逻辑推理过程，比较缜密。尽管该算法在表述方面相对于图形化的描述不够直观，但是算法的逻辑性更加强了，更方便计算机对算法的实现，从而能有效弥补这些方面的不足之处。考虑算法的复杂度与现有算法1的复杂度相同。4 结束语在本文中主要给出了表示模糊产生式规则的FPN模型，并设计了一个基于模糊推理Petri网的逆向模糊推理算法，结合实例讨论了算法的特点。由于模糊产生式规则的逆向推理算法可以有效地应用到实时系统的故障诊断7中，所以该算法具有一定的实用价值。从另外一方面来讲，该算法可以看作是在现有算法基础上提出的一种与之相对应的比较有效的逆向模糊推理算法，所以同样也具有例如文献6中提出的算法的一些优点。参考文献：1CHEN S M. Fuzzy backward reasoning using fuzzy Petri netsJ. Systems, Man and Cybernetics, Part B, IEEE Transactions, 2000, 30(6): 846-856.2CHEN S M, KE J S, CHANG J F. Knowledge representation using fuzzy Petri netsJ. Knowledge and Data Engineering, IEEE Transactions, 1990, 2(3): 311-319.3GAO M M, ZHOU M C. Fuzzy reasoning Petri nets for demanufacturing process decisionA. Electronics and the Environment, 2001. Proceedings of the 2001, IEEE International SymposiumC. 2001. 167-172.4GAO M M, WU Z M, ZHOU M C. A Petri net-based formal reasoning algorithm for fuzzy production rule-based systemsA. Systems, Man, and Cybernetics, 200