人工智能导论机工版教学课件第3章.pptx

1、人工智能导论学习目标学习难点p 利用搜索和推理技术进行问题求解的实现过程学习重点p搜索的概念、意义p状态空间的概念p状态空间盲目搜索p启发式状态空间搜索p遗传算法搜索p推理的概念、方法及基本类型p基于规则的演绎推理p产生式系统推理和不确定性原理面对具体问题，人工智能如何运用知识解决问题（面对具体问题，人工智能如何运用知识解决问题（思维过程）？思维过程）？p思维过程，思维过程，是人类认识客观世界后体现人类的智力功能的工作方式，往往直接体现在一个问题求解的过程中。p搜索与推理搜索与推理，就是人类重要的两个思维过程。p 机器使用知识也是主要采用搜搜索和推理技术索和推理技术【知识目标】【知识目标】p了

2、解搜索和推理的定义和意义了解搜索和推理的定义和意义p掌握状态空间的搜索策略及过程掌握状态空间的搜索策略及过程p了解基于状态空间的盲目搜索分类和特点了解基于状态空间的盲目搜索分类和特点p了解基于状态空间的启发式搜索过程了解基于状态空间的启发式搜索过程p了解正向、逆向、混合和双向等规则演绎推理方法了解正向、逆向、混合和双向等规则演绎推理方法p了解产生式系统推理基本原理了解产生式系统推理基本原理p 掌握基于概率和模糊原理的不确定性推理实现过程掌握基于概率和模糊原理的不确定性推理实现过程【能力目标】【能力目标】p能用状态空间深度优选搜索原理描述出具体问题的求解过程能用状态空间深度优选搜索原理描述出具体

3、问题的求解过程p能用启发式搜索原理描述出具体问题的求解过程能用启发式搜索原理描述出具体问题的求解过程p能用遗传算法原理描述出具体问题的求解过程，形成努力改变自己去适能用遗传算法原理描述出具体问题的求解过程，形成努力改变自己去适 应环境的世界观应环境的世界观p能用产生式推理原理描述出具体问题的求解过程能用产生式推理原理描述出具体问题的求解过程p能用模糊推理原理描述出具体问题的求解过程能用模糊推理原理描述出具体问题的求解过程3 3.1.1 搜索和推理概述搜索和推理概述 在问题求解过程中，人们所面临的大多数现实问题往往去无法获得其一致信息，更没有现成的方法可以直接求解使用，此刻，人类会。p 对于结构

4、性问题采用搜索方法p 对于非结构性问题采用推理方法 3.1.13.1.1 搜索搜索p“搜索”是“寻找隐藏的东西”p 被寻找的东西常常被称为“目标”或者“解”p 处理问题方式：明确目标搜索产生序列的动作输出p 搜索问题一般包括。目标：搜索什么 搜索空间：在哪里搜索1.搜索的含义搜索的含义3.1.13.1.1 搜索搜索p“按图索骥”的意思是按照书上的图或条文去找好马。比喻机械的按老办法办事。也比喻按照线索寻找需要的东西。p 以上寻找好马的过程就是搜索。3.1.13.1.1 搜索搜索p 搜索过程中采用的搜索策略、是否使用启发式信息分为盲目搜索和启发式搜索2.搜索的分类搜索的分类3.1.13.1.1

5、搜索搜索p 救援人员会在河流下游距离沉船点L远的地点进行搜索p 距离L=水流速度v 距离沉船多长时间tp 采用距离L来指引搜索，3.1.13.1.1 搜索搜索p 根据问题的表示方式分为状态空间搜索和与或树搜索 状态空间搜索：八字棋的状态空间，根据此空间图可以搜索得到八字棋游戏的解决路径2.搜索的分类搜索的分类3.1.13.1.1 搜索搜索p 根据问题的表示方式分为状态空间搜索和与或树搜索 与或树搜索：与或树搜索是指用问题规约法表示问题时进行的搜索。状态空间法和问题规约法是人工智能中最基本的两种问题表示和求解方法 基于与或树搜索的原理形成了与/或树的广度优先搜索、与/或树的深度优先、博弈树、-剪

6、枝技术搜索方法2.搜索的分类搜索的分类3.1.13.1.1 搜索搜索p A、B、C、D、E五个城市的连接网络图p 城市间连线上的数字代表它们的距离，如A和C城市的连线上有数字3，代表它们之间的距离为3，表示为LAC=3p 通过与或树可以获取从A城市出发到E城市的最短路程城市交通图城市交通图城市交通图与或树城市交通图与或树3.1.3.1.2 2 推理推理p 图3-8是一个简易的逻辑推理问题，有以下的约束：p 1个空心小球=3个条纹小球p 1个条纹小球=2个黑心小球p 得到结论：1个空心小球=6个黑心小球3.1.3.1.2 2 推理推理推理推理=语言语言+语义语义+推理规则推理规则u 语言：具有一

