文档介绍：人工智能与机器翻译
主讲:杨宪泽
——产生式系统及其搜索方法
第3 章产生式系统及其搜索方法
产生式系统
产生式系统的搜索(控制)策略
图搜索算法
产生式系统的规则问题
应用举例
产生式系统的不确定性问题
系统设计技巧
3 . 1 产生式系统
产生式系统使用类似于文法的规则, 对符号串作替换运算。它是智能软件中使用最普遍、最典型的一种结构。为什么要采用产生式系统作为智能软件的主要结构呢? 这可以有两点理由:
(1) 用产生式系统结构求解问题的过程和人类求解问题时的思维过程很相象, 因而可以用它来模拟人类求解问题时的思维过程;
(2) 可以把产生式系统作为智能软件中的基本结构单元或基本模式看待, 就好象是积木世界中的积木块一样, 因而研究产生式系统的基本问题就具有一般意义。
3 . 1 产生式系统
3 . 1 . 1 产生式系统的组成部分
一个智能软件用产生式系统设计的基本组成是: 一个综合数据库; 一组产生式规则; 一个控制系统。
综合数据库是产生式系统所使用的主要数据结构, 用来表述问题的状态或有关事实。它包含求解问题的信息, 其中有些部分可以是不变的, 有些部分可能只与当前问题的解有关。人们可以根据问题的性质, 用适当的方法来构造综合数据库的信息。
3 . 1 产生式系统
3 . 1 . 1 产生式系统的组成部分
产生式规则的一般形式为:
条件─→行动或前提─→结论
即表示成为: if┄┄then┄┄的形式。
其中, 左边确定了该规则可应用的先决条件; 右边描述了应用这条规则所采取的行动或得出的结论。一条产生式规则满足了应用的先决条件之后, 就可对综合数据库进行操作, 使其发生变化。如综合数据库代表当前状态, 则应用规则后就使状态发生转换, 生成新状态。
3 . 1 产生式系统
3 . 1 . 1 产生式系统的组成部分
控制系统是软件的控制程序, 也是规则的解释(推理)程序。它规定了如何选择一条可应用的规则对数据库进行操作, 即确定了求解过程的推理路线。当数据库满足结束条件时, 系统就应停止运行; 还要使系统在求解过程中记住应用过的规则序列, 以便最终能给出解的路径。
控制系统也称控制策略, 它也可以是从规则集中选择规则并作用于状态的一种广义选取函数。确定某一种策略后, 可以算法的形式给出。在建立产生式系统描述时, 还要给出初始状态和目标条件, 具体说明所求解的问题。产生式系统中控制策略的作用就是从初始状态出发, 寻求一个满足一定条件的问题状态。目标条件也是产生式系统结束条件的基础。
3 . 1 产生式系统
3 . 1 . 1 产生式系统的组成部分
上述产生式系统的定义具有一般性, 它可用来模拟任一可计算过程。在研究人类进行问题求解过程时, 完全可用一个产生式系统来模拟求解过程, 及可作为描述搜索的一种有效方法。作为智能中的一种形式体系, 它还具有以下优点:
(1) 适合于模拟强数据驱动特点的智能行为。当一些新的数据数入时, 系统的行为就要改变;
(2) 易于添加新规则去适应新的情况, 而不破坏系统的其他部分。这是由于产生式系统的各组成部分具有相对的独立性, 因而便于扩展和修改。
3 . 1 产生式系统
3 . 1 . 1 产生式系统的组成部分
用产生式系统来求解问题, 首先必须建立起问题的产生式系统描述, 即规定出数据库、规则集合及其控制策略。这种把一个问题的叙述转化为产生式系统的三个组成部分, 在智能技术中通常称为问题的表示。一般来说一个问题可有多种表示方式, 而选择一种较好的表示是运用智能技术解决实际问题首先要考虑的, 而且要有一定的技巧。
建立了产生式系统描述之后, 通过控制策略, 可求得实现目标的一个规则序列, 这就是所谓问题的解, 这个解序列是根据控制系统记住搜索目标过程中用过的所有规则而构造出来的。
3 . 1 产生式系统
3 . 1 . 1 产生式系统的组成部分
在一般情况下, 问题可能有多个解的序列, 但有时会要求得到有某些附加约束条件的解, 例如要求步数最少、距离最短等。这些约束条件通常是用耗散或代价这一概念来概括, 这时问题可称为寻找具有最小耗散的解。
在用产生式系统求解问题时, 有时引入状态空间图。状态空间图是一个有向图, 其节点可表示问题的各种状态(综合数据库), 节点之间的弧线代表一些操作(产生式规则), 它们可把一种状态导向另一种状态。这样建立起来的状态空间图, 描述了问题所有可能出现的状态及状态和操作之间的关系, 因而可以较直观地看出问题的解路径及其性质。当然, 只有问题空间规模较小才可能作出状态空间图。
3 . 1 产生式系统
3 . 1 . 1 产生式系统的组成部分