【大学课件】环境决策支持系统技术基础之三模型与知识.ppt

《【大学课件】环境决策支持系统技术基础之三模型与知识.ppt》由会员分享，可在线阅读，更多相关《【大学课件】环境决策支持系统技术基础之三模型与知识.ppt（156页珍藏版）》请在三一文库上搜索。

1、环境决策支持系统技术基础之三 模型与知识,http:/ 基础信息、路网信息、公交系统信息、历史路况信息、路况实时信息 方法库 最短路径算法、空间Buffer方法等 模型库 针对不等交通方式的交通方案生成与评估模型等,http:/ 提供方案生成和选择的功能,http:/ 决策问题难以预见性，不可能预建完整的模型。建模过程与决策过程相伴随。 建模支持的目标：使决策者成为建模者。 建模支持的方法：通过对模型的有序管理和对决策者的训练和启发，将其领域知识转变为模型。,http:/ 从建模支持的角度看模型的分类。 管理 形式 基本 模型 启发 存储 空间 特征 关系 建模 以多维基本特征坐标构成形式空间

2、，进行模型分类管理。 以基本特征形成模型间的关系纽带，进行建模启发。,http:/ 其中定类变量为无序变量，定量变量为全序变量，结构化图序变量可分有序与无序。,例：,图形,有 细 多边形 卵形 序 化 三角形 四边形 圆 椭圆 正三角 直三角 矩形 棱形 无序,有序关系形成粗化与细化 的启发，无序关系形成类 比启发。宏观与微观，定 性与定量均是粗、细化关 系。,http:/ 粗化归纳推理过程。 细化演绎推理过程。,http:/ 建模的实用方法： 分析问题的若干典型元素 假设（默认）模型（建模启发） 更新模型。 启发式建模方法：模型由若干算子（元模型）组合而成，算子的可用条件为P（前提）。 启发

3、规则：IF 现问题状态结构与P相匹配， THEN 应用算子OP，并将其变量限于B（定义域）。,http:/ 对问题求解器的一般化讨论 ： 模型是对复杂对象的简化描述，简化必存在前提条件，即作假设前提的匹配；在满足前提的情况下进行模型搜索选择，即作输出输入的匹配。 输出输入匹配过程可有下述情况：,http:/ 模型库子系统包括模型库（MB）和模型库管理系统（MBMS），它是决策支持系统的核心，是最重要的也是较难实现的部分。 模型库管理系统管理的模型有两类：一类是标准模型（如规划模型、网络模型等），这些模型按照某些常用的程序设计语言编程，并存在库中。 另一类是由用户应用建模语言而建立的模型，即使是

4、标准模型也有个再开发的过程,http:/ 模型种类很多，有数学模型、数据处理模型、智能模型、图形模型、图像模型等。数学模型可以用数学方程形式表达，也可以用算法形式描述。数据处理模型一般用数据处理过程来说明。它们在计算机中均以计算机程序的形式表示。而图形、图像模型等在计算机中都是以数据文件形式表示。模型库既包含数据文件，又包含程序文件，需要设计统一的格式进行存储，以便使模型库管理系统对它们进行有效的管理。 模型库管理系统可以参照数据库管理系统的功能，如库的建立、模型的查询、增加、删除、修改等。由于模型比数据复杂，模型库比数据库复杂得多，模型库管理系统的功能相应地也复杂许多。 数据库管理系统是通过

5、数据库语言来完成各项管理功能，模型库管理系统同样需要设计一套语言来完成模型库的各项管理功能，模型库语言比数据库语言复杂。,http:/ 模型库子系统与对话子系统的交互作用，可使用户控制对模型的操作、处置和使用； 它与数据库子系统交互作用，以便提供各种模型所需的数据，实现模型输入、输出和中间结果存取自动化； 它与方法库子系统交互作用，实行目标搜索、灵敏度分析和仿真运行自动化等。 模型库子系统的主要作用是通过人机交互语言使决策者能方便利用模型库中各种模型支持决策，引导决策者应用建模语言和自己熟悉的专业语言建立、修改和运行模型。,http:/ EDSS采用可二级框架结构来描述每一个模型， 第一层框架