7、个句法用以规定在这种语言中什么是合法的表达。u 语义：用以把这种语言中的要素和某些主题中的要素联系起来。u 推理规则：用以操作这种语言的语句。3.1.3.1.2 2 推理推理p 按照推理的逻辑基础，常用的推理方法分为演绎推理、归纳推按照推理的逻辑基础，常用的推理方法分为演绎推理、归纳推理和默认推理理和默认推理u 归纳推理：是从足够多的事例中归纳出一般性结论的推理过程。即个别到一般的推理 完全归纳推理 不完全归纳推理3.1.3.1.2 2 推理推理p 按照推理的逻辑基础，常用的推理方法分为演绎推理、归纳推按照推理的逻辑基础，常用的推理方法分为演绎推理、归纳推理和默认推理理和默认推理u 默认推理：

8、在知识不完全的情况下假设某些条件已经具备所进行的推理3.1.3.1.2 2 推理推理p 按所用知识的确定性分类按所用知识的确定性分类u 确定性推理（精确推理）确定性推理（精确推理）：是指推理时所用的知识与证据都是确定的，退出的结论也是确定的，其真值或者为真或者为假，没有第三种情况出现。u 不确定性推理（不精确推理）不确定性推理（不精确推理）：是指推理时所用的知识与证据不都是确定的，推出的结论也是不确定的。3.1.3.1.2 2 推理推理p 推理过程的单调性分类推理过程的单调性分类u 单调推理：是指在推理过程中随着推理向前推进及新知识的加入，推出的结论越来越接近最终目标。u 非单调推理：是指在推

9、理过程中由于新知识的加入，不仅没有加强已推出的结论，反而要否定它，使推理退回到前面的某一步，然后重新开始。3.1.3.1.2 2 推理推理3.1.3.1.2 2 推理推理p 按推理中是否运用与推理有关的启发性知识来划分按推理中是否运用与推理有关的启发性知识来划分u 启发性推理启发性推理：是指在推理过程中运用与推理有关的启发性知识。u 非启发性推理非启发性推理：是指在推理过程中未运用与推理有关的启发性知识。3.1.3.1.2 2 推理推理推理的控制策略及其分类推理的控制策略及其分类推理过程不仅依赖于所用的推理方法，同时也依赖于推理的控制推理过程不仅依赖于所用的推理方法，同时也依赖于推理的控制策略

10、。策略。推理的控制策略是指如何使用领域知识使推理过程尽快达到目标推理的控制策略是指如何使用领域知识使推理过程尽快达到目标的策略的策略。推理的控制策略可分为：推理的控制策略可分为：p搜索策略搜索策略p推理策略推理策略3.1.3.1.2 2 推理推理推理的控制策略及其分类推理的控制策略及其分类搜索策略：搜索策略：在知识库中寻找可利用的知识，从而构造一条在知识库中寻找可利用的知识，从而构造一条代价较代价较小小的推理路线。主要解决推理线路、推理效果、推理效率等问题。的推理路线。主要解决推理线路、推理效果、推理效率等问题。按是否使用启发式信息可分为：按是否使用启发式信息可分为：p盲目搜索盲目搜索p启发式

11、搜索启发式搜索按问题的表示方式可分为：按问题的表示方式可分为：p状态空间搜索状态空间搜索p与或树搜索与或树搜索3.1.3.1.2 2 推理推理推理的控制策略及其分类推理的控制策略及其分类推理策略：推理策略：包括推理方向控制策略、求解策略、限制策略、冲突包括推理方向控制策略、求解策略、限制策略、冲突消解策略等消解策略等p推理方向控制策略：推理方向控制策略：用于确定推理的控制方向，可分为用于确定推理的控制方向，可分为正向推理正向推理逆向推理逆向推理混合推理混合推理双向推理双向推理3.23.2状态空间的搜索策略状态空间的搜索策略3.23.2.1 1 状态空间搜索的基本思想状态空间搜索的基本思想先把问

12、题的初始状态作为当前先把问题的初始状态作为当前扩展节点扩展节点对其进行对其进行扩展扩展，生成一组，生成一组子节点。子节点。然后检查问题的目标状态是否出现在这些子节点中。若出现，则然后检查问题的目标状态是否出现在这些子节点中。若出现，则搜索成功，找到了问题的解；若没出现，则再搜索成功，找到了问题的解；若没出现，则再按照某种搜索策略按照某种搜索策略从已生成的子节点中选择一个节点作为当前扩展节点从已生成的子节点中选择一个节点作为当前扩展节点。重复上述过程，直到目标状态出现在子节点中或者没有可供操作重复上述过程，直到目标状态出现在子节点中或者没有可供操作的节点为止。的节点为止。所谓对一个节点进行所谓对

