Rete算法：研究现状与挑战

产生式规则推理系统因其可理解性、易增删、易修改等特点而被广泛用于各种智能领域,但其规则匹配效率极其低下,不适合大规模推理。Rete算法通过规则条件共享和保存临时匹配结果大大加速了产生式推理,使其成为效率最高的产生式推理算法之一。但随着数据规模的日益增大、业务信息的频繁变更以及不完整数据和模糊逻辑的广泛出现,Rete算法也面临前所未有的挑战。基于这些背景,对Rete算法的原理、研究现状与面临的问题进行综述,指出了Rete算法的常用改进方法。介绍常见的改进方法,并对其进行分析和比较,最后总结了该算法面临的挑战,指出了未来的研究方向。

IMPR:一种优于RETE算法的多模式/多对象匹配算法

RETE算法是应用于产生式系统的 ,迄今为止被认为是性能最好的匹配算法 .但该算法本身也包含某些影响执行效率的因素 .本文在分析该算法优缺点的基础上 ,针对该算法删除操作与栈操作开销过大的情况 ,提出了一种新的匹配算法—— IMPR算法 ,并通过理论分析和实验检验表明 ,在各种情况下 ,IMPR均优于

智能环境下分布式Rete算法

针对智能环境中基于Rete的规则推理引擎需要将数据集中到sink节点,导致传感器网络中数据传输量过大的问题,建立了Rete网络代价模型,并提出了最小传输代价的Rete分布的算法(MCoRDS)。该算法通过统计Rete网络中子模式对事实数据的依赖,发现大部分子模式在对应事实数据采集Sensor附近便具备了计算推理条件,故将Rete网络中的子模式规则分布到最早汇集其所需所有事实数据的Sensor中,即可避免事实数据进一步往sink节点的传输,从而大量减少传感器网络中的数据传输量。对比将Rete网络放置在sink节点的集中式推理进行了4组仿真实验。其中第4组实验,传感器网络总跳数由85000减至8036,减少约90.5%;其余组实验传输跳数也有一定的减少。实验结果表明,最小代价的Rete分布具有更小的数据传输量,在规则触发频率低、规则规模较大的情况下尤甚。

基于工业环境的改进Rete算法

针对在拥有大量数值比较的工业应用中实现Rete算法的匹配模式,系统需要占用更多资源的问题,详细的分析了Rete算法的过程特性和执行机制,通过建立算符机制、实行标识量共享、加入预匹配的方法对其在工业应用中的不足进行了改进,从而极大地提高了规则存贮和快速匹配的效率。实验结果表明,改进后的Rete算法有效地解决了传统算法在工业应用中实时性差、资源占用率高的难题,极大地提高了系统的整体性能。

基于Rete算法的多Agent的实时协同推理

In this paper, we first introduce the high efficient pattern matching algorithm named Rete. Second, we analyze the problem appeared in using Rete algorithm to develop expert system. But it develops a new way to realize Agents' real-time and cooperative reference. Then we put forward to embed the Rete algorithm into Agents and realize cooperative inference by Agents' communication. On these bases, we discuss the accuracy and real-time feature of cooperative inference in detail. Finally, we describe two Agent-communication performatives and a developing instance of multi- agent system to monitor oil tanks.

支持演化规则引擎的Rete算法研究

在演化规则模式匹配过程中,存在内存空间有限与用户请求响应要求快速等问题,传统的Rete算法并不能完全适合此类实际应用。针对此类问题,在经典Rete算法的基础上,通过从算法空间复杂度的角度对Rete网络结构匹配效率进行分析,并结合系统动态演化过程中强动态和高实时性的特点,引入节点复用技术构造Re-te网络,且以规则权重、入网时间为依据,增设了Rete网络节点存储空间可调整机制,完成了Rete算法在内存消耗与调节、匹配耗时方面的优化。对比测试表明,优化后的算法提高了网络匹配性能,实现了系统的平稳安全运行,解决了演化系统模式匹配过程中存在的问题。

基于Rete算法的JAVA规则引擎

在软件应用中若能抽取出规则,可以使软件实体更灵活,规则引擎使得这成为可能。其算法Rete也逐渐发展成为了一种最重要的主流算法。先着重叙述了规则引擎的原理及其JAVAAPI,其次阐述了Rete算法,最后简单介绍了Jess与开源项目产品Drools。

Rete算法的优化及在动车组故障知识库推理中的应用

为了解决动车组在运行途中出现的各类故障,检修段需要根据动车组发生的故障进行原因分析,并及时采取相应的解决措施.因此本文将故障知识库应用到高速铁路动车组,着重研究了基于Rete算法的推理机在知识库系统的应用,并对Rete算法进行了改进,最后利用动车组故障数据对优化前后的Rete算法进行了比较,证明了改进算法的有效性.

Rete匹配算法在知识库机中的实现方案

Rete算法是目前公认的用于产生式系统的高速匹配算法。本文根据Rete算法的主要特点,提出在知识库机中实现 Rete算法的方案,并讨论了该方案中的流水匹配等技术问题,目的在于提高匹配效率,从而加快产生式系统的执行速度。

基于故障树与Rete算法的电泵井工况诊断方法研究

为了实现对电泵井运行过程中电泵工况与电机工况的智能诊断,对基于故障树与Rete算法的电泵井工况诊断方法进行研究。通过对电泵井工况故障的特征表现进行分析,构建了支持电泵工况与电机工况诊断的故障树与知识库,并结合Rete算法实现了基于产生式的规则引擎,用于推理得到电泵井的工况诊断结果,从而给出相应的优化建议。最后在电泵井基础数据和电机测试数据的事实数据基础上,对63口井进行了工况诊断。实践表明,诊断结果与实际相符,提高了工况故障定位的效率与精确度。