6、结构主要描述模型的外部特征，包括模型名、类型、用途、可执行文件名、模型的实体参数，如输入项、输出项、约束条件等， 第二层框架结构主要描述模型的运行环境，包括输入、输出数据文件的类型以及是否需要预处理，模型主体以可执行文件的形式存在于文件中。 模型库管理功能包括模型库维护、模型操纵和模型结果显示等功能。,http:/ 第一阶段：模型数据 第二阶段：数据库系统 模型软件包 第三阶段：模型库系统 数据库系统,http:/ 第二阶段以数据库系统的引入为特点，但缺乏对大批模型的有效管理，不利于用户选择自己需要的模型； 第三阶段实现了数据库和模型库两者之间的通讯，减少了模型存储的冗余度，为模型的操纵提供了

7、良好的环境，使模型应用的灵活性大大加强。,http:/ 应用模型则是用户自己开发的、针对某些具体问题的模型集。它由代码库、源库、模型属性库以及应用模型库索引四部分组成，其中代码库和源库属于子程序级的文本库，前者存贮模型的执行代码，后者存贮模型的源代码，考虑到应用模型的复杂性和可执行代码和源代码在操作系统中均以文件方式管理的特点，故代码库和源库均可以以软件包形式管理，以便充分利用操作系统的文件管理功能， 属性库和库索引文件则引入关系的概念，将模型属性及库说明以关系方式存于各自的库中，通过对属性库和索引库的操作进入相应代码库中的相应地址，从而可执行所选的模型，应用模型库中的层次结构见图。,http

8、:/ 综合环境是模型库系统的运行环境，由模型库管理系统和构模工具等组成，是模型库系统的用户界面。模型库系统的功能应具备下列功能 。 （1）辅助规划与决策。 （2）构造新模型。根据用户自己的目标制定分目标，利用构模工具和模型构件库构造用户自己的模型。 （3）模型库的维护。,http:/ W. Blanning提出了模型管理的关系方法。它不将模型视为一计算过程，而是视为一个关系，其属性分别为输入、输出变量。关系作为模型的一种表示方法，特别是作为用户视图中的模型，可大大地方便非专业用户；而且由于它和关系数据库的表示方法一致，人们可集中管理数据和模型。关系方法提供了一个一致的用户使用界面。,http:

9、/ 。,http:/ 。,http:/ 4、修改模型：系统员对模型的模型体的修改和模型描述信息的修改。不管是修改模型体还是模型描述信息都是删除旧的内容和增加新的内容； 5、删除模型：从指定的模型库中删除一个模型。在EDSS中，这种删除只是逻辑上的删除，模型体及模型描述仍留在库中；,http:/ 7、创建模型库：系统员建立一个新的模型库，这里是指建立用户自己的模型库； 8、删除模型库：系统员把用户认为已经无用的模型库删除。,http:/ 其次，在编译新模型的过程中，怎样减少用数学或逻辑等表示的模型转换为计算机内部的二进制表示时的信息损失； 最后，必须根据模型构造语言和模型描述语言的定义，构造一个

10、功能强大的编辑器，同时，这个编辑器应嵌入到模型构件库中。,http:/ 知识表示是基础 搜索技术是核心 专家系统是目标,各部分间的关系,http:/ 什么是人工智能？ 人工智能是研究知识的一门科学，即如何表示知识，如何获取知识和如何利用知识的科学。,http:/ 人工智能研究的目标 近期目标：在近期，人工智能研究的任务是利用冯.偌依曼型计算机模拟人类智力行为，研制智能程序； 远期目标：远期是研制全新的计算机，即智能计算机。,http:/ 知识与知识表示 知识是人类认识自然界的精神产物，是人类进行智能活动的基础。知识可以分为五类： 描述性知识 判断性知识 过程性知识 对象级知识，或称为领域相关的

