人工智能基础之搜索技术.pptx

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,单击此处编辑母版标题样式,a单击此处编辑母版文本样式,a第二级,a第三级,a第四级,a第五级,*,合肥工业大学 人工智能与数据挖掘研究室,*,/79,单击此处编辑母版标题样式,a单击此处编辑母版文本样式,a第二级,a第三级,a第四级,a第五级,*,合肥工业大学 人工智能与数据挖掘研究室,1,/79,目录,第一章,绪论,第二章,知识表示,第三章搜索技术,第四章推理技术,第五章机器学习,第六章教授系统,第七章自动规划系统,第八章 自然语言了解,第九章 智能控制,第十章 人工智能程序设计,人工智能基础之搜索技术,第1页,3.1,盲目搜索,盲目搜索：即 无信息搜索 宽度优先与深度优先,3.1.1,图搜索策略,图搜索策略可看作一个在图中寻找路径方法。初始节点和目标节点分别代表初始数据库和满足终止条件数据库。求得把一个数据库变换为另一数据库规则序列问题就等价于求得图中一条路径问题。研究图搜索普通策略，能够给出图搜索过程普通步骤。,人工智能基础之搜索技术,第2页,3.1,盲目搜索,3.1.1,图搜索策略,例,3.1,从王某家族四代中找王,A,后代且其寿命为,X,人,A,47,B1,77,A3,52,B2,65,C2,87,C1,96,D1,77,E1,57,E2,92,F1,32,G1,27,H1,51,人工智能基础之搜索技术,第3页,3.1,盲目搜索,3.1.1,图搜索策略,1.,图搜索,(GRAPHSEARCH),普通过程,(1),建立一个只含有起始节点,S,搜索图,G,，把,S,放到一个叫做,OPEN,未扩展节点表中。,(2),建立一个叫做,CLOSED,已扩展节点表，其初始为空表。,(3)LOOP,：若,OPEN,表是空表，则失溃退出。,(4),选择,OPEN,表上第一个节点，把它从,OPEN,表移出并放进,CLOSED,表中。称此节点为节点,n,。,(5),若,n,为一目标节点，则有解并成功退出，此解是追踪图,G,中沿着指针从,n,到,S,这条路径而得到,(,指针将在第,7,步中设置,),。,人工智能基础之搜索技术,第4页,3.1,盲目搜索,3.1.1,图搜索策略,1.,图搜索,(GRAPHSEARCH),普通过程,(6),扩展节点,n,，同时生成不是,n,祖先那些后继节点集合,M,。把,M,这些组员作为,n,后继节点添入图,G,中。,(7),对那些未曾在,G,中出现过,(,既未曾在,OPEN,表上或,CLOSED,表上出现过,)M,组员设置一个通向,n,指针。把,M,这些组员加进,OPEN,表。对已经在,OPEN,或,CLOSED,表上每一个,M,组员，确定是否需要更改通到,n,指针方向。对已在,CLOSED,表上每个,M,组员，确定是否需要更改图,G,中通向它每个后代节点指针方向。,(8),按某一任意方式或按某个探试值，重排,OPEN,表。,(9)GO LOOP,。,人工智能基础之搜索技术,第5页,3.1,盲目搜索,节点,父辈节点,3.1.1,图搜索策略,2.,图搜索算法几个主要名词,（,1,）,OPEN,表与,CLOSE,表,OPEN,表,CLOSED,表,编号,节点,父辈节点,人工智能基础之搜索技术,第6页,3.1,盲目搜索,3.1.1,图搜索策略,3.,搜索图与搜索树,搜索过程框图,开,始,初始化,：,S,放入,OPEN,表,，,CLOES,表置空,n,=,1,OPEN,表中第一个结点,n,移至,CLOSE,表,若,n,后继未曾在搜索图,G,中出现,，,则将其放入,OPEN,表末端,，,并提供返回结点,n,指针,置,n,=,n,+,1,依据后继结点在搜索图,G,中出现情况,修改指针方向,依某种准则重新排序,OPEN,表,失败,成功,N,Y,N,OPEN,为空表,NULL,？,n,=,目标结点,D,吗,?,Y,人工智能基础之搜索技术,第7页,3.1,盲目搜索,3.1.1,图搜索策略,4.,图搜索方法分析：,图搜索过程第,8,步对,OPEN,表上节点进行排序，方便能够从中选出一个“最好”节点作为第,4,步扩展用。这种排序能够是任意即盲目标,(,属于盲目搜索,),，也能够用以后要讨论各种启发思想或其它准则为依据,(,属于启发式搜索,),。每当被选作扩展节点为目标节点时，这一过程就宣告成功结束。这时，能够重现从起始节点到目标节点这条成功路径，其方法是从目标节点按指针向,S,返回追溯。当搜索树不再剩有未被扩展端节点时，过程就以失败告终,(,一些节点最终可能没有后继节点，所以,OPEN,表可能最终变成空表,),。在失败终止情况下，从起始节点出发，一定达不到目标节点。,人工智能基础之搜索技术,第8页,3.1,盲目搜索,3.1.2,宽度优先搜索,定义,3.1,假如搜索是以靠近起始节点程度依次扩展节点，那么这种搜索就叫做宽度优先搜索（,breadth-first search),人工智能基础之搜索技术,第9页,3.1,盲目搜索,3.1.2,宽度优先搜索,宽度优先搜索算法,(1),把起始节点放到,OPEN,表中,(,假如该起始节点为一目标节点，则求得一个解答,),。,(2),假如,OPEN,是个空表，则没有解，失溃退出；不然继续。,(3),把第一个节点,(,节点,n),从,OPEN,表移出，并把它放入,CLOSED,扩展节点表中。,(4),扩展节点,n,。假如没有后继节点，则转向上述第,(2),步。,(5),把,n,全部后继节点放到,OPEN,表末端，并提供从这些后继节点回到,n,指针。,(6),假如,n,任一个后继节点是个目标节点，则找到一个解答，成功退出；不然转向第,(2),步。,人工智能基础之搜索技术,第10页,3.1,盲目搜索,3.1.2,宽度优先搜索,例,3.2,八数码问题,操作要求,:,允许空格四面上、下、左、右数码块移入空格中，不许斜方向移动，不许返回先辈结点。,初始布局,S,和目标状态,D,以下列图所表示：,人工智能基础之搜索技术,第11页,3.1,盲目搜索,3.1.2,宽度优先搜索,例,3.2,八数码问题,人工智能基础之搜索技术,第12页,3.1,盲目搜索,3.1.3,深度优先搜索,深度优先算法步骤：,(1),初始结点,S,放到未扩展节点,OPEN,中；,(2),若,OPEN,为空，则搜索失败，问题无解；,(3),弹出,OPEN,表中最顶端结点放到,CLOSE,表中，并给出次序编号,n,；,(4),若,n,为目标结点,D,，则搜索成功，问题有解；,(5),若,n,无子结点，转,(2),；,(6),扩展,n,结点，将其全部子结点配上返回,n,指针，并按次序压入,OPEN,堆栈，转,(2),。,人工智能基础之搜索技术,第13页,3.1,盲目搜索,3.1.3,深度优先搜索,人工智能基础之搜索技术,第14页,3.1,盲目搜索,3.1.3,深度优先搜索,有界深度优先搜索,：,引入搜索深度限制值,d,，,使深度优先搜索过程含有完备性。,设定搜索深度限制,d=5,，,问题同深度优先算法中八数码问题,(2),。,人工智能基础之搜索技术,第15页,3.1,盲目搜索,3.1.3,深度优先搜索,人工智能基础之搜索技术,第16页,3.1,盲目搜索,3.1.3,深度优先搜索,有界深度优先算法步骤：,(1),初始结点,S,放入堆栈,OPEN,中；,(2),若,OPEN,为空，则搜索失败，问题无解；,(3),弹出,OPEN,中栈顶结点,n,，放入,CLOSE,表中，并给出次序编号,n,；,(4),若,n,为目标结点,D,，则搜索成功，问题有解；,(5),若,n,深度,d(n)=d,，则转,(2),；,(6),若,n,无子结点，即不可扩展，转,(2),；,(7),扩展结点,n,，将其全部子结点配上返回,n,指针，并压入,OPEN,堆栈，转,(2),。,人工智能基础之搜索技术,第17页,3.1,盲目搜索,3.1.4,等代价搜索,宽度优先搜索可被推广用来处理寻找从起始状态至目标状态含有最小代价路径问题，这种推广了宽度优先搜索算法叫做等代价搜索算法,。,等代价搜索中几个记号,起始节点记为,S,；,从节点,i,到它后继节点,j,连接弧线代价记为,c(i,，,j),；,起始节点,S,到任一节点,i,路径代价记为,g(i),。,假如全部连接弧线含有相等代价，那么等代价算法就简化为宽度优先搜索算法,。,人工智能基础之搜索技术,第18页,3.2,启发式搜索,盲目搜索不足：效率低，花费空间与时间。,启发式搜索：利用问题域特征信息（启发信息）进行搜索。,3.2.1,启发式搜索策略,启发式信息按用途分为三种：,（,1,）用于确定要扩展下一个节点，防止盲目扩展。,（,2,）在扩展一个节点过程中，用于确定要生成哪一个或哪几个后继节点，防止盲目生成全部可能节点。,（,3,）用于确定一些应该从搜索树中抛弃或修剪得节点。,人工智能基础之搜索技术,第19页,3.2,启发式搜索,有序搜索（,ordered search,）：利用第一个启发信息，总是选择“最有希望”节点作为下一个被扩展节点。,估价函数（,evaluation function),：估算节点“希望”量度，这种量度叫做估价函数。,建立估价函数普通方法：试图确定一个处于最正确路径上节点概率；提出任意节点与目标集之间距离量度或差异量度；或者在棋盘式博弈和难题中依据棋局一些特点来决定棋局得分数。这些特点被认为与向目标节点前深入希望程度相关。,f(n),表示节点,n,估价函数值,人工智能基础之搜索技术,第20页,3.2,启发式搜索,3.2.2,有序搜索,用估价函数,f,来排列,GRAPHSEARCH,第,8,步中,OPEN,表上节点。应用某个算法,(,比如等代价算法,),选择,OPEN,表上含有最小,f,值节点作为下一个要扩展节点。这种搜索方法叫做,有序搜索,或,最正确优先搜索,(best-first search),，而其算法就叫做,有序搜索算法,或,最正确优先算法,。,人工智能基础之搜索技术,第21页,3.2,启发式搜索,3.2.2,有序搜索,有序状态空间搜索算法：,(1),把起始节点,S,放到,OPEN,表中，计算,f(S),并把其值与节点,S,联络起来。,(2),假如,OPEN,是个空表，则失溃退出，无解。,(3),从,OPEN,表中选择一个,f,值最小节点,i,。结果有几个节点合格，当其中有一个为目标节点时，则选择此目标节点，不然就选择其中任一个节点作为节点,i,。,(4),把节点,i,从,OPEN,表中移出，并把它放入,CLOSED,扩展节点表中。,人工智能基础之搜索技术,第22页,3.2,启发式搜索,3.2.2,有序搜索,(5),假如,i,是个目标节点，则成功退出，求得一个解。,(6),扩展节点,i,，生成其全部后继节点。对于,i,每一个后继节点,j,：,(a),计算,f(j),。,(b),假如,j,既不在,OPEN,表中，又不在,CLOSED,表中，则用估价函数,f,把它添入,OPEN,表。从,j,加一指向其父辈节点,i,指针，方便一旦找到目标节点时记住一个解答路径。,(c),假如,j,已在,OPEN,表上或,CLOSED,表上，则比较刚才对,j,计算过,f,值和前面计算过该节点在表中,f,值。假如新,f,值较小，则,人工智能基础之搜索技术,第23页,3.2,启发式搜索,3.2.2,有序搜索,(i),以此新值取代旧值。,(ii),从,j,指向,i,，而不是指向它父辈节点。,(iii),假如节点,j,在,CLOSED,表中，则把它移回,OPEN,表。,(7),转向,(2),，即,GO TO(2),。,人工智能基础之搜索技术,第24页,3.2,启发式搜索,3.2.2,有序搜索,开始,把,S,放入,OPEN,表,OPEN,为空表？,失败,选取,OPEN,表中,f,值最小,节点,i,，放入,CLOSED,表,i=Sg,？,成功,是,是,扩展,i,得后继节点,j,，计算,f(j),，提,供返回,i,指针，利用,f(j),对,OPEN,表重新排序调整父子关系及指针,人工智能基础之搜索技术,第25页,3.2,启发式搜索,3.2.2 有序搜索,宽度优先搜索、等代价搜索和深度优先搜索统统是有序搜索技术特例。对于宽度优先搜索，选择f(i)作为节点i深度。对于等代价搜索，f(i)是从起始节点至节点i这段路径代价。,有序搜索有效性直接取决于f选择，如果选择f不合适，有序搜索就可能失去一个最好解甚至全部解。如果没有适用准确希望量度，那么f选择将涉及两个方面内容：一方面是一个时间和空间之间折衷方案；其次是保证有一个最优解或任意解。,人工智能基础之搜索技术,第26页,3.2,启发式搜索,3.2.2,有序搜索,例,3.4,：八数码难题,采取了简单估价函数,f(n)=d(n)+W(n),其中：,d(n),是搜索树中节点,n,深度；,W(n),用来计算对应于节点,n,数据库中错放棋子个数。所以，起始节点棋局,f,值等于,0+4=4,。,2,8,3,1,6,4,7,5,人工智能基础之搜索技术,第27页,3.2,启发式搜索,3.2.2,有序搜索,2,8,3,1,6,4,7,5,2,8,3,1,6,4,7,5,2,8,3,1,4,7,6,5,2,8,3,1,6,4,7,5,2,8,3,1,4,7,6,5,2,3,1,8,4,7,6,5,2,8,3,1,4,7,6,5,8,3,2,1,4,7,6,5,2,8,3,7,1,4,6,5,2,3,1,8,4,7,6,5,2,3,3,1,8,4,7,6,5,1,2,3,8,4,7,6,5,1,2,3,8,4,7,6,5,1,2,3,7,8,4,6,5,人工智能基础之搜索技术,第28页,3.2,启发式搜索,3.2.3 A*,算法,A*,算法是一个有序搜索算法，其特点在于对估价函数定义上。,1.A*,算法估价函数,k(n,i,，,n,j,),：表示任意两个节点,n,i,和,n,j,之间最小代价路径实际代价,(,对于两节点间没有通路节点，函数,k,没有定义,),。,k(n,t,i,),：从节点,n,到某个详细目标节点,t,i,，某一条最小代价路径代价。,h*(n),：表示整个目标节点集合,t,i,上全部,k(n,t,i,),中最小一个，所以，,h*(n),就是从,n,到目标节点最小代价路径代价，而且从,n,到目标节点能够取得,h*(n),任一路径就是一条从,n,到某个目标节点最正确路径,(,对于任何不能抵达目标节点节点,n,，函数,h*,没有定义,),。,人工智能基础之搜索技术,第29页,3.2,启发式搜索,3.2.3 A*,算法,定义,g*,为,g*(n)=k(S,n),从已知起始节点,S,到任意节点,n,一条最正确路径代价。,定义函数,f*,，,f*(n)=g*(n)+h*(n),使得在任一节点,n,上其函数值,f*(n),就是从节点,S,到节点,n,一条最正确路径实际代价加上从节点,n,到某目标节点一条最正确路径代价之和。,人工智能基础之搜索技术,第30页,3.2,启发式搜索,3.2.3 A*,算法,希望估价函数,f,是,f*,一个预计，此预计可由下式给出：,f(n)=g(n)+h(n),其中：,g,是,g*,预计；,h,是,h*,预计。,对于,g(n),：一个显著选择就是搜索树中从,S,到,n,这段路径代价，这一代价能够由从,n,到,S,寻找指针时，把所碰到各段弧线代价加起来给出,(,这条路径就是到当前为止用搜索算法找到从,S,到,n,最小代价路径,),。这个定义包含了,g(n)g*(n),。,h(n),：对,h*(n),预计，依赖于相关问题领域启发信息。这种信息可能与八数码难题中函数,W(n),所用那种信息相同。把,h,叫做启发函数。,人工智能基础之搜索技术,第31页,3.2,启发式搜索,3.2.3 A*,算法,2.A,算法和,A*,算法定义,定义,3.3,在,GRAPHSEARCH,过程中，假如第,8,步重排,OPEN,表是依据,f(x)=g(x)+h(x),进行，则称该过程为,A,算法。,定义,3.4,在,A,算法中，假如对全部,x,存在,h(x)h*(x),则称,h(x),为,h*(x),下界，它表示某种偏于保守预计。,定义,3.5,采取,h*(x),下界,h(x),为启发函数,A,算法，称为,A*,算法。当,h=0,时，,A*,算法就变为有序搜索算法。,A,算法和,A*,搜索算法目标有所不一样：,A,搜索算法即使希望能找到问题最优解，但主要追求是求解效率；而,A*,搜索算法直接目标就在于要找到问题最优解及其解路径，即便搜索效率有所降低也在所不惜。,人工智能基础之搜索技术,第32页,3.2 启发式搜索,3.2.3 A*,算法,开始,把,S,放入,OPEN,表,记,f=h,OPEN,为空表？,失败,选取,OPEN,表中未设置过含有最小,f,值,节点,BESTNODE,，放入,CLOSED,表,BESTNODE=Sg,？,成功,是,是,扩展,BESTNODE,，产生后继节点,SUVVESSOR,建立从,SUCCESSOR,返回,BESTNODE,指针,计算,g(SUCCESSOR)=g(BESTNODE)+h(BESTNODE)_SUCCESSOR),SUCCESSOROPEN,？,否,是,人工智能基础之搜索技术,第33页,3.2 启发式搜索,3.2.3 A*,算法,把,SECCESSOR,放入,OPEN,表，,加入,BESTNODE,后代表,g(SUCCESSOR)g(OLD),？,否,重新确定,OLD,父辈节点为,BESTNODE,，,并修正父辈节点,g,值和,f,值，记下,g(OLD),SUCCESSORCLOSED,？,否,是,SECCESSOR=OLD,，把它添到,BESTNODE,后继节点表中,是,否,计算,f,值,人工智能基础之搜索技术,第34页,3.3,博弈树搜索,3.3.1,博弈概述,何谓博弈？,博弈就是下棋、打牌、竞技、战争等一类竞争性智能活动。,“二人零和非偶然性全信息”博弈,（,1,）二人零和：,对垒,MAX,、,MIN,双方轮番采取行动，博弈结果只有三种情况：,MAX,方胜，,MIN,方胜，和局。,（,2,）全信息：,在对垒过程中，任何一方都了解当前格局及过去历史。,（,3,）非偶然性：,任何一方在采取行动前都要依据当前实际情况，进行得失分析，选取对自己最为有利而对对方最为不利对策，不存在“碰运气”，“侥幸”及“偶然失误”等随机原因。,人工智能基础之搜索技术,第35页,3.3,博弈树搜索,3.3.1,博弈概述,参加博弈各方都希望己方取得胜利。所以，当首先临多个行动方案选择时，,博弈各方总是要挑选对自己最为有利而对对方最不利那个行动方案。,假如,MAX,方目标：,尽可能使自己到达最大（或最高）分数分枝节点，,可用,“或”,关系来描述，称之为,MAX,方,节点；,而当轮到,MIN,方行动时，,MIN,方目标：,尽可能使,MIN,方取得最小（或最低）分数分枝节点，,这对,MIN,方来说，这些行动方案或分数分枝节点之间，能够用,“与”,关系来描述，是由,MIN,方,自主进行控制，故又称之为,MIN,节点。,人工智能基础之搜索技术,第36页,3.3,博弈树搜索,3.3.1,博弈概述,把上述双方逐层交替博弈过程用与,/,或树（图）描述表示出来，就得到了一棵含有“与,/,或”节点交替出现博弈树。,博弈树有以下特点：,（,1,）博弈初始格局是初始节点。,（,2,）在博弈树中，因为,双方轮番地扩展节点，“或”节点和“与”节点逐层交替出现。,假如自己一方扩展节点之间是“或”关系，则对方扩展节点之间是“与”关系。,（,3,）把本方获胜终局定义为本原问题，对应最优搜索路径上节点是可解节点，而全部使对方获胜终局和属于对方最优搜索路径上节点则是不可解节点。另外，全部其它节点则是含有风险中间节点。,人工智能基础之搜索技术,第37页,3.3,博弈树搜索,3.3.2,极小极大分析法,在二人博弈过程中，最直观而可靠惯用分析方法就是极小极大化搜索法。其主要描述思想和算法：,（,1,）设博弈一方为,MAX,方，其目标是尽可能使自己得到最高分；另一方为,MIN,方,其目标是尽可能给,MAX,方送出最低分。所谓极小极大化分析法是一个要轮番为每一方寻找一个最优行动方案方法。在图中，方框形状“”表示是,MAX,方控制或节点；圆形框形状“”表示,MIN,方控制与节点。,（,2,）考虑每一方案实施后对方可能采取全部行动，并为其计算可能得分；,（,3,）为计算得分，需要依据问题特征信息定义一个估价函数，用来估算当前博弈树全部端节点得分。此时估算出来得分称为静态估值。,人工智能基础之搜索技术,第38页,3.3,博弈树搜索,3.3.2,极小极大分析法,（,4,）当端节点估值计算出来后，再推算父辈节点等分，推算方法是：对“或”节点，选择其子节点中最大得分作为父辈节点得分（选择对自己最有利方案）；对“与”节点，选其子节点中一个最小得分作为作为父辈节点得分（立足于最坏情况）。这么计算出父辈节点等分称为倒推值。,（,5,）假如一个行动方案能取得较大倒推值，则它就是当前最好行动方案。,存放受限问题：先生成一定深度博弈树，进行极小极大分析，找出当前最好行动方案。然后再已选定分支上再扩展一定深度，如此重复。,人工智能基础之搜索技术,第39页,3.3.2,极小极大分析法,4 -1 -1 8 1 2 -5 0 -4 -9 -1,5 11 4 3 -1 1 5 8 10 1 4 2 5 -5 9 6 0 6-4 10 9-1 12 5,MAX-MIN,博弈树倒推值计算,h,(,S0)=,？,4 8 2 0 -1,4 -1,3.3,博弈树搜索,人工智能基础之搜索技术,第40页,3.3,博弈树搜索,3.3.3-,剪枝技术,基本思想：边生成博弈树边估算各节点倒推值，而且依据评定出倒推值范围，及时停顿扩展那些已无必要再扩展子节点。,详细剪枝方法：,（,1,）对于一个“与”节点,MIN,，若能预计出其倒推值上界,，而且这个,值小于,MIN,父辈节点（一定是“或”节点）预计倒推值下界,，即,，则就无须要再扩展该,MIN,节点其余子节点了。这一过程称为,剪枝。,（,2,）对于一个“或”节点,MAX,，若能预计出其倒推值下界,，而且这个,值大于,MAX,父辈节点（一定是“与”节点）预计倒推值上界,，即,，则就无须要再扩展该,MAX,节点其余子节点了。这一过程称为,剪枝。,人工智能基础之搜索技术,第41页,3.3,博弈树搜索,3.3.3-,剪枝技术,从算法中看到：,（,1,）,MAX,节点（包含起始节点）,值永不降低。,（,2,）,MIN,节点（包含起始节点）,值永不增加。,在搜索期间，,和,值计算以下：,（,1,）一个,MAX,节点,值等于其后继节点当前最大最终倒推值。,（,2,）一个,MIN,节点,值等于其后继节点当前最小最终倒推值。,人工智能基础之搜索技术,第42页,3.3,博弈树搜索,3.3.3-,剪枝技术,例,3.5,一字棋搜索树,和,值计算,估价函数,g(p),定义以下：,（,1,）若当前棋局对任何一方都不是获胜，则,g(p)=(,全部空格都放上,MAX,棋子之后,3,个棋子所组成行列及对角线总数）,（全部空格都放上,MIN,棋子之后,3,个棋子所组成行列及对角线总数）,（,2,）若,p,是,MAX,获胜，则,g(p)=+,（,3,）若,p,是,MIN,获胜，则,g(p)=-,上图中，,g(p)=6-4=2,，其中,表示,MAX,方，表示,MIN,方,人工智能基础之搜索技术,第43页,3.3.3-,剪枝技术,3.3,博弈树搜索,初始节点,=-1,A,B,C,-1,=-1,6-5=1,5-5=0,6-5=1,5-5=0,4-5=-1,5-6=-1,人工智能基础之搜索技术,第44页,3.3.3-,剪枝技术,3.3 博弈树搜索,4 -1 -1 8 1 2 -5 0 -4 -9 -1,5 11 4 3 -1 1 5 8 10 1 4 2 5 -5 9 6 0 6-4 10 9-1 12 5,MAX-MIN,博弈树倒推值计算,h,(,S0)=,？,4 8 2 0 -1,4 -1,人工智能基础之搜索技术,第45页,3.3.3-,剪枝技术,3.3 博弈树搜索,h,(,S0)=,？,4,4,11,3,3,1,1,8,8,10,8,2,2,-5,-5,2,2,4,4,x5,5,4,博弈树,-,剪枝实现过程,人工智能基础之搜索技术,第46页,3.3,博弈树搜索,3.3.3-,剪枝技术,要进行,-,剪枝，必须最少使某一部分搜索树生长到最大深度，因为,和,值必须以端节点静态估值为依据。所以采取,-,剪枝技术通常都要使用某种深度优先搜索方法。,人工智能基础之搜索技术,第47页,3.4,遗传算法,生物群体生存过程普遍遵照达尔文物竞天择、适者生存进化准则；生物经过个体间选择、交叉、变异来适应大自然环境。生物染色体用数学方式或计算机方式来表达就是一串数码，仍叫染色体，有时也叫个体；适应能力用对应一个染色体数值来衡量；染色体选择或淘汰问题是按求最大还是最小问题来进行。,遗传算法是模仿生物遗传学和自然选择机理，经过人工方式结构一类优化搜索算法，是对生物进化过程进行一个数学仿真，是进化计算一个最主要形式。,人工智能基础之搜索技术,第48页,3.4,遗传算法,遗传算法提出：,于,20,世纪,60,年代由密歇根,(Michigan),大学,Hollstien,Bagleyh,和,Rosenberg,等人在其博士论文中首先加以研究；,1975,年，美国,J.H.Holland,教授在其著作“,Adaptation in Natural and Artificial Systems”,中系统地阐述了遗传算法，给出了遗传算法基本定理和大量数学理论证实。,遗传算法发展：,David E.Goldberg,教授,1989,年出版了“,Genetic Algorichms”,一书，这一著作通常被认为是遗传算法方法、理论及应用全方面系统总结。从,1985,年起，国际上开始陆续举行遗传算法国际会议，以后又更名为进化计算。参加进化计算国际会议人数及收录文章数量、广度和深度逐年扩大。从此，进化计算逐步成为人们用来处理高度复杂问题新思绪和新方法。,人工智能基础之搜索技术,第49页,3.4,遗传算法,遗传算法特点：,遗传算法是一个基于空间搜索算法，它经过自然选择、遗传、变异等操作以及达尔文适者生存理论，模拟自然进化过程来寻找所求问题解答。遗传算法含有以下特点：,(1),遗传算法是对参数集合编码而非针对参数本身进行进化；,(2),遗传算法是从问题解编码组开始而非从单个解开始搜索；,(3),遗传算法利用目标函数适应度这一信息而非利用导数或其它辅助信息来指导搜索；,(4),遗传算法利用选择、交叉、变异等算子而不是利用确定性规则进行随机操作。,人工智能基础之搜索技术,第50页,3.4,遗传算法,遗传算法应用：,J.H.Holland,博士于,1975,年提出遗传算法,当初并没有引发学术界足够重视。直到二十世纪,80,年代中期,伴随计算机技术日新月异高速发展与进步,遗传算法首先成功地应用于,AI,机器学习和神经网络方面,;,以后又在诸如函数优化、自动控制、图象识别、分子生物学、优化调度以及机械、土木、电力工程等工业系统和许多领域中得到应用,显示出诱人前景。从此，遗传算法始才得到学术界普遍关注与认可。,人工智能基础之搜索技术,第51页,3.4,遗传算法,3.4.1,遗传算法基本原理,霍兰德提出遗传算法通常称为简单遗传算法（,SGA,）。现以此作为讨论主要对象，加上适应改进，来分析遗传算法结构和机理。在讨论中会结合销售员旅行问题（,TSP,）来说明。,1.,编码与解码,许多应用问题结构很复杂，但能够化为简单位串形式编码表示。将问题结构变换为位串形式编码表示过程叫编码；而相反将位串形式编码表示变换为原问题结构过程叫解码或译码。把位串形式编码表示叫染色体，有时也叫个体。,人工智能基础之搜索技术,第52页,3.4,遗传算法,3.4.1,遗传算法基本原理,例：对于销售员旅行问题（,Travelling salesman Problem,TSP,），设有,n,个城市，城市,i,和城市,j,之间距离为,d(i,j),，要求找到一条遍访每个城市一次而且恰好一次旅行线路，使其路径总长度为最短。按一条回路中城市次序进行编码。从城市,w,1,开始，依次经过城市,w,2,，,，,w,n,，最终回到城市,w,1,，我们就有以下编码表示：,w,1,w,2,w,n,因为是回路，记,w,n,+1,=,w,1,。它其实是,1,，,，,n,一个循环排列。要注意,w,1,，,w,2,，,，,w,n,是互不相同。,人工智能基础之搜索技术,第53页,3.4,遗传算法,3.4.1,遗传算法基本原理,2.,适应度函数,为了表达染色体适应能力，引入了对问题中每一个染色体都能进行度量函数，叫适应度函数（,fitness function,）。,TSP,目标是路径总长度为最短，自然地，路径总长度倒数就可作为,TSP,问题适应度函数,:,其中,w,n+1,=w,1,适应度函数要有效反应每一个染色体与问题最优解染色体之间差距。适应度函数取值大小与求解问题对象意义有很大关系。,人工智能基础之搜索技术,第54页,3.4,遗传算法,3.4.1,遗传算法基本原理,3.,遗传操作,简单遗传算法遗传操作主要有有三种,:,选择,(selection),、交叉,(crossover),、变异,(mutation),。改进遗传算法大量扩充了遗传操作，以到达更高效率。,选择操作也叫复制（,reproduction,）操作，依据个体适应度函数值所度量优劣程度决定它在下一代是被淘汰还是被遗传。,简单遗传算法采取赌轮选择机制，令,f,i,表示群体适应度值之总和，,f,i,表示种群中第,i,个染色体适应度值，它产生后代能力恰好为其适应度值所占份额,f,i,/f,i,。,人工智能基础之搜索技术,第55页,3.4,遗传算法,3.4.1,遗传算法基本原理,3.,遗传操作,交叉操作简单方式是将被选择出两个个体,P1,和,P2,作为父母个体，将二者部分码值进行交换。,产生一个,17,之间随机数,c,，假设为,3,，则将,P1,和,P2,低,3,位交换,1,0,0,0,1,1,1,0,P1,：,1,1,0,1,1,0,0,1,P2,：,人工智能基础之搜索技术,第56页,3.4,遗传算法,3.4.1,遗传算法基本原理,3.,遗传操作,1,0,0,0,1,1,1,0,P1,：,1,1,0,1,1,0,0,1,P2,：,1,0,0,0,1,0,0,1,1,1,0,1,1,1,1,0,Q1,：,Q2,：,人工智能基础之搜索技术,第57页,3.4,遗传算法,3.4.1,遗传算法基本原理,3.,遗传操作,变异操作简单方式是改变数码串某个位置上数码。二进制编码表示简单变异操作是将,0,与,1,交换：,0,变异为,1,，,1,变异为,0,。,随机产生一个,18,之间数,k,，假设,k=5,，对从右往左第,5,位变异操作。,1,0,1,0,0,1,1,0,1,人工智能基础之搜索技术,第58页,3.4,遗传算法,3.4.1,遗传算法基本原理,4.,控制参数,交叉发生概率：,0.60.95,变异概率：,0.0010.01,种群个数：,30100,个体长度：定长和变长,人工智能基础之搜索技术,第59页,3.4,遗传算法,3.4.2,遗传算法结构,选择：由个体适应度值决定,某个规则。,交叉：按概率,P,c,进行,变异：按概率,P,m,进行,终止条件：,完成了预先给定进化代数,种群中最优个体在连续若干代,没有改进或平均适应度在连续若,干代基本没有改进,开始,初始化种群,选择操作,终止条件,否,适应度最有优个体,计算适应度值,交叉操作,变异操作,结束,人工智能基础之搜索技术,第60页,3.4,遗传算法,3.4.3,遗传算法性能,遗传算法求得解是一满意解。影响解质量原因：,种群数量：太小缺乏多样性，太多影响效率,适应度函数：提升优良个体适应度,交叉和变异：不一样问题需结构性能更优交叉和变异操作,交叉概率和变异概率：,人工智能基础之搜索技术,第61页,分析：对该问题即使也能够采取枚举方法来处理,但枚举法却是一个效率很低方法,.,可利用遗传算法来求解该问题,.,解：首先对问题进行初始化，以取得初始种群,;,（,1,）确定适当编码方案：将,x,编码表示为染色体数字符号串。针对本题自变量,x,定义域,取值范围为,0,，,31,考虑采取二进制数来对其编码,由,2,5,=32,故使用,5,位无符号二进制数组成染色体数字字符串,用以表示变量,x,及问题解答过程。,例,:,设有函数,f(x,)=,x,2,请用遗传算法求其自变量,x,在区间,0,，,31,取整数值时最大值，并说明此函数优化问题。,3.4,遗传算法,人工智能基础之搜索技术,第62页,（,2,）选择初始种群,:,经过随机方法来产生染色体数字串，并组成初始种群。比如，为得到数字串某位,又称之为基因,(genes),，使用计算机在,0,1,之间产生随机数,K,，并按照数,K,改变区域来要求基因代码以下：,0,，（,0,K,0.5,）,1,，（,0.5,K,1,）,3.4,遗传算法,G=,人工智能基础之搜索技术,第63页,于是,随机生成,4,个,染色体数字符串为：,01101,11000,01000,10011,从而结构了初始种群，完成了遗传算法准备。,3.4,遗传算法,人工智能基础之搜索技术,第64页,表,初始种群染色体及对应适应值,3.4,遗传算法,染色体标号,串,x,适应值,f,(,x,)=,x,2,占整体百分数,1,01101,169,14.4%,2,11000,576,49.2%,3,01000,64,5.5%,4,10011,361,30.9%,总计（初始种群值）,1170,100.0%,人工智能基础之搜索技术,第65页,（,3,）复制,(,选择,):,选择适应值大串作为母本，使在下一代中有更多机会繁殖其子孙。,要在四个种子个体中做选择，要求依然得到四个染色体，可依据适应度概率百分比制订以下规则：,低于,0.125,以下染色体被淘汰；,在,0.125,0.375,之间染色体被复制一个；,在,0.375,0.625,之间染色体被复制两个；,在,0.625,0.875,之间染色体被复制三个；,在,0.875,以上染色体可复制四个。,3.4,遗传算法,人工智能基础之搜索技术,第66页,对应于上例，按照适应度计算，经复制操作后，得到新染色体种群为,01101,11000,11000,10011,3.4,遗传算法,人工智能基础之搜索技术,第67页,某个染色体是否被复制,能够经过概率决议法、适应度百分比法或“轮盘赌”随机方法来断定。对应轮盘赌转盘随机方法,依据表,6.1,数据，绘制出轮盘赌转盘,如图所表示,:,进化计算,基本,遗传算法原理,49.2,30.9%,14.4%,5.5%,01101,11000,11000,10011,人工智能基础之搜索技术,第68页,3.4,遗传算法,初始种群,x,值 适应度 选择概率 期望值 实际复制数,编号 （随机产生）（无符号整数）,f,(,x,)=,x,2,P,c,f,(,x,i,)/,f,A,（或转轮法）,1 01101 13 169 0.144 0.58 1,2 11000 24 576 0.492 1.97 2,3 01000 8 64 0.055 0.22 0,4 10011 19 361 0.309 1.23 1,1170 1.00 4.00 4.0,平均,(A,),293,0.25 1.00 1.0,MAX,576,0.49 1.97 2.0,初始种群染色体准备复制操作各项计算数据,人工智能基础之搜索技术,第69页,（,4,）,交叉,:,交叉