13、一个节点进行“扩展扩展”是指对该节点用某个可用操作进行是指对该节点用某个可用操作进行作用，生成该节点的一组子节点作用，生成该节点的一组子节点。“扩展扩展”节点节点3.23.2.1 1 状态空间搜索的基本思想状态空间搜索的基本思想v状态空间搜索算法的数据结构和符号约定状态空间搜索算法的数据结构和符号约定OPEN表：表：未扩展节点表，用于存放刚生成节点未扩展节点表，用于存放刚生成节点CLOSED表：表：已扩展节点表，用于存放已经扩展或将要扩展节点的已扩展节点表，用于存放已经扩展或将要扩展节点的S：用表示问题的初始状态用表示问题的初始状态G：表示搜索过程所得到的搜索图表示搜索过程所得到的搜索图M：表

14、示当前扩展节点新生成的且不为自己先辈的子节点集表示当前扩展节点新生成的且不为自己先辈的子节点集3.23.2.1 1 状态空间搜索的基本思想状态空间搜索的基本思想3.2.2 3.2.2 图搜索的一般过程图搜索的一般过程图搜索策略可看作一种在图中寻找路径的方法。图搜索策略可看作一种在图中寻找路径的方法。3.2.2 3.2.2 图搜索的一般过程图搜索的一般过程图搜索策略图搜索策略的流程图的流程图3.3 3.3 状态空间的盲目搜索状态空间的盲目搜索盲目搜索又叫做无信息搜索，一般只适用于求解比较简单的问题盲目搜索又叫做无信息搜索，一般只适用于求解比较简单的问题。p 宽度优先搜索宽度优先搜索p 深度优先搜

15、索深度优先搜索p 代价树搜索代价树搜索3.33.3.1.1 宽度优先搜索宽度优先搜索p宽度优先搜索宽度优先搜索：从节点S开始，对他后继节点按从左至右搜索，然后再对下一级的后继节点按从左至右搜索，依此下去。p宽度优先搜索的特点宽度优先搜索的特点：以接近起始节点的程度依次扩展节点的3.33.3.1.1 宽度优先搜索宽度优先搜索1.宽度优先搜索的基本过程宽度优先搜索的基本过程3.33.3.1.1 宽度优先搜索宽度优先搜索2.宽度优先搜索的例子宽度优先搜索的例子：八数码难题八数码难题在在33的方格棋盘上，分别放置了表有数字的方格棋盘上，分别放置了表有数字1、2、3、4、5、6、7、8的八张牌，初始状态

16、的八张牌，初始状态S0，目标状态，目标状态Sg，如下图所示。要求应用广度优先，如下图所示。要求应用广度优先搜索策略寻找从初始状态到目标状态的解路径搜索策略寻找从初始状态到目标状态的解路径。1238476528314765S0Sg3.33.3.1.1 宽度优先搜索宽度优先搜索八八数数码码难难题题的的宽宽度度优优先先搜搜索索树树3.33.3.1.1 宽度优先搜索宽度优先搜索v在上述广度优先算法中需要注意两个问题：在上述广度优先算法中需要注意两个问题：对于任意一个可扩展的节点，总是按照固定的操作符的顺序对其进对于任意一个可扩展的节点，总是按照固定的操作符的顺序对其进行扩展（行扩展（空格左移、上移、右

17、移、下移空格左移、上移、右移、下移）。）。在对任一节点进行扩展的时候，在对任一节点进行扩展的时候，如果所得的某个子节点（状态）前如果所得的某个子节点（状态）前面已经出现过，则立即将其放弃，不再重复画出（不送入面已经出现过，则立即将其放弃，不再重复画出（不送入OPEN表）表）。因此，广度优先搜索的本质是，以初始节点为根节点，在状态空间因此，广度优先搜索的本质是，以初始节点为根节点，在状态空间图中按照广度优先的原则，生成一棵搜索树。图中按照广度优先的原则，生成一棵搜索树。3.33.3.2.2 深深度优先搜索度优先搜索v状态空间的深度优先搜索状态空间的深度优先搜索深度优先搜索的基本思想：深度优先搜索

18、的基本思想：p从初始节点从初始节点S开始，在其子节点中选择一个最新开始，在其子节点中选择一个最新生成的节点进行考察。生成的节点进行考察。p如果该子节点不是目标节点且可以扩展，则扩如果该子节点不是目标节点且可以扩展，则扩展该子节点，然后再在此子节点的子节点中选展该子节点，然后再在此子节点的子节点中选择一个最新生成的节点进行考察。择一个最新生成的节点进行考察。p依此向下搜索，直到某个子节点既不是目标节依此向下搜索，直到某个子节点既不是目标节点，又不能继续扩展时，才选择其兄弟节点进点，又不能继续扩展时，才选择其兄弟节点进行考察。行考察。3.33.3.2.2 深深度优先搜索度优先搜索v状态空间的深度优