RETE算法的改进与实现

本文详细描述了模式匹配算法—RETE算法,深入分析了RETE算法的性能,并对其进行了改进。改进后,事实的删除过程利用了事实添加过程中的信息,使得删除过程中不需要联结测试操作与查找操作,大大提高了删除事实时的性能。

OPS5并行选择全状态处理模型RETE-Plus及其算法

本文首先通过建立一种状态分析方法,证明了RETE算法所保存的中间状态集IS(P_1)的不完备性,论述了RETE算法用于并行处理的局限性以及产生式间状态处理时间的差异.然后,提出了一种产生式系统并行选择全状态处理模型RETE^+,证明了RETE^+所处理的全状态集FS(P_j)具有准完备性质.计算表明,RETE^+的状态处理时间比RETE快得多,并且消除了状态处理时间差异.最后给出了RETE^+模型的主要算法.

基于Rete算法的几何自动推理系统

智能几何教学软件都使用基于前推法的几何推理系统作为推理引擎。推理引擎的主要工作是做推理规则和几何信息的匹配计算。推理过程中产生的大量冗余匹配严重地影响了推理效率。为了提高推理引擎的推理效率,作者首次将Rete模式匹配算法整合到推理引擎中,构造了一种高效的几何自动推理引擎,称为几何自动推理网。几何自动推理网通过消除推理过程中的冗余匹配达到了提高系统推理效率的目的。使用L isp语言编写了几何自动推理网程序iGeo,并做了50多个非平凡几何定理的推理实验,实验结果表明iGeo具有更高的推理效率。

Rete算法的应用研究

对专家系统和基于规则的专家系统进行了研究,尤其对基于规则的专家系统中的模式匹配算法进行了深入分析和理解。在此理论基础上,将一种高效的模式匹配算法——Rete算法引入到实际的故障的诊断系统中,以保证故障诊断的高效性和准确性。为此在实际系统中,借助规则引擎将故障信息规则化,并将故障诊断流程以层次分明的XML文档进行表示,来模拟领域专家进行故障诊断和故障排除的功能。实践表明,该故障诊断系统可以提高定位故障的速度和准确度。

结合Rete的RDF数据分布式并行推理算法

现有的资源描述框架(RDF)数据分布式并行推理算法大多需要启动多个MapReduce任务,但有些算法对于含有实例三元组前件的RDFS/OWL规则的推理效率低下,整体推理效率不高.针对此问题,文中提出结合Rete的RDF数据分布式并行推理算法(DRRM).首先结合RDF数据本体,构建模式三元组列表和规则标记模型.在RDFS/OWL推理阶段,结合MapReduce实现Rete算法中的alpha阶段和beta阶段.然后对推理结果进行去重处理,完成一次RDFS/OWL全部规则推理.实验表明,文中算法能高效正确地实现大规模数据的并行推理.

一个基于Rete算法的可视化产生式系统

国内常见的产生式系统 ,如OPS5和CLIPS ,他们的应用和开发界面都是类似LISP的文本界面 ,可操作性差 .基于面向对象的方法和技术 ,设计并实现了一个可视化的产生式系统 ,该系统采用Rete算法进行推理 ,提供了事实库、规则库和Rete网络的可视化的维护功能 .使用VC ++6 .0实现了该系统 .实际运行表明 ,该系统效率高 ,可操作性强 .

基于Rete算法的攻击图构建方法

针对现有攻击图构建方法适用的网络规模受限的问题,通过分析现有方法存在的缺陷及构建过程中的特点,使构建攻击图转化为威胁行动属性之间的模式匹配,将Rete引入到攻击图构建过程中,提出基于Rete的攻击图构建方法。实验结果表明,该方法具有较好的构建效率,能够适用于大规模网络的攻击图构建。

基于代价模型的RETE优化算法

RETE匹配算法是基于规则推理系统中的经典高效算法,但是在飞行器评估这种规则和事实数量较多的系统,推理效率并不高,因为在模式匹配中,join操作的开销与事实的平方成正比。事实和规则数量较多时,产生的中间匹配信息大大增加,增加了时间复杂度和空间复杂度,严重降低了推理效率。针对飞行器评估系统的特点,本文分析了优化RETE拓扑结构是提高推理效率的关键,然后提出了基于代价模型的RETE优化算法,该算法可以自动寻找最优的RETE拓扑结构,减少了join中间结点的数据,大大降低RETE算法的时间复杂度和空间复杂度。经实验测试,基于代价模型的RETE算法在飞行器评估系统中的运行效率较高,满足飞行器评估的需求。

专家系统中的Rete算法在Jess中的实现

专家系统的重要部分是推理机。推理机利用已有知识库,结合现有事实做出决策,产生新的事实,直至问题解决。推理机专家系统工具的核心,它的能力和效率至关重要。Rete算法是现实对象问题求解的推理过程,以牺牲空间来赢得速度的算法。Rete算法利用推理机的"时间冗余"特性和规则结构的相似性,并通过保存中间运算结果的方法来提高推理的效率。

基于Rete模式匹配算法的入侵检测系统

设计并实现了一个基于专家系统的网络入侵特征检测系统.针对当前入侵检测推理机制中存在的时间冗余性问题,在入侵检测推理过程中采用了Rete模式匹配算法,对推理机制进行了优化.实验结果表明,该系统在检出率和检测效率上要明显高于未采用Rete模式匹配算法的系统,采用Rete模式匹配算法能有效地克服时间冗余性问题,并改善了系统的性能.