秦旭东

（沈阳工业大学，沈阳 110027）

推理机是专家系统中最重要的部分，它决定了整个专家系统性能的优劣。现在，绝大多数的专家系统采用了规则产生式系统。规则产生式系统由三个部分组成：第一部分是事实或断言组成的工作内存，被用于问题求解；第二部分是规则集，其中所有规则都是由LHS和RHS组成，LHS由一个或多个条件元素构成，对工作内存中元素的操作存放在RHS；第三部分是控制规则推理引擎。规则产生式系统匹配规则约占90%的工作时间，因此，选择合适的匹配算法极其重要。传统上我们在产生式系统中运用RETE、TREAT和Matchbox几种匹配方法，而本文提出HAL算法，HAL综合了以上算法的优点，减少了匹配时间，通过建立相关规则和类的启发式反馈通道，减少了冗余内容和匹配网络。

1 专家系统结构

专家系统主要由知识库、推理机、解释系统、动态数据库、人机界面等组成。专家系统结构见图1。

图1 专家系统结构Fig.1 Expert system structure

2 推理算法

在专家系统中使用的推理算法多种多样，下面主要介绍被广泛使用的RETE算法和TREAT算法。

2.1 RETE算法

在RETE中，将每条规则转化为包含alpha和beta在内的内存匹配网络，网络的纵向和横向成正比，alpha节点位于匹配网络上方，alpha节点存储事实集合和匹配条件的记号。其余节点都是beta节点，储存条件变量绑定和连接的记号。RETE匹配原理见图2。

图2 RETE匹配原理Fig.2 RETE matching principle

2.2 TREAT算法

TREAT算法为每条规则建立一个alpha节点。其alpha节点分成三个部分，分别是旧节点、新添加节点、新删除节点。例如，将新的删除节点插入到alpha节点时，新的删除节点会触发搜索操作，冲突集可能会发生变化，匹配原理见图3。

图3 TREAT匹配原理Fig.3 TREAT matching principle

2.3 HAL匹配算法

HAL主要使用类的启发式信息，而不是规则的启发式信息，HAL基于类只需定义一个全局匹配网络，网络中包括规则节点、类节点和中间节点。

2.3.1 HAL算法的匹配过程

建立一个全局匹配网络，规则和类转化为规则节点和类节点。若规则节点有类的变量绑定则建立中间节点，规则节点和中间节点之间进行双向通信。若规则不涉及类的变量绑定，则类节点与规则节点直接相连。

遍历旧事实，选取一个事实，查看事实对应的类节点，若此类节点连接中间节点，当加入事实时，将新事实发送给中间节点；当有删除信息时，中间节点和规则节点接收删除信息，转到步骤3。若无中间节点，若满足检查类节点的事实条件，则此类节点连接的规则节点被激发，转到步骤4。若没有新事实信息或删除操作时，则算法终止。

对于所有的中间节点，若新的绑定值不属于被监视的事实或者删除操作，则中间节点激发所有相连的类节点，不添加新的事实或删除操作；反之，添加新的事实或删除操作，转到步骤4。

遍历新的绑定值或者删除操作后，确定规则节点是否全部匹配条件元素。若部分匹配，则修改中间节点对应的条件元素；若全部匹配，则执行RHS部分操作。若没有“结束”操作则转入步骤3，否则结束算法。

2.3.2HAL匹配原理图

图4 HAL伪双向网络Fig.4 HAL pseudo two way network

例如，当添加事实时，匹配过程见图5。

图5 添加事实A1Fig.5 Add facts A1

向A类节点添加事实A1，中间节点被激发，中间节点激发B节点，B节点中B1*开始监听A1匹配规则1。

图6 添加事实A2Fig.6 Add facts A2

向A类节点添加事实A2，中间节点被激发，中间节点激发B节点中B2*监听A2匹配规则1。

图7 添加事实B14Fig.7 Add facts B14

向B类节点添加事实B14，中间节点被B类节点激发，然后中间节点激发C节点C4*监听B14匹配规则1。

图8 添加事实B46Fig.8 Add facts B46

向B类节点添加事实B46，中间节点被B类节点激发，然后中间节点激发C节点C4*，同时激发A节点A4监听B46进行匹配规则1。

图9 添加事实B47Fig.9 Add facts B47

向B类节点添加事实B47，中间节点被B类节点激发，中间节点激发C节点C7*监听B47进行匹配。

3 结语

其他规则产生式系统的程序复杂度与HAL的大致相同，但HAL建立的伪双向网络是一个常数，而且在多数专家系统中，规则的数量要远多于类的数量，因此，HAL匹配速度更快。

在实际应用中，还要考察大型的基于规则系统HAL运用的效果如何，防止发生没有预料到的问题，最终将HAL有效的应用到实践中。

［1］ 耿庆宦，吕良双.产生式系统规则匹配算法研究［J］.计算机科学，2009，(11)：26-29.

［2］ P.-Y.LeeandA.M.K.Cheng,"HAL：A Faster Match Algorithm",IEEE Trans. Knowledge and Data Eng.,vol.14,no.5,Sept./Oct.2002..

［3］ 历长云.钢板矫直专家系统的设计［D］.沈阳：沈阳工业大学，2004.