11、知识 元级知识,http:/ 对知识表示的要求 表示能力 可理解性 可访问性 可扩展性 3 知识表示方法 一阶谓词逻辑：它是一种描述性的表示方法，它的推理机制是归结原理。主要应用于定理证明。 语义网络：是由Quillian等人于1968年提出的，它在知识表示中可以表示对象、概念及其相互间的关系。它广泛用于基于知识的系统。 产生式规则：产生式系统把知识表示成“模式动作”对，表示方式自然、简洁。它的推理机制以演绎为基础。它是专家系统的知识表示的主要方法。,http:/ 框架：框架理论是Minsky于1974年提出的，它将知识表示成高度模块的结构，它是把关于一个概念或对象的所有信息和知识都存储在一起

12、的数据结构。框架的层次结构可以表示对象之间的相互关系，用框架表示知识的系统称为框架的系统。 状态空间：状态空间表示法把求解问题表示成问题状态、操作、约束、初始状态和目标状态。状态空间是所有状态的集合。 脚本：脚本也称为剧本。它是用来描述固定事件序列，它的结构类似于框架。剧本更强调事件间的因果关系。 Petri网：Petri网是由德国计算机科学家Petri提出的，由于它很好的模拟异步操作，所以在并行处理和分布式计算机领域中应用很多。,http:/ 一阶谓词逻辑表示法：谓词逻辑适合于表示事物的状态、属性、概念等事物之间的知识，也可以用来表示事物之间的因果关系，谓词公式一般用合适公式表示。 谓词的选

13、取 量词的选取（作用的范围） 从自然语言翻译成谓词公式不能丢失信息 易于理解 谓词公式表示法的特点：自然性、精确性、严密性、容易实现。,http:/ 或者 其中P是产生式前提，Q是一组结论或操作。 产生式组成：规则库，综合数据库，控制系统。 产生式系统分类：可交换的产生式系统，可分解的产生式系统，可恢复的产生式系统 产生式表示法的特点：自然性，有效性，模块性，清晰性，效率不高，不能表示具有结构性的知识,http:/ 使用知识。它是问题求解和专家系统的基础。 知识表示遵循的思路,产生式规则 与或图 状态空间 等,人工智能语言 （如Prolog语言） 通用程序设计语言 （如C、C+）,自然语言表示

14、 格式化表示 计算机语言表示,难点分析,http:/ 如果吃肉，那么它是食肉动物； 如果有犬齿、有爪、眼视前方，那么它是食肉动物； 如果是哺育动物、食肉动物、黄褐色、有黑色条纹，那么它是老虎。,自然语言描述知识,http:/ 有毛发或者产奶 then 它是哺育动物； if 吃肉 then 它是食肉动物； if 有犬齿，且有爪，且眼视前方 then 它是食肉动物； if 是哺育动物，且是食肉动物，且是黄褐色，且有黑色条纹 then 它是老虎。,产生式规则表示知识,产生式规则的基本形式： If P then Q 或者PQ,http:/ 框架的结构：一个框架是由若干槽组成，每个槽又可以有若干个侧面。

15、槽用来描述所论对象的某方面的属性，侧面用来描述相应属性的一个方面。槽和侧面所具有的属性值分别称为槽值和侧面值。 框架网络：框架中的槽值或侧面值可以是另一个框架的名字，这就在框架之间建立了联系，构成了框架网络。通过框架网络可以找到另一个框架。 继承性是框架表示法的一个重要特征。它不仅可以在两层框架之间实现继承关系，而且可以通过两两的继承关系，从最底层追溯到最高层，使最高层的信息逐层向底层传递。 框架中槽的设置与组织：,http:/ 充分表达事物个有关方面的属性 充分表达相关事物间的各种关系 ISA槽 AKO槽 Subclass槽 Instance槽 Part of槽 Infer槽 Possibl

