（计算机软件与理论专业论文）mpi环境下的pclips的设计与实现.pdf

摘要 摘要 c l i p s 是一种重要的专家系统开发工具，广泛应用于专家系统的各个 研究领域。目前，以c l i p s 为原型的各种版本的专家系统开发工具层出不 穷，但是现有的开发工具都不具有直接支持并行处理的功能，给并行机上 构建专家系统带来很多不便。本文以对c l i p s 进行改进为目的，在对c l i p s 工作原理深入分析和研究的基础上，设计并初步实现了一个并行c l i p s 实 验模型p c u p s 。 本文首先分析了c l i p s 的工作原理和推理匹配技术。对推理中的不确 定性问题进行了研究，将p r o s p e c t o r 中修正推理不确定性的方法引入到 p c l i p s 中。针对推理和匹配过程中的时间冗余性问题进行分析，在对r e t e 算法进行研究的基础上，提出了r e t e 算法的改进方案。同时，对p c l i p s 的 推理和匹配效率问题进行了研究。 其次，分析了当前通用的两种并行编程模型，将m p i 的消息传递功能 引入至i j p c l i p s 中。设计了模式网络结构，实现了正向推理算法。在对c l i p s 核心函数和处理机制进行研究的基础上，设计了p c l i p s 的并行处理算法， 实现了基本的并行处理功能。 最后，针对p c l i p s 设计了两组实验，根据实验结果对p c l i p s 的性能 进行了分析，指出了p c l i p s 的优点和不足。 关键词专家系统工具；c l i p s ；并行；m p i ；推理 燕山大学工学硕士学位论文 a b s t r a c t c l i p si sr ni m p o r t a n td e v e l o p m e n tt o o lf o re x p e r ts y s t e m sa n di sw i d e l y u s e di na l lk i n d so fe x p e r ts y s t e m sr e s e a r c hf i e l d s r e c e n t l y , v a r i o u sv e r s i o n s o fd e v e l o p m e n tt o o l sf o re x p e r ts y s t e m sh a v eb e e nd e v e l o p e d h o w e v e r , n o n e o ft h e ms u p p o r t sp a r a l l e lc o m p u t i n gd i r e c t l y ，w h i c hc a u s e si n c o n v e n i e n c ef o r d e s i g n i n ge x p e r ts y a e m s o n p a r a l l e lp r o c e s s i n gm a c h i n e a i m i n g i m p r o v e m e n to fc l i p st h i sp a p e rg i v e st h ed e s i g na n di n i t i a li m p l e m e n to fa t e s t i n gm o d e lo fp a r a l l e lc l i p sw h i c hi sc a l l e dp c l i p sb a s e do na n a l y z i n g a n dr e s e a r c h m gt h ep r i n c i p l eo f c l i p s i nt h i sp a p e r , f i r s t l y ，t h ew o r k i n gp r i n c i p m s ，i n f e r e n c et e c h n o l o g ya n d m a t c h i n gm e c h a n i s mw e r ea n a l y z e d a n da r e rs t u d y i n gt h eu n c e r t a i np r o b l e m o fi n f e r e n c et h em e t h o dw h i c hc a nr e v i s et h e u n c e r t a i n t yp r o p o s e di n p r o s p e c t o ri si n t r o d u c e di n t op c l i p s b a s e do nt h er e t ea r i t h m e t i c ，a m o d i f i e dp e t ea r i t h m e t i ci sp r o p o s e dt or e s o l v et h et i m er e d u n d a n c yi nt h e p r o c e d u r eo fi n f e r e n c ea n dm a t c h i n g m e a n w h i l e ，t h ei n f e r e n c ea n dm a t c h i n g e f f i c i e n c yo f p c l i p si sa l s os t u d i e d s e c o n d l y , t w oc o m m o np a r a l l e lp r o g r a m m i n gm o d e l sa r ea n a l y z e da n dt h e m e s s a g ep a s s i n gm e c h a n i s mi nm p ii si n t r o d u c e di n t op c l i p s t h ep a t t e r n n e t w o r kc o n s t r u c ti sd e s i g n e da n dt h ef o r w a r di n f e r e n c ea r i t h m e t i ci sr e a l i z e d b a s e do i la n a l y s i so ft h ek e r n e lf u n c t i o n sa n dp r o c e s s i n gm e c h a n i s m , t h e p a r a l l e lp r o c e s sa r i t h m e t i co fp c l i p si sd e s i g n e da n dt h eb a s i cf u n c t i o no f p a r a l l e lp r o c e s s i n gi sr e a l i z e d f i n a l l y , t w oe x p e r i m e n t sa r ed e s i g n e da n dt h ep e r f o r m a n c eo fp c l i p si s a n a l y z e da c c o r d i n gt ot h ee x p e r i m e n tr e s u l t t oc o n c l u d e ，t h ea d v a n t a g e sa n d d i s a d v a n t a g e so f p c l i p sa r ep r e s e n t e d k e y w o r d se x p e r ts y s t e m st o o l ；c l i p s ；p a r a l l e l ；m p i ；i n f e r e n c e 燕山大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文m 口i 环境下的p c l i p s 的设计与实现，是本人在导师指导下，在燕山大学攻读硕士学位期间独立 进行研究工作所取得的成果。据本人所知，论文中除己注明部分外不包含 他人已发表或撰写过的研究成果。对本文的研究工作做出重要贡献的个人 和集体，均已在文中以明确方式注明。本声明的法律结果将完全由本人承 担。 作者签字毒手凤桐日期：硎戽尹月名目 燕山大学硕士学位论文使用授权书 m p i 环境下的p c l i p s 的设计与实现系本人在燕山大学攻读硕士 学位期间在导师指导下完成的硕士学位论文。本论文的研究成果归燕山大 学所有，本人如需发表将署名燕山大学为第一完成单位及相关人员。本人 完全了解燕山大学关于保存、使用学位论文的规定，同意学校保留并向有 关部门送交论文的复印件和电子版本，允许论文被查阅和借阅。本人授权 燕山大学，可以采用影印、缩印或其他复制手段保存论文，可以公布论文 的全部或部分内容。 保密口，在年解密后适用本授权书。 本学位论文属于 不保密留。 ( 请在以上相应方框内打“4 ”) 作者签名：缸凰桐 日期：聊年争月彩日 导师签名：聋耗-日期：2 ，“年4 月z f 目 第1 章绪论 1 1 研究背景 第1 章绪论 专家系统( e x p e r ts y s t e m ) 1 是一种最具代表性的智能应用系统，旨在研 究如何设计基于知识的计算机程序系统来模拟人类专家求解专门问题的能 力。专家系统可以处理多种领域的问题，是人工智能中最活跃的一个分支， 是人工智能发展的最主要推动力。 经过几十年的发展，专家系统及其开发工具的研究已经取得了丰硕的 成果。国外的研究人员现在一方面深入研究专家系统基本理论和技术，另 方面致力于专家系统的实用化和研究专家系统的建构方法。近年来，在 专家系统理论、知识获取 2 1 、推理技术1 3 l 、用户界面、应用平台等方面的 研究都产生了新成果。此外，我国专家系统的研究也取得了很大的进展， 国内的研究人员提出了专家系统开发环境优化、中文字符嵌入、多平台支 持、多种知识表示，以及知识自动获取等方面的新概念、新理论。但在专 家系统开发工具的研究方面，还有许多工作要做。 专家系统一般由知识库、事实库、推理机、解释机及知识获取等五个 部分组成。其中知识的获取和推理是一个操作瓶颈。为解决这一操作瓶颈， 人们提出了不少高效率的算法和实现方法，如采用索引结构、知识划分等。 但由于传统方法仍然是以串行操作为基础的，所以难以在解决这一瓶颈问 题方面有突破性的进展。 随着科技的飞速发展，并行计算已成为解决研究科学与工程技术问题 的一种崭新的手段和方式。提高计算机系统处理速度的一个重要措施是增 加处理的并行性。并行处理是指在同一时刻或在同一时间间隔内完成两种 或两种以上性质相同或不相同的工作。采用并行处理可以加快速度，即在 更短的时间内解决更多更复杂的问题，特别是对一些近年来新出现的挑战 性问题。采用并行处理还可以节省投入，并行处理可以以较低的投入完成 燕山大学工学硕士学位论文 大量串行处理的任务。并行处理和并行计算 4 1 已经在科学研究、工程技术 以及军事领域得到了大量的应用，并取得了巨大的成就。 c l i p s ( cl a n g u a g ei n t e g r a t e dp r o d u c t i o ns y s t e m ) 5 ，6 j 是美国航空航天局 n a s a 约翰逊太空中心开发的一种专家系统开发工具，意在克服l i s p 移植 性差、开发工具和硬件成本高、嵌入性低的缺点。c l i p s 是一种多范例编 程语言，它支持基于规则的、面向对象的和面向过程的编程。c l i p s 是一 个基于r e t e 算法【7 】的推理语言，用标准c 语言编写，目前最新的版本为6 2 3 。 现在国内外有数干人在研究c l i p s ，用c l i p s 开发出的专家系统也已经应用 到各大领域。由于具有源代码开放、兼容性良好等特点，研究人员根据各 自的需要对c l i p s 进行了各种改造和扩充。 鉴于并行处理的优点和c l i p s 开放源代码的特点，把c l i p s 改造成 p c l i p s m j ，即并行c l i p s ( p a r a l l e lc l i p s ) ，实现专家系统任务的并行处理， 可以缩减系统的推理时间，大大提高专家系统的工作效率。应用p c l i p s 构 建并行专家系统，也可以显著提高系统的性能，增加系统的实用性。 1 2 研究现状与发展趋势 课题的研究现状与发展趋势包括了对专家系统及其开发工具c l i p s 的 研究现状和发展趋势的分析，以及对并行计算技术和m p i 的研究现状和发 展趋势的分析。 1 2 1 专家系统与c l i p s 上世纪六十年代中期，世界上第一个专家系统d 】n d & a l 问世。七十 年代以来，各国都在研制开发实用的专家系统，m y c i n ( 医疗诊断专家系 统) 、p r o s p e c t o r ( 矿产探测专家系统) 、x c o n r 1 ( d e c 计算机配置专家 系统) 等专家系统相继开发成功并取得了良好的应用效果。目前专家系统广 泛应用于农业、医疗、地质、气象、勘探、军事、教育等领域，取得了重 大的社会和经济效益。近年来，我国在专家系统的研究与应用方面也取得 了很大进展，但由于起步较晚、发展不平衡等因素，我国专家系统的研究 2 第1 章绪论 水平和其它发达国家相比还有一定的差距。国内的专家系统研究主要集中 在实际应用方面，而在理论研究方面进展不大。 专家系统的语言工具主要有以下几种。 ( 1 ) 程序设计语言包括通用程序设计语言和人工智能语言两种。通用 程序设计语言包括c 、p a s c a l 等高级语言和c + + 等面向对象语言。人工智 能语言包括p r o l o g 、l i s p 等。 ( 2 ) 专家系统外壳它是由一些成熟的具体专家系统通过抽取其中的 专家知识，而保留体系结构和功能来实现的。利用专家系统外壳【9 】可以快 速构建一个专家系统。但它的主要缺点在于灵活性和通用性比较差，其应 用只局限于某些特定的领域。 ( 3 ) 专家系统专用开发工具它介于前两者之间，为知识的表示提供了 固定的模式，使专家系统的构造变得更加方便。专家系统专用开发工具不 局限于特定的领域，与专家系统外壳相比具有更大的通用性和灵活性，其 代表有o p s 、f r l 、c l i p s 等。 c l i p s 由八十年代中期的最初版本逐步发展到现在的c l i p s 6 2 3 ，在 c l i p s 6 0 以后的版本中增加了对面向对象表示法的支持。c l i p s 的基本结 构属于产生式系统，它与面向对象的方法优势互补，从而提高了c l i p s 的 应用能力。现在各种适于v c + + 、v b 、d e l p h i 等语言工具调用的c l i p s d l l 已经开发出来，并在实际项目中得到了良好的应用，这使得在开发专家系 统中调用其他工具等变得方便快捷。同时，支持n e t 平台和j 2 e e 平台的 c l i p s 组件也已经出现并投入使用了。现在，w e b c l i p s 的实现与完善， 使开发人员构建b s 模式的专家系统更加方便自如，客户在远程浏览器端 即可使用和操控专家系统。多种c l i p s 形式的出现，丰富了专家系统的开 发形式，满足了用户不断增加的需求。 1 2 2 并行计算技术与m p i 随着超级计算机的迅速发展，计算领域最高端的高性能计算将成为i t 领域人们争夺的制高点。人们已经逐渐认识到了高性能计算的意义，但是 高性能计算的发展一直面临着挑战，其巨大的计算潜力与性能始终没有被 燕山大学工学硕士学位论文 充分利用起来。 并行计算技术自6 0 年代中期出现以来得到了快速的发展，其并行处理 方式经历了从阵列机( s i m d ) 、向量机及向量并行机( v p p ) 、共享存储的对 称多处理器系统( s m p ) 、分布存储的大规模并行处理系统( m p p ) 到非一致访 问的分布共享存储( n u m a ) 并行机系统和计算机机群系统( c l u s t e r s ) 的演 变过程。 在研制上述并行计算机系统的过程中，人们逐渐认识到系统的规模可 伸缩。陛( s c a l a b i l i t y ) 和可编程性( p r o g r a m m a b i l i t y ) 己成为并行计算技术领域 进一步发展的关键问题。规模可伸缩并行计算机系统能以最低可能成本向 用户提供最高可能性能，因此得到了广泛的重视和快速的发展。通过高速 网络将计算机或工作站连接起来，组成计算机机群( 工作站机群n o w c o w 等) ，就能够提供更加经济有效的高性能计算能力，事实上这已经成为当前 并行计算技术发展的主流。 并行计算领域的基本发展状况是：并行软件的发展远远落后于并行计 算体系结构的发展；并行计算应用远远落后于并行计算技术理论的发展。 由于可移植异构编程环境p v m 口a r a l l e lv i r t u a lm a c r i n e ) e 1 1 1 日益流行和 标准的消息传递接u m p i ( m e s s a g ep a s s i n gi n t e r f a c e ) i ”，1 3 1 并行编程环境的 日益普及，加上经济有效的特点，由高速网络联成的各种类型的规模可伸 缩计算机机群，必将进一步促进并行计算应用领域的发展。 消息传递接v i m p i 是一个基于消息传递的标准并行函数库，提供在并 行机系统及网络并行计算机上编写并行程序的环境。m p i 给出了并行库的 规格说明，提供一套完整的消息传递函数库例程。m p i 标准化涉及到大约 6 0 个国家的研究人员，他们主要来自于美国和欧洲的4 0 个组织，包括并行 计算机的主要生产商，还有来自大学、政府实验室和工厂的研究者们。1 9 9 2 年4 月，并行计算研究中心在w i l l i a m s b u r g 召开了一个关于消息传递标准的 工作会议，会议上讨论了标准消息传递的必要特点，并建立了工作组继续 进行标准化工作。1 9 9 2 年l o 月，m p i 的初步草稿m p l l 形成，m p l l 主要包含 的是在w i l l i a m s b u r g i 作组会议上讨论的基本消息传递的接口，因为它的基 本目的就是促进标准的讨论并继续此项工作，所以它的目标主要集中在点 第l 苹绪论 对点通信上。1 9 9 7 年，在对原来的m p i 作了重大扩充的基础上，又推出了 m p i 的扩充部分m p l 2 。m p l 2 的扩充主要体现在以下三方面：并行i o ，远 程存储访问和动态进程管理。 m p i 的实现包括m p i c h “】、l a m 、i b mm p l 等多个版本，其中m p i c h 是一个最重要的m p i 实现，它与m p l l 规范同步发展，目前的最新版本是 m p i c h l 2 7 。m p i c h 含三层结构，最上层是m p i 的a p i ，基本是点到点通信 和在点到点通信基础上构造的集群通信；中间层是抽象设备接口层，其中 抽象设备可以简单地理解为某一种底层通信库，该层就是对各种不同的底 层通信库接口的统一标准；底层是具体的底层通信库。 由于标准的提高和用户需求的不断增加，m p i 在动态进程管理和远程 存储访问等方面不断得到改进，其结构和功能也不断完善和提高。 1 3 研究的主要内容 随着科学技术的发展，专家系统的需求也日新月异，各种大数据量、 大计算量的专家系统不断产生，随之而来的是不断提高的推理和计算速度 的需求，这就需要高性能并行计算机来解决。当前存在的专家系统开发工 具不支持并行操作命令，这使得在并行计算机上构建和运行专家系统十分 困难，而重新开发一套专用于并行计算机的专家系统工具需要大量时间和 复杂的工作。所以，对现有的专家系统工具c l i p s 进行改造是一个较为理 想的解决办法。实现这一方法，需要考虑以下几个问题。 首先，专家系统和c l i p s 的基本工作原理和推理机制。在对c l i p s 的基 本结构进行分析的基础上，考虑是对推理功能进行改造，还是在现有基础 上进行扩充。 其次，推理和匹配算法的设计与实现。如何针对p c l i p s 的特点，对 c l i p s 原有的推理机制和功能进行改造和扩充，如何对当前推理和匹配算 法进行改进和实现。 再次，p c l i p s 的设计与实现。如何利用c l i p s 的自定义函数对c l i p s 进行改造，如何结合m p i 的进程间通信函数来设计p c l i p s 的并行处理算 5 燕山大学工学硕士学位论文 法，即如何实现p c l i p s 的并行处理功能。 最后，系统实现和实验。在有限的硬件条件下，如何进行实验平台的 搭建，如何设计和选用实验用例。如何进行实验和测试，得出实验结果。 1 4 本文的结构 本文探讨了把m p i 并行计算技术与c l i p s 相结合，将专家系统工具 c l i p s 扩充为可执行并行命令【1 5 】的p c l i p s 等问题。其中包括结构分析、算 法的改进与设计、系统结构设计以及系统的实现。在对上述问题进行深入 研究的基础上，设计并初步实现了一个可以处理并行命令的专家系统实验 模型p c l i p s 。本文内容安排如下。 第l 章绪论，介绍了本文的研究背景，课题相关领域的研究现状与发展 趋势，以及研究的主要内容。 第2 章p c u p s 的理论基础，介绍了专家系统和c l i p s 的基本理论，探讨 了c l i p s 中的事实与规则机构和模式匹配机制【l “。同时，介绍了m p i 的消 息传递机制【1 7 ，1 8 1 和消息传递基本过程。 第3 章p c l i p s 推理技术和效率的研究，着重对专家系统的推理技术和 匹配效率进行分析和研究。首先分析了几种常用的推理方法，并对推理流 程和推理控制技术进行了研究。然后提出了推理链【1 9 】中的不确定性【2 0 】问题 的修正方法，并对r e t e 算法进行了改进，对匹配效率问题进行了研究。 第4 章p c l i p s 的结构设计与算法实现，介绍了并行计算模型的分析选 用，模式网络【2 1 1 结构设计和模式匹配【2 2 1 算法的实现。其中的算法实现部分 包括模式网络算法和连接算法，以及正向推理【2 孔算法。接着给出了p c l i p s 并行处理算法的设计实现过程，并对并行处理函数的实现和编译运行实现 进行了阐述。 第5 章实验结果与性能分析，介绍了系统实验的软硬件平台配置和实验 结果，给出了两组具体的实验数据，并根据实验结果对p c l i p s 的性能进行 了分析。 6 第2 章理论基础 第2 章理论基础 专家系统是人工智能领域的一个分支，是当前研究的热点，c l i p s 是 一种常用的专家系统开发工具。本章将对专家系统和c l i p s 系统的基本理 论进行介绍，同时对m p i 的消息传递机制进行分析，并对消息传递的基本 过程进行详细介绍。 2 1 专家系统理论 专家系统理论部分主要介绍专家系统的定义、结构和工作过程，以及 知识的表示和推理。 2 1 1 专家系统定义 专家系统是针对传统人工智能问题中智能程序设计提出的一个非常成 功的近似解决方案。专家系统早期先导之一，斯坦福大学的e d w a r df e i g e n b a u m 教授把专家系统定义为“一种智能的计算机程序，它运用知识和推理 解决只有专家才能解决的复杂问题”。也就是说，专家系统是一种模拟专家 决策能力的计算机系统，模拟一词表明专家系统做出的推理和解释要像领 域专家一样。 专家系统作为人工智能中最活跃、最重要的一个分支，具有很多独特 的特点，主要表现在以下几点。 ( 1 ) 具有专家水平的专门知识一般来说，专家系统中的知识可分为三 个层次，即数据级、知识级和控制级。对于一个面向具体领域的专家系统 而言，求解的问题往往只局限于一个较窄的范围，正因为如此才使它能抓 住领域内问题的共性与本质，使系统有较高的可信性与处理效率。 ( 2 ) 能进行有效的推理专家系统的根本任务是求解领域内的现实问 题。问题的求解过程是一个思维过程，即推理过程阱】。专家系统具有相应 ， 燕山大学工学硕士学位论文 的推理机制，能根据用户的已知事实，通过运用掌握的知识进行有效的推 理，以实现对问题的求解。 ( 3 1 具有获取知识的能力专家系统的基础是知识，获取知识是专家系 统的基本能力。 ( 4 ) 具有交互性专家系统一般是交互式系统。一方面它需要与领域专 家或知识工程师对话以获取知识，另一方面也需要通过与用户对话以索取 求解问题时所需的己知事实以及回答用户的提问。 ( 5 ) 有较强的实用性专家系统是根据领域问题的实际需求开发的，这 一特点就决定了它具有坚实的应用背景。另外，专家系统使用了大量高质 量专家知识，使得它处理问题的能力达到很高的水平，有时甚至超过了人 类专家，容易被人们所接受。 ( 6 ) 具有灵活性专家系统往往在其体系结构上采用知识库【25 j 与推理 机【2 6 】相分离的构造原则，彼此既有联系，又相互独立。这样就使得人们有 可能把一个成熟的专家系统变成为一个专家系统工具，方便用户使用。 ( 7 1 具有一定的复杂度和难度在建立一个专家系统时会遇到多种需 要解决的困难问题，这些都增加了专家系统的复杂度和难度。 正是由于这些特点，在很大程度上促进了专家系统的研究、推广和应 用，表2 1 列出了专家系统常用的一些领域。 表2 - 1 专家系统的应用领域 t a b 2 - 1a p p l i c a t i o nf i e l do f e x p e ns y s t e m s 种类应用的领域 配置以正确的方法配置系统的集成 诊断基于已观察到的迹象推断潜在的问题 教学智能教学使得学生可以问为什么、怎么样等问题，如同人类教学一样 解释解释观察到的数据 监测比较观察数据和预测数据以判断性能 规划规划行为以产生预期结果 预测预测给定情况的结果 补救对问题给定补救措施 控制管理一个过程，可能要求解释、诊断、设计、预测和补救 s 第2 章理论基础 专家系统的基本技术包括规目j j 2 7 , 2 5 、推理机、模式匹配和算法等，基 于规则的专家系统的一些基本技术如图2 1 所示。 基于规则的专家系统 规则推理机 事实 产生式规则高效模式匹配冲突处理r h s 的执行 里德算法 马尔柯夫算法 图2 - 1 专家系统的一些基本技术 f i g u r e2 - 1s o m eb a s i ct e c h n o l o g i e so f e x p e r ts y s t e m s 如今专家系统已成为人们研究的热点，并产生了巨大的经济效益与社 会效益，这是人工智能的其他研究领域所不能相比的。 2 1 2 专家系统结构和工作过程 专家系统由一些主要模块组成，各模块相对独立，各有其功能。其基 本结构由下面的几个部分组成。 ( 1 ) 知识库知识库是领域知识口9 1 与经验的存储器，通常包括领域事实 和启发式知识【3 0 】。领域事实是指广泛共有的知识，常指写在书本上的知识 及常识。启发式知识是一个领域中能保证正确的实现和正确的判断的知识， 是凭经验得到的知识。 计算机领域的专家w m h 有如下经典表述： 算法+ 数据结构= 程序 在专家系统中，知识是决定一个系统性能是否优越的主要因素。与 w i r t h 的表述相类似，在专家系统中有： 知识+ 推理= 专家系统 按照知识工程口1 1 理论，一个专家系统推理能力的高低取决于知识库的 9 燕山大学工学硕士学位论文 三个特性，即可用性、确实性和完善性。知识的确实性和完善性取决于领 域专家，而知识的可用性既与领域专家有关，也与知识工程师有关。 ( 2 1 事实库事实库用于存储问题求解的初始数据和推理过程中得到 的各种中间信息，也就是存入了用户回答的事实，或已知的事实和推理而 得的事实。总之，事实库存放的是该系统当前需要处理的对象的一些事实， 即存放当前状态。同时，专家系统中数据的存储格式也必须满足推理时所 使用的形式要求。 f 3 ) 推理机推理机是一组程序，用于控制和协调整个系统的工作。它 根据当前输入的数据，如设计参数的值，利用知识库中的知识，按一定的 推理策略去解决当前的问题。由于专家系统是模拟人类专家进行工作，设 计推理机时，我们采用使其推理过程与专家系统的推理过程类似的模式。 具体有四种：正向推理方式，逆向推理方式、双向推理和混合推理方式。 ( 4 ) 解释部分解释部分【3 2 3 3 j 也是一组程序，其任务是负责人机对话， 即对用户提问及回答用户的问题。对于系统来说，用户大致可以分为两类： 一是设计和维护系统的工程技术人员，二是系统的使用人员。一个专家系 统必须能够解释它所给的决策和建议，否则，即使它的决策或建议是正确 的，也很难为人们所接受。解释部分的主要功能是解释系统本身的推理结 果，回答用户提出的问题。 ( 5 ) 知识获取部分专家系统的知识获取部分，也称系统的学习功能， 它为系统的改善提供方便，主要的工作是系统维护，如知识库的一致性检 查、知识的扩充与修改等等。在专家与系统的交互过程中，认为哪些知识 不合理，甚至错了，或者需要加进新知识，都要利用这一部分。实际上， 一个专家系统是否具有知识渐增【3 4 l 的能力，将影响系统使用的生命力。 在专家系统的这五大组成部分中，知识库与推理机是它的核心。对于 一个简单的专家系统，仅有这两个组成部分就可以实现一些基本的智能功 能。但对于一个功能比较齐全，性能比较完善的专家系统而言，仅有知识 库和推理机这两大部分是远远不够的，它必须要由上述五个部分有机的结 合起来，才能实现全面的推理功能。 由专家系统的基本组成结构，可以描述出专家系统的功能结构。专家 1 0 第2 章理论基础 系统的功能结构如图2 2 所示。 f 人机接口界面( 将输入的数据转化为c l 口s 事实格式) ： 分类处理模块 t ，恐、襞鬈 。淼卜 ( 推出断言冲矣落磊器 图2 - 2 专家系统的功能结构 f i g u r e2 - 2f u n c t i o ns t r u c t u r eo f e x p e r ts y s t e m s 专家系统的基本工作过程是，用户通过人机界面回答系统的提问，推 理机将用户输入的信息与知识库中各个规则的条件进行匹配，并把被匹配 规则的结论存放到综合数据库中。最后，专家系统将得出最终结论和解释 器呈现给用户。专家系统的工作过程如图2 3 所示。 图2 - 3 专家系统的工作过程 f i g u r e2 - 3w o r k i n gp r o c e s so f e x p e r ts y s t e m s 2 1 3 知识的表示和推理 专家系统中知识库的建立是开发一个专家系统最重要、最艰难的工作 之一，专家系统性能的好坏就取决于专家知识。在专家系统领域内，知识 燕山大学工学硕士学位论文 是规律、规则、法则等的总称，是人们在学习与工作的实践过程中所获得 的对于客观、主观信息的内在联系的认识和经验的总和。 对于人工智能而言，知识作为一种可以被存储、传播的信息，只有存 储到计算机中去，才能建立一个模拟人类智能行为的系统，供求解现实问 题使用。因此首先就要研究知识的表示方法。知识的表示方法又称为知识 表示技术，其表示形式称为知识表示模式1 3 ”。知识表示实际是对知识的一 种描述，或者说是一组约定，一种计算机可以接受的用于描述知识的数据 结构。对知识进行表示的过程就是把知识编码成某种数据结构的过程。目 前用的较多的知识表示方法1 3 6 l 主要有：一阶谓词逻辑表示法，产生式表示 法，语义网络表示法，面向对象表示法等。具体表示方法如图2 4 所示。 一产生式表示法_ 一谓词逻辑表示法 _ 一 框架表示法_ | 命题逻辑表示法 一 语义网表示法_ _计算逻辑表示法 知识表示方法 一 逻辑表示法l 一一 概率逻辑表示法 一 特征表示法j 模糊逻辑表示法 一面向对象表示法一非单调逻辑表示法 图2 - 4 知识表不方法 f i g u r e2 - 4r e p r e s e n t a t i o no f k n o w l e d g e 推理是人们从己知的事物出发，通过运用已掌握的知识找出其中蕴含 的事实或归纳出新的事实，并对各种事物进行分析、综合最后做出决策的 过程。严格地说就是按某种策略由已知判断推出另一个判断的思维过程。 一般来说，推理都包括两种判断：一种是已知的判断，它包括已掌握的与 求解问题有关的知识及关于问题的已知事实：另一种是由已知判断推出的 新判断，即推理的结论。在人工智能系统中，推理是由程序实现的，这部 分称之为推理机。 人类的智能活动具有多种思维方式，人工智能作为对人类智能的模拟， 1 2 第2 章理论基础 相应产生多种推理方式，几种不同的分类方法如下。 n 1 按推理结论划分从推理的结论来看，有演绎推理口”、归纳推理、 默认推理。演绎推理是从全称判断推导出特称判断和单称判断的过程，从 一般性知识推出适合于某一具体情况的结论。它一般有大前提、小前提和 结论这三个部分。只要大前提和小前提正确，则结论必然正确。这种推理 方式是现在专家系统中用得最多的同时也是最重要的推理方式。归纳推理 是从足够多的实例中归纳出一般性结论的推理过程。而演绎推理恰好相反， 是从个别到一般的推理。默认推理是一种在知识不完全的情况下假设某些 条件已经具备所进行的推理，这与我们平时所说的反证法有些相似。 ( 2 ) 按知识的确定性划分按推理所用知识的确定性可以把推理划分 为确定性与不确定性两种推理。确定性推理由于所用的知识都是精确 的，推出的结论也是确定的，要么是真，要么就是假，没有第三种情况。 不确定性推理其所用推理知识不都是精确的，所以结论不能完全肯定，其 值或真或假，命题的外延性模糊不清。这里需要注意的是，由于人类的思 维活动经常是在知识不完全、不精确的情况下进行多方位的思考和推理， 要使计算机具有模拟人类智能的能力，就必须要使它具有不确定性推理的 能力，这也是近年来非经典逻辑【3 9 】迅速发展的根本原因。 ( 3 ) 按结论的单调性划分若从结论的单调增加与否来讨论，可以把推 理分为单调和非单调两种类型。对于单调推理而言，随着推理过程向前推 进和新知识的不断加入，推出的结论越来越接近终点目标，不会出现反复 情况来否定前面推出的结论。而非单调推理可能还要否定前面结论，使得 推理退回到以前的某一步，再重新开始新一轮的推理。 ( 4 ) 按推理的启发式划分从推理中是否运用与问题有关的启发式知 识来看，有启发式推理和非启发式推理。启发式推理能加快推理进程，优 先求解问题。 ( 5 ) 按方法论划分从方法论的角度划分，推理可分为基于知识的推 理、统计推理【4 0 】及直觉推理。基于知识的推理是从已掌握的事实出发，运 用专门知识进行推理。这是用得最广泛的一种推理方式。统计推理是根据 对数据的统计来进行推理。直觉推理是根据常识进行推理。 1 3 燕山大学工学硕士学位论文 2 2c l i p s 基本理论 c l i p s 的基本理论包括c l i p s 系统的基本组成，c l i p s 中的事实与规则 以及模式匹配机制和基本工作原理。 2 2 1c l i p s 系统的基本组成 c l i p s 是一种由标准c 语言开发的集成产生式系统，是一种通用的专家 系统开发工具。它包括工作存储器( w m ) 、产生式规则库、匹配器、冲突消 解器和解释器五部分。 c l i p s 的产生式规则( 简称规则) 由条件部分和条件满足时的执行动作 组成，条件部分由一系列待匹配的模式组成。工作存储器【4 1 】存放反映推理 中各问题状态的数据信息，又称事实列表，由多条事实组成。匹配器利用 工作存储器中当前事实状态去匹配所有规则的条件部分。基于事实列表和 知识库推理的推理机在一般采用所谓规则寻找事实的算法，即推理机检查 每一条规则并寻找一组事实来决定规则的条件部分是否满足，当某条规则 的所有条件均被匹配时，该规则被激活，并被加入到日程表 4 2 ，4 3 1 ，日程表 中的规则经冲突消解器t 4 4 1 选中后被解释器执行，执行的主要动作是在事实 列表中插入或删除事实，即对事实库中的部分事实进行更改。 c l i p s 系统的基本组成包括以下几个部分。 ( 1 ) 事实列表包含推理所需的事实数据，通常用自定义事实或模板来 构成一个事实库。 ( 2 ) 知识库包含所有推理所用的规则，通常用自定义规则或模板的形 式来形成多个规则。 ( 3 ) 推理机按定推理机制进行推理，并对运行进行总体控制。 事实列表中的事实是c l i p s 系统中数据的基本形式。每一条事实表示 当前事实列表【4 5 】中的一条信息。规则条件的满足依赖于事实列表中某些事 实的存在或不存在的状态。一条事实由一系列由空格隔开的域组成，事实 可以在推理执行之前在事实列表中插入或从事实表中删除，也可以在推理 执行中作为规则的动作部分，执行事实的插入或删除操作。 1 4 第2 章理论基础 2 2 2c l i p s 中的事实与规则 c l i p s 作为专家系统开发工具，包含了完整的编辑器和调试器，为开 发专家系统提供了比较完善的环境。在一个c l i p s 程序中，包含了规则、 事实和对象，以便推理机决定规则是否执行或什么时候执行。一个基于规 则的c l i p s 程序实际上就是一个数据驱动程序，所需的事实和对象就是其 中的数据，这些数据的执行通过推理机来激发。在c l i p s 中，事实是程序 用来推理的数据和信息，一般用关系名和槽 4 6 】来表示，如： ( p e r s o n ( n a m e ”g u of e n g t o n g ”) ( a g e2 8 ) ( g e n d e rm a l e ) ) 此事实的关系名就是字符段p e r s o n ，有三个槽：n a m e 、a g e 和g e n d e r ， 槽值分别为：g u of e n g t o n g 、2 8 和m a l e 。当然，对于那些包含共同信息的 几组事实，我们可以利用自定义模板结构【4 7 】来描述。它的一般格式是： ( d e t t e m p l a t e 】 ) 在自定义模板结构中有关系名的事实称为自定义模板事实，c l i p s 遇 到这种事实时会自动生成一个显式自定义模板。而对于那些有关系名但没 有自定义模板结构的事实称为有序事实1 4 8 1 ，c l i p s 遇到这种事实时会自动 生成一个隐式自定义模板。一般而言，我们应该尽可能多地使用自定义模 板事实，因为槽名使事实更具有可读性和更易于操作。 对于上例的同类事实，我们可以描述成下面的自定义模板： ( d e f t e m p l a t ep e r s o n ( s l o tn a m e ) ( s l o ta g e ) ( s l o tg e n d e r ) ) 定义了模板之后，我们只要通过使用a s s e r t 命令，就可以往其中添加若 干具有同种属性的事实，如： ( a s s e r t ( p e r s o n ( n a m e ”l il e i ”) 燕山大学工学硕士学位论文 ( a g e2 9 ) ( g e n d e rm a l e ) ) ( p e r s o n ( n a m e ”c u im i n ”) ( a g e 2 7 ) ( g e n d e rf e m a l e ) ) ) 专家系统要完成工作，除了要有事实之外，还必须给出赖以推理的规 则。在c l i p s 中规则可以直接键入，也可以从编辑器创建的规则文件中调 入。但对于一个专门领域的专家系统来说，调入已有的规则往往是不够的， 我们必须通过使用c l i p s 的集成编辑器来定义各种必需的规则。规则大多 用i f 。t h e n 形式表示。其一般格式为： ( d e f i - u l e = ；c l i p s 中的符号，表示“推导出” ) 对于上一例，若我们要作如下推导：“如果一个人姓名p q l il e i ，其性 别是男，那么他的年龄是2 9 ”，用c l i p s 表示是： ( d e f i a l l el l ( p e r s o n ( n a m e ”l il e i ”) ( g e n d e rm a l e ) ) = ；推出 ( h i s a g e i s2 9 ) ) 在这条规则中，我们给规则取了一个口t t l l 的名字，程序遇到这条规则 后马上激活【4 9 】并去搜寻适合的条件，然后做出判断，得到正确的结论。 2 2 3c l i p s 中的模式匹配 所谓模式就是规则里面的条件元素，每一个模式由一个或多个约束组 成，其目的是匹配自定义模板事实之中的字段。在上面所列举的规则中， 模式就是0 e r s o n ( ) ) ，它有两个约束条件，即：( n a m el il e i ) 和( g e n d e rm a l e ) 。 c l i p s 将规则的模式与事实列表中的事实相匹配，如果规则的所有模式与 第2 章理论基础 事实匹配，则规则就被激活并放入议程，即已被激活的规则集合。 对于单一事实以单一方式与模式匹配的情形比较简单，而对于多种方 式进行的模式匹配往往变得非常复杂，这时候我们一般是通过使用多字段 通配符( $ ? ) 、字段约束与组合、函数控制等来实现模式匹配的。对于高级 模式匹配问题，主要是通过谓词函数、谓词字段约束、返回值字段约束以 及各种条件元素创建一个控制流来控制规则的执行。这时候的规则模式就 是控制模式，专门用于控制规则何时可用。控制事实用来触发控制模式。 2 3m p i 消息传递原理 进程间的消息传递机制是m p i 标准的核心机制。m p i 消息传递原理部 分将就消息传递机制和消息传递的基本过程进行介绍和分析。 2 3 1m p i 消息传递机制 在消息传递机制中，一个处理机上的进程可以将其内存中任意数据的 拷贝通过互联网络传递给其他处理机的进程，同时它也可以接受其他处理 机上的