19、先搜索状态空间的深度优先搜索深度优先搜索的深度优先搜索的算法流程算法流程：3.33.3.2.2 深深度优先搜索度优先搜索2.深深度优先搜索的例子度优先搜索的例子：八数码难题八数码难题在在33的方格棋盘上，分别放置了表有数字的方格棋盘上，分别放置了表有数字1、2、3、4、5、6、7、8的八张牌，初始状态的八张牌，初始状态S0，目标状态，目标状态Sg，如下图所示。要求应用广度优先，如下图所示。要求应用广度优先搜索策略寻找从初始状态到目标状态的解路径搜索策略寻找从初始状态到目标状态的解路径。1238476528314765S0Sg3.33.3.2.2 深深度优先搜索度优先搜索v深度优先搜索：深度优先

20、搜索：八数码难题八数码难题八数码难题的深度优八数码难题的深度优先搜索如右图先搜索如右图首先扩展最新产生的首先扩展最新产生的(最深的最深的)节点节点如果目标节点不在当如果目标节点不在当前搜索的分支上？前搜索的分支上？3.33.3.2.2 深深度优先搜索度优先搜索v有界深度优先搜索：有界深度优先搜索：动机：动机：为了防止搜索过程沿着无益的路径扩展下去，往往给为了防止搜索过程沿着无益的路径扩展下去，往往给出一个节点扩展的最大深度，即深度界限。出一个节点扩展的最大深度，即深度界限。思想：思想：对状态空间的深度优先搜索引入搜索深度界限，设为对状态空间的深度优先搜索引入搜索深度界限，设为dm，当搜索深度达

21、到了深度界限而仍未出现目标节点时，就，当搜索深度达到了深度界限而仍未出现目标节点时，就换一个分支进行搜索。换一个分支进行搜索。3.33.3.2.2 深深度优先搜索度优先搜索v有界深度优先搜索：有界深度优先搜索：3.33.3.2.2 深深度优先搜索度优先搜索八数码难题：八数码难题：dm=43.33.3.2.2 深深度优先搜索度优先搜索v有界深度优先搜索：有界深度优先搜索：问题：问题：如果问题有解，且其路径长度如果问题有解，且其路径长度 dm，则上述搜索过，则上述搜索过程一定能求得解。但是，若解的路径长度程一定能求得解。但是，若解的路径长度 dm,则上述搜索则上述搜索过程就得不到解。这说明在有界深

22、度优先搜索中，深度界过程就得不到解。这说明在有界深度优先搜索中，深度界限的选择是很重要的。限的选择是很重要的。要恰当地给出要恰当地给出dm的值是比较困难的。即使能求出解，它也的值是比较困难的。即使能求出解，它也不一定是最优解。不一定是最优解。3.33.3.3.3 代价树搜索代价树搜索v代价树：代价树：边上标有代价边上标有代价(或费用或费用)的树称为代价树的树称为代价树v 在代价树中，若用在代价树中，若用g(x)表示从初始节点表示从初始节点S到节点到节点x的代价，用的代价，用c(x1,x2)表示从父表示从父节点节点x1到子节点到子节点x2的代价，则有：的代价，则有：g(x2)=g(x1)+c(x

23、1,x2)v代价树搜索：代价树搜索：考虑边的代价的搜索方法，代价树搜索的目的是为了找到考虑边的代价的搜索方法，代价树搜索的目的是为了找到一条代价最小的解路径。代价树搜索方法包括：一条代价最小的解路径。代价树搜索方法包括：代价树的宽度优先搜索代价树的宽度优先搜索代价树的深度优先搜索代价树的深度优先搜索3.33.3.3.3 代价树搜索代价树搜索v 代价树的宽度优先搜索算法流程：代价树的宽度优先搜索算法流程：(1)把初始节点把初始节点S放入放入OPEN表中，置表中，置S的代价的代价g(S)=0；(2)如果如果OPEN表为空，则问题无解表为空，则问题无解，失败退出；，失败退出；(3)把把OPEN表的第

24、一个节点取出放入表的第一个节点取出放入CLOSED表，并记该节点为表，并记该节点为n；(4)考察节点考察节点n是否为目标。若是，则找到了问题的解，成功退出；是否为目标。若是，则找到了问题的解，成功退出；(5)若节点若节点n不可扩展，则转第不可扩展，则转第(2)步；否则转第步；否则转第(6)步；步；(6)扩展节点扩展节点n，为每一个子节点都配置指向父节点的指针，计算各子节点的，为每一个子节点都配置指向父节点的指针，计算各子节点的代价，并将各子节点放入代价，并将各子节点放入OPEN表中。表中。并根据各子结点的代价对并根据各子结点的代价对OPEN表中的表中的全部结点全部结点按由小到大的顺序排序按由小

25、到大的顺序排序。然后转第。然后转第(2)步。步。3.33.3.3.3 代价树搜索代价树搜索v 代价树的宽度优先搜索算法流程：代价树的宽度优先搜索算法流程：3.33.3.3.3 代价树搜索代价树搜索v 代价树的宽度优先搜索例子：代价树的宽度优先搜索例子：v例子：例子：城市交通问题。设有城市交通问题。设有5个城市，它们之间的交通线路如下方左图所个城市，它们之间的交通线路如下方左图所示，图中的数字表示两个城市之间的交通费用，即代价。用代价树的广度示，图中的数字表示两个城市之间的交通费用，即代价。用代价树的广度优先搜索，求从优先搜索，求从A市出发到市出发到E市，费用最小的交通路线。市，费用最小的交通路

