clips专家系统编程语言学习教程，专家系统原理与编程

【实例简介】
该教材详细的介绍了clips语言的编程方法，规则，是学习专家系统编程的很好的资料
Clinal ct 第11章基于规则语言的效率 11.1概述 本章介绍了许多提高基于规则的专家系统效率的技巧,专家系统使用的是Rete模式匹配算 法。在解释Rete算法之前,将讨论需要一个有效的模式匹配算法的原因。同样,也将讨论一些 更加有效地组织规则的技巧。 112Rete模式匹配算法 基于规则的语言,如 CLIPS、ART、OPS5和OPS83,使用了一种非常有效的算法,将事实 和规则中的模式相匹配,以确定哪些规则满足了它们的条件。这种算法称为Rete模式匹配算法 ( Rete Pattern- Matching algorithm) Forgy79;Fony85; Brownston85)。编写有效的 CLIPS规则 不需要理解Rete算法。然而,理解 CLIPS及其他基于规则的语言中使用的基本算法,使人们更 易于明白为什么用这种方法写规则会比另一种方法更有效。 要明白为什么Rete算法是有效的,可研究一下通常将事实和规则进行匹配的问题,并接着 考察不那么有效的其他算法,这是有帮助的。图11-1示出了Ret算法所提出的问题 事实 推理机 规则 议程 图11-1模式匹配规则和事实 如果匹配过程只需一次,那么这个问题的解决方法就简单易懂。推理机可以检查每条规则 并寻找一套事实来决定规则的模式是否已满足。如果是,则将此规则记入议程中。图112示出 了这一方法。 然而,在基于规则的语言中,匹配过程不断重复进行。通常,事实列表在每次执行中都会 被修改,添加新的事实到事实列表或删除旧的事实。这些改变可令先前不满足条件的模式得到 满足,反之亦然。匹配问题因此成了不断进行的过程。在每次循环中,随着事实的添加和删除, 第1章基于规则语言的效率 343 事实 规则 议程 图11-2寻找事实的规则 必须对已满足条件的规则集合进行维护和更新。 在每次循环后,令推理机检查每条规则以指导对事实的寻找,从而为解决这个问题提供了 简单直接的技巧。这种方法最主要的缺点是速度太慢。大多数基于规则的专家系统都显示了这 种特征:时间冗余性( Temporal redundancy)一般地说,一条规则的运行仅会改变事实列表中 的少数事实。即:专家系统中的事实随时间改变很慢。在每次循环中,仅添加、删除很少一部 分事实,所以,事实列表中的变化一般只影响很少部分的规则。因此,令规则推动对所需事实 的寻找,需要大量不必要的计算。这是因为,在当前循环中,大多数规则所找到的事实很可能 与上一次循环所找到的相同。图113示出了这种低效的方法。阴影部分代表了对事实列表所做 的改变。正如图114所显示的,在不断循环中,通过记住哪些是已经匹配好的,然后,只计算 那些刚添加或删除事实所引起的必要变化,从而,可避免不必要的计算。规则是不变的,而事 实是变化的,所以应是事实寻找相应的规则,而不是反过来。 Rete模式匹配算法正是利用了基于规则的专家系统所具有的时间冗余性。它的实现是通过 事实 规则 事实 规则 议程 议程 图11-3当规则寻找事实时,产生不必要的计算 图114事实寻找规则 344 专家系统原理与编程 存储不断循环中匹配过程的状态,并且,只重新计算在事实列表中发生了变化、又反映到本次 状态中的变化。也就是说,如果在一次执行周期中,一组模式找到三个所需事实中的两个,那 么,在下一周期中,就无需对已经找到的这两个事实进行检查——只有第三个事实才是需要关 注的。仅当添加或删除事实时,匹配过程的状态才被更新。如果添加、删除事实的数量与事实 和模式的总数相比很小,那么匹配过程会进行得很快。最糟的情况是,如果所有的事实都改变 了,那么,所有的事实将与所有的模式进行匹配。 如果仅是事实列表进行更新,那么每一条规则必须记住已与之匹配的事实。也就是说,如 果一个新的事实与规则的第三个模式相匹配,那么,头两个模式的匹配信息必须存在以完成匹 配过程。这种状态信息指出了与某一规则中前面的模式相匹配的事实,称之为部分匹配( Partial match)。规则的部分匹配是满足规则模式的任何一组事实,它以规则的第一个模式为开始,以 任一模式(包括最后一个模式)为结束。因此,一条有三个模式的规则对第一个模式、第一和第 二个模式及第一、第二和第三个模式都有部分匹配。一条规则的所有模式的部分匹配也是一个 激活。另一种存储的状态信息称为模式匹配( Pattern match)。当一个事实满足了任一规则中的 单个模式而不需考虑在其他模式中可能会限制匹配过程的变量时,则出现的就是模式匹配。 Rete模式匹配算法的主要缺点是内存使用量大。将所有的事实与所有的模式进行简单的比 较不需要使用内存。但是,存储使用了模式匹配和部分匹配的系统的状态会消耗大量的内存。 总的来说,为了速度而牺牲内存是值得的,然而要记住,一条设计不好的规则不仅运行速度慢, 而且会消耗掉大量内存。 通过利用规则中结构相似性( Structural similarity的优点,Rete算法同样也会提高基于规则 的系统的效率。结构相似性是指许多规则通常包含了相似的模式或模式群。利用这一特性, Rete算法通过将公共部分放在一起来提高效率,因为公共部分不必多次计算。 113模式网络 事实与规则的匹配问题可分为两步。首先,当添加或删除事实时,必须决定哪些模式是已 匹配的。其次,必须对跨模式的变量约束进行比较,以决定模式群的部分匹配。 决定哪些事实已与哪些模式匹配的过程是在模式网络( Pattern network)中进行的。为简单起 见,我们将模式匹配限于自定义模板事实的单字段槽。所有不涉及与其他模式中的约束变量相 比较的匹配均可在模式网络中进行。模式网络的结构像一棵树。所有模式的第一槽值约束是与 树根相连的节点。所有模式的第二槽值约束又是与此节点相连的另一些节点,依此类推。一个 模式中的最后一些槽值约束是该树的叶子。因为每一节点只接收它上层节点的信息,所以,模 式网络中的节点称为单输入节点(one- input node)。模式网络中的节点有时也称为模式节点 ( Pattern node)。叶节点也称为终端节点( Terminal node)。每一个模式节点包含一个说明,用来 决定一个事实的槽值是否与一个模式的槽值约束相匹配。例如,因为只有一个槽值约束,所以, 模式 (data (x 27)) 只需一个节点来表示。第一个节点的匹配说明是 he Blot x value·⊥ s aqua1t。 the constant 实际上,还须检查是否为事实取了一个合适的对应于模式的关系名(例如,不希望仅因有相同 的槽名而将 foobar事实与data模式相匹配)。为了执行这一测试, CLIPS为每一个自定义模板设 有独立的模式网络。这样,在建立事实,但在模式匹配进行之前,就进行关系名的检查 为匹配单个槽,匹配说明包括了所有的信息。几个测试可同时进行。例如,模式: M认QNm345 (data (E -reds green)) 会产生以下x槽的匹配说明 he1 ot x va1ue自 t。 the constant a it to the constant gueen 除非变量在模式中使用一次以上,否则,模式网络通常不检查变量约束。例如,模式 data《xx)￠yry)【z?x) 不会为x槽或y槽生成匹配说明,因为槽值变量的第一个约束对模式是否与事实相匹配没有影响。 然而,z槽一定与x槽有相同的值,所以,z槽的匹配说明是: The z slot value is equal to the x slot value 在模式网络中可以检查那些全部位于模式中的含有变量的描述。例如,模式 (data(x?κk:>?x2y))) 不会为x槽生成匹配说明,因为变量?y不在模式中(当然,假设变量y在前一模式中已被定义), 然而,x槽在模式 (x?x:(>2X4))) 中将有匹配说明: The x Blot value is greater than the constant 4 因为在描述中找到的唯一变量?同样在该模式之内。 正如前面所述,模式网络是按层次分布的,顶部是与模式第一槽值约束相对应的模式节点。 当声明一个事实时,会检查模式网络中的第一槽值约束的模式节点。任何满足匹配说明的模式 节点会直接激活它以下的模式节点。这一过程将持续下去直到模式网络的终端节点。模式网络 的终端节点表示一个模式的结尾和一次成功的模式匹配。每一终端节点有一个 alpha或 right memory. Alpha memory包含与终端节点有关、且已与模式匹配的所有事实的集合。换句话说, alpha memory存储了某一特定模式的模式匹配集 通过共享模式间的公共模式节点,模式网络利用了结构相似性的优点。因为模式节点是按 层次存储的,所以,如果两个模式的头N个槽值约束的匹配说明相同,则它们共享头N个模式 节点,例如,模式: 【dnta《xred)y geen】) data【xred)(yhue)) 可以共享x槽的公共模式节点。注意:匹配说明必须相同,而模式中的槽值约束不必相同。例 如,模式 data ( x ? x)cy?x】 (data (x ?y) (y ?y)) 可以共享y槽的模式节点,尽管这两个模式中的变量不一样。x槽并不形成匹配说明,所以,为 了共享而忽略这些x糟槽。然而,将槽的顺序变为: (data (x ?x)(y ?x) (data (y ?y) (x ?y)) 会使模式不能共享节点,因为第一模式会产生y槽的匹配说明,而第二模式会产生x槽的匹配说 明 图11-5示出了由下面规则生成的模式网络。 ( defrule Rete-mule-1 (match (a red)) (aata (x ? x)(y ?x) 346 专家系统原理与编程 China wheel (d。 Rule Ret-xu1e-2 (match (a ?x)(b red) (data (x -green)(y 2x) (data (x ?x)(y ?x)) 匹配模式网络 数据模式网络 槽值等 b槽值等 槽值等于 y值等 于常量red 于常量red 常量 green 于x檀值 匹配的模式 匹配的模式 匹配的模式 匹配的模式 图11-5两个规则的模式网络 114连接网络 旦确定哪些模式与事实匹配,则必须要进行跨模式的变量约束比较以保证多个模式中所 用的变量有一致的值。这种比较是在连接网络( Join network)中实现的。模式网络的每一个终端 节点在连接网络中作为一个连接(oin),即双输入节点( Two-input node)的一个输入。每一个连 接包括一个匹配说明,该匹配说明是为与终端节点相联系的 alpha内存的匹配和已经与前面模 式匹配了的部分匹配集而设置的。前面模式的部分匹配保存在连接的beta戎 left memory中。 条有N个模式的规则将有N-1个连接(但是CLPS实际上用N个连接来简化Rcte算法,因此,每 个连接只允许一个模式输入) 第一个连接和最先的两个模式比较,剩下的连接将其余的模式与前面连接的部分匹配相比 较。例如,假如在前面的例子中使用规则 Rete-rule2 【 defrule Rete-xu-2 match【a?x)[bred) (data (x -green](y ?x)) data (x ?x)(y ?x)) 第一个连接包含如下的匹配说明: 如°tva1u· of the fact bound to the first pattern it l t teya。tv1 ue of the￡act bound to the Becond pattern 第二个连接将收到来自第一个连接的一组部分匹配作为输入,它将包含如下的匹配说明: x觑] ot value of the fact bound to the third pattern is equal to the y slot value of the fact DialCom 第1章基于规则语言的效率 347 bound to the second pattern 注意,第三模式中的变量x的值可与第一模式中的变量?x的值进行比较,而不是与第二模式 中的变量?x的值进行比较。x在第三模式中的第二次出现可以在模式网络中被检查到,因此, 它不用在连接网络中被检查。规则 Rete-rule-2的模式和连接网络如图11-6所示。 匹配模式网络 数据模式网络 b槽值等 槽值不等 值等 于常量red 于常量 green 于x槽值 匹配的模式 匹配的模式 匹配的模式 约束于第二模式的事 实的a槽值等于约束于 第一模式的事实的y槽值 约束于第二模式的事 实的x槽值等于约束于 第三模式的事实的y值 连接网络 Rete-rule-2 规则被激活 图116规则 Rete-rule2的模式网络和连接网络 连接网络通过共享规则间的连接来利用结构相似性。从第一个模式开始,连接网络中的连 接可被两条规则共享,前提是这两条规则有相同的模式和两个以上模式的连接比较。例如,这 些规则: 348专家系原理与图 (match (a ?x)(b red) (data (E -green)(y 2x) )y2x) thez【sz) (defrule sharing (match(a ?y)(b red) data(x- 'reen)《yy)) data【xz)yy) other【qy)) 能够共享它们在模式网络中的所有模式,并共享在连接网络中为前三个模式所生成的连接。在 连接网络中第四个模式的连接不能被共享,因为两条规则的匹配说明不相同。规则 sharing-1的 第四模式的匹配说明不需要进行任何比较,因为变量?z没有在其他模式里使用。然而,规则 sharing2的第四模式的匹配说明一定要把变量?y和其他模式中所使用的y进行比较,以保证 变量约束的一致性。再次注意,利用结构相似性特点时,变量名不需要相同,最重要的是匹配 说明一定要相同。 如果发出 watch compilations命令, CLIPS将提供有关共享连接的有用信息。例如,以下命 令阐明了如何显示有关共享的信息。假定规则 sharing-1和& haring-2在文件“ rules.clp”中。 cIp(ttho4at。)d Defining defrule: aharing-1 +3+3+1+ Defining defrule: sharing-2 =3=j=3+3 CIPS> 输出中的“+j”表示增加一个连接,而“=j”表示一个连接被共享。因此,当加上规则 sharing-1时,就生成四个新的连接;当加上规则 sharing2时,它将与 sharing-1共享头三个连接 同时为它最后的模式生成一个新的连接。注意,与通常需要的三个连接不同, CLIPS用四个连 接来表达规则。由于实现原因,每个连接只有一个模式更方便,所以,CIPS在前两个模式中 不用一个连接而用两个。 115模式顺序的重要性 为了提高速度和节省内存,规则中的模式要按正确顺序排列,刚使用基于规则的语言的程 序员往往会误解这一点。因为Rete算法网络保存了从一个循环到下一个循环的状态,所以,确 保规则不产生大量的部分匹配是很重要的。例如,考虑以下筒单的程序段 (deffacts information 【王ind- match p) 【王 cem al 【tmb (item c) 【 item d) 【王 土teg 孟-g) 【 defrule match-1 【End- match?x?y?z2wl CliapuLcoN MIR KP EPIS TPMX*349 (item ?x) item ?y) 【tem?z 【 assert( found-math?x?y7z?w)】 这段程序重置〔rese)很快,在 reset命令前发一个 watch facts命令将证实这一点。现在考虑以 下程序: Bleffact8 in:。2 mator (find-match ace g) (item a) (item b) 【tme (item d) (item e) (item f) (item g)) (defrule match-2 【王te?x) (item ?y) 王tam?z) 〔tmw) (Eind-tatca ?x ?Y ?z w) (assert (found-match ? ?y ?z ?w))) 在这段程序中,一个后面跟着重置命令的 watch facts命令将展示一段很慢的重置时间。当 重置执行时,自定义事实结构中的头几个事实很快被声明,而随后的事实则需要越来越长的时 间。规则 match-1和 match-2各自有相同的模式,但 match-2重置时间更长,实际上,在一些电脑 中,规则 match-2会让 CLIPS内存不足。通过向 information自定义事实增加事实,速度的差别 会更大(事实上,为了显示明显差别,在一些电脑中必须向 information自定义事实加入额外的 事实)。 11.51计算规则 match-1的匹配 计算规则 match-1的模式匹配和部分匹配能提供有用的信息,在列出模式匹配和部分匹配 时,使用事实标识,而不用整个事实。而且部分匹配将被括在括号中,事实标识如下: E-1【￡ina- match ace g -2【itea f-3【temb f-4【itea) f→5【 item a) f-6【teme) -7【em f-8【 iten g) 规则 match-1包含以下模式匹配: Pattern1:三-1 Pattern2:'E-2,￡-3,f-4,￡-5,王-6,王7,王-8 Pattern 3: E-2 f-4,￡-5,三-6,E-7。-B pattern4:f-2,E-3,￡-4,E-5,E-6,E-7,E-8 patter5:f-2,E-3,￡-4,￡-5,f-6,f-7,f-8 【实例截图】
【核心代码】