16、e-Reason槽 有利于进行框架的推理,http:/ 结构性 继承性 自然性 语义网络表示法：语义网络是通过概念及其语义关系表达知识的一种网络图。最简单的语义网络是如下的三元组： （节点1，弧，节点2） 知识的语义网络表示 用语义网络表示有关事实间的关系：分类关系；聚集关系；推论关系；时间、位置关系；多元关系 用语义网络表示比较复杂的知识：把一个复杂的知识命题划分为若干个子命题，每个子命题用一个较简单的语义网络表示，称为子空间，多个子空间构成一个大空间。,http:/ 常用的语义联系 A-Member-of Composed-of Have Before,After,At Located-o

17、n(-at,-under,-inside,-outside)等 Similar-to, Near-to 语义网络系统中求解问题的基本过程 用语义网络表示知识的问题求解系统称为语义网络系统。 系统由语义网络构成的知识库；问题求解的解释程序（语义网络推理机）组成。 问题求解一般是通过匹配实现的。,http:/ 语义网络表示法的特点 结构性 联想性 自然性,http:/ 脚本表示法：脚本的知识表示方法是R.C.Schank 根据他的概念依赖理论提出的一种知识表示方法。它与框架类似，由一组槽组成，用来表示特定领域内一些事件的发生序列。 概念依赖理论：把人类生活中的各类故事情节的基本概念抽取出来，构成一

18、组原子概念，确定这些原子概念之间的相互依赖关系，然后把所有故事情节都用这组原子概念及其依赖关系表示出来。 脚本一般由以下几部分组成：进入条件；角色；道具；场景；结局。,http:/ 过程表示法：过程性表示方法着重于对知识的利用，它把问题有关的知识以及如何应用这些知识求解问题的控制策略都表述为一个或多个求解问题的过程。每一个过程是一个程序，用于完成对一个具体事件或情况的处理。 用过程规则表示过程 过程规则的一般结构： 激发条件 演绎操作 状态转换 返回 过程表示法的特点：效率较高；控制系统容易设计,http:/ Petri网表示法：对于不同的应用Petri网的构成及构成元素的意义均不相同，但有三

19、种元素是基本的：位置、转换、标记。 Petri网的特点 便于描述系统状态的变化 便于对系统特点进行分析 可以在不同层次上变换描述，而不必注意细节几相应的物理表示。 面向对象表示法：对象、类、封装、继承是面向对象技术的基本概念。 在面向对象方法中，类、子类、具体对象构成了一个层次结构，而且子类可以继承父类的数据和操作。这种层次结构及继承机制直接支持了分类知识的表示。,http:/ 基本概念 什么是搜索 人工智能要解决的问题大多数是结构不良或者非结构的问题，对这样的问题一般不存在成熟的求解算法，而只能利用已有的知识一步步地摸索着前进。在这个过程中，存在着如何寻找一条推理路线，使得付出的代价尽可能地

20、少，而问题又能够得到解决。我们称寻找这样路线的过程为搜索。 搜索分为盲目搜索和启发式搜索：盲目搜索是按预定的控制策略进行，在搜索的过程中所获得的信息不用来改进控制策略的一种搜索。启发式搜索是在搜索中加入了与问题有关的启发式信息，用来指导搜索朝着最有希望的方向前进，加速问题的求解过程，并找到最优解。,http:/ 状态空间表示法：状态空间表示法是用“状态”和“算符”来表示问题的一种方法。 状态：状态是描述问题求解过程中任一时刻状况的数据结构。 算符：引起状态的某些分量变化，从而使问题从一个状态变为另一个状态的操作称为算符。 状态空间：问题的全部状态和一切算符所构成的集合成为状态空间。 例如 二阶

21、梵塔问题。 解：设立柱 1、2和3以及两个圆盘A和B 。用Sk=( Sk0, Sk1)表示问题状态，Sk0表示圆盘A所在的立柱，Sk1表示圆盘B所在的立柱，全部可能的状态共有九种： S0=( 1，1)， S1=( 1，2)， S2=( 1，3) S3=( 2，1)， S4=( 2，2)， S5=( 2，3) S6=( 3，1)， S7=( 3，2)， S8=( 3，3) 问题的初始状态集合是S=S0，目标状态集合是G=S4，S8。,http:/ 与/或树表示法：对于一个复杂的问题，可以通过“分解”和“等价变换”两种手段相结合使用，得到一个图，这个图就是与/或图。 等价变换：是一种同构或同态的变