26、线。ABCDE43 4 523城市交通图城市交通图3.33.3.3.3 代价树搜索代价树搜索v 代价树的宽度优先搜索例子：代价树的宽度优先搜索例子：v解：解：首先将交通图转化为代价树。具体转化首先将交通图转化为代价树。具体转化方法如下：方法如下：从起始节点从起始节点A开始，把与它直接相邻的节点作为它开始，把与它直接相邻的节点作为它的子节点的子节点 对其他节点也做相同的处理对其他节点也做相同的处理 若一个节点已经为某节点的直系先辈节点时，就不若一个节点已经为某节点的直系先辈节点时，就不能作为这个节点的子节点。能作为这个节点的子节点。图中除了起始节点图中除了起始节点A之外，其它节点都可能要在代之外

27、，其它节点都可能要在代价树中出现多次，为了区分它们的多次出现，分别价树中出现多次，为了区分它们的多次出现，分别用下标用下标1,2，标出标出城市交通图的代价树城市交通图的代价树2 4 5AC1B1D1D2E1E2B2C2E3E43 43 4 2 353.33.3.3.3 代价树搜索代价树搜索v解：解：对此代价树进行广度优先搜索，可得到最优解，如图红线部对此代价树进行广度优先搜索，可得到最优解，如图红线部分为最优解，其代价为分为最优解，其代价为8ABCDE43 4 5232 4 5AC1B1D1D2E1E2B2C2E3E43 43 4 2 353.33.3.3.3 代价树搜索代价树搜索v代价树的深

28、度优先搜索代价树的深度优先搜索基本思想：基本思想：与代价树的广度优先搜索不同，代价树的深度优先搜与代价树的广度优先搜索不同，代价树的深度优先搜索是索是从刚扩展出的子节点中选择从刚扩展出的子节点中选择一个代价最小的节点送入一个代价最小的节点送入CLOSED表进行考察，而不是在整个表进行考察，而不是在整个OPEN表中选择代价最小的。表中选择代价最小的。3.33.3.3.3 代价树搜索代价树搜索v代价树的深度优先搜索代价树的深度优先搜索3.43.4 状态空间的启发式搜索状态空间的启发式搜索v状态空间的盲目搜索状态空间的盲目搜索上述几种搜索方法的本质是，以初始节点为根节点，按照既定上述几种搜索方法的本

29、质是，以初始节点为根节点，按照既定的策略对状态空间图进行遍历，并希望能够尽早发现目标节点。的策略对状态空间图进行遍历，并希望能够尽早发现目标节点。由于对状态空间图遍历的策略是既定的，因此这些方法统称为由于对状态空间图遍历的策略是既定的，因此这些方法统称为盲目搜索方法。盲目搜索方法。盲目搜索具有较大的盲目性，产生的无用节点较多，效率不高。盲目搜索具有较大的盲目性，产生的无用节点较多，效率不高。3.4.13.4.1 启发性信息和估价函数启发性信息和估价函数v启发式搜索：启发式搜索：采用问题自身的特性信息，以指导搜索朝着最有希望的方向前采用问题自身的特性信息，以指导搜索朝着最有希望的方向前进。进。v

30、启发性信息的概念：启发性信息的概念：启发性信息是指那种与具体问题求解过程有关的，并可启发性信息是指那种与具体问题求解过程有关的，并可指导搜索过程朝着最有希望方向前进的控制信息。指导搜索过程朝着最有希望方向前进的控制信息。启发信息的启发能力越强，启发信息的启发能力越强，扩展的无用结点越少。扩展的无用结点越少。v启发性信息的种类启发性信息的种类有效地帮助确定扩展节点的信息有效地帮助确定扩展节点的信息有效的帮助决定哪些后继节点应被生成的信息有效的帮助决定哪些后继节点应被生成的信息能决定在扩展一个节点时哪些节点应从搜索树上删除的信息能决定在扩展一个节点时哪些节点应从搜索树上删除的信息3.4.13.4.

31、1 启发性信息和估价函数启发性信息和估价函数v估价函数：估价函数：用于评估节点重要性的函数称为估价函数。估价函数的用于评估节点重要性的函数称为估价函数。估价函数的一般形式为：一般形式为：f(x)=g(x)+h(x)g(x)表示从初始节点表示从初始节点S0到节点到节点x的代价；的代价；h(x)是从节点是从节点x到目标节点到目标节点Sg的最优路径的代价的的最优路径的代价的估计估计，它体现了，它体现了问题的启发性信息。问题的启发性信息。h(x)称为称为启发函数启发函数。3.4.13.4.1 启发性信息和估价函数启发性信息和估价函数v例子：例子：八数码难题八数码难题设问题的初始状态设问题的初始状态S0

