1、目录1.人工智能概述2.用搜索求解问题的基本原理3.搜索的基本策略4.图搜索策略5.博弈与搜索1目录6.演化搜索算法7.群集智能算法8.知识表示与处理方法9.机器学习10.智能机器人2目录1 1.人工智能概述人工智能概述2.用搜索求解问题的基本原理3.搜索的基本策略4.图搜索策略5.博弈与搜索34第一讲 概述人工智能概述l 人工智人工智能能（Artificial Intelligence，AI）是研究、开发用于模拟、延伸和扩展人的智能用于模拟、延伸和扩展人的智能的理论、方法、技术及应用系统的一门新的技术科学。l 人工智能自20世纪70年代以来被称为世界三大尖端技术世界三大尖端技术（空间技术、能
2、源技术、人工智能）之一，也被认为是2121世纪三大尖端技术世纪三大尖端技术（基因工程、纳米科学、人工智能）之一。l 人类的自然智能自然智能伴随着人类活动无时不在、无处不在。人类的许多活动，如解题、下棋、猜谜、写作、编制计划和编程，甚至驾车骑车等，都需要智能。如果机器能够完成这些任务的一部分机器能够完成这些任务的一部分，那么就可以认为机器已经具有某种程度的“人工智能”。5第一讲 概述AI的起源AI的起源可以追溯到丘奇（Church）、图灵（Turing）和其他一些学者关于计算本质计算本质的思想萌芽。早在20世纪30年代，他们就开始探索形式推理概念形式推理概念与即将发明的计算机之计算机之间的联系间
3、的联系，建立起了关于计算和符号处理计算和符号处理的理论。早在计算机产生之前，丘奇和图灵就已发现，数值计算并数值计算并不是计算的主要方面不是计算的主要方面。被称为“人工智能之父人工智能之父”的图灵，不仅仅创造了一个简单的非数字计算模型，而且直接证明了计算机可能以某种智能的方式进行工作，这就是人工智能的思想的萌芽。6第一讲 概述符号主义学派1.1.符号主义（符号主义（SymbolicismSymbolicism）学派）学派：符号主义又称为逻辑主义（Logicis）、心理学派（Psychlogism）或计算机学派（Computerism）。该学派认该学派认为人工智能源于数理逻辑为人工智能源于数理逻辑
4、。数理逻辑在19世纪获得迅速发展，到20世纪30年代开始用于描述智能行为。计算机产生以后，又在计算机上实现了逻辑演绎系统，其代表的成果代表的成果为启发式程序为启发式程序LTLT（逻辑理论家）（逻辑理论家），人们使用它证明了38个数学定理，从而表明了人类可利用计算机模拟人类的智能表明了人类可利用计算机模拟人类的智能活动活动。代表人物：约翰麦卡锡7第一讲 概述符号主义学派lAI的核心问题是知识表示、知识推理和知识运用。l知识可用符号表示，也可用符号进行推理。l符号主义就是在这种假设之下，建立起基于知识的人类智能和机器智能的核心理论体系。l至今符号主义仍是AI的主流派。8第一讲 概述联结主义学派2.
5、2.联结主义（联结主义（ConnetionismConnetionism）学派：）学派：联结主义又称仿生学派（Bionicsism）或生理学派（Physiogism），是基于生物进化论的基于生物进化论的AIAI学派学派，其主要理论基础为神经网络及神经网络间的连接机制与学习算法神经网络及神经网络间的连接机制与学习算法。联结主义认为AIAI源于仿生学，特源于仿生学，特别是对人脑模型的研究别是对人脑模型的研究，认为人的思维基元是神经元，而不是符号处理过程，人脑不同于电脑，并提出联结主义的大脑工作模式，提出联结主义的大脑工作模式，用于否定基于符号操作的电脑工用于否定基于符号操作的电脑工作模式作模式。美
6、国 心理学家爱德华李桑代克（1874-1949）9第一讲 概述行为主义学派3 3行为主义（行为主义（ActionismActionism）学派：）学派：行为主义又称为进化主义（Evolutionism）或控制论学派（Cyberneticsism），其原理为控制论及原理为控制论及“感知感知动作动作”型控制系统型控制系统。行为主义提出了智能行为的“感知动作”模式，认为：u 智能取决于感知和行动智能取决于感知和行动；u 人工智能可以像人类智能一样人工智能可以像人类智能一样 逐步进化逐步进化；u 智能行为只能在现实世界中与智能行为只能在现实世界中与 周围环境交互作用而表现出来周围环境交互作用而表现出来
7、。美国 机器人制造专家罗德尼布鲁克斯（1954-）10第一讲 概述知识工程l 19771977年年著名的人工智能专家爱德华爱德华费根鲍姆（费根鲍姆（E.FeigenbaumE.Feigenbaum）在第5届国际人工智能会议(IJCAI)上，以人工智能的艺术：知识工程的课题及实例研究为题，对知识工程作了全面论述。从此，知识工程这个术语为全世界广泛使用，费根鲍姆因此被誉为“知识工程知识工程之父之父”。美国 人工智能专家爱德华费根鲍姆（1936-）11第一讲 概述图灵测试l 19501950年年，英国数学家图灵图灵提出了一个测试方法来确定一个机器能否思考。l 该方法需要两个人对机器进行测试，其中一人
8、扮演提问者，另外一人作为被测人员。这两人与机器分别处在三个不同的房间，提问者通过打印问题和接受打印问题来与被测人员和被测机器进行通迅。提问者可以向被测机器和被测人 提问，但他只知道接受提问的是 A或B，但并不知道他是人还是机 器，并试图确定他们谁是机器，谁是人。英国数学家，逻辑学家艾伦麦席森图灵（1912-1954）12第一讲 概述图灵测试l 进行多次测试后，如果有超过超过30%30%的测试者不能确定出被测试者是人还是机器，那么这台机器就通过了测试，并被认为具有人类智能。l 图灵测试一词来源于计算机科学和密码学的先驱艾伦麦席森图灵写于1950年的一篇论文计算机器与智能，其中30%30%是图灵对
9、是图灵对20002000年时的机器思考能力的一个年时的机器思考能力的一个预测预测，目前我们已远远落后于这个预测13第一讲 概述人工智能的技术特征l 人工智能作为一门科学，有其独特的技术特征，主要表现为：1.1.利用搜索利用搜索2.2.利用知识利用知识3.3.利用抽象利用抽象4.4.利用推理利用推理5.5.利用学习利用学习6.6.遵循有限合理性原则遵循有限合理性原则目录1.人工智能概述2 2.用搜索求解问题的基本原理用搜索求解问题的基本原理3.搜索的基本策略4.图搜索策略5.博弈与搜索1415搜索求解的基本思路l 搜索搜索：利用计算机强大的计算能力来解决人类智能可以解决人类智能可以解决的问题解决
10、的问题。l 思路：把问题的各个可能的解各个可能的解交给计算机进行处理，从中找出问题的最终解最终解或一个较为满意的解较为满意的解，从而可以用接近算法的角度，把搜索的过程理解为根据初始条件初始条件和拓展规则拓展规则构造一个解答空间解答空间，并在这个空间中寻找符合符合目标状态目标状态的过程。16搜索过程三大要素搜索对象17搜索过程三大要素搜索对象l 状态空间：状态空间：问题的状态空间（state space）是一个表示该问题全部可能状态及其关系全部可能状态及其关系的集合。有离散和连续两种，由于真正的连续空间问题难以在计算机中表示，因此一般讨论的状态空间为离散状态空间离散状态空间。l 它包含三种类型的
11、集合：该问题所有可能的初始状态集合S 操作符集合F 目标状态集合G因此，可把状态空间记为三元组（三元组（S S，F F，G G）。l 状态空间通常以图图的形式出现，图上的节点节点代表对应问题的状态状态，节点之间的边边对应的是状态转移的可能性可能性，边上的权权值值代表转移所需的代价代价。18搜索过程三大要素拓展规则l 拓展规则：由控制策略控制策略和生成系统生成系统两部分组成。u 控制策略：包括节点扩展顺序选择节点扩展顺序选择，算子选择算子选择，数据维护数据维护，搜索回路判定搜索回路判定，目标测试目标测试等。u 生成系统：由约束条件约束条件和算子算子组成。l 几乎所有搜索算法的改进都是通过修改或优
12、化控制结构修改或优化控制结构来实现的，其中遗传算法中对算子的改进比较特别，而从遗传算法中有衍生处很多算法。l 算子：使问题从一种状态变化为另一种状态的手段一种状态变化为另一种状态的手段称为操作操作符符或算子（算子（operatoroperator）。算子可能是某种动作，过程，规划，数学算子，运算符等。19搜索过程三大要素目标测试l 目标测试包含两层含义：是否满足所有限制条件限制条件（条件宽条件宽，与目标非常接近即可）是不是目标目标（条件紧条件紧，必须与目标完全相符）l 宽条件一般指：当目标状态未知目标状态未知，而求解只需要接近目标即只需要接近目标即可时可时定下的条件，这种条件或是由问题本身限定
13、，或是人为设置。例如分支有界的深度，遗传算法的遗传代数等。l 紧条件一般指：当目标状态已知目标状态已知，直接判定是否达到这些状态。20基本思想l 通过搜索求解问题的前提是凭借人类自身智能可以解决前提是凭借人类自身智能可以解决，在搜索之前应对问题有充分的认识后再考虑选用合适的搜索算法。l 搜索求解问题的基本思想基本思想：将问题中的已知条件已知条件看成状态空间中初始状态初始状态；将问题中要求的目标要求的目标看成状态空间中目标状态目标状态；将问题中其它可能的情况其它可能的情况看成状态空间的任一状态任一状态 设法在状态空间寻找一条路径路径，由初始状态出发，能由初始状态出发，能够沿着这条路径达到目标状态
14、够沿着这条路径达到目标状态21基本步骤l 搜索求解问题的基本步骤基本步骤：根据问题，定义出相应的状态空间定义出相应的状态空间，确定出状态的一确定出状态的一般表示般表示，它含有相关对象的各种可能的排列。这里仅仅是定义这个空间的状态，而不必枚举该状态空间的不必枚举该状态空间的所有状态所有状态，但由此可以得出问题的初始状态初始状态、目标状目标状态态，并能够给出所有其它状态的一般表示其它状态的一般表示。规定一组算子算子,能够使状态从一个状态变为另一个状从一个状态变为另一个状态态。决定一种搜索策略搜索策略，使得能够从初始状态出发，沿某从初始状态出发，沿某个路径达到目标状态个路径达到目标状态。22问题特征
15、分析l 为选择最适合于特定问题最适合于特定问题的搜索方法，需要对问题的几个关键指标或特征关键指标或特征加以分析。一般需要考虑以下几点：u 问题可分解成独立的，更小，更容易解决独立的，更小，更容易解决的子问题子问题吗？u 当结果表明解题步骤不合适解题步骤不合适的时，能忽略或撤回忽略或撤回吗？u 问题的全域可预测全域可预测吗？u 在未与所有其它可能解作比较之前，能说当前的解是最当前的解是最好好的吗？u 用于求解问题的知识库是相容知识库是相容的吗？u 求解问题一定需要大量的知识需要大量的知识吗？或者说，有大量知识时候，搜索时应加以限制吗？u 只把问题交给电脑，电脑就能返回答案吗？或者说，为得到问题的
16、解，需要人机交互需要人机交互吗？目录1.人工智能概述2.用搜索求解问题的基本原理3.3.搜索的基本策略搜索的基本策略4.图搜索策略5.博弈与搜索2324盲目搜索方法l 盲目搜索盲目搜索方法又叫非启发式搜索非启发式搜索，是一种无信息搜索无信息搜索（uninformed search），一般只适用于求解比较简单适用于求解比较简单的问题的问题。下面我们要讨论的几个搜索方法，它们均属于盲目搜索方法。25宽度优先搜索l 在一个搜索树搜索树中，如果搜索是以同层邻近节点依次扩展同层邻近节点依次扩展节点的,那么这种搜索就叫宽度优先搜索宽度优先搜索（breath-first search）,这种搜索是逐层逐层进
17、行的,在对下一层的任一节点进行搜索之前,必须搜索完本层的所有节点必须搜索完本层的所有节点 26深度优先搜索l 与宽度优先搜索对应的一种盲目搜索方法叫做深度优先深度优先搜索搜索（depth-first search）。在深度优先搜索中,我们首先扩展最新产生的首先扩展最新产生的(即最深的即最深的)节点节点。深度相等的节深度相等的节点可以任意排列点可以任意排列。27分支有界搜索l 分枝有界搜索分枝有界搜索（branch-and-bound）也是一种深度优深度优先搜索先搜索，但每个分支都规定了一个统一的搜索深度每个分支都规定了一个统一的搜索深度，搜索到这个深度后，如果没有找到目标便自动退回到上一如果没
18、有找到目标便自动退回到上一层层，继续搜索。1 12 25 53 36 68 89 94 47 71010111128迭代加深搜索l 迭代加深搜索迭代加深搜索（iterative deepening）：在分支有界分支有界搜索搜索的基础上，对界界dmaxdmax进行迭代进行迭代，保证了对宽度节点的搜索，如果没有找到解，再加深深度如果没有找到解，再加深深度。1 12 25 53 36 68 89 94 47 71010111129一个盲目搜索问题的几种实现l 马踏棋盘问题算出中国象棋中“马”的行进位置：对于中国象棋，如果马当前所在的位置是当前所在的位置是(x,yx,y),它跳一步可能到达的位置最多有
19、8个。要求设计一个算法，对于给定目标位置目标位置tptp，输出马从初始初始位置位置cpcp出发，通过搜索搜索达到坐标位置的路径路径。1234567234马567x xy y30一个盲目搜索问题的几种实现l 求解过程如下：定义状态空间定义状态空间：设状态空间为10109 9的矩阵的矩阵（中国象棋棋盘为10行9列）定义操作规则定义操作规则：马走棋盘可以模拟成一个搜索过程搜索过程：每到一处，总让它按按8 8个方向顺序试探下一个位置个方向顺序试探下一个位置；如果某方向可以通过，并且在前面的搜索过程中不曾到达，则可以前进一步；在新位置上按上述方法重新搜索，并将到达的位置标记31一个盲目搜索问题的几种实现
20、 定义搜索策略：定义搜索策略：1.宽度优先宽度优先搜索：沿着8个搜索方向，如果可行，都前进如果可行，都前进一步一步，看看是否到达目标位置tp。如果没到达就再从新的再从新的8 8个位置继续前进个位置继续前进，直到到达目标位置2.深度优先深度优先搜索：沿着8个方向中的某一个方向前进一步某一个方向前进一步，看看是否到达目标位置tp，如果没到达，就在从这个位置选一个方向再前进一步选一个方向再前进一步，直至到达。当这条分支搜索不搜索不通时，再更换下一个方向通时，再更换下一个方向继续搜索3.分支有界分支有界搜索：在深度优先的基础上，设定最大搜索步设定最大搜索步数，若达到这个步数，则立即更换下一个方向数，若
21、达到这个步数，则立即更换下一个方向继续搜索32启发式搜索l 盲目搜索的效率低，耗费过多的时间。l 如果能够找到一种方法用于排列待扩展节点的顺序排列待扩展节点的顺序，即选择最有希望的节点加以扩展选择最有希望的节点加以扩展，那么，搜索效率将会大大提高。启发式搜索启发式搜索就是基于这种想法,它是深度优先深度优先的改进的改进。搜索时不是任取一个分枝，而是根据一些启发不是任取一个分枝，而是根据一些启发式信息，选择最佳一个分枝或几个分枝往下搜索式信息，选择最佳一个分枝或几个分枝往下搜索。33启发式信息的表示l 启发式搜索的依据依据：启发式搜索作为一种基本的搜索方法，其主要根据如下 人们善于利用一些线索来帮
22、助自己选择搜索方向利用一些线索来帮助自己选择搜索方向，这些线索线索统称为启发式信息启发式信息(启发式Heuristics，源自希腊语heuriskein，意为“发现”)现实问题往往只需一个解现实问题往往只需一个解，而不要求最优解最优解或全部解全部解 启发式信息可以避免某些领域里的组合爆炸问题可以避免某些领域里的组合爆炸问题34启发式信息的表示l 搜索方向的选择：搜索过程的目的在于：在问题空间中找出从开始状态到目标状态的一条最好的或较好的路径最好的或较好的路径。这种搜索可按两个方向进行：正向正向搜索：从初始状态朝着目标状态从初始状态朝着目标状态方向搜索 逆向逆向搜索：从目标状态朝着初始状态从目标
23、状态朝着初始状态方向搜索将以上两种搜索方法结合起来，就产生了双向搜索双向搜索：同时同时从初态和目标态出发，朝着对应的方向搜索从初态和目标态出发，朝着对应的方向搜索S0 Sg Sg S0 正向搜索正向搜索逆向搜索逆向搜索35启发式信息的表示l 一般来说，采用双向搜索是为了提高搜索效率采用双向搜索是为了提高搜索效率，如图，最理想的双向搜索和最不当的双向搜索差距巨大。l 选用最不当的双向搜索不会比单独使用正向或逆向搜索最不当的双向搜索不会比单独使用正向或逆向搜索好好，因为它取了正逆向搜索种最差的结果。S0 Sg Sg S0 理想情况最差情况36启发式信息的表示l 究竟采用正向搜索好还是采用逆向搜索好
24、采用正向搜索好还是采用逆向搜索好，可以考虑以下因素：朝分支因子低的方向更有效朝分支因子低的方向更有效分支因子分支因子指从一点出发可以直接到达的平均结点数可以直接到达的平均结点数。朝着分支因子低分支因子低的方向搜索意味着朝着“收敛收敛”的方向搜索。由状态少的一方出发，朝着大量的可识别的状态的方由状态少的一方出发，朝着大量的可识别的状态的方向更容易向更容易 依据用户可接受的方向更自然依据用户可接受的方向更自然特别是需要向用户解释推理过程时，顺应用户的心理顺应用户的心理是必不可少的目录1.人工智能概述2.用搜索求解问题的基本原理3.搜索的基本策略4.4.图搜索策略图搜索策略5.博弈与搜索3738图搜
25、索策略l 图搜索策略图搜索策略是一种在图中寻找解路径在图中寻找解路径的方法。l 对于一个实际搜索问题,应该采用什么形式来表示搜索搜索路径路径？是用图图还是用树树,可以作如下比较:用树树结构：允许搜索图中有相同结点出现允许搜索图中有相同结点出现，不必考虑产生的是否为重复的节点，因为同一节点可由不同路同一节点可由不同路径产生径产生优点：控制简单控制简单缺点：占空间较大占空间较大，产生相同结点多，则时空均需要较大的代价39图搜索策略 用图图结构：不允许搜索图中有相同结点出现不允许搜索图中有相同结点出现 优点：节省大量空间节省大量空间(相同的结点只存一次）和时间和时间(相同结点不需要重复产生）缺点：每
26、产生一个新的结点需判断这个节点是否已生成需判断这个节点是否已生成过过,因而控制更复杂控制更复杂，判断也要占用时间判断也要占用时间。碰到具体问题时，要权衡二者的利弊。若可能产生大量相同结点，则若可能产生大量相同结点，则应采用搜索图应采用搜索图。40通用或图搜索算法l 图搜索算法：只记录只记录状态空间那些被搜索过的状态被搜索过的状态，它们组成一个搜索图搜索图G G。l G由两张表内的节点组成：Open表：用于存放已经生成，且已用启发式函数作过估计或评价，但尚未产生它们的后继节点的那些结点，也称未考察结点未考察结点。Closed表：用于存放已经生成，且已考察过的结点已考察过的结点。l还有一个辅助结构
27、辅助结构TreeTree：节点为G G的一个子集的一个子集。Tree 用来存放当前已生成的搜索树存放当前已生成的搜索树,该树由G G的反向边的反向边(反反向指针向指针)组成组成41A算法l A算法与A*算法定义：或图通用算法或图通用算法中，将启发式函数定义为f(n)=g(n)+h(n)，并在步骤步骤时，按照该启发式函数f的值的大小取出节点，或者在步骤步骤-1-1时，以升序或降序排列Open表，然后根据f的值在某一位置加入节点时，这样的或图通用算法称为 A A算法算法l 其中g(n)g(n)表示从从S0S0到到n n点费用的估计点费用的估计，因为n为当前节点，搜索已达到n点，所以g(n)g(n)
28、可计算出可计算出。l h(n)h(n)表示从从n n到到SgSg接近程度的估计接近程度的估计，因为尚未找到解路径，所以h(n)h(n)仅仅是估计值仅仅是估计值。42A*算法43A*算法的性质l A*算法与一般的最佳优先最佳优先比较，有其特有的性质：l 如果问题有解如果问题有解，即S0Sg存在一条路径，A A*算法一定能算法一定能找到最优解找到最优解。这一性质称为可采纳性可采纳性(admissibility）l A*算法优点优点：A*算法一定能保证找到最优解一定能保证找到最优解。若以搜索的节点数来估计它的效率，则当启发式函数h的值单调上升时，它的效率只会提高，不会降低。有比较合理的渐近性质渐近性
29、质。44A*算法的性质l A*算法缺点缺点：在不仅考虑搜索节点的多少，而且还要考虑搜索节点被搜索的次数的时候，则当当h(nh(n）过低估计）过低估计h h*(n(n）时，有时会）时，有时会显出很高的复杂性显出很高的复杂性。45A*算法求解8数码问题l 对于下图的8数码问题：2831647512384765l 以前采用的估计函数为:f=放错位置的数字个数l 现在使用A*算法，采用f(n)=d(n)+w(n)式中，d(n)为搜索树的深度；w(n)为放错位置的数字个数l 这里g(n)=d(n),h(n)=w(n),且w(n)h*(n)：因为w只估计放错位置的数字个数，远未考虑纠正其位置的困难程度(移
30、动次数只可能1次)，所以其满足A*算法。46A*算法求解8数码问题28316475283164752831476528316475左上右A1f=1+5=6A3f=1+5=6A2f=1+3=447问题归约求解方法l 在与与/或图或图中，要求解要求解的大问题称为初始问题初始问题，可以直可以直接求解接求解的问题为本原问题本原问题。l 一般来讲，使用归约方法求解问题需要三大要素需要三大要素：初始问题的描述描述 一组将问题变换成子问题的变换规则变换规则 一组本原问题的描述描述l 从初始问题出发，建立子问题以及子问题的子问题，直至把初始问题归约成一个本原问题的集合，这就是问题规约方法求解的基本途径规约方法
31、求解的基本途径。48与/或图搜索l 将问题求解归约为与与/或图或图的搜索时，作如下规定：初始节点（根节点）：对应原始问题原始问题的描述 终叶节点（叶节点）：对应本原问题本原问题的描述 可解节点的可递归可递归定义：1.终叶节点是可解节点终叶节点是可解节点 2.若n是一个非终叶节点，且含有“或”后继节点，则只有当后继节点中至少有一个是可解节点至少有一个是可解节点时，n才可解 3.若n是一个非终叶节点，且含有“与”后继节点，则只有当后继节点全部可解全部可解时，n才可解49与/或图搜索l 将问题求解归约为与与/或图或图的搜索时，作如下规定：不可解节点的可递归可递归定义：1.没有后继节点没有后继节点的非
32、终叶节点为不可解 2.若n是一个非终叶节点，且含有“或或”后继节点，则仅当全部后继节点全部后继节点为不可解时，n不可解 3.若n是一个非终叶节点，且含有“与与”后继节点，则只要有一个后继节点有一个后继节点为不可解时，n为不可解50与/或图搜索l 将问题求解归约为与与/或图或图的搜索时，作如下规定：与/或图搜索费用计算：设从当前节点节点n n到目标集目标集SgSg的费用费用估计为h(n)h(n)1.若nSg,则h(n)=0 2.若n有一组由“与与”弧弧连接的后继节点n1,n2,ni 则:h(n)=c1+c2+ci+h(n1)+h(n2)+h(ni)其中：ci是n到ni弧的费用 3.若n既有既有“
33、与与”弧，又有弧，又有“或或”弧弧，则“与”弧算作一个“或”后继，再取各“或或”弧后继中费用最小者弧后继中费用最小者为n的费用51与/或图搜索的特点:费用估计l 与与/或图或图搜索费用的估计：或图或图搜索时，如果搜索到某个节点时，不论不论n n是否生成了是否生成了后继后继节点，n的费用是由其自身决定由其自身决定的。但与与/或图或图不同，其计算规则如下：l n未生成后继未生成后继节点：费用由由n n本身的估计值决定本身的估计值决定，费用为给定的估计值。l n已生成后继已生成后继节点：费用由由n n的后继节点的费用的后继节点的费用决定，即-1-1，2 2，3 3步计算。l 因为后继节点代表分解的子
34、问题后继节点代表分解的子问题，子问题的难易程度决子问题的难易程度决定了原问题的难易程度定了原问题的难易程度，所以不再考虑n本身的难度。l 当决定了某条路径时，要将后继节点的估计值回传要将后继节点的估计值回传。目录1.人工智能概述2.用搜索求解问题的基本原理3.搜索的基本策略4.图搜索策略5.5.博弈与搜索博弈与搜索5253围棋人机大战l 博弈的本质是人工智能的问题求解博弈的本质是人工智能的问题求解l 人工智能问题之所以能求解，是因为状态空间满足了两状态空间满足了两个条件个条件：待解决的问题必须有十分准确的定义 人求解问题的方法（算子和策略）能被精确描述l 因此在处理人工智能问题时，首先它能够被
35、精确的定义能够被精确的定义，其次需要问题范围十分小问题范围十分小，这样的问题才能被计算机解决。l 但目前的现实情况是，人们生活中的问题绝大多数都是人们生活中的问题绝大多数都是不能被精确定义的，而且解决问题的范围并不受限不能被精确定义的，而且解决问题的范围并不受限54博弈与对策l 博弈一向被认为是富有挑战性的智力的游戏，有着难以言语的魅力，博弈问题常与对策问题联系在一起。l 对策论（Game Theory）用数字方法研究对策问题。l 一般将对策问题分为零和对策零和对策和非零和对策非零和对策。l 零和：博弈各方收益和损失总和为零零和：博弈各方收益和损失总和为零l 零和例子：田忌赛马，棋牌类游戏等零
36、和例子：田忌赛马，棋牌类游戏等l 非零和例子：囚犯问题，开窗难题，中美合作等非零和例子：囚犯问题，开窗难题，中美合作等55博弈与对策l 要提高博弈问题求解程序的效率，应作到如下两点：改进生成过程改进生成过程，使之只生成好的走步，如按棋谱的方法生成下一步 改进测试过程改进测试过程，使最好的步骤能够及时被确认。l 要达到上述目的有效途径是使用启发式方法使用启发式方法引导搜索过程，使其只生成可能赢的走步。l 而这样的博弈程序应具备：一个好的（即只产生可能赢棋步骤的）生成过程一个好的（即只产生可能赢棋步骤的）生成过程。一个好的静态估计函数一个好的静态估计函数。56极小极大搜索的思想l 极小极大搜索的思
37、想：l 极小极大搜索策略是考虑双方对弈若干步之后，从可能的步中选一步相对好的走法来走，即在有限的搜索深度范围内进行求解。l 为此要定义一个静态估计函数静态估计函数f f，以便对棋局的势态作出优劣估计。这个函数可根据棋局优劣势态的特征来定义57极小极大搜索的思想l 这里规定：MAX代表程序方程序方 MIN代表对手方对手方 P代表一个棋局棋局（即一个状态状态）l f（P）的大小由棋局势态的优劣来决定:有利于MAX的势态，f（P）取正值正值 有利于MIN的势态，f（P）取负值负值 势态均衡，f（P）取零取零58极小极大搜索的思想l 使用静态函数进行估计必须以下述两个条件为前提：双方都知道各自走到什么
38、程度、下一步可能做什么。不考虑偶然因数影响。l 在这个前提下，博弈双方必须考虑：如何产生一个最好的走步。如何改进测试方法，能尽快搜索到最好的走步。59极小极大搜索的思想l MINMAX的基本思想是：当轮到MINMIN走步的结点时走步的结点时，MAXMAX应考虑最坏的情况应考虑最坏的情况（因此，f(p)f(p)取极小值取极小值）。当轮到MAXMAX走步的结点时走步的结点时，MAXMAX应考虑最好的情况应考虑最好的情况（因此，f(p)f(p)取极大值取极大值）。当评价往回倒推时评价往回倒推时，相应于两位棋手的对抗策略，不同层上交替的使用、两种方法向上传递倒推值。60剪枝算法l-剪枝算法就是把生成后
39、继和倒推值估计结合起来，及时剪掉一些无用分枝，以此来提高算法的效率。l-剪枝法，采用有界深度优先策略进行搜索，当生成节点达到规定的深度时，就立即进行静态估计，而一旦某个非端节点有条件确定倒推值时，就立即赋值。61剪枝算法l 只要在搜索过程中记住倒推值的上下界只要在搜索过程中记住倒推值的上下界并进行比较，当时就可以实现修剪时就可以实现修剪操作。l,值还可以随时修正值还可以随时修正，但极大层的但极大层的倒推值下界永倒推值下界永不下降不下降，因为实际的倒推值取后继节点最终确定的倒推值中的最大者最大者。l 同理，极小层的倒推值上界极小层的倒推值上界永不上升永不上升，因为实际倒推值取后继节点最终确定的倒
40、推值中的最小者。62剪枝算法l剪枝规则：剪枝：若任一极小值层节点的值小于或等于它任一先辈极大值层节点的值，即（先辈层）（后继层），则可中止该极小值层中这个节点以下的搜索。该节点最终的倒推值就确定为这个值。剪枝：若任一极大值层节点的值大于或等于它任一先辈极小值层节点的值，即（后继层）（先辈层），则可以中止该极大值层中这个节点以下的搜索。这个MAX节点的最终倒推值就确定为这个值目录6.6.演化搜索算法演化搜索算法7.群集智能算法8.知识表示与处理方法9.机器学习10.智能机器人6364遗传算法l 遗传算法遗传算法（Genetic Algorithm,GAGA）由美国J.Holland教授1975年
41、首先提出，是一种借鉴生物界的进化规律借鉴生物界的进化规律（优胜劣汰优胜劣汰机制）的随机化搜索方法随机化搜索方法。l 它的基本思想是使用模拟生物和人类进化的方法，求解复杂的优化问题，因此也称模拟进化优化算法。l 它在计算原理上是自适应自适应的，结构上是并行并行的，而且模仿了人的智能处理特征，因此成为人工智能的一个重要研究领域。l 现在被广泛应用组合优化、机器学习、信号处理、自适应控制和人工生命等领域。65遗传算法的基本概念l 遗传算法将择优与随机信息交换结合在一起，在每一代中，使用上一代最好的，即最适应环境的位或片段，形成新的人工生物集。l 虽然遗传算法是随机化方法，但它不是简单的随机搜索，而是
42、有效利用历史信息来推测新的搜索点l 为了推测新的搜索点，遗传算法利用了遗传操作l 因此遗传算法是计算机学与遗传学相结合的产物lGA的主要特点：不存在求导和函数连续性的限定很好的全局寻优能力采用概率化的寻优方法，不需要确定的规则66遗传算法的基本概念l 遗传算法是一个迭代过程，在每次迭代中有保留一组候选解，并按照某种优劣指标进行排序，然后按某种指标从中选取一些解，利用遗传算子，进行遗传操作运算，生成新的一代解，重复该过程直至收敛编码初始化种群解码&适应度评估择优选择（下位个体淘汰）个体基因交叉变异迭代运算迭代运算67遗传算法的基本流程l 遗传算法涉及5大要素：参数编码 初始群体设定 适应度函数设
43、计 遗传操作设计 控制参数设定68遗传算法的基本流程l 标准遗传算法（Standard GA,SGA）或者规范遗传算法（Canonical GA,CGA）的基本流程框图：确定实际问题参数集对参数进行编码初始化群体(t)评价群体满足停止准则?遗传操作结束群体(t)群体(t)三个基本操作：1.选择2.交叉3.变异其它高级操作69二进制编码70实数编码l 为了克服二进制编码的缺点，对于问题的变量是实向量的情形，可以直接采用十进制进行编码l 这样可以直接在解的表现形式上进行遗传操作，从而便于引入与问题领域相关的启发式信息以增加系统的搜索能力71适应值函数l 遗传算法将问题空间表示为染色体位串空间，为了
44、执行适者生存的原则，必须对个体位串的适应性进行评价l 适应值函数构成了个体的生成环境。根据个体的适应值可以决定它在此环境下的生存能力l 一般来说，好的染色体位串结构具有比较高的适应值，即可以获得较高的评价，具有较强的生存能力72适应值函数l 由于适应值是群体中个体生存机会选择的唯一确定性指标，所以适应值函数的形式直接决定着群体的进化行为l 根据实际问题，适应值可以是收入，利润，生产占有率，匹配度，可靠性，胜率等等l 为了能够直接将适应值函数与群体中个体的优劣度量相联系，在遗传算法中适应度函数定义为非负，并且在任何情况下总是希望越大越好73选择l 选择（selection）即从当前群体中选出个体
45、以生成交配池（mating pool）的过程。l 所选出的这些个体具有良好的特征，以便产生优良的后代。l 选择策略对算法性能的影响会起到举足轻重的作用，不同的选择策略将导致不同的选择压力，即下一代中父代个体的复制数目的不同分配关系。74选择l 较大的选择压力使最优个体有较高的复制数目，使算法更快收敛，但也较容易出现过早收敛现象。l 较小的选择压力可以使群体保持足够的多样性，从而增大算法收敛到全局最优解的概率，但算法的收敛速度一般较慢。75基于适应值比例的选择76基于排名的选择l 这种策略首先根据个体i的适应值在群体中的排名来分配其选择概率p，然后根据这个概率使用轮盘赌选择，这个个体的适应值不直
46、接影响后代的数量l 优点是：避免使用基于适应值比例的选择策略，常常会出现的过早收敛和停滞现象l 它的另外一个优点就是：无论对极小化问题，还是极大化问题，都不需要进行适应值的标准化和调节，可以直接使用原始的适应值进行排名选择l 选择方法有：线性排名选择 非线性排名选择77基于局部竞争机制的选择l 基于适应值比例的选择和基于排名的选择，都是根据个体的适应值在种群中所占的比例，或者排名位置来确定选择概率，然后进行选择l 这两种选择策略在群体规模很大时，其额外计算量也相当可观（计算总体适应值比例/排序等）l 而基于局部竞争机制的选择策略基于局部竞争机制的选择策略能在一定程度上避免这些问题l 选择方法有
47、：锦标赛选择(，)和+选择78交叉操作l 交叉操作（crossover）：将两个个体的遗传物质交换产生新的个体l 它可以把两个个体优良的格式传递到下一代的某个个体中，使其具有优于前驱的性能。l 如果交叉后得到的个体性能不佳，则可以在后面的复制操作中将其淘汰。l 交叉是遗传算法中获得新优秀个体的最重要手段。79二进制编码的交叉算子l 对二进制编码常用的交叉算子有：单点交叉 多点交叉 均匀交叉80二进制编码的交叉算子 单点交叉：l 例：考虑如下两个11位变量的父个体：父个体1：0 1 1 1 0 0 1 1 0 1 0父个体2：l 交叉点在位置5，交叉后生成两个子个体：子个体1：0 1 1 1 0
48、 子个体2：0 1 1 0 1 081二进制编码的交叉算子 单点交叉：l 单点交叉操作的信息量比较小l 交叉点位置的选择可能带来很大的偏差l 单点交叉不利于长距模式的保留和重组l 而且位串末尾的重要基因总是被交换l 所以在实际应用中采用较多的是多点交叉82二进制编码的交叉算子 多点交叉：l 例：考虑如下两个11位变量的父个体：父个体1：0 1 1 1 0 0 1 1 0 1 0父个体2：l 交叉点在位置2，6，10，交叉后生成两个子个体：子个体1：0 1 1 1 0 1 子个体2：1 0 1 1 0 0 083二进制编码的交叉算子 均匀交叉：l 例：父个体1：0 1 1 1 0 0 1 1 0
49、 1 0父个体2：模板：0 1 1 0 0 0 1 1 0 1 0子个体1：0 1 0 0 0 0子个体2：1 1 1 1 1 84变异操作l 变异与选择和交叉结合在一起，保证了遗传算法的有效性，使遗传算法具有局部的随机搜索能力l 同时使得遗传算法保持种群的多样性，以防非成熟收敛l 在变异操作中，变异概率不能取的太大：l 如果变异概率大于0.5，则遗传算法退化为随机算法，遗传算法的一些重要特性和搜索能力也不复存在85变异操作l 常用的变异操作有：实值变异：实值变异用于采用了实数编码形式的遗传算法，需要定义一个变异算子：在原数的基础上随机增加或减小一个较小的随机实数，以达到局部搜索的作用 二进制
50、变异：二进制变异用于采用了二进制编码形式的遗传算法，对于二进制编码的个体而言，变异意味着串的某些位发生翻转，对于每个个体，串的每一位都会有一定几率翻转86控制参数的选取l 在遗传算法的运行过程中，存在着对其性能产生重大影响的一组参数l 在初始阶段或者群体进化过程中，需要合理的选择和控制这组参数，使GA以最佳的搜索轨迹达到最优解87控制参数的选取88控制参数的选取l 根据大量的实践研究，人们总结出一些用于确定这些参数的建议：位串长度L：位串长度L的选择取决于特定问题的精度 要求精度越高，位串就越长，但需要更多的计算时间89控制参数的选取第六讲 演化搜索算法 群体规模n：大群体含有较多的模式，为遗
