文档介绍：规则引擎与RETE算法
舒琴(瀞心)
阿里云-弹性计算
规则引擎是什么
起源于专家系统, 人工智能领域的商业应用方向
基于产生式规则的推理系统,将领域知识和业务规则集合作为知识库进行存储和管理; 规则引擎根据给定数据及知识库进行推理,执行相应规则,从而作出决策;
使用预定义的规则语言编写业务规则,将业务逻辑从应用程序中分离,业务规则更加可读、可编辑、动态可配置, 从而应对复杂多变的商业规则;
嵌入到应用程序中的可复用计算组件。
适用场景:
替换复杂嵌套难以维护的条件、分支语句;
业务规则变化迅速, 且不能经常重新编译和部署应用;
必须由业务专家动态地维护和管理可变的业务规则和商业机密;
计费系统、积分系统、知识推理系统等;
规则引擎的组成(一)
产生式规则库(Production Memory): 存放企业规则的可编译形式;
工作内存区(Working Memory): 存放事实, 对应于企业应用系统中的数据对象;
推理引擎(Inference Engine) :决定哪些规则满足事实,并授予规则执行优先级,满足要求的待执行规则被加入议程。推理引擎由模式匹配器、议程和执行引擎组成。模式匹配器决定哪些规则满足事实,并授予规则执行优先级,满足要求的待执行规则被加入议程;议程使用指定的冲突消解策略,来决定已匹配的规则集的执行次序;执行引擎负责执行规则,输出结果。
模式匹配器(Pattern Matcher)是规则引擎的核心,决定着规则引擎实现的效率。一个经典而高效的算法是 ReteOO 算法。
规则引擎的组成(二)
RETE 算法的基本思想是将产生式规则库预编译成一个规则匹配网络—— RETE 网络。
规则/规则流可以使用excel, xml, drl, rf 等多种格式存储和表达。
规则引擎的组成(三)
[步骤一]: 应用程序启动规则引擎,激活指定的规则/断言集区。激活的规则/断言集被加载入内存,并通过规则/断言编译器,最终构建出规则匹配网络;
[步骤二]: 工作内存区从应用程序接收输入数据或对象,将其插入规则匹配网络,经过数据-规则匹配过程,产生完全匹配的<rule, data>集合;
[步骤三]:选择器根据元规则集合提供的优先级描述从<rule,data>集合中选择出<rule,data>集合并包装成Activation实例集作为候选执行单位;
[步骤四]:议程用来管理Activation实例集合的活动,支持添加、删除和更新等操作。它将优先执行的Activation实例集合交给调度器;
[步骤五]:调度器会预先从外部获取控制过程子例程集合。当接收到由议程传来的Activation实例集合时,通过一定的调度算法调度一个过程,并根据过程控制程序来选出将要执行的规则动作,交给解释器执行。此外,调度器还负责未能完成的Activation实例执行过程的调度处理。
[步骤六]:解释器拥有一个执行栈,用于存放要执行的动作。当解释器执行完一个Activation时,就会从议程中删除已执行的Activation;如果有必要,会产生两种可能的附加结果和操作:或者更新工作内存区,并触发新的数据到规则匹配网络中进行匹配;或者激活新的规则/断言集合,放入规则/断言编译器,更新规则匹配网络;
[步骤七]:解释器依次执行完所有的Activation实例集合并输出结果,或者根据用户指定的执行策略执行Activation实例集合,并在指定时刻输出结果;
[步骤八]:用户通过规则引擎提供的API接口取出结果,进一步由应用程序处理。
RETE算法
Charles 1982
多模式/多对象匹配
前向推理
产生式规则解释器
美国国防高级研究计划局发起
Artificial Intelligence 19 (1982) 17-37
前向推理是根据已有事实,不断地应用规则进行推理或者执行动作,从而得出某些结论或结果,类似于演绎法;
后向推理是首先进行假设和猜想,然后不断应用规则来寻找符合假设的事实,从而证明或否定假设或猜想,类似于回溯法。
分析判断系统通常采用前向推理,而证明诊断系统通常采用后向推理。
RETE 算法- 基本概念
[产生式]:亦称规则,指一条由IF-THEN表述的语句,其中包括规则条件及规则动作;
[规则条件]:通常称为LHS,是产生式的IF部分的表达,其中含有待匹配的“模式”元素;
[规则动作]:通常称为RHS,是产生式的THEN部分的表达,含有当规则被激活和调度时要执行的操作;
[对象]: 用来匹配产生式的事实或数据,在面向对象的语境中统称对象;
[工作内存]:全局数据区,包含运行时将会插入、删除或更新的对象;当工作内存区插入、删除或更新对象时,都将引发事实在规则集合中的匹配过程。
[冲突