（计算机应用技术专业论文）基于模糊petri网的与或树算法研究.pdf

摘要 与或树是用于表示问题及其求解过程的一种形式化方法，它为问题的解决提供了一 种问题归约的方法。p e t r i 网是一种系统建模工具，由于其异步、并发的特性很适合描述 动态系统，因此在现实问题的解决中有着广泛应用。基于与或树在问题求解中的简便性 和p e t r i 网对系统的描述能力，将与或树运用到p e t r i 网的推理过程中，将给问题推理带 来方便。 本文研究了基于模糊p e t r i 网的与或树算法的理论和方法，并在此基础上实现了基 于该算法的系统设计，研究内容如下： ( 1 ) 对与或树和产生式规则进行研究，实现了用与或树表示产生式规则；对p e t r i 网和产生式规则进行研究，实现了用p e t r i 网表示产生式规则；通过产生式规则，在与 或树和p e t d 网之间建立了一种对应关系。 ( 2 ) 对模糊理论进行研究，在产生式规则和p e t r i 网的基础上，得到模糊产生式规则 的概念和模糊p e t r i 网的概念，并对基于知识表示的模糊p e t r i 网数学模型进行定义。 ( 3 ) 对可信度方法进行研究，结合与或树的结构特点，提出了基于模糊p e t r i 网的 与或树推理算法。 ( 4 ) 设计基于模糊p e t r i 网的与或树算法系统，该系统基于p e t r i 网的与或树算法， 使用x m l 文档、d o m 解析、j a v a 模式等技术，实现对问题求解的全过程。 ( 5 ) 针对一个网络入侵检测实例，用基于模糊p e t r i 网的与或树算法系统进行分析 求解，来验证算法的正确性。 关键词：与或树，可信度方法，模糊p e t r i 网，推理算法 a b s 仃a c t a n d o rt r e ei saf o r m a lm e t h o dt h a te x p r e s s e sp r o b l e m sa n dt h e i rs o l v i n gp r o c e s s e s i t p r o v i d e sap r o b l e mr e d u c t i o na p p r o a c ht o s o l v ep r o b l e m s p e t r in e ti sak i n do fs y s t e m m o d e l i n gt o o l s b e c a u s ei t sa s y n c h r o n o u sa n dc o n c u r r e n c ya r ew e l ls u i t e dt od e s c r i b et h e d y n a m i cs y s t e m ，i th a sab r o a da p p l i c a t i o ni ns o l v i n gt h er e a lp r o b l e m s b a s e do nt h ea n d o r t r e e se a s i n e s si np r o b l e ms o l v i n gp r o c e s sa n dt h ep e t r in e t sd e s c r i p t i o nc a p a c i t yo fs y s t e m s ， p u t t i n gt h ea n d o rt r e ei n t ot h ep e t r in e t sr e a s o n i n gp r o c e s sw i l l 嘶n gc o n v e n i e n c et ot h e p r o b l e mr e a s o n i n g i nt h i sp a p e r , is t u d i e dt h et h e o r ya n dm e t h o d so fa n d o rt r e ea l g o r i t h m st h a tb a s e do nt h e f u z z yp e t r in e t ，a n do nt h i sb a s i sd e s i g n e dt h ea l g o r i t h ms y s t e m s t u d i e sa r ea sf o l l o w s ： ( 1 ) s t u d i e dt h ea n d o rt r e e ，p e t r in e ta n dt h ep r o d u c t i o n a c h i e v e du s i n gt h ea n d o rt r e e ， p e t r in e tt oe x p r e s st h ep r o d u c t i o n ；t h r o u g ht h ep r o d u c t i o n , e s t a b l i s h e dar e l a t i o n s h i p b e t w e e na n d o rt r e ea n dt h ep e t r in e t ( 2 ) s t u d i e dt h ef u z z yt h e o r y , p u tf o r w a r dt h ec o n c e p to ff u z z yp r o d u c t i o na n dt h e c o n c e p to ff u z z yp e t r in e t sb a s e do nt h ep r o d u c t i o na n dp e t r in e t ，a n dd e f i n e dt h ef u z z yp e t r i n e t sm a t h e m a t i c a lm o d e lw h i c hb a s e do nt h ek n o w l e d g er e p r e s e n t a t i o n ( 3 ) s t u d i e d t h ec r e d i b i l i t ym e t h o d s ，c o m b i n e dw i t ht h ea n d o rt r e e ss t r u c t u r a l c h a r a c t e r i s t i c s ，p u tf o r w a r da n d o rt r e er e a s o n i n ga l g o r i t h mb a s e do nf u z z yp e t r in e t ( 4 ) d e s i g n e da n d o rt r e ea l g o r i t h ms y s t e mb a s e do nt h ef u z z yp e t r in e t t h i ss y s t e mu s e d a n d o rt r e ea l g o r i t h mw h i c hb a s e do np e t r in e t a c h i e v e dt h ew h o l ep r o c e s so f p r o b l e m - s o l v i n gu s i n g x m ld o c u m e n t s ，d o m a n a l y s i s ，j a v ap a t t e m a n ds u c ha s t e c h n o l o g i e s ( 5 ) f o ran e t w o r ki n t r u s i o nd e t e c t i o ne x a m p l e ，u s e da n d o rt r e ea l g o r i t h ms y s t e mb a s e d o nf u z z yp e t r in e tt oa n a l y s i sa n ds o l v et h ep r o b l e m ，a n dv e r i f i e dt h ec o r r e c t n e s so ft h e a l g o r i t h m k e y w o r d s ：a n d o rt r e e ，c r e d i b i l i t ym e t h o d s ，f u z z yp e t r in e t ，r e a s o n i n ga l g o r i t h m i i 论文独创性声明 本人声明：本人所呈交的学位论文是在导师的指导下，独立进行研究工 作所取得的成果。除论文中已经注明引用的内容外，对论文的研究做出重 要贡献的个人和集体，均己在文中以明确方式标明。本论文中不包含任何 未加明确注明的其他个人或集体已经公开发表的成果。 本声明的法律责任由本人承担。 论文作者签名：弛n1劬7 年6 月日 论文知识产权权属声明 本人在导师指导下所完成的论文及相关的职务作品，知识产权归属学 校。学校享有以任何方式发表、复制、公开阅览、借阅以及申请专利等权 利。本人离校后发表或使用学位论文或与该论文直接相关的学术论文或成 果时，署名单位仍然为长安大学。 ( 保密的论文在解密后应遵守此规定) 论文作者签名： 他川i 妒。7 年6 月f 日 抛尹年多月1 日 长安大学硕士学位论文 1 1 与或树的定义 第一章绪论 与或树是人工智能中用于表示问题归约及其求解过程的一种方法，它把复杂的多阶 问题分解成多个子问题。问题的分解过程可以用一个图表示出来。例如，把问题p 分解 为三个子问题p l 、p 2 、p 3 。如果只有当p l 、p 2 、p 3 三个子问题都可解时，原问题p 才可解， 称p l 、p 2 、p 3 之间存在“与关系”；称节点p 为“与”节点；由p 、p i 、p 2 、p 3 所构成的图称为 “与树”；为了标明某个节点是与节点，通常用一条弧把与节点连接其与关系的子节点的 各条边连接起来，如下图1 1 ( a ) 所示。如果当p l 、p 2 、p 3 中只要有一个可解，则原问 题p 就可解，称p l 、p 2 、p 3 之间存在“或关系”；节点p 称为“或”节点；由p 、p l 、p 2 、p 3 所 构成的图称为”或树”；如下图1 1 ( b ) 所示。将上述两种方法也可结合起来使用，此时 的图称为与或树( 与或图) 。在与或树中既有与节点，也有或节点，如下图1 1 ( c ) 所 示。 pp p p l p 2p 3 p l p 2p 3p l lp n p 3 1 p 3 2p 3 3 ( a ) 与树( b ) 或树( c ) 与或树 图1 1 与戚树的图形表示 在与或树中有以下相关定义【l 2 】： 定义1 1 对不能再分解变化或等价变换，而且直接可解的子问题称为本原问题。 定义1 2 在与或树中，没有子节点的节点称为端节点；本原问题所对应的节点称为 终叶节点。 定义1 3 在与或树中，满足下列条件之一的，称为可解节点： ( 1 ) 它是一个终叶节点。 ( 2 ) 它是一个或节点，且其子节点至少有一个是可解节点。 第一章绪论 ( 3 ) 它是一个与节点，且其子节点全部都是可解节点。 定义1 4 在与或树中，满足下列条件之一的，称为不可解节点： ( 1 ) 它是一个非终叶节点的端节点，即无法变换的非终叶节点。 ( 2 ) 它是一个或节点，且其子节点全部都是不可解节点。 ( 3 ) 它是一个与节点，且其子节点至少有一个是不可解节点。 定义1 5 由可解节点构成的、且由这些可解节点可推出初始节点为可解节点的与 或树称为解树。 实际上，状态空间问题可以看成与或树的特例，仅由等价变化算符形成的状态空间 图的所有节点都是或节点，因此状态空间图可称为或树。如果既有等价变化算符又有分 解算符，那么将形成与或树，树中既有与节点，也有或节点。 传统上解决与或树的方法主要有两种，一种是基于o p e n 表c l o s e 表的方式1 3 。5 】，另 外一种就是基于p e t r i 网的与或树求解方式。前者主要用于搜索技术，但对于现实中一 些并发的问题的求解就很难利用o p e n 表c l o s e 表，而基于p e t r i 网的与或树求解则可以 对并发问题进行解决【6 。 1 2 基于p e t r i 网的与或树研究及发展现状 p e t r i 网( p e t r in e t ) 是在1 9 6 2 年由德国数学家c a r la d a mp e t r i 在其博士论文用自 动机通讯中提出的一种通用的数学模型，它以描述系统中各元件之间的关系为基础， 用网络来表示系统中同时发生、次序发生或循环发生的各种活动。该模型就成为理论计 算机科学包括自动机模型和形式语言理论的一个分支。在分析并行系统的状态行为的技 术中，p e t r i 网模型具有自然，直观，简单易懂等特点。它是一种形式化模型描述方法， 在并行模型分析，协议的验证，自动控制等方面有广泛的应用9 1 3 1 。 经过近五十年的发展，p e t r i 网无论在应用还是在理论方面都取得了长足的进步。 p e t r i 网理论与应用的发展过程大体可以分为下面几个阶段： 整个2 0 世纪6 0 年代，发展的是被称为特殊网论( s p e c i a ln e tt h e o r y ) 的p e t r i 网 系统，研究主要以孤立的p e t r i 网本身为研究对象，以寻求分析技术和应用方法为主要 目标。 2 0 世纪7 0 年代，为了克服p e t r i 网系统节点过多的不足，也为了增强p e t r i 网描述 系统的能力，以c a r l a d a mp e t r i 为主的一批科学家以p e t r i 网建立的系统的全体对象作 为研究对象，提出了通用网论的p e t r i 网逻辑。 2 长安大学硕士学位论文 2 0 世纪8 0 年代提出了形式语义学的p e t r i 网工程，以理论和应用的结合以及计算机 辅助工具的开发为主要内容。 2 0 世纪9 0 年代p e t r i 网理论研究主要以传统的p e t r i 网系统为基础，提出针对特定 领域的网模型，借助原有的系统性质( 活性、有界性等) 来定义新的性质，借助原有分 析技术来完成分析。 p e t r i 网在解决与或树的应用研究中，主要就是基于与或树使用p e t r i 网在故障分析、 推理算法、调度优化、决策支持中的应用，文献【1 4 】在分析故障诊断问题特点的基础上， 提出一种不增力n p e t d 网元组的故障诊断新模型；文献【1 5 】提出了一种基于默认推理的加 权模糊p e t r i 网模型；文献 1 6 】提出利用数据库的查询技术来实现模糊p “网的推理；文 献 1 7 】以带有控制器的p e t r i 网为建模工具对柔性生产调度中的离散事件建模；文献 1 8 】 提出了一种应用遗传算法解决柔性制造系统调度优化问题的新方法；文献【1 9 】提出了一 种建立非结构化决策支持的模糊p e t r i 网模型。 p e t r i 网解决与或树问题主要是基于两种方式：图的方式和数学模型的方式。图的 方式有直观易懂的特点，但是图的存储需要占用很大的空间，而且存储方式比较复杂。 数学模型的方式在问题变化时，可以对模型进行相应的改变，且存储相对方便，故本论 文采用数学模型的方式对与或树的p e t r i 网表示进行研究。目前，国内对与或树的研究 还很少，可以查找的资料也不多，针对此状况，本文力图将与或树应用到模糊p e t r i 网 中，利用与或树和p e t r i 各自的优点，对现实问题进行建模。 1 3 本课题的任务 本课题的主要任务如下： ( 1 ) 收集与或树和p e t r i 网论文等资料对与或树和p e t r i 网理论进行研究，讨论与 或树的概念性质以及p e t r i 网的模型与定义。 ( 2 ) 对产生式规则进行研究，建立产生式规则、与或树、p e t r i 网相互的联系。 ( 3 ) 模糊p e t r i 网是p e t r i 网与模糊理论相结合的产物，是普通p e t r i 网的模糊化。本 文对模糊理论进行研究，并结合与或树和p e t r i 网知识，讨论能够表示与或树的模糊p e t r i 网的模型，特点以及与模糊产生式规则的对应关系。 ( 4 ) 对x m l 技术进行研究，将产生式规则以x m l 文档的形式进行存储。 ( 5 ) 研究如何使用模式建立模式树，使该模式树能够表示与或树。 ( 6 ) 基于与或树和p e t r i 网对问题解决的各自特点，将与或树与p e t r i 网结合，研究 3 第一章绪论 结合后解决问题的推理算法。 1 4 本文研究的主要内容 第一章为绪论，研究与或树的定义和p e t r i 网的概念，分析与或树和p e t r i 网的发 展现状，提出研究与或树与p e t r i 网结合的课题。 第二章通过研究产生式规则，将现实问题转化为产生式规则；然后通过产生式规则 和与或树之间的联系建立产生式规则的与或树表示的设计；再对p e t r i 网理论基本概念 进行分析，然后通过产生式规则和p e t r i 网之间的联系建立产生式规则的p e t r i 网表示的 设计；从而在与或树和p e t r i 网之间通过产生式规则建立联系，为基于p e t r i 网的与或 树算法的实现打下基础。最后对基于p e t r i 网的知识检测方法进行研究，设计p e t r i 网对 知识检测方法，对规则进行检测。 第三章通过对模糊理论的研究，得到模糊产生式规则的概念；然后，分析产生式规 则可信度方法，为模糊推理提供推理方法；接着对基于模糊产生式规则的模糊p e t r i 网 进行数学模型定义，将产生式规则与模糊p e t r i 建立映射；最后，完成对模糊p e t r i 网与 或树算法的设计。 第四章主要针对模糊p e t r i 网与或树算法进行分析设计。首先是对现实问题建立规 则库，然后将规则库转化为与或树结构，再将基于与或树结构的产生式规则以x m l 文档的形式存储起来，接着对存储规则的x m l 文档用d o m 进行解析，而后使用j a v a 程序实现合成模式的树结构建立并用建造模式进行封装，最后，用程序实现基于模糊 p e t r i 网的与或树推理算法。 第五章给出一个网络入侵检测的实例，针对该网络入侵检测实例，逐步实现第四章 中对模糊p e t r i 网与或树算法设计的六个步骤，对入侵检测实例进行求解，用入侵检测 实例验证推理算法程序。 最后对论文所做工作进行总结，并对今后研究方向和进一步工作做出展望。 4 长安大学硕士学位论文 第二章基于产生式规则的与或树转换为p e t r i 网的设计 从前面的论述可以知道与或树是一种很好的解决问题的方法，但是如何将问题转化 为与或树，这就用到了产生式规则。 2 1 产生式规则的与或树表示 产生式规则可以对知识进行直观的描述，与推理机制相对独立，而且每条规则都具 有相同的形式，这就便于对其进行模块化处理，使得知识的增加、删除、更改带来了方 便。用与或树表示产生式规则，利用与或树的结构特点，会给问题求解带来便利。 2 1 1 产生式规则 数据是记录信息的符号，是信息的载体和标识。信息则是对数据的解释，是数据在 特定场合下的具体含义。人们一般把有关信息关联在一起所形成的信息机构称为知识。 知识、信息和数据是三个层次的概念。有格式的数据经过处理、解释过程会形成信息， 而把有关的信息关联到一起，经过处理过程就形成了知识。知识是用信息表达的，信息 则是用数据表达的，这种层次不仅反映了数据、信息和知识的因果产生关系，也反映了 它们不同的抽象程度。人们在社会实践过程中，其主要的智能活动就是获取知识并运用 知识解决生活中遇到的各种问题。 一条知识一般可以由据有完整意义的一句话或几句话表示出来，而这些知识可以用 谓词逻辑表示出来，一般是一个谓词公式。谓词公式就是用谓词联接符号将一些谓词联 接起来形成公式。谓词公式既可以表示事物的状态、属性、概念等事实性知识，也可以 表示事物间具有确定因果关系的规则性知识。 产生式规则表示法用“如果，则”的形式表示知识，它具有直观、自然，便 于进行推理的特性产生式规则是规则库中最基本的知识单元，它们与推理机制相对独 立，而且每条规则都具有相同的形式，这就便于对其进行模块化处理，使得知识的增加、 删除、更改带来了方便，为规则库的建立和扩展提供了可管理性。同时，它既可以表示 确定性的知识，又可表示不确定性的知识；既有利于表示启发式知识，又可方便地表示 过程性知识。目前己应用的专家系统大多是用产生式规则来表示其过程性知识。产生式 规则有固定的形式，每条产生式规则都是由前提与结论这两部分构成，而且每一部分所 含的知识量都比较少，这就便于对规则进行设计，有益于对规则库中知识的一致性及完 整性进行检测。产生式规则的不足之处就是效率不高，不能够表达具有结构性的知识。 5 第二章基于产生式规则的与或树转换为p e t r i 网的设计 产生式规则通常用于表示因果关系的知识，其基本形式是： p _ q 或者i f pt h e nq 其中，p 是产生式规则的前提，用于指出该产生式规则将选用的条件：q 是一组结论或操 作，用于指出当前提p 所指示的条件被满足时，应该得出的结论或应该执行的操作。整 个产生式规则的含义是：如果前提p 被满足，则可推出结论q 或执行q 所规定的操作。 为了严格地描述产生式规则，用巴科斯范式b n f ( b a e k u sn o r m a lf o r m ) 给出产生 式规则的形式描述及语义： ：= _ ：= i ：= i ：= a n d = 【( a n d ) 】i o r 了 【( o r ) 】 ：= 【 ，】 产生式规则的条件与结论可以由多个命题组成，各命题间可能包含“o r ( 或) ”或“a n d ( 与) ”算符，产生式规则有四种类型，如下所示： 类型1 ：i fp la n dp 2a n d a n dp 。t h e np 。 类型2 ：i fp zt h e np la n dp 2a n d a n d 巩 类型3 ：i fp 1o rp 2 o r o rp 。t h e np ： 类型4 ：i fp 。t h e np io r p 2 o r o rp 。 其中，类型4 这种产生式规则是没有任何实际意义的，因此在知识表示中不允许有这种 产生式规则存在。 2 1 2 产生式规则转化为与或树的设计 由产生式规则的定义可知，利用产生式规则可以实现有前提条件的指令性操作，也 可以实现逻辑推理 2 0 a l 】。实现操作的方法是：当测试到一条规则的前提条件得到满足时， 就执行其后部的动作。利用产生式规则实现逻辑推理的方法是当有事实能与某规则的前 提匹配时，就得到该规则后部的结论。产生式系统的任务可以看作是寻找从起始节点到 终节点的某个解图。粗略地说，就是从一个与或树的节点n 到节点集合n 的一个解树 类似于一个普通树中的一条路径。 6 长安大学硕士学位论文 我们可以这样将产生式规则以与或树的形式进行转换，转换方式如下：将产生式规 则中的条件或前提看作与或树中的子节点，将产生式规则中的操作或结论看作与或树 中的“与，节点或“或”节点，规则可以看作从节点到子节点的边，由于规则中的前提可能 是多个条件的与或关系，所以产生式规则可以使用与或树来表示。以产生式规则i f p t h e nq 为例，其树结构图如图2 1 所示： q 厂、 pv 图2 1 产生式规则转化为树结构 同样前面介绍的产生式规则类型1 、2 、3 也可转化为树结构分别如图2 2 中的图a 、 图b 和图c 所示： p 、 p 2p np ip 、p 2 p n ( a ) 类型1( b ) 类型2 ( c ) 类型3 图2 2 产生式规则的与，或树结构表示 2 2p e t r i 网表示产生式规则的设计 产生式规则由于规则之间相互独立，特别是知识库与推理是分离的，规则之间的相 互依赖就难以从规则表示中反映出来，对于个大的知识库尤为明显【2 2 】。因此有必要采 用一种形式化的分析模型来表示产生式规则，在本论文中采用p e t r i 网来对产生式规则 进行表示。 2 2 1p e t r i 网的定义 p e t r i 网由两类元素组成：表示状态的元素和表示变化的元素，因此一个简单的有向 网可以用一个三元组表示田1 。 7 第二章基于产生式规则的与威树转换为p e t r i 网的设计 定义2 1 三元组n = ( p ，t ；f ) 称为有向网( d i r e c t e dn e t 简称网( n e t ) ) 的充分必要 条件是： ( 1 ) p n t = 国 ( 2 ) p k j t o ； ( 3 ) fcp x t u t x p ( 其中”为笛卡尔积) ； ( 4 ) d o m ( f ) u 以刃= p u t ；其中 a o m ( f ) = 缸i3 y ：o ，力毋 c o a ( f ) = 秒1 3 x ： ，力毋 定义2 1 中p 为n 的库所( p l a c e ) 集，t 为变迁( t r a n s i t i o n ) 集，f 为流关系。p u t 叫做n 的元素集。p 中的元素叫做库所( 也称p 元素) ，t 中的元素叫做变迁( 也称t 元素) 。p o t 为空集。“，号表示两集合的笛卡儿乘积运算。f 是由一个p 元素和一个t 元素组成的有序偶的集合，d o m ( f ) 是f 所含有序偶的第1 个元素组成的集合，c o d ( f ) 功是f 所含有序偶第2 个元素的集合。 库所集p 和变迁集t 是有向网的基本成分，流关系是从它们构造出来的，所以在p ， t 和，之间用分号隔开。变迁和库所是两种不同的元素，所以p n t = o ，而p u 丁g 表 示网中至少要有一个元素。每个库所代表一种资源，资源的流动由流关系规定，所以变 迁只能与库所有直接的流关系：fsp x t u t x p ，不参与任何变迁的资源表现为孤立的 库所，不引起资源流动的变迁表现为孤立的变迁，所以可以得出有向网定义中 d o m ( f ) u c o d ( f ) = 尸u 丁规定网中不能有孤立元素。 网的图形表示中是用“o ”( 圆) 表示库所，用“r 表示变迁( 有些资料中定义用矩形 来表示) ，用从节点x 到y 的有向弧( 箭头) 表示有序偶( x ，y ) 。如果有向弧是从库所 到变迁，则称库所是输入库所，变迁是库所的输出变迁；如果有向弧是从变迁到库所，则 称库所是变迁的输出库所，变迁是库所的输入变迁。有向弧只存在于库所和变迁或者变 迁和库所之间，任意的两个库所之间或者任意的两个变迁之间都没有有向弧相连接。如 图2 3 就是一个最简单的p e t r i 网模型。 t i p lo p 2 图2 3 简单p e t r i 网图形表示 8 长安大学硕士学位论文 2 2 2 产生式规则的p e t r i 网表示设计 文献 2 4 1 q b 提出了基于p e t r i 网的产生式规则表示。在此基础上，产生式规则的p e t r i 网表示设计如下： p e t r i 网中的一个库所映射一条产生式规则的条件或结论； p e t r i 网中一个变迁表示一条产生式规则的执行。 将三种产生式规则的三种类型表示成对应的p e t d 网，依次对应如图2 4 的图( a ) 、 图( b ) 、图( c ) 。 p lp 2 p lp 2p n p lp 2p n ( a ) 类型1( b ) 类型2( c ) 类型3 图2 4 产生式规则的p e t r i 网表示 2 3 基于p e t r i 网的知识检测方法设计 建立知识库的过程是知识经过一系列变换进入计算机系统的过程，在这个过程中存 在着各种各样导致知识不健全的因素，破坏知识库的完整性与一致性。如： ( 1 ) 领域专家提供的知识中存在某些不完整、不一致甚至错误的知识，这必然会影 响到知识库的完整性与一致性。 ( 2 ) 在获取知识的过程中，知识工程师未能准确、全面地理解专家的意图，使得形 成的知识存在错误，也会影响到知识库的完整性与一致性。 ( 3 ) 采用的知识表示模式不适当，不能准确表示领域知识，同样会影响到知识库的 完整性与一致性。 ( 4 ) 对知识库的增加、删除、更改时，没有充分考虑其产生的影响，以致新知识库 出现不完备的情况，尤其是知识之间存在着非常复杂的联系的时候。 为了使知识库具有完整性和正确性，还需要对知识库进行知识检测与维护。知识库 经常会出现这样或那样的问题，主要表现在知识冗余、矛盾、从属、环路、不完整等方 面，下面用产生式规则表示法为例说明这些问题的表现形式2 5 , 2 6 ： 9 第二章基于产生式规则的与，或树转换为p e t r i 网的设计 ( 1 ) 知识冗余 所谓知识冗余是指在知识库中存在多余的知识或者多余的约束条件，主要分以下三 种情况，分别设计如下： a 等价规则。当两条规则在相同条件下有相同结论时称为等价规则。对于等价的 规则，可以从知识库中删除其中任意一条。 b 冗余规则链。如果两条规则链中第一条规则的条件相同，且最后一条规则的结 论等价，则称此两条规则链中存在冗余。对于冗余规则可以进行删除，但删除 的时候应注意知识库的完整性。 c 冗余条件。如果两条规则有相同的结论，但一条规则中的某个子条件在另一条 规则的前提条件中被否定，而其它子条件保持一致，则称这两条规则具有多余 的条件。对于多余的条件可以进行删除，删除时应注意知识库的完整性。 ( 2 ) 矛盾 两条规则或规则链在相同条件下得到的结论是互斥的，或者它们虽有相同的结论， 但规则强度不同，则称它们是矛盾的。例如： r 1 ：i fpt h e n q l r 2 - i fpt h e n q 2 若o l = 1 q z ，则r 1 与r 2 是矛盾的。再如： r 1 ：i f p t h e nq r 2 - i f q t h e nr r 3 ：i frt h e n s l r 4 - i fpt h e nt r 5 - i ftt h e n s 2 其中，r 1 ，r 2 ，r 3 是一条规则链；r 4 ，r 5 是另一条规则链。它们有相同的初始条件， 即p 。此时，若s i = - 1 s2 ，则这两条规则链是矛盾的。 对于矛盾规则或矛盾规则链，不能让他们共处于同一知识库里，应舍弃其中一个。 ( 3 ) 从属 如果规则r 1 与r 2 有相同的结论，但r l 比r 2 要求更多的约束条件，则称r l 是r 2 的 从属规则。出现此种情况时，需要知识库中的实际状况，对规则进行取舍。 ( 4 ) 环路 l o 长安大学硕士学位论文 当一组规则形成一条循环链时，称它们构成了一个环路。例如： r l ：i fpt h e n q r 2 - i f q t h e nr r 3 ：i frt h e ns r 4 ：i fst h e np 对这四条规则无论是执行哪一条，最终都又回到了出发点，即它们之间出现了环路。 环路有可能使推理陷入死循环。此时，就修改其中的一条规则，破坏形成环路条件。 除了上述四种情况外，在知识库中还可能存在一种称为“不可达”的知识，它指的是 约束条件永远得不到满足的知识，这种知识在推理过程中不会被激活，应该被舍弃。 以上对知识库中知识出现的问题做了描述，为了保证知识库的正确性，需要对做好 的知识进行检测。检测分为静态检测和动态检测。静态检测主要是在知识输入之前进行 检查工作。动态则是在输入过程中以及系统运行过程中。因此，我们仅讨论动态监测方 法。动态检测方法有很多种，目前常用的方式是基于经典逻辑的检测方法和基于p e t r i 网的检测方法。现研究基于p e t r i 网的知识检测方法。 ( 1 ) 冗余的检测。等价规则及冗余条件在p e t r i 网模型中，有相同的输入库所和输出 库所，因此建模过程就可被发现。下面来看冗余规则链的检测。设有如下产生式规则： r l ：i f a l t h e n 1 2 r 2 ：i f a 2 t h e n a 3 r 3 ：i f , 4 1 t h e n a 3 r 4 - i f , 4 2a n d , 4 4t h e na 5 r 5 ：i f a 5 t h e n 彳6 其p e t r i 网模型如图2 5 所示： 图2 5 基于p e t r i 网的冗余检测 图2 5 中各符号的含义及与p e t r i 网中含义相同，边线上的“，r ，是状态标志，它表示 由库所p i 所代表的命题a i 的真值为真，若为f ”，则表示相应命题真值为假。由图2 5 第二章基于产生式规则的与戚树转换为p e t r i 网的设计 中可以看出，当a l 所要求的事实存在时，则从p l 出发经p 2 可以到达p 3 ，同时还可以经 另一条路线( 即由r 3 所表示的路线) 直接到达p 3 ，因此出现了冗余规则链。但因a 2 还 在“的条件部分出现，即从p 2 还可到达p 5 ，所以r 3 是冗余规则。 此外，由p 5 可以到达p 6 ，而p 6 是一个终点，如果p 6 所代表的命题a 6 不是最终结 论，则r 5 将成为一条死规则，故也是多余的。 ( 2 ) 矛盾、从属及环路的检测。设有如下产生式规n - r l ：i f a l t h e n a 2 r 2 - i f a 2 t h e n a 3 r 3 ti f a 3 t h e n a 4 r 4 ：i f a l t h e n a 5 r 5 i f a s t h e n 1 么4 r 6 ：i f a 3a n da s t h e n a 7 r 7 ：i f a 6t h e na 7 r 8 ：i f a 5 t h e n a s r 9 ：i f a s t h e n a 9 r 1 0 i f a 9 t h e n a 5 其p e t r i 网如图2 6 所示： 崩 ， 力 图2 6 矛盾、从属及环路的检测 由图2 6 可以看出： ( 1 ) 由p l 出发，经p 2 ，p 3 到达p 4 时，推出p 4 所代表的命题a 4 为真；但由p l 出发经 p 5 到达p 4 时，得到为假，这就产生了矛盾。由此可知由r l ，r 2 ，r 3 所构成的规则链 与由r 4 ，r 5 所构成的规则链是矛盾的。 1 2 长安大学硕士学位论文 ( 2 ) 由p 3 及p 6 可到达p 7 ，另外仅由p 6 也可到达p 7 ，这表示r 6 比r 7 要求更多的条件， 即币是r 7 的从属规则。 ( 3 ) 由p 5 出发经p 8 ，p 9 又回到了p 5 ，构成了环路，这表示r 8 ，r 9 及r l o 形成环路。 以上讨论了用p e t r i 网进行知识检测的方法，模糊p e t r i 网的检测方法与p e t r i 网的检 测方法相同。所以，在用模糊p e t r i 网进行知识检测时，首先通过模糊p e t r i 网模型把知 识表示出来，再用模糊p e t r i 网模型的图形对知识进行分析，从而达到对知识的检测。 2 4 小结 本章主要是基于产生式规则的p e t r i 网的设计。首先研究了了产生式规则的与或树 表示，然后分析了如何把产生式规则以p e t r i 网的方式进行转化设计，最后对基于p e t r i 网的知识检测方法进行了研究。 1 3 第三章基于模糊p e t r i 网的与，或树算法设计 第三章基于与或树的模糊p e t r i 网 产生式规则的p e t r i 网表示能够解决边界确定的问题，但现实生活中很多问题的描 述并不是确定的，这就产生了模糊理论的概念。 3 1 模糊理论 在现实世界中，我们经常遇到事物或对象是模糊的、不确定的，它们互相渗透，互 相贯通，彼此之间没有明显的分界线，也没有精确定义的判别准则。比如，人们通常说 “某人身高很高”，“某人身高很矮”等，但究竟哪个高度算是“很高”，多少高度才算“很矮”， 却是不能明确的，且“很高”与“很矮”之间也没有明确的界线，因而它们都是模糊的，具 有模糊性。1 9 6 5 年扎德( l a z a d e h ) 从集合论的角度对模糊性问题的表示与处理进行 了研究，建立了模糊理论的基础，为定量描述与处理模糊性问题提供了一种新理论。 3 1 1 基本定义 模糊理论主要研究的是一类边界不确定的问题，其特征函数的取值在【0 ，1 】区间上， 下面先给出模糊理论的一些定义【2 7 。2 9 1 ： 定义3 1( 模糊集合) 设u 为论域，助是把任意u 映射为【0 ，1 】上某个函数， 即 k t a ：u 一 0 ，1 】 u 一心 ) 则称队为u 上的一个隶属函数，由队( “u ) 所构成的集合a 称为u 上的一个模糊 集， i l a ( u ) 称为斗对a 的隶属度。在给定的论域u 上可以有多个f 集，记u 上的f 集的全体为f ( 【厂) 。 定义3 2 ( 模糊集的九水平截集) 设a f ) ，九 0 ，1 】，则称普通集合 4 = , i u u ，以( “) 椰 为a 的一个九水平截集，九称为阈值或置信水平。 定义3 3 ( 模糊度) 设a f ( u ) ，d 是定义在f 缈) 上的一个实函数，如果它满 足如下条件： ( 1 ) 对任意a f ( u ) ，都有d ( 么) 【o ，l 】； 1 4 长安大学硕士学位论文 ( 2 ) 当且仅当彳是一个普通集合时，d ( 彳) = o ： ( 3 ) 若a 的隶属函数u a ( u ) 鲁0 5 ，则d ( 彳) = 1 ； ( 4 ) 若a ，b ef ( u ) ，且对任意u eu ，满足 鳓( ) 儿( “) o 5 或者鳓( “) - - - , u a ( u ) o 5 则有d ( b ) j ( 彳) ； ( 5 ) 对任意a f ( u ) ，有d ( a ) d ( 一) 则称d 为定义在f ( u ) 上的一个模糊度，d ( 彳) 称为彳的模糊度。 定义3 4 ( 模糊关系) 设尺是u x v 上的一个f 子集，它的隶属函数： r ：u x v 一 o ，1 】 ，d 专r ( u ，1 ，) 确定了u 中的元素u 与y 中的元素v 的关系程度，则称r 为从u 到y 的一个模糊关系， 记为：u 与矿。 3 1 2 模糊集合的表示方法 在论域u 上的模糊集合彳，通常采用的表达方式有下面三种： ( 1 ) 序偶表示法 在一般情形下，模糊集合都可以表示为：a = ( ”，彳 ) ) iu u ) ( 2 ) z a d e h 表示法 若u 是有限集或可数集，采用z a d e h 表示方式表示为：a = 彳( ) ( 3 ) 向量表示法 a = ( 彳( ”1 ) ，a ( u 2 ) ，彳( ) ) 3 1 3 模糊集合的基本运算 两个模糊子集间的运算，实际上就是逐点对隶属函数作相应运算。 定义3 5 设彳，b f ) ，若 v u u ，8 ( u ) 彳( z ，) 则称彳包含口，记为b 彳。 定义3 6 设彳，b f ( u ) ，分别称运算a u b , a n b 为么与b 的并集、交集。称彳。为 彳的补集，也称为余集。它们的隶属函数分别为： 1 5 第三章基于模糊p e t r i 网的与或树算法设计 ( a u 召) ( ”) = a ( u ) vb ( u ) = ma ) ( c a ( u ) ，b ) ) ( a n b ) ( “) = 么( “) a b ( ”) = m 血c a ( u ) ，b ) ) a 。 ) = 1 - a ( u ) 式中，z a d e h 算子“v ”表示“取最大值”运算；“a ”表示“取最小值”运算。 3 1 4 模糊命题与模糊知识表示 人们在日常生活及科学试验中经常用到一些模糊数据和模糊概念，这些含有模糊数 据、模糊概念或带有确信程度的陈述句称为模糊命题。在知识表示中，模糊推理句与模 糊产生式规则基本形式有相同的形式。并且模糊产生式规则可以看作是两个模糊命题之 间模糊关系的规则，因此以下在模糊产生式规则基础上讨论模糊知识的表示问题【3 0 1 。模 糊产生式规则刻画了多个命题之间的模糊关系，很适合表达模糊的或不确定的知识。 模糊产生式规则的条件与结论可以由多个命题组成，各命题间可能包含“o r ( 或) ” 或“a n d ( 与) ”算符，这就是复合模糊产生式规则。基于产生式规则的三种类型，复杂 模糊系统中的模糊产生式规则可以分成以下两种类型： 类型1 ：i fp la n dp 2a n d a n dp 。t h e np 。( c f = a ) ，w i ，w 2 w n ，w 4 类型2 ：i fp lo rp 2o r o rp 。t h e np ：( c f = ) ，w i ，w 2 w n ，w z 其中： p i 为条件命题或者结论命题； w i 为对应命题p i 的可信度( 根据经验对一个事物或现象为真的相信程度称为可信 度) ； “为规则的强度，也就是规则的可信度。 对于前面提出的形如 i f p l t h e n p 2 a n dp 3 ( c f = “) ，w l ，w 2 ，w 3 的这类模糊推理规则分解为 i fp lt h e np 2 ( c f 2 肛) ，w l ，w 2 和i fp lt h e np 3 ( c f = l x ) ，w l ，w 3 这样的两条或多条规则其实就是模糊产生式规则类型1 的特例。所以模糊产生式规 则就只有上述的类型l 和类型2 两种表示形式。 长安大学硕士学位论文 3 2 产生式规则可信度方法 在可信度的概念的基础上，人们在对可信度的推理过程中提出了可