（计算机应用技术专业论文）基于RETE模式匹配的柑橘栽培专家系统研究与实现.pdf

摘要 专家系统是人】：智能领域中一个重要的研究领域，它已经被成功运用到各个行业中。柑 橘栽培是贵州农业的重要部分但是贵州交通条件相对落后，经济与技术信息传播较慢，农 业专家数量少因此建立柑橘栽培专家系统对贵州农业的发展具有重要的意义。 通过研究柑橘栽培的特点，应用了产生式系统的方法来构建此柑橘专家系统。产生式系 统在人工智能领域占据着非常重要的地位，且被应用到许多方面，但是产生式系统也有它的 缺点，就是当产生式系统的规模越来越大的时候，系统的执行速度和工作效率会越来越低。 为了提高产生式系统的性能，研究人员已经作了许多努力。大部分的研究都主要集中于提 高产生式系统中三个阶段中匹配的速度，作为产生式系统推理三个阶段的第一个阶段，匹 配效率问题时产生式系统效率问题的重要问题。据统计，匹配阶段的时间开销要i ! 丁到接个产 生式系统运行时间的9 0 5 以上。因此，研究并提出快速的匹配算法是提高产生式系统效率的 重要条件。 在诸多匹配算法中，r e t e 算法是最有效率的算法。r e t e 算法主要是通过存储一系列已 经匹配的规则和部分匹配，减少了大量的规则与工作存储器中事实的比较，显著地降低了复 杂性。它有效地防止了许多不必要的重复匹配。仅仅当工作存储器中的元素发生变化的时 候，它才将这种变化反映到建立的网络中去。r e t e 是一种经典的匹配算法，但是它自身存 在一些影响执行效率的因素，例如：在算法的执行过程中，删除操作和栈的操作太过于庞大， 消耗大量的时间；其b m e m o r y 和双输入节点结构的效率一般。针对这些缺陷本文提出相 应的改进措施，有效地提高了推理的速度和效率。 关键字：专家系统，产生式系统，推理机，r e t e 算法 a b s t r a c t e x p e r ts y s t e m so c c u p yap r o m i n e n tp l a c ei na r t i f i c i a li n t e l l i g e n c ea n db e i n gi m p l e m e n t e di n m a n yf i e l d s a g r i c u l t u r ee x p e r ts y s t e mi sam a i nb r a n c ho fe x p e r ts y s t e ma ，t h eo r a n g ep l a n t i n g p l a yai m p o r t a n tr o l ei ng u i z h o up r o v i n c e e x p e r ts y s t e m sh a v ean u m b e ro fm a j o rs y s t e m c o m p o n e n t sa n di n t e r f a c ew i t hi n d i v i d u a l si nv a r i o u sr o l e s i nt h i sp a p e r ，iu s ep r o d u c t i o ns y s t e mt ob u i l dt h eo r a n g e e x p e r ts y s t e m t h ep r o d u c t i o n s y s t e mo c c u p yap r o m i n e n tp l a c ei na r t i f i c i a li n t e l l i g e n c e ，a n dh a sb e e nu s e di nm a n ya s p e c t s s u c h 粥e x p e r ts y s t e m s b u tw h e nt h es c a l eo ft h ep r o d u c t i o ns y s t e mi sb e c o m i n gl a r g e ra n d l a r g e r ，t h ep r o b l e mo fi t se x e c u t i n gs p e e da n dw o r k i n ge f f i c i e n c yi sg e r i n gm o r e a n dm o r e o b v i o u s t ot h i sp r o b l e m ，as o l u t i o nw a sp u tf o r w a r d ，w h i c hi sm a i n l yf o c u s e do nm a t c h a l g o r i t h m t oi m p r o v et h ep e r f o r m a n c eo fp r o d u c t i o ns y s t e m s ，m a n yr e s e a r c he f f o r t sh a v e b e e n d o n e t h e s er e s e a r c he f f o r t sa r em a i n l yf o c u s e do ns p e e d i n gu pt h em a t c ho fp r o d u c t i o ns y s t e m s b yd e v e l o p i n gt h ef a s t e rm a t c ha l g o r i t h m s t h em o s te f f e c t i v es u c hs o l u t i o nt ot h i si st h er e t e a l g o r i t h m t h er e t ea l g o r i t h mr e d u c e st h ec o m p l e x i t yb yr e d u c i n gt h en u m b e ro fc o m p a r i s o n s b e t w e e nr u l ec o n d i t i o n sa n df a c ti nt h ew o r k i n gm e m o r y t oa c c o m p l i s ht h i s ，t h ea l g o r i t h ms t o r e s al i s to fr u l e sm a t c h e do rp a r t i a l l ym a t c h e db yt h ec u r r e n tw o r k i n gm e m o r y t h u s ，i ta v o i d s u n n e c e s s a r yc o m p u t a t i o n si nr e c h e c k i n gt h ea l r e a d ym a t c h e dr u l e s ( 1 1 1 e ya r ea l r e a d ya c t i v a t e d ) o r u n - m a t c h e dr u l e s ( t h e i rc o n d i t i o n sc a n n o tb es a t i s t i e du n d e rt h ee x i s t i n ga s s e r t i o n si nt h ew o r k i n g m e m o r y ) o n l yw h e nt h ew o r k i n gm e m o r yc h a n g e sd o e si t r e - c h e c kt h er u l e s ，a n dt h e no n l y a g a i n s tt h ef a c t sa d d e do rr e m o v e df r o mw o r k i n gm e m o r y t h er e t ei sac l a s s i c a lm a t c ha l g o r i t h m b u tt h i sa l g o r i t h mi ui t s e l fc o n t a i n ss o m ef a c t o r s d i s a d v a n t a g e o u st ot h ee x e c u t i o ne f f i c i e n c y b a s e do nt h ea n a l y s i so ft h ef e a t u r eo ft h er e t e a l g o r i t h m t h ep r o b l e mo f i tt h a tt h eo v e r h e a d so f d e l e t i o no p e r a t i o n sa n ds t a c ko p e r a t i o na ”t o o l a r g e ，a n dt h es t r u c t u r eo fb - m e m o r i e so f t h et w o i n p u tn o d e si sn o tv e r ye f f i c i e n t i nt h i sp a p e r ， an u m b e ro fi m p l e m e n t a t i o no p t i m i z a t i o nw a sp u tf o r w a r do nt h e s eo b s e r v a t i o n s k e yw o r d s ：e x p e r ts y s t e m ，p r o d u c t i o ns y s t e m ，i n f e r e n c ee n g i n e ，r e t ea l g o r i t h m 3 1 1 序言 第一章绪论 农业专家系统( 又叫农业智能系统) ，是运用人 ：智能的专家系统技术，井集成了地理 信息系统、信息网络、智能计算、机器学习、知识发现、优化模拟、虚拟现实等多方面高新 技术，汇集农业领域知识、模型和专家经验等采用合宦的知识表示技术和推理策略，运用 多媒体技术并能以信息网络为载体，向农业生产管理提供咨询服务，指导科学种田。对提高 农业科技文化素质t 就地培训基层农技人员，促进农业科技推广体制现代化，推动农业可 持续发展，改变传统农业向现代化农业转变，将发挥重大作_ 【f ；i ，它是适合我国国情的精确农 业，它不仅适用于广火农村，建造各种种植业、养殖业专家系统，是设施农业智能化、自动 化的重要技术。 农业专家系统，是由生态系统、经济系统、社会系统和技术系统在特定的时间和空间上 组合而成的复杂大系统，是农业信息技术中的一项重要技术。它是运用人工智能的专家系统 技术结合农业特点发展起来的门高新技术。它是一个具有大量农业知识与经验的计算机 系统依据多个农业专家提供的特殊领域的知识和经验，模拟农业专家解决某个农业复杂问 题进行决策。专家系统具有解释功能，容易为农业用户所接受，通过友好的人机交互界面， 像人类专家那样根据用户提供的不同信息进行咨询，并根据用户的知识水平，以用户可以理 解的形式解释自己的推理思路。农业专家系统的开发与应用不仅有助于农业决策科学化，而 且也给我们带来了很高的经济效益和社会效益 1 5 。 柑橘的栽培是贵州农业的重要部分。多年来，针对我省的柑橘栽培技术j 。大农业专家 及科研人员，积累了大量的宝贵经验和众多的科研成果，应当尽快深入浅山的将这些成果准 确合理的普及应用到生产实践中去，使其产生更人的杜会效茄和经济效益。贵州的j ：业化和 现代农业开发的时间起步晚，经济与技术信息的传播慢。农业专家数量远远不能满足实际需 要，而且交通条件相对落后，对农民科学种植的指导更是不便。本系统的实现，无疑可以 缓解这个问题农民在家里就可以随时远程得到科学的决策支持。 1 2 农业专家系统的发展趋势 自第一个专家系统问世以来，专家系统技术虽然取得了很大的发展，但随着麻用领域的 扩大牲及人们对它的期望日益提高，也暴露出了许多薄弱的环节，针对这些薄弱环氍有些 学者已经开始了新一代专家系统的研究，其主要研究的领域有： 分布协同式的体系结构；所谓分布协同体系结构是指把知识库分布于一个计算机网络 的不同节点上，或者把推理机分布于计算机网络的不同节点上，或者两者同时分布，但在求 解问题是，它们能互通信息，密切合作，共同完成问题的求解任务 2 2 1 ；在这种体系结构中， 主要应解决的问题是任务分布和合作策略的问题。 知识的自动获取：知识获取可以分为两个阶段：一是从领域专家及有关文献资料那里获 取知识以示从系统运行实践中不断总结出新的知识。对丁前一种情况，需要解决自然语言 4 识别以及火蟹实例中门纳戋u 识等问题，对丁历种情况，还需要解决如何从系统得运行实践中 发现问题以及通过总结经验教训归纳出新的知识，修改旧的知识等问题。 深层知识的利用；所谓深层知识是指相关领域中的理论性的知识，原理性的知识，丽专 家的经验遁常被称为袭层知识或浅层知识，在这当中的主要问题是如何确定深层知识的容量 和边缘，另外，非单调亦是深层知识利用中的一个凼难润题【1 7 】【】8 】。 1 3 课题的研究内容 该项目以现在正在研究实现少量专家及时为广大农民服务，改变贵卅】落后种植技术的现 状其主要功能包括病虫害预警诊断防治决策、品种选择决策、施肥管理决策等，向果农提 供柑桔生产管理全过程详细周到的咨询和决策服务指导柑桔生产。 本系统采用客户层，应用逻辑层数据库层的结构体系，遵循人t 智能的技术原理，基于 p r o l o g 构建系统的知识库用户可以通过浏览器访问在线专家系统，在任何时间获取决 策信息。对于不能上嚼的地方，开发了相应单机平台的专家系统，将其制作成系列光盘，安 装好后即可使用。 该系统以信息网络为载体，提供病虫害和柑桔栽培生产管理过程的咨询服务缓解了农 业专家短缺、充分发挥信息技术的主导作用，可产生重要的经济效益。 根据柑橘农业专家系统的特点，本研究主要涉及知识获取，知识表示，知识库内规则冲 突解决，推理机实现。具体的理论和算法将会涉及到产生式系统人l ：神经网络，模式识 别近似推理。m a r k o v 算法，r e t e 算法，贝叶斯定理。 第二章柑橘专家系统的系统结构 2 1 专家系统工作原理和基本组成概述 专家系统技术是人工智能中面向应_ i = f j 的重要分支之一。首先它是人i ：智能的范畴，与传 统的计算机程序重点是研究算法、建立数学模型不同，它的技术基础是人l 智能的知识表示 技术和问题求解技术。知识和推理构成专家系统的两大要素 1 9 。 专家系统与一般人一 智 能系统又有所区别。昂重要的特征是它的研究对象不是普通人的智能，而是某个领域具有技 术特长的专家在解决专r j 问题的本领。它把所选择的专家称为领域专家，而建造专家系统的 计算机技术人员或人工智能工作者称之为知识工程师。 专家系统一般可以分为以下凡个主要部分：知识库，工作存储器，推理机，用户界面。 但通常建立一个专家系统还需要以下几个部分；d o m a i ne x p e r t 、k n o w l e d g ee n g i n e e r 、用 户。以上几个部分可以用下图来表示： d o m a i n e x p e r t e n g i n e e r k n o w l e d g e 要 l 、 s y s t e m e n g i n e e r d o m a i ne x p e r t 就是某个领域的专家，他提供原始的知识。k n o w l e d g ee n g i n e e r 是把专 家的知识翻译成电脑所能够识别的知识的工程师。某领域的专家把他所知道的知识告诉 k n o w l e d g ee n g i n e e r 以后，由k n o w l e d g ee n g i n e e r 对这些知识进行处理，最j 亓做成知识库 k n o w l e d g eb a s e 。s y s t e me n g i n e e r 是设计专家系统的程序员，他的主要任务是编写专家系 统的推理机构i n f e r e n c ee n g i n e ，和用户界面u s e ri n t e r f a c e 。用户使用用户界面和专家 系统打交道，他和专家系统之间的交流的一些信息由工作空间w o r k i n gs t o r a g e 储存。推理 机构根据用户信息和知识库中的信息为用户提供服务。 6 吴 2 2 知识获取 知识获取是一个与领域专家，专家系统建造者和专家系统本身都密切相关的一个问 题，出于种种原因，至今仍然是一件比较困难得问题使专家系统建造中一个“瓶颈”问题 知识获取的基本任务是为专家系统获取知识，建立起健全，完善，有效的知识库，以满足求 解问题的需要。 知识获取的方式主要有：非自动知识获取，主要是首先由知识1 ：程师从领域专家或有 关的技术资料那里获取知识，然后再由知识j ：禅师用某种知识编辑软件输入到知识库中； 自动知识获取，主要是指系统本身具有获取知识的能力，它不仅可以直接与领域专家对话， 从专家提供的原始信息中“学习”专家系统所需的知识，而且还能从系统自身的运行实践中 总结，归纳出新的知识，发现知识中可能出现的错误不断自我完善，建立超性能优良，只 是完善的知识库 3 4 。由于在实际当中拄术上的种种限制。目前还做不到知识的完全自动获 墩。 在进行知识获取的时候，可以采用图形化导航的方式所谓图形化导航的方式是指开发 人员根据系统提供的图形化提示和图形化谓词，来输入概念，包括名称，属性，值等，以及 建立规则和命题。这样就可以使开发人员不必学习某种知识表示语言就能进行知识编辑。不 必记住知识表示的具体规则方法就能都建案例产生式规则，这样就简化了开发人员建立知识 库的过程。 2 3 推理机 推理机是专家系统的重要组成部分，它是专家系统解决问题的基本技术。专家系统常用 于没有合适算法和无算法的情形，而推理是解决这种情形的唯一可行方法。推理就是按某种 镱略由已知判断推出另一判断的思维过程。一般来说，推理包括两种判断，一种是已知的判 断，它包括已掌握的与求解问题有关的知识及关于问题的已知事实；另一种判断是由已知判 断推出的新的判断，既推理的结论。 它通过决定哪些规则满足事实或目标井授予规则优先级，然后执行最高优先级规则 来进行推理。在下一章中。将对推理机作详细的讨论。 2 4 知识表示 2 4 1 知识的定义 知识是人类在实践中所积累的认识和经验的总和。其中e s 的知识指与领域问题 求解相关的知识即“数据”和“符号” 3 。 2 4 2 知识的分类 ( 1 ) 按知识的作用，将计算机处理的知识分为三类 描述性知识：表示对象及概念的特征及其相互关系的知识：问题求解状况的知 识： 判断性知识：表示与领域有关的问题求解知识，如推理规则等： 过程性知识：表示问题的求解策略，即如何麻阁判断陛知识等进行推理的知识： ( 2 ) 按知识的作_ = j 层次分 对象级知识：直接描述有关领域对象的知识。 元级知识：描述对象级知识的知识，如关于领域知识的内容、特征、应用范围 的知识，如何运用这些知识的知识。 2 4 3 知识表示问题 ( 1 ) 知识表示的定义 将知识进行符号化，并用特定的数据结构( 逻辑与物理两方面) 进行描述与存 储的方法。 ( 2 ) 知识表示的要求 表示能力：能够将问题求解所需的知识正确有效的表达山来： 可理解性：所表达知识简单、明了、易于理解； 可访问性；能够有效地利用所表达的知识； 可扩充性：能够方便、灵活的对所表达的知识进行扩充； ( 3 ) 知识表示方法的分类( 按其表示的特征分) 叙述性表示：将知识与控制分开。把知识的使用方法，即控制部分留给计算机 程序。它的特点是：严密性强、易于模块化、具有推理的完备性；但推理效率较低。 过程性表示：将知识与控制结合起来( 利弊与上述方法相反) 。 两种表示方法各有利弊，对不同性质的问题应采j j 不同形式的表达方法。 ( 4 )常用的知识表示方法简介 1 产生式规则表示法 将知识表示成“i f t h e n ”的形式；表示方法自然、简洁； 2 框架表示法 将知识表示为层状结构，一个对象或概念的所有信息均属于该层次的结构中； 该层次结构还可以表示对象间的关系；该层次结构由一系列的“槽”和相关于“槽”的一系 列“侧面”组成； 3 语义网络表示法 采用结点和结点间的弧表示对象、概念及其相互关系。 2 4 4 知识的产生式规则表示法 1 概述 产生式最早由p p o s t 于1 9 4 3 年提出，用于构造p o s t 机计算模型；1 9 7 2a n e w e l l 和h a s i m o n 在研究人类的认识模型中提出了r u l e b a s e d 产生式方法及规则表示模式； r u l e b a s e d 的表示法是目前应用最为普遍的一种 2 7 。产生式通常用于具有因果关系的知 识。 2 产生式规则的逻辑结构 ( 1 ) 格式 i f ( 前提1 ) ( 前提2 ) t h e n ( 结论1 ) ( 结论2 ) 8 ( 2 ) 产生式规则的基本单元 前提：符号化的事实型知识，不同前提形式构成不同产生式规则类型。 常量型前提( t i g e rh a sl e g ) ； 变掇测前提( l i e a t s $ v a r ) ； 缔柬型前提( s v a r = 2 8 ) ： 表达式计算型( s v a r = 2 x + s y 一【6 ) ； 结论：符号化事实型知识； 例如规则t ：i f该动物有羽毛t h e n该动物是鸣 规则2 ：i f该动物是鸣a n d 有k 脖子a n d有k 腿 a n d不会e t h e n 该动物是鸵鸟 3 产生式规则的物理结构 产生式规则为变化数据结构，采用“链接袭”实现。 4 产生式规则的组织 规则的组织是构造规则库的核心l ( 1 ) 规则库的实质 一种隐含的“与或图”，该“与或图”以“事实性知识”为节点，：_ i 芎点间的连接关系 由规则确定，为“与”关系，规则间的关系为“或”关系。 ( 2 )原则上规则库的规则可以顺序存放，但存在r 列矛盾 规则的一致性问题虑解决： 如何控制冲突； 提高规则的匹配效率； ( 3 ) 推荐的组织形式 1 以规树的形式组织，最高点为推理目标规则，依次按层次组织： 2 以类层次形式的“与或图”组织规则； 5 产生式规则的特点 ( 1 ) 性知识。 ( 2 ) ( 3 ) ( 4 ) ( 5 ) 产生式规则表现的是“表层”知识，即人类在特定的领域关于“做什么”的过程 产生式规则与推理机分离，且规则间的联系与上下文的数据结构相关。 产生式规则的匹配效率随着知识库增加而迅速降低； 产生式规则的解释能力较差 1 6 。 产生式规则主要表示对象操作过程或对数据对象进行求解的过程的“动态知识”。 9 2 5 柑橘专家系统的系统结构 2 5 1 系统概述 本系统采用b s 结构，前台运用j s p ，s e r v l e t ，e j b 等j 2 e e 技术实现，后台使用 t o m c a t 作w e b 容器，j b o s s 做组件容器，数据库选用m y s q l 。这样做的可以跨平台使用， 可以在w i n d o w s 和l i n u x 平台上实现，而不用做任何修改。而且使_ i j 的都是开放源代码的服 务器，也为今后的实际投入使用节约一火笔开支【13 】。 髂个架构，采用m v c 模式。把系统的用户视图，控制，模烈分成独立的模块 来处理，对于现在的简单的开发，会带来一些额外的开销。 不过对下人型的应用 采 用这种架构能很容易的添加新的功能，而不会影响其他模块。结构图如f ： s e r v l e t j s p 容器 模型 a c t i o n s e 删越p a c t i o n f o r m j a v ab p a n e j b w e b ，t 泛孓 八，action 、 w 曲 客户 s e r v e r ij s p 视图 w e b 客户通过h t t p 协议发送一个r e q u e s t ，由a c t i o n s e r v l e t 对象获取r e q u e s t 里的参数t 然后再生一个a c t i o n f o r m 对象验证， 又由a c t i o n s e r v l e t 根据配置信息决定将请求转发给 a c t i o n ，并且建立一个a c t i o n m a p p i n g 对象存放这个a c t i o n 的配置信息。完成之后调用 a c t i o n 的e x e c u t e 方法返回一个a c t i o n f o r w a r d 对象，a c t i o n s e r v e r l e t 再把客户请求转发给 a c t i o n f o r w a r d 对象指向的j s p 组件，最后由这个j s p 网页生成动态网页返回给客户 8 】。 0 具体流程例如4 f 根据柑橘专家系统的特点，可以将其模块化，如f 图所示 各具体子模块具体说明： 植前决簧 植前决策帮助用户决定本地是否适合种植柑橘。涉及到组建知识库的数据有十壤、气候 地理条件。相关子知识库中具有的事实有十壤的情况，气候娃怎么样的，地理条件的情况 由用户界面给用户提出选项用户作出选择。然后形成目标，与知识库中的规则、事实匹配 得出相应的结论( 是o r 否) 。 数据流图； 病虫害决策 病虫害决策帮助用户在柑橘栽培中所遇到的痈虫吉问题进行诊断。其中j 己分为病害和虫 害。涉及组建痛害子知识库的数据有痛变发生部位、病斑颜色、病斑形状。( 具体知识库设 计详见“知识库构建”) 。用户给出得病特征，我们系统给出的同答是得了什么病，采_ i j 什么 诊断措施。 数据流圈： 知识的表示 在知识库中，主要采_ j 事实和规则来表现知识，在p r o l o g 中事实的形式是 p r o d ( a r g l ，a r 9 2 ) , p r e d 是事实的名称a r g 是参数。规则的形式是h e a d ：- b o d y 其中： 符 号读作如果。 为了减少推理时间，我们的整个系统的知识库根据具体模块，建立相应的于知识库，也 就是说我们知识库是由多个子知识库蛆台而成的。 在这段时间，我们利用模拟数据，针对病虫害决策建立了相应的子知识库。 用户可咀通过我们的知识库更新模块连接我们的弼络部分随时更新知识库保持决策 的权威| 生。 3 1 推理机 第三章r e t e 模式匹配算法及其优化 3 1 1 推理机的基本思想 推理机是专家系统的“思维”机构是构成专家系统的核心部分。其任务是模拟领域专 家的思维过程，控制并执行对问题的求解。它能根据当前已知的事实，利用知识库中的知识， 按一定的推理方法和控制策略进行推理，求得问题的答案或证明某个假设的正确性。 推理机的性能与构造一般与知识的表示方式及组织方式有关，但与知识的内容无关，这有利 于保证推理机与知识库的相对独立性，当知识库中的知识有变化时，无须修改推理机 4 。 但是，如果推理机的搜索策略完全与领域问题无关，那么它将是低效的，当问题规模较大时， 这个问题就更加突出。为了解决这个问题，目前专家系统一方面为了提高系统的运行效率而 使用了一些与领域有关的启发性知识，另一方面又为了保证推理机与知识库的相对独立性而 采取了用元知识来表示启发性知识的方法。 推理机实际上是要把知识( i f t h e n 规则) 链接起来，形成一条或多条推理链如果 链接是从一组条件( 数据) 开始，按照一定策略运用知识推出结论，则称之为正向推理或 正向链( f o r e w a r dc h a i n ) ：如果结论( 即要达到的目标) 是已知的。链接由此出发找出支 持这个结论的证据。则称之为反向推理或反向链( b a c k w a r dc h a i n ) 7 。 完成一项任务时，领域的知识将指导求解问题采取的步骤，即知识将对推理产生一种 驱动的作用如果知识非常抽象，成为某领域中“事情如何动作( h o wt h i n gw o r k ) ”的符 号模型，那么从模型的抽象到更细节( 较少抽象) 描述的推理称为模型驱动推理( m o d e l d r i v e nr e a s o n i n g ) 当从较抽象的符号描述到较少抽象的描述时，人们总是产生一种期 望，这种求解问题的行为称为期望驱动( e x p e c td r i v e nr e a s o n i n g ) 。以上这两种驱动的推 理属于反向推理的范畴。反向推理常常也被称为目标驱动推理( g o a ld r i v e nr e a s o n i n g ) 在问题求解过程中，人们经常从某个细节某个具体问题的数据开始工作。逐渐上升到较高 级的抽象( 即沿着“它们意味着什么”的方向) ，沿着这个方向的推理称为数据驱动推理 ( d a t ad r i v e nr e a s o n i n g ) 。如果根据某些新数据，或根据求解问题所刚刚采取的最后一步 来选择下一步的工作，那么就必须响应各种事件，这种推理称为事什驱动推理( e v e n t d r i v e nr e a s o n i n g ) 这两种推理属于正向推理范畴 5 3 1 2 推理机的分类 从逻辑基础上的分类 1 演绎推理 演绎推理( d e d u c t i o n ) 是指由一组前提必然地推导出某个结论的过程，其核心就是三段 论法。三段论法是由两个前提( 大前提、小前提) 和一个结论组成的，它包括直言三段论法、 假言三段论法、选言三段论法和二难推理等类型。在目前的推理系统中主要使用的是假言 三段论法、也称为假言推理。如果使用i f - - t h e n 表达方式，假言三段论可表示为肯定式和 否定式两大基本形式。 2 归纳推理 归纳推理( i n d u c t i o n ) 是指以某命题为前提，推论出与其有归纳关系的其它命题的过程。 一般包括由特殊剑一般的归纳，由特殊到特殊的归纳和统计三段论法。 3 外展推理 外展推理( a b d u c t i o n ) 可以表示由因到果的解释论证过程，更能反映事物的本质。用于医 疗诊断系统，推理过程更接近于医生的实际思想方法。因为医生不需要考虑所有疾病的可能 性只要选择一组病冈验证其症状，通过外展推理即可得出合理的诊断 1 2 。对于田果关系明 确的事物如l _ l 程设备的设计与故障诊断等，采用外展推理更为有效。 4 非单调推理 非单调推理( n o n m o n o t o n i cr e a s o n i n g ) 是指在推理过烈中，在增加某些新的事实时，能 够取消以前得出的一些结论。在人类的思维活动中，这种情况是非常多的。例如m i n s k y 提 出的一个例子：当我们知道x 是只鸟时，我们一般就认为x 能飞。但以后又知道x 是企鹅， 而企鹅是不会飞的，我们随即取消了x 能飞的结论，而认为x 是不会飞的 5 不精确推理 不精确推理也称为近似推理( a p p r o x i m a t er e a s o n i n g ) ，是指在事实或知识存在不确定性 时的推理。不精确推理与非单调推理相比，前者处理的是信息的不确定性，后者处理的是信 息的不完全性。 2 4 3 从推理方法上的分类 1 基于规则的推理 基于规则的推理( r u l e - - b a s e dr e a s o n i n g ) 是指以产生式规则表示知识的推理。由丁产 生式规则其有简单、灵活和易于理解的特点因此广泛用于表达启发性知识 2 6 。 知识除了可以表示成规则形式以外，还可以谓词逻辑、框架、语义网络等形式表示。因 此还有相应形式的推理，这些推理的核心都是演绎推理，而且理论上都是等价的。很多系统 使用框架或语义网络表示概念或事实，使用规则表示启发性知识。这样就充分利用了各种袭 示方法的特长。这种系统仍然可归入基于规则的系统的范畴。 2 基于模型的推理 与基于规则的推理不同，基于模型的推理( m o d e l - - b a s e dr e a s o n i n g ) 强调采州反映事物 内部规律的客观世界模型。有代表性的是定性物理模型和因果模型。 定性物理模型是d e k l e e r 等人( 1 9 8 4 ) 提出来的 该模型用定性方法描述技术系统的功能 与行为。它可以直接表示输入条件( 前提或原因) 到输出结果( 现象或结论) 的推理过程称之 为定性推理( q u a l i t a t i v er e a s o n i n g ) 。它把知识与推理结合成为一体，不得建立与修改独 立的知识库缩小了主观思维与客观事物的差距，比较接近事物的本来面目 3 0 。 k o t o n 提出的j j j 果核型( 1 9 8 5 ) 是早期c a s n e t 专家系统所j i ； 的因果网络的深入发展，充 分显示了客观事物的内部因果关系。它人大提高了系统的透明度与可理解性，只需要设计 套“粒度”较细的描述性语言，即可设计深层专家系统，还可以自动进行外展推理。提高了 系统曲解释能力。 4 3 基于事例的推理 基于事例的推理( c a s e - - b a s e dr e a s o n i n g ) 就是将过去成功的事例存人事例库，遇到新 问题时，在事例库中寻找类似的过去事例，利用类比推理的方法，得到新问题的近似解答 再加以适当修改。使之完全适合于新问题。 基_ r 事例的推理的优点是不必对每个问题都从头进行求解而趋充分利_ l = j 类似问题的答 案进行求解，大大提高了问题求解的效率。另一个优点是自学能力。由下每得到一个新的结 果都可以存人事例库，从而扩充了知识无须经过基于规则的系统所必需的学习阶段。 3 2 产生式系统 产生式系统源予1 9 4 3 年由p o s t 提出的p o s t 系统。这个系统中定义了符号替换的规则， 其计算能力等价于t u r i n g 机。1 9 6 5 年n e w e l l 和s i m o n 将心理学的“刺激一反应”与产生 式联系起来用来建立认知模型，描述事物的因果关系。f e i g e n b a u m 与1 9 6 5 年一1 9 7 6 年研 究了d e n d r a l 专家系统，采用了产生式系统表示。d e n d r a l 本公认为第一个专家系统。产生 式系统也被称为基于规则的系统 【 。 2 5 1 产生式系统组成 产生式系统由3 个部分组成即总数据库( 或作存储器，w o r k i n gm e n m o r y ) 、产生 式规则库( 或产生式存储器，p r o d u c t i o nm e m o r y ) 和推理机( i n f e r e n c ee n g i n e ) 。 ( 1 )工作存储器 工作存储器用来存放在推理过程中产生的当前数据元素，称为工作存储器元素 ( w o r k i n gm e m o r ye l e m e n t ) ，其形式为： ( l ) 即每个工作存储器元素由一个类名和一组与之相关的( 属性。值) 对组成。 ( 2 ) 产生式存储器 产生式存储器用以存放一组产生式规则，产生式规则的一般形式为； ( p ) 产生式的左手部l h s 也就是条件部分，它由一个或多个元素组成。条什元素可以看成 是一个描述工作存储嚣元素的表达式，或者看成一个可以与工作存储器元素匹配的模式。l 瞄 中的条件可以是负的。当不存在匹配该条件元素的工作存储器元素是，称该负条件被满足。 产生式的右手部r h s 也就是动作部分。它由一组操作组成，这些操作包括对：i = 作存储器 元素进行增，删，改等操作，输入输出，以及停止操作等。 6 ( 3 ) 推理机 推理机控制齄个产生式系统的执行过程，它由匹配一冲突归集一执行( 点火) 这二个阶 段的循环组成 2 。 1 。匹配 考察所有产生式规则的右手部条件元素，根据当前】：作存储器的内容确定哪些规则被 满足。匹配阶段的结果是冲突集，冲突集中的元素称为例示。一个元素是一个序偶有产 生式名字以及满足该产生式l h s 的所有工作存储器元素组成的一个表构成a 2 冲突归结 当冲突集中有一条以上规则时，就需要决定首先使用哪一条规则，这称为冲突归结。 在冲突归结中所遵循的原则称为冲突归结策略( c o n f l i c tr e s o l u t i o ns t r a t e g y ) 。 3 执行 这一步执行被选中规则的右手部操作部分，经过操作以后，+ 丁= 作存储器的内容将被 修改。然后，其他的规则有可能被满足 3 3 。 产生式系统的执行就是匹配一冲突归结一执行三个阶段的推理循环过程，赢到冲突集为 空执行一条显示停止命令为止。 7 3 3 模式匹配算法 作为产生式系统推理三个阶段的第一个阶段，匹配效率问题财产生式系统效率问题 的重要问题。据统计，匹配阶段的时间开销要- b 到整个产生式系统运行时间的9 0 以上。因 此研究并提出快速的匹配算法是提高产生式系统效率的重要条件。 如果匹配过程只需一次，那么这个问题的解挟方法就很简单。推理机可以检测每条规则 并找出一套事实来决定规则的模式是否已满足。如果是，则将此规则执行。 然而，在基于规则的语言中，匹配过程不断重复进行。通常，事实列表在每次执行的时 候都会被修改。添加新的事实到事实列表中或删除旧的事实。这些改变可令先前不满足条件 的模式得到满足。匹配问题因此成了不断进行的过程。在每次循环中，随着事实的添加和删 除必须对已满足条件的规则集合进行更新和维护。 在每次循环后，令推理机检查每条规则以指导对事实的寻找，从而解决这个问题提供了 简单直接的技巧。这种方法最主要的缺点是速度太慢。人多数基于规则的专家系统都显示了 这种特征：时间冗余性。一般地说，条基于规则的运行仅会改变事实列表中的少数事实。 即：专家系统中的事实随着时间的改变很慢。在每次循环中，仅添加、删除很少一部分事实， 所以事实列表中的变化一般只影响很少部分的规则。冈此，令规则推动对所需事实的寻找， 需要大量不必要的计算 2 6 。这是因为，在当前的循环中，大多数规则所找到的事实很可能 与上一次循环所找到的相同。 如果可以记住哪些是匹配好的。然后只计算那些刚添加或删除的事实所引起的必要变 化，从而，可避免不必要的计算。规则是不变的，而事实是可以变化的，所以应是事实寻 找相应的规则，而不是反过来。如下图所示： 3 ，3 1r e t e 模式算法 r e t e 模式匹配算法正是利用了基于规则的专家系统所具有的时间冗余性。它的实现是 通过存储不断循环中的匹配过程的状态，并且，只从新计算在事实列表中发生了变化、又反 映到本次状态中的变化。也就是说，如果在一次执行周期中，一绵模式找到了二个所需事实 中的两个那么，在f 一个周期中就无需对已经找到的这两个事实进行检商只有第三 个事实是需要关注的。仅当添加或删除事实。匹配过程的状态才被更新。如果添加、删除事 实的数量与事实和模式的总数相比很小，那么匹配过程会进行得很快。 通过规则中的相似性，r e t e 算法同样也会提高基于规则的系统效率。结构相似性是指 许多规则通常包含了相似的模式或模式群。利用这一特性，p e t e 算法通过将公共部分放在 一起来提高效率因为公共部分不用多次计算。 r e t e 算法是较为经典的快速匹配算法，在该算法提山以后所出现的各种匹配算法多数 是基于对r e t e 算法的某些方面进行改进。这些算法往往是为了获得某些性能的而牺牲其他 一些性能。因此对于具有某些方面特点的产生式程序来说，这些匹配算法的效率可能会超过 r e t e 算法，但对于尽可能多种类的产生式程序来说，这些算法的通用性往往不如r e t e 2 4 。 产生式规则的左手部由一个模式序列构成，每一个模式( 也称条件元索) 都是工作存储 器元素的部分描述。当一个模式p 描述了一个元素e ，则称p 匹配e 。在某些产生式规则中t 有的模式前面有一个负号 ” ，称一个产生式的左手部被满足，如果： ( 1 ) 每一个非负模式都匹配一个u l 作存储器元素； ( 2 ) 没有负模式匹配任何一个： 作存储器元素 卜t 面举一个模式的例子： ( e x p r e s s i o nn a m ee x p r 9a r g l la r 9 2 ) 放在尖括号的符号串是变量如v a l ，如果模式的某个属性是常量，则它所匹配的工作 存储嚣元素的相应属性必须为相同的值。如上个模式所匹配的1 作存储器元素的n a m e 必 1 9 须取值e x p r 9 。模式中的变馘可以j ji 作存储器中的任何值匹配，但如果一个变姑在产生式 的左手部不止出现一次，则所有的山现必须匹配相同的值 2 5 。 因此模式 ( e x p r e s s i o na r g l la r 9 2 ) 将匹配以下两个元素 ( e x p r e s s i o n n a m ee x p r 9 la r g le x p r 2 3 lo p la r ge x p r 2 3 ) ( e x p r e s s i o nn a m ee x p r 5a r g l0a r 9 20 ) 但不匹配以下元素： ( e x p r e s s i o n n a m ee x p r 8a r g l0h r 9 2e x p r 2 9 ) 下面给出一个产生式规则的例子： ( pt i m e o x ( g o a l t y p es i m p lj p yo b j e c t ) ( e x p r e s s i o nn a m e a r g0 o p * ) ) 、 ( m o d i f y2o pn