32、和目标状态和目标状态Sg如图所示如图所示估价函数为：估价函数为：f(n)=d(n)+W(n)d(n)：表示节点：表示节点n在搜索树中的深度在搜索树中的深度W(n)：表示节点：表示节点n中中“不在位不在位”的数码个数的数码个数请计算初始状态请计算初始状态S0的估价函数值的估价函数值f(S0)1238476528314765S0Sg3.4.13.4.1 启发性信息和估价函数启发性信息和估价函数v计算初始状态计算初始状态S0的估价函数值的估价函数值f(S0)v解：解：取取g(n)=d(n)，h(n)=W(n)它说明是用从它说明是用从S0到到n的路径上的单位代价表示实际代的路径上的单位代价表示实际代价

33、价 用结点用结点n中中“不在位不在位”的数码个数作为启发信息。的数码个数作为启发信息。一般来说，某节点中的一般来说，某节点中的“不在位不在位”的数码个数越多，的数码个数越多，说明它离目标节点越远（代价的估计）。说明它离目标节点越远（代价的估计）。对初始节点对初始节点S0，d(S0)=0，W(S0)=3。因此，。因此，f(S0)=0+3=3 1238476528314765S0Sg3.4.3.4.2 2 A A算法算法vA算法：算法：在图搜索算法中，如果能在搜索的每一步都在图搜索算法中，如果能在搜索的每一步都利用估价函数利用估价函数f(n)=g(n)+h(n)对对OPEN表中的节点进行排序表中的

34、节点进行排序，则该搜索算法为，则该搜索算法为A算法算法。由于估价由于估价函数中带有问题自身的启发性信息，因此，函数中带有问题自身的启发性信息，因此，A算法也被称为算法也被称为启发式搜索算法启发式搜索算法。vA算法的类型：算法的类型：可根据搜索过程中选择扩展节点的范围，将启发式搜索算法分可根据搜索过程中选择扩展节点的范围，将启发式搜索算法分为：为：全局择优搜索算法全局择优搜索算法：从从OPEN表的表的所有节点所有节点中选择一个估价函数值最小的一中选择一个估价函数值最小的一个进行扩展。个进行扩展。局部择优搜索算法：局部择优搜索算法：仅从刚生成的子节点仅从刚生成的子节点中选择一个估价函数值最小的一个

35、中选择一个估价函数值最小的一个进行扩展。进行扩展。3.4.3.4.2 2 A A算法算法3.4.3.4.2 2 A A算法算法3.4.3.4.2 2 A A算法算法v全局择优搜索算法：全局择优搜索算法：八数码难题八数码难题设问题的初始状态设问题的初始状态S0和目标状态和目标状态Sg如图所示如图所示估价函数为：估价函数为：f(n)=d(n)+W(n)d(n)：表示节点：表示节点n在搜索树中的深度在搜索树中的深度W(n)：表示节点：表示节点n中中“不在位不在位”的数码个数的数码个数用全局择优搜索解决该问题用全局择优搜索解决该问题1238476528314765S0Sg3.4.3.4.2 2 A A

36、算法算法v 用全局择优搜索求解八数码难题用全局择优搜索求解八数码难题v 解：解：该问题的全局择优搜索树如右图所示该问题的全局择优搜索树如右图所示 在该图中，每个节点旁边的数字是该节点的估在该图中，每个节点旁边的数字是该节点的估价函数值价函数值 该问题的解为：该问题的解为：S0S1S2S3Sg表3-10 各节点的估价值3.3.5 5 遗传算法搜索遗传算法搜索 遗传算法是模仿生物遗传学和自然选择机理，通过人工方式构造的一类优化搜遗传算法是模仿生物遗传学和自然选择机理，通过人工方式构造的一类优化搜索算法，是对生物进化过程进行的一种数学仿真，是进化计算的一种最重要形式。索算法，是对生物进化过程进行的一

37、种数学仿真，是进化计算的一种最重要形式。染色体染色体(chromosome)：生物生物的遗传物质的主要载体。的遗传物质的主要载体。基因基因(gene)：扩展生物性状扩展生物性状的遗传物质的功能单元和结的遗传物质的功能单元和结构单位。构单位。基因座（基因座（locus）：染色体：染色体中基因的位置。中基因的位置。等位基因（等位基因（alleles）：基因：基因所取的值。所取的值。3.3.5 5 遗传算法搜索遗传算法搜索生物遗传概念生物遗传概念遗产算法中的应用遗产算法中的应用适者生存适者生存目标值比较大的解被选择的可能性大目标值比较大的解被选择的可能性大个体（个体（Individual）解解染色体