22、换。 本原问题：不能再分解或变换，而且直接可以求解的子问题，称为本原问题。 终端节点与终止节点：在一棵与/或树中，没有子节点的节点称为终端节点；本原问题所对应的节点称为终止节点。 可解节点：在与/或树中，满足下列条件之一者就称为可解节点： 它是一个终止节点 它是一个“或”节点，且其子节点中至少有一个是可解节点 它是一个“与”节点，且其子节点全部是可解节点 不可解节点：关于可解节点的三个条件全部不满足的节点称为不可解节点。 解树：由可解节点构成，且由这些可解节点可推出初始节点（它对应于原始问题）为可解节点的子树称为解树。,http:/ 状态空间搜索 状态空间搜索的一般过程 OPEN表和CLOSE

23、D表：OPEN表是用于存放刚生成的节点；CLOSED表用于存放将要扩展的节点。 搜索的一般过程 广度优先搜索：从初始节点S0开始，逐层地对节点进行扩展并考查它是否为目标节点。在第n 层的节点没有全部扩展并考查之前，不对第 n+1层节点进行扩展。OPEN表中的节点总是按进入的先后顺序排列，先进入的节点排在前面，后进入的节点在后。 深度优先搜索：从初始节点S0开始，在其子节点中选择一个子节点进行考查，若不是目标节点，则再在该子节点中选择一个子节点进行考查，一直如此向下搜索。当到达某个子节点，且该子节点既不是目标节点又不能继续扩展时，才选择其兄弟节点进行考察。 与广度优先搜索不同，深度优先搜索是把节

24、点n的子节点放入OPEN表的首部。,http:/ 有界的深度优先：对深度优先搜索引入搜索深度的界限，当搜索深度达到了深度界限，而尚未出现目标节点，就换一个分支进行搜索。 代价树的广度优先搜索：与/或树中，边上有代价（或费用）的树称为代价树。 代价树的广度优先搜索的基本思想是每次从OPEN表中选择节点往CLOSED表中传送时，总是选择其代价最小的节点。 代价树的深度优先搜索：基本思想是从刚扩展的子节点中选择一个代价最小的节点送入CLOSED表进行考查。,http:/ 启发式搜索：启发式搜索是利用问题本身的某些启发信息，以制导搜索朝着最有希望的方向前进。 估价函数：用于估价节点重要性的函数称为估价

25、函数。它的一般形式为 局部择优搜索：当一个节点被扩展后，按f(x)对每个子节点计算估价值，并选择最小者作为下一个要考查的节点。由于它每次都只是在子节点的范围中选择要考查的子节点，所以称为局部择优搜索。 全局择优搜索：每次都是从OPEN表的全体节点中选择一个估价值最小的节点进行扩展。,http:/ 算法：把OPEN表中的节点按估价函数的值从小到大进行排序；g(x)是对g*(x)的估计，g(x)0；h(x)是h*(x)的下界，即对所有x的均有： 。其中g*(x)是从初始节点S0到节点x的最小代价； g*(x)是从x节点到目标节点的最小代价，若多个目标节点，则为其中的一个。,http:/ 与/或树搜

26、索 与/或树搜索的一般过程 与/或树搜索的广度优先搜索 与/或树搜索的深度优先搜索 与/或树搜索的有序搜索,http:/ 博弈树的启发式搜索 博弈树的概念：博弈树是与/或树的一个特例；博弈的初始格局是初始节点；在博弈树中与节点和或节点总是逐层交替出现的；所有能使自己一方获胜的终局都是本原问题，相应的节点是可解节点。所有使对方获胜的终局都是不可解节点。 极大极小法 -剪枝技术 值：对于一个或节点来说，取当前子节点中的最大倒推值作为它倒推值的下界，称此值为值。 值：对于一个与节点来说，取当前子节点中的最小倒推值作为它倒推值的上界，称此值为值。,http:/ -剪枝技术：任何或节点x的值如果不能降低