38、（染色体（Chromosome）解的编码（字符串、向量等）解的编码（字符串、向量等）基因（基因（Gene）解的编码中每一分量解的编码中每一分量适应性（适应性（Fitness）适应度函数值适应度函数值群体（群体（Population）根据适应度值选定的一组解（解的个数为群体的根据适应度值选定的一组解（解的个数为群体的规模）规模）婚配（婚配（Marry）交叉（交叉（Crossover）选择两个染色体进行交叉产生）选择两个染色体进行交叉产生一组新的染色体的过程一组新的染色体的过程变异（变异（Mutation）编码的某一分量发生变化的过程编码的某一分量发生变化的过程3.5.1 3.5.1 遗传算法的结

39、构遗传算法的结构 霍兰德提出的遗传算法通常称为简单遗传算法（霍兰德提出的遗传算法通常称为简单遗传算法（SGA）。现以此作为讨论主要）。现以此作为讨论主要对象，加上适应的改进，来分析遗传算法的结构和机理。在讨论中会结合销售员旅对象，加上适应的改进，来分析遗传算法的结构和机理。在讨论中会结合销售员旅行问题（行问题（TSP）来说明。）来说明。1.编码与解码编码与解码 许多应用问题的结构很复杂，但可以化为简单的位串形式编码表示。将问题结许多应用问题的结构很复杂，但可以化为简单的位串形式编码表示。将问题结构变换为位串形式编码表示的过程叫编码；而相反将位串形式编码表示变换为原问构变换为位串形式编码表示的过

40、程叫编码；而相反将位串形式编码表示变换为原问题结构的过程叫解码或译码。把位串形式编码表示叫染色体，有时也叫个体。题结构的过程叫解码或译码。把位串形式编码表示叫染色体，有时也叫个体。3.5.1 3.5.1 遗传算法的结构遗传算法的结构例：对于销售员旅行问题（例：对于销售员旅行问题（Travelling salesman Problem,TSP），设有），设有n个城市个城市，城市，城市i和城市和城市j之间的距离为之间的距离为d(i,j)，要求找到一条遍访每个城市一次而且恰好一次，要求找到一条遍访每个城市一次而且恰好一次的旅行线路，使其路径总长度为最短。按一条回路中城市的次序进行编码。从城的旅行线路

41、，使其路径总长度为最短。按一条回路中城市的次序进行编码。从城市市w1开始，依次经过城市开始，依次经过城市w2，wn，最后回到城市，最后回到城市w1，我们就有如下编码表，我们就有如下编码表示：示：w1 w2 wn由于是回路，记由于是回路，记wn+1=w1。它其实是。它其实是1，n的一个循环排列。要注意的一个循环排列。要注意w1，w2，wn是互不相同的。是互不相同的。3.5.1 3.5.1 遗传算法的结构遗传算法的结构2.适应度函数适应度函数 为了体现染色体的适应能力，引入了对问题中的每一个染色体都能进行度量为了体现染色体的适应能力，引入了对问题中的每一个染色体都能进行度量的函数，叫适应度函数（的