27、其父辈节点的值，则对节点x以下的分支可停止搜索，并使的倒推值为 ，这种剪枝称为剪枝； 任何“与”节点x的值如果不能升高其父辈节点的值，则对节点x以下的分支可停止搜索，并使的倒推值为 ，这种剪枝称为剪枝。,http:/ 推理的基本概念 推理通常是指从已知的事实出发，通过运用已掌握的知识，找出其中蕴藏的事实，或归纳出新的事实，这一过程就称为推理。 推理包括两种判断：一种是已知的判断，它包括已掌握的求解问题有关的知识和关于问题的已知事实；另一种是由已知判断推出新的判断，即推理的结论。 2 推理方式和分类 按推理机制划分，可以有 演绎推理：演绎推理是从全称判断推导出特称或单称判断的过程。 归纳推理：归

28、纳推理是从足够的事例中归纳出一般性结论的推理过程。 默认推理：默认推理又称缺省推理。它是在知识不完全的情况下假设某些条件已经具备所进行的推理。,http:/ 按所用知识的确定性划分，可以有 确定性推理：确定性推理是指推理时所用的知识都是精确的，推理出的结论也是精确的。 不精确推理：不精确推理是指在推理时所用到的知识不都是精确的，推理出的结论也不完全是肯定的。 按推理过程划分，可以有 单调推理：单调推理是指在推理的过程中随着推理的向前推进及新知识的加入，推理的结论呈单调增长的趋势，并越来越接近最终目标。 非单调推理：非单调推理是指在推理的过程中，由于新的知识的加入，不仅没有加强推出的结论，反而要

29、否定它，使得推理退回到前面的一步，重新开始。,http:/ 按启发性知识划分，可以有 启发式推理：在推理的过程中利用了能够加快推理进程、求得最优解的启发性知识的推理。 非启发性推理：在推理的过程中并不利用能够加快推理进程、求得最优解的启发性知识的推理。 按方法论划分，可以有 基于知识的推理 统计推理 直觉推理：直觉推理又称为常识性推理，是根据常识进行的一种推理。,http:/ 推理控制策略 正向推理：从用户提供的初始事实出发，在知识库中找出当前可适合的知识，构成可适用的知识集，然后按某种冲突消解策略从知识集中选出一条知识进行推理，并将推理出的新事实加入到数据库作为下一步推理的已知事实，如此重复

30、这一过程。 逆向推理：首先选定一个假设目标，然后寻找支持该假设的证据，若所需要的证据都能找到，则说明假设是成立的；若无论如何都找不到所需要的证据，说明原假设不成立。 混合推理：即有正向推理又有逆向推理的推理方法就是混合推理。 双向推理：所谓双向推理是指正向推理和逆向推理同时进行，且在某一步骤上相遇。基本思想是：一方面根据已知事实进行正向推理，但并不推到最终目标；另一方面，从某一假设目标出发进行逆向推理，但并不推至原始事实，而是让它们在途中相遇，既正向推理所得的中间结论恰好是逆向推理此时所需要求的证据。,http:/ 归结反演 归结反演就是用归结和反演的方法实现定理证明。 子句定义为由文字的析取组成的公式 谓词公式化为子句集的过程 消去蕴涵符号 把否定符号移到每个谓词符号的前面 变量标准化 消去存在量词 将公式化为前束形 把母式化为合取范式 略去全称量词 把母式用子句表示 子句变量标准化,http:/ 归结反演的一般过程：设有公式集S，希望从S证明某个目标公式W，证明的过程如下： 将W加入到S集合 将新的集合S转换成一组子句，应用归结原理推导出一个空子句 归结反演过程主要就是证明一个集合是不可满足的过程，即从集合