42、函数，叫适应度函数（fitness function）。）。TSP的目标是路径总长度为最短，自的目标是路径总长度为最短，自然地，路径总长度的倒数就可作为然地，路径总长度的倒数就可作为TSP问题的适应度函数问题的适应度函数:其中其中wn+1=w1适应度函数要有效反映每一个染色体与问题的最优解染色体之间的差距。适应度函数要有效反映每一个染色体与问题的最优解染色体之间的差距。适应度函数的取值大小与求解问题对象的意义有很大的关系。适应度函数的取值大小与求解问题对象的意义有很大的关系。n1j1jj21)w,d(w/1),.,(nwwwf3.5.1 3.5.1 遗传算法的结构遗传算法的结构3.遗传操作遗传

43、操作简单遗传算法的遗传操作主要有有三种简单遗传算法的遗传操作主要有有三种:选择选择(selection)、交叉、交叉(crossover)、变、变异异(mutation)。改进的遗传算法大量扩充了遗传操作，以达到更高的效率。改进的遗传算法大量扩充了遗传操作，以达到更高的效率。选择操作也叫复制（选择操作也叫复制（reproduction）操作，根据个体的适应度函数值所度量）操作，根据个体的适应度函数值所度量的优劣程度决定它在下一代是被淘汰还是被遗传。的优劣程度决定它在下一代是被淘汰还是被遗传。简单遗传算法采用赌轮选择机制，令简单遗传算法采用赌轮选择机制，令fi表示群体的适应度值之总和，表示群体的

44、适应度值之总和，fi表示表示种群中第种群中第i个染色体的适应度值，它产生后代的能力正好为其适应度值所占份额个染色体的适应度值，它产生后代的能力正好为其适应度值所占份额fi/fi。3.5.1 3.5.1 遗传算法的结构遗传算法的结构3.遗传操作遗传操作交叉操作的简单方式是将被选择出的两个个体交叉操作的简单方式是将被选择出的两个个体P1和和P2作为父母个体，将两作为父母个体，将两者的部分码值进行交换。者的部分码值进行交换。产生一个产生一个17之间的随机数之间的随机数c，假设为，假设为3，则将，则将P1和和P2的低的低3位交换位交换10001110P1：11011001P2：3.5.1 3.5.1

45、遗传算法的结构遗传算法的结构3.遗传操作遗传操作1 0 0 0 1 1 1 0P1：1 1 0 1 1 0 0 1P2：1 0 0 0 1 0 0 11 1 0 1 1 1 1 0Q1：Q2：3.5.1 3.5.1 遗传算法的结构遗传算法的结构3.遗传操作遗传操作变异操作的简单方式是改变数码串的某个位置上的数码。二进制编码表变异操作的简单方式是改变数码串的某个位置上的数码。二进制编码表示的简单变异操作是将示的简单变异操作是将0与与1互换：互换：0变异为变异为1，1变异为变异为0。随机产生一个随机产生一个18之间的数之间的数k，假设，假设k=5，对从右往左第，对从右往左第5位变异操作。位变异操作

46、。1010011013.5.1 3.5.1 遗传算法的结构遗传算法的结构4.控制参数控制参数 交叉发生的概率：交叉发生的概率：0.60.95 变异的概率：变异的概率：0.0010.01 种群的个数：种群的个数：30100 个体的长度：定长和变长个体的长度：定长和变长 3.5.23.5.2遗传算法的基本原理遗传算法的基本原理3.5.23.5.2遗传算法的基本原理遗传算法的基本原理开始开始初始化种群初始化种群选择操作选择操作终止条件终止条件否否适应度最有优个体适应度最有优个体计算适应度值计算适应度值交叉操作交叉操作变异操作变异操作结束结束选择：由个体适应度值决定选择：由个体适应度值决定 的某个规则

47、。的某个规则。交叉：按概率交叉：按概率Pc进行进行变异：按概率变异：按概率Pm进行进行终止条件：终止条件：完成了预先给定的进化代数完成了预先给定的进化代数 种群中的最优个体在连续若干代种群中的最优个体在连续若干代 没有改进或平均适应度在连续若没有改进或平均适应度在连续若 干代基本没有改进干代基本没有改进3.5.33.5.3 遗传算法的性能遗传算法的性能 遗传算法求得的解是一满意解。影响解质量的因素：遗传算法求得的解是一满意解。影响解质量的因素：种群的数量：太小缺少多样性，太多影响效率种群的数量：太小缺少多样性，太多影响效率 适应度函数：提升优良个体的适应度适应度函数：提升优良个体的适应度 交叉

48、和变异：不同的问题需构造性能更优的交叉和变异操作交叉和变异：不同的问题需构造性能更优的交叉和变异操作 交叉概率和变异概率：交叉概率和变异概率：3.6 3.6 基于规则的演绎推理基于规则的演绎推理基于规则的演绎推理基于规则的演绎推理正向推理正向推理反向推理反向推理正反向混合推理正反向混合推理3.6.1 3.6.1 正向推理正向推理正向推理：是以事实作为出发点的一种推理。正向推理：是以事实作为出发点的一种推理。基本思想基本思想：从用户提供的初始已知事实出发，在知识库：从用户提供的初始已知事实出发，在知识库KB中找出当中找出当前可适用的知识，构成可适用知识集前可适用的知识，构成可适用知识集KS，然后

49、按某种冲突消解策略从，然后按某种冲突消解策略从KS中选出一条知识进行推理，并将推出的新事实加入到数据库中作为中选出一条知识进行推理，并将推出的新事实加入到数据库中作为下一步推理的已知事实，此后再在下一步推理的已知事实，此后再在KB中选取可适用的知识进行推理中选取可适用的知识进行推理，如此重复这一过程，直到求得了问题的解或者知识库中再无可适用，如此重复这一过程，直到求得了问题的解或者知识库中再无可适用的知识为止。的知识为止。3.6.3.6.2 2 逆向推理逆向推理逆向推理：逆向推理：是以某个假设目标为出发点的一种推理。是以某个假设目标为出发点的一种推理。基本思想基本思想：首先选择一个假设目标，然

50、后寻找支持该假设的证据，若：首先选择一个假设目标，然后寻找支持该假设的证据，若需的证据都能找到，则说明原假设是成立的；若无论如何都找不到所需的证据都能找到，则说明原假设是成立的；若无论如何都找不到所需的证据，则说明原假设不成立，为此需要另作新的假设。需的证据，则说明原假设不成立，为此需要另作新的假设。3.6.3.6.3 3 混合混合推理推理 正向推理具有盲目、效率低等缺点，推理过程中可能会推出许正向推理具有盲目、效率低等缺点，推理过程中可能会推出许多与问题无关的子目标。逆向推理中，若提出的假设目标不符合实多与问题无关的子目标。逆向推理中，若提出的假设目标不符合实际，也会降低系统效率。可以把正向