【教学课件】第三章搜索技术.ppt

第三章 搜索技术,第一节 引言一、搜索 对于无成熟方法可用的问题求解，必须一步步地摸索求解，这种问题求解过程就是搜索。注：搜索技术是人工智能的核心技术之一。二、研究和选用搜索算法的原则1、有限搜索还是无限搜索？若搜索空间有限，则任何一种穷举算法均能完成任务。,第三章 搜索技术,第一节 引言二、研究和选用搜索算法的原则2、搜索空间是静态的还是动态生成的？在人工智能中，搜索的对象(常称状态)是在搜索过程中逐步生成的，需将搜索对象的生成和评估的代价计算在内。对于一般搜索，搜索空间基本是静态的，或表或数组或数据库。3、已知目标还是未知目标？4、只要目标还是也要路径？路径是解题过程中应用的操作序列。,第三章 搜索技术,第一节 引言二、研究和选用搜索算法的原则5、状态空间搜索还是问题空间搜索？在解题过程中的每一时刻，所要解决的问题均处于一定的状态，搜索过程只是将一个状态变成另一个状态(如，一盘棋局变成另一盘棋局)，则称为状态空间搜索。若搜索的对象是问题，搜索的原则是把一个复杂的问题化为一组比较简单的子问题(如把一个复杂的下棋策略分为几个子策略)，则称为问题空间搜索。注：问题空间搜索常常比状态空间搜索有效，但算法要复杂些。,第三章 搜索技术,第一节 引言二、研究和选用搜索算法的原则6、有约束还是无约束？问题空间搜索时，若子问题间互相无约束关系，则求接比较简单，否则，一般需要回溯，即，放弃已解决的子问题，走回头路，寻找新的解法。7、数据驱动还是目标驱动？数据驱动是向前搜索，目标驱动是向后搜索。8、单向搜索还是双向搜索？,第三章 搜索技术,第一节 引言二、研究和选用搜索算法的原则9、盲目搜索还是启发式搜索？按照预定的控制策略实行搜索，在搜索过程中获取的中间信息不用来改进控制策略，称为盲目搜索，反之，称为启发式搜索。注：关于“启发式”，可有两种看法：1)任何有助于找到问题的解，但不能保证找到解的方法均是启发式方法；2)有助于加速求解过程和找到较优解的方法是启发式方法。,第三章 搜索技术,第一节 引言二、研究和选用搜索算法的原则10、有对手搜索还是无对手搜索？若有两个控制源均能改变同一状态空间，并且任何一方向目标前进时，另一方均试图将它从目标拉开，则称为有对手搜索，通常称为博弈搜索。注：博弈搜索算法可以看成是一种特殊的问题空间搜索。,第三章 搜索技术,第一节 引言三、一般搜索方法分类1、盲目搜索 1)无变量的盲目搜索 状态空间、问题空间的盲目搜索 深度优先、广度优先、代价优先、混合 向前、向后、双向 2)有变量的盲目搜索 通代2、启发式搜索,第三章 搜索技术,第二节 启发式搜索一、启发式搜索 把要求解的问题的具体领域的知识加进搜索算法中，控制搜索过程，以提高算法效率的搜索方法，称为启发式搜索。注：1)这里，搜索的对象(常称状态)往往是边搜索边生成，因此在考虑这种搜索的复杂性时，必须将搜索对象的生成和评估的代价计算在内。,第三章 搜索技术,第二节 启发式搜索一、启发式搜索注：2)根据启发性信息(特定领域的知识信息)，在生成搜索树时可考虑种种可能的选择：a)下一步展开哪个节点？b)是部分展开还是全部展开？c)使用哪个规则(算子)？d)怎样决定舍弃还是保留新生成的节点？e)怎样决定舍弃还是保留一棵子树？f)怎样决定停止或继续搜索？g)如何定义启发函数(估值函数)？h)如何决定搜索方向？,第三章 搜索技术,第二节 启发式搜索二、有序搜索算法1、基本思想 a)对于每个在搜索过程中遇到的新状态，计算一个估计值，根据估计值的大小，确定下一步将从哪一个状态开始继续前进。b)一般以估计值小者作为较优的状态，以此实现最佳优先搜索。c)计算状态估计值的函数是确定的，但每个状态的估计值的大小与初始状态到该路径有关。,第三章 搜索技术,第二节 启发式搜索二、有序搜索算法2、算法 1)建立一个空的状态序列SS 2)建立一个空的状态库SB 3)定义一个估值函数f 4)若初始状态为S0,则定义初始状态S0(0,f(0)为当前新状态 5)将当前新状态按估计值从小到大的顺序插入到SS中，若新状态为目标状态，则将相应状态插入到具有相同估计值的状态的最前面；否则将相应状态插入到具有相同估计值的状态的最后面,第三章 搜索技术,第二节 启发式搜索二、有序搜索算法2、算法 6)若在SS或SB中原有一个状态与当前新状态共一个状态，则删去原有状态 7)若新状态在SS的最前面，则转11)8)若某种状态极限已达到，则搜索失败，算法运行结束，无解,第三章 搜索技术,第二节 启发式搜索二、有序搜索算法2、算法 9)若任何规则均不能应用于状态序列SS中的第一个状态，或者虽能应用，但不能产生合适的新状态(在SS或SB中均没有者，称为新)，或虽能产生合适的新状态S(path2,f(path2),但不是改进型的(若SS和SB中已有状态S(path1,f(path1),它与新状态共一个状态S，且f(path2)f(path1),则称新状态不是改进型的)，则将此第一个状态从SS中除去，送入SB中，否则转12),第三章 搜索技术,第二节 启发式搜索二、有序搜索算法2、算法 10)若SS成为空序列，则搜索失败，算法运行结束，无解 11)若SS中第一个状态已是目标状态，则搜索成功，算法运行结束(若该状态形如S(path,f(path)，则解就是(path)；否则转9)12)取一个可应用于SS的第一个状态S(path,f(path)，并产生改进型的合适新状态的规则Rn，产生新状态T(path,n,f(path)，定义它为当前新状态，转5)#算法完,第三章 搜索技术,第二节 启发式搜索二、有序搜索算法2、算法 注：1)状态是带路径和估计值的状态，而状态只是一个状态 2)对当前生成的新状态是否是目标状态的判断需要两次 3)这里每次只生成一个后代 4)给定估计值函数f的意义，则有序搜索就可归结为已知的搜索，如令f为状态节点的深度，则有序搜索就成为广度优先搜索,第三章 搜索技术,第二节 启发式搜索二、有序搜索算法2、算法 注：5)有序搜索算法不一定找到解，即使有解 6)有序搜索算法的特点是使用启发式信息(表现在估计值函数f上)，可是启发式信息也会骗人，会引人误入歧途 7)有序搜索即使能找到解，也未必一定是最优的,第三章 搜索技术,第二节 启发式搜索二、有序搜索算法3、算法改进 1)用多个估计值函数来“层层设卡”2)对估计值函数的形式加以限制，以保证它一定能找到解，甚至一定能找到最优解。,第三章 搜索技术,第二节 启发式搜索三、估计值函数的改进 令S为初始节点，ti为一组目标节点，n,ni,nj为任意节点 k*(ni,nj)为从ni到nj的最小代价 g*(n)=k*(S,n)为从初始节点S到节点n的最小代价 h*(n)=min k*(n,ti)为从节点n到一个目标节点ti的最小代价 f*(n)=g*(n)+h*(n)为从初始节点出发，经过节点n，到达一个目标节点的最小代价,ti,第三章 搜索技术,第二节 启发式搜索三、估计值函数的改进 g(n)为对g*(n)的估计，g(n)0 h(n)为对h*(n)的估计，h(n)0 f(n)=g(n)+h(n)为每个节点n处的估计值函数,第三章 搜索技术,第二节 启发式搜索四、H算法 使用上述改进的估计值函数f的有序搜索算法就是H算法。注：1)g(n)是容易找到的，如将从初始节点到节点n实际上走过的路径的代价作为g(n)，且永远有g*(n)g(n)。g(n)不断改进，随着更多的搜索信息的获取，g(n)的值呈下降趋势。2)h(n)的选取要与具体问题领域的启发信息相关。3)由于h(n)的选择仍有很大的随意性，因此，H算法并不能保证找到一个解，更不能保证找到最优解。从而需要改进。,第三章 搜索技术,第二节 启发式搜索五、H*算法 1.在H算法中规定h(n)h*(n)2.推广k*(ni,nj)的定义：令k*(n1,n2,nm)为从n1出发，经过n2,到达nm的最小代价，规定存在一个正整数e0，使得对任意的ni,nj,nm(njnm)均有k*(ni,nj,nm)-k*(ni,nj)e 3.经过如此限制以后的H算法就是H*算法。注：1)可以证明：只要目标状态存在，并且从初始状态到目标状态有一条通路，则H*算法一定在有限步内终止，并找到一个最优解(即代价为最低的解）。,第三章 搜索技术,第二节 启发式搜索五、H*算法注：2)H*算法的搜索效率在很大程度上取决于函数h(n)的选择，它要求h(n)h*(n)，但若h(n)太小，则启发信息就很少。3)若h(n)0，g(n)为搜索深度或代价，则H*算法将退化为广度优先搜索或代价优先搜索。4)h(n)的值在满足小于或等于h*(n)的前提下越大越好，启发式信息多(即h值大)的H*算法展开的节点是启发式信息少(即h值小)的H*算法展开的节点的子集。,第三章 搜索技术,第二节 启发式搜索五、H*算法注：5)若估计值函数h(n)满足单调条件：h(ni)-h(nj)k*(ni,nj)（其中k*(ni,nj)是从ni到nj的最小代价，nj是ni的后续节点），则H*算法是循着从初始状态通向该节点的最优路径到达该节点的。6)在H*算法中，每次只生成一个后续节点。,第三章 搜索技术,第二节 启发式搜索六、完全展开的有序搜索算法 1)建立一个空的状态序列SS 2)建立一个空的状态库SB 3)定义一个估值函数f 4)若初始状态为S0,则定义初始状态S0(0,f(0)为当前新状态 5)将所有当前新状态按估计值从小到大的顺序插入到SS中,第三章 搜索技术,第二节 启发式搜索六、完全展开的有序搜索算法 6)若在SS或SB中原有一个状态与当前某个新状态共一个状态，则删去原有状态 7)若SS的第一项是一个新状态，则转11)8)若某种状态极限已达到，则搜索失败，算法运行结束，无解,第三章 搜索技术,第二节 启发式搜索六、完全展开的有序搜索算法 9)若任何规则均不能应用于状态序列SS中的第一个状态，或者虽能应用，但不能产生改进型的合适新状态，则将此第一个状态从SS中除去，送入SB中，否则转12)10)若SS成为空序列，则搜索失败，算法运行结束，无解 11)若SS中第一个状态已是目标状态，则搜索成功，算法运行结束(若该状态形如S(path,f(path)，则解就是(path)；否则转9),第三章 搜索技术,第二节 启发式搜索六、完全展开的有序搜索算法 12)取所有可应用于SS的第一个状态S(path,f(path)，并产生各不相同的改进型的合适新状态的规则Ri(iI)，产生新状态集T(path,i,f(path)，其中对属于同一状态的各个状态只取一个最优者，转5)#算法完,第三章 搜索技术,第二节 启发式搜索七、A算法 使用估计值函数f(n)=g(n)+h(n)的完全展开的有序搜索算法。,第三章 搜索技术,第二节 启发式搜索八、A*算法 在A算法规定：h(n)h*(n),k*(ni,nj,nm)-k*(ni,nj)e,则A算法成为A*算法注：1)A*算法与H*算法的主要区别有a)在H*算法中每次只生成一个后继节点，而在A*算法中每次生成一个节点的所有节点b)在H*算法中，每生成一个新节点，就询问它是否是目标节点，而在A*算法中，只询问栈顶节点是否是目标节点 2)在A*算法中，估计值函数f(n)=g(n)+h(n)的选择是一个关键,第三章 搜索技术,第二节 启发式搜索八、A*算法注：3)A*算法一定能保证找到最优解 4)若按展开的节点个数来估计它的效率，则当启发式函数h的值单调上升时，它的效率只会上升，不会下降，且有较合理的渐近性质 5)若不是考虑被展开的节点个数，而是考虑各节点被展开的次数，则A*算法在最坏情况下表示出很高的复杂性 6)为了避免不正常的h值对解题路径的影响，Martelli提出了B算法，基本思想是h(n)可动态修改,在h值不正常时，只根据g的值来选择展开的节点。,第三章 搜索技术,第二节 启发式搜索八、A*算法注：7)在f(x)=g(x)+h(x)中，g(x)是“经验”项，起着稳定形势的作用，而h(x)是“冒险”项。九、双向启发式搜索十、几种特殊的启发式搜索 1、生成与测试方法 穷举？仍需要经验知识的指导 2、并行搜索法 3、爬山法 4、黄金分割法 十一、与或树的启发式搜索 AO*算法,第二节 启发式搜索十二、遗传算法 1、基本概念 模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法。,第三章 搜索技术,第三章 搜索技术,第二节 启发式搜索十二、遗传算法2、基本思想 寻找X，使得,第三章 搜索技术,第二节 启发式搜索十二、遗传算法2、基本思想式中，为决策变量，f(X)为目标函数，U是基本空间，R是U的一个子集。遗传算法中，将n维决策向量用n个记号所组成的符号串X来表示：,第三章 搜索技术,第二节 启发式搜索十二、遗传算法2、基本思想 把每一个 看作一个遗传基因，它的所有可能取值称为等位基因，这样，X就可看作是由n个遗传基因所组成的一个染色体。染色体的长度可以是固定的，也可以是变化的。等位基因可以是一组整数，也可以是某一范围内的实数值，或者是记号。最简单的等位基因是由0和1这两个整数组成的，相应的染色体就可表示为一个二进制符号串。,第三章 搜索技术,第二节 启发式搜索十二、遗传算法2、基本思想这种编码所形成的排列形式X是个体的基因型，与它对应的X值是个体的表现型。染色体X也称为个体X，对于每一个个体X，要按照一定的规则确定出其适应度。个体的适应度与其对应的个体表现型X的目标函数值相关联，X越接近于目标函数的最优点，其适应度越大；反之，其适应度越小。,第三章 搜索技术,第二节 启发式搜索十二、遗传算法2、基本思想遗传算法中，决策变量X组成了问题的解空间。对问题最优解的搜索是通过对染色体X的搜索过程来进行的，从而由所有的染色体X就组成了问题的搜索空间。生物的进化是以集团为主体的。与此相对应，遗传算法的运算对象是由M个个体所组成的集合，称为群体。,第三章 搜索技术,第二节 启发式搜索十二、遗传算法2、基本思想与生物一代一代的自然进化过程相似，遗传算法的运算过程也是一个反复迭代过程，第t代群体记做P(t),经过一代遗传和进化后，得到第t+1代群体，它们也是由多个个体组成的集合，记做P(t+1)。这个群体不断地经过遗传和进化操作，并且每次都按照优胜劣汰的规则将适应度较高的个体更多地遗传到下一代，这样最终在群体中将会得到一个优良的个体X，它所对应的表现型X将达到或接近于问题的最优解。,第三章 搜索技术,第二节 启发式搜索十二、遗传算法2、基本思想生物的进化过程主要是通过染色体之间的交叉和染色体的变异来完成的。遗传算法中最优解的搜索过程也模仿生物的这个进化过程，使用所谓的遗传算子(genetic operators)作用于群体P(t)中，进行下述遗传操作，从而得到新一代群体P(t+1)。,第三章 搜索技术,第二节 启发式搜索十二、遗传算法2、基本思想选择(selection):根据各个个体的适应度，按照一定的规则或方法，从第t代群体P(t)中选择出一些优良的个体遗传到下一代群体P(t+1)中。交叉(crossover):将群体P(t)内的各个个体随机搭配成对，对每一个个体，以某个概率(称为交叉概率，crossover rate)交换它们之间的部分染色体。,第三章 搜索技术,第二节 启发式搜索十二、遗传算法2、基本思想变异(mutation):对群体P(t)中的每一个个体，以某一概率(称为变异概率，mutation rate)改变某一个或一些基因座上基因值为其它的等位基因。,第三章 搜索技术,第二节 启发式搜索十二、遗传算法3、特点以决策变量的编码作为运算对象以目标函数值作为搜索信息同时进行解空间的多点搜索使用概率搜索技术,第三章 搜索技术,第二节 启发式搜索十二、遗传算法4、算法实现关键染色体编码群体的初始化适应值评价选择种群（轮盘赌）种群交配种群变异算法流程,第三章 搜索技术,第二节 启发式搜索十二、遗传算法5、基本遗传算法 基本遗传算法（Simple Genetic Algorithms,简称SGA）是一种统一的最基本的遗传算法，它只使用选择、交叉、变异这三种基本遗传算子，其遗传进化操作过程简单，容易理解，是其他一些遗传算法的雏形和基础，它不仅给各种遗传算法提供了一个基本框架，同时也具有一定的应用价值。,第三章 搜索技术,第二节 启发式搜索十二、遗传算法5、基本遗传算法 基本遗传算法的构成要素 染色体编码方法。基本遗传算法使用固定长度的二进制符号串来表示群体中的个体，其等位基因是由二值符号集0，1所组成的。初始群体中各个个体的基因值可用均匀分布的随机数来生成。,第三章 搜索技术,第二节 启发式搜索十二、遗传算法5、基本遗传算法 基本遗传算法的构成要素个体适应度评价。基本遗传算法按与个体适应度成正比的概率来决定当前群体中每个个体遗传到下一代群体中的机会多少。为正确计算这个概率，这里要求所有个体的适应度必须为正数或零。遗传算子。基本遗传算法使用下述三种遗传算子：选择运算使用比例选择算子，交叉运算使用单点交叉算子，变异运算使用基本位变异算子或均匀变异算子。,第三章 搜索技术,第二节 启发式搜索十二、遗传算法5、基本遗传算法 基本遗传算法的构成要素 基本遗传算法的运行参数。基本遗传算法有下述4个运行参数需要提前设定：群体大小M，即群体中所含个体数目，一般取为20100；遗传运算的终止进化代数T，一般取为100500；交叉概率Pc，一般取为0.40.99；变异概率Pm，一般取为0.00010.1。,第三章 搜索技术,第二节 启发式搜索十二、遗传算法5、基本遗传算法 基本遗传算法的实现个体适应度评价在遗传算法中，以个体适应度的大小来确定该个体被遗传到下一代群体中的概率。个体适应度越大，该个体被遗传到下一代的概率也越大；反之，个体的适应度越小，该个体被遗传到下一代的概率也越小。基本遗传算法使用比例选择算子来确定群体中各个个体遗传到下一代群体中的数量。为正确计算不同情况下各个个体的遗传概率，要求所有个体的适应度必须为正数或零，不能是负数。,第三章 搜索技术,第二节 启发式搜索十二、遗传算法5、基本遗传算法 基本遗传算法的实现比例选择算子比例选择实际上是一种有退还随机选择,也叫做赌盘(Roulette Wheel)选择,因为这种选择方式与赌博中的赌盘操作原理非常相似。比例选择算子的具体执行过程是：先计算出群体中所有个体的适应度之和；其次计算出每个个体的相对适应度的大小，此值即为各个个体被遗传到下一代群体中的概率；最后再使用模拟赌盘操作（即0到1之间的随机数）来确定各个个体被选中的次数。,第三章 搜索技术,第二节 启发式搜索十二、遗传算法5、基本遗传算法 基本遗传算法的实现单点交叉算子单点交叉算子是最常用和最基本的交叉操作算子。单点交叉算子的具体执行过程如下：对群体中的个体进行两两随机配对；对每一对相互配对的个体，随机设置某一基因座之后的位置为交叉点；对每一对相互配对的个体，依设定的交叉概率 在其交叉点处相互交换两个个体的部分染色体，从而产生出两个新个体。,第三章 搜索技术,第二节 启发式搜索十二、遗传算法5、基本遗传算法 基本遗传算法的实现基本位变异算子基本位变异算子的具体执行过程为：对个体的每一个基因座，依变异概率 指定其为变异点；对每一个指定的变异点，对其基因值做取反运算或用其他等位基因值来代替，从而产生出一个新的个体。,第三章 搜索技术,第二节 启发式搜索十二、遗传算法5、基本遗传算法 遗传算法的应用步骤遗传算法提供了一种求解复杂系统优化问题的通用框架。对于具体问题，可按下述步骤来构造：确定决策变量及其各种约束条件，即确定出个体的表现型X和问题的解空间；建立优化模型，即描述出目标函数的类型及其数学描述形式或量化方法；,第三章 搜索技术,第二节 启发式搜索十二、遗传算法5、基本遗传算法 遗传算法的应用步骤确定表示可行解的染色体编码方法，即确定出个体的基因型X及遗传算法的搜索空间；确定解码方法，即确定出由个体基因型X到个体表现型X的对应关系或转换方法；确定个体适应度的量化评价方法，即确定出由目标函数值 到个体适应度的转换规则；,第三章 搜索技术,第二节 启发式搜索十二、遗传算法5、基本遗传算法 遗传算法的应用步骤设计遗传算子，即确定出选择运算、交叉运算、变异运算等遗传算子的具体操作方法；确定遗传算法的有关运行参数。,第三章 搜索技术,第二节 启发式搜索十二、遗传算法6、应用组合优化生产调度问题自动控制机器人学图象处理,第三章 搜索技术,第二节 启发式搜索十二、遗传算法7、免疫遗传算法 基于免疫的改进遗传算法，是免疫原理与传统遗传算法的结合。算法的核心在于免疫算子的构造，而免疫算子又是通过接种疫苗和免疫选择两个步骤完成的。在理论上，免疫算法是概率1收敛的。,第三章 搜索技术,第二节 启发式搜索十三、免疫算法1、免疫算法流程图,第三章 搜索技术,第二节 启发式搜索十三、免疫算法2、免疫算法七要素识别抗原将目标函数和约束作为抗原生成初始化的抗体随机生成N个抗体计算亲和度抗体和抗原的亲和度抗体和抗体的亲和度,第三章 搜索技术,第二节 启发式搜索十三、免疫算法2、免疫算法七要素记忆细胞分化与抗原有最大亲和度的抗体加入记忆细胞抗体促进和抑制促进高亲和度的个体,消除低期望值的抗体产生新的抗体选择两个抗体做变异和交叉,得到新的抗体结束条件,第三章 搜索技术,第二节 启发式搜索十三、免疫算法3、常用免疫算法负选择算法依靠T细胞表面的受体，识别非自体，并消灭非自体（注：受体与所有的自体均不匹配）克隆选择算法只关注抗原和抗体的亲和度对B细胞的复制的影响，而不考虑抗体之间的亲和度,免疫系统与一般免疫算法之间的比较,第三章 搜索技术,第二节 启发式搜索十四、模拟退火算法(Simulated Annealing)1、基本思想(1)是基于Monte Carlo迭代求解策略的一种随机寻优算法，源于物理退火原理；类似物理退火让固体粒子收敛到一个能量最低状态的过程，实现算法最终收敛到最优解的目的。(2)结合爬山法和随机行走,第三章 搜索技术,第二节 启发式搜索十四、模拟退火算法(Simulated Annealing)1、基本思想(3)结合概率突跳特性在解空间中随机寻找目标函数的全局最优解。(4)首先生成一个随机解,然后对其进行扰动(在同一温度下进行多次扰动),对扰动后得到的解进行评估与替换,温度逐渐下将形成多代。,第三章 搜索技术,第二节 启发式搜索十四、模拟退火算法(Simulated Annealing)2、算法步骤标准模拟退火算法的一般步骤可描述如下：给定初温，随机产生初始状态，令；Repeat:Repeat 产生新状态；,第三章 搜索技术,第二节 启发式搜索十四、模拟退火算法(Simulated Annealing)2、算法步骤 Until 抽样稳定准则满足；退温，并令；Until 算法终止准则满足；输出算法搜索结果。,第三章 搜索技术,第二节 启发式搜索十四、模拟退火算法(Simulated Annealing)3、算法关键参数和操作的设定 模拟退火算法包括三函数两准则，即状态产生函数、状态接受函数、温度更新函数、内循环终止准则和外循环终止准则，这些环节的设计将决定SA算法的优化性能。此外，初温的选择对SA算法性能也有很大影响。,第三章 搜索技术,第二节 启发式搜索十四、模拟退火算法(Simulated Annealing)3、算法关键参数和操作的设定状态产生函数 设计状态产生函数（邻域函数）的出发点应该是尽可能保证产生的候选解遍布全部的解空间。通常，状态产生函数由两部分组成，即产生候选解的方式和候选解产生的概率分布。,第三章 搜索技术,第二节 启发式搜索十四、模拟退火算法(Simulated Annealing)3、算法关键参数和操作的设定状态接受函数状态接受函数一般以概率的方式给出，不同接受函数的差别主要在于接受概率的形式不同。,第三章 搜索技术,第二节 启发式搜索十四、模拟退火算法(Simulated Annealing)3、算法关键参数和操作的设定初温 实验表明，初温越大，获得高质量解的几率越大，但花费的计算时间将增加。初温的确定应折衷考虑优化质量和优化效率。,第三章 搜索技术,第二节 启发式搜索十四、模拟退火算法(Simulated Annealing)3、算法关键参数和操作的设定温度更新函数 温度更新函数，即温度的下降方式，用于在外循环中修改温度值。目前，最常用的温度更新函数为指数退温函数。,第三章 搜索技术,第二节 启发式搜索十四、模拟退火算法(Simulated Annealing)3、算法关键参数和操作的设定内循环终止准则 内循环终止准则，或称Metropolis抽样稳定准则，用于决定在各温度下产生候选解的数目。,第三章 搜索技术,第二节 启发式搜索十四、模拟退火算法(Simulated Annealing)3、算法关键参数和操作的设定外循环终止准则 外循环终止准则，即算法终止准则，用于决定算法何时结束。设置温度终值是一种简单的方法。SA算法的收敛性理论中要求温度终值趋于零，这显然不合实际。,第三章 搜索技术,第二节 启发式搜索十五、禁忌搜索算法(Tabu Search)1、基本思想 模仿了人类的记忆功能，是一种全局逐步寻优算法。对已经搜索过的局部最优解进行标记（禁忌）在迭代搜索中尽量避免重复相同的搜索（但不是完全隔绝）,第三章 搜索技术,第二节 启发式搜索十五、禁忌搜索算法(Tabu Search)2、算法步骤(1)给定算法参数，随机产生初始解x，置禁忌表为空。(2)判断算法终止条件是否满足？若是，则结束算法并输出优化结果；否则，继续以下步骤。(3)利用当前解x的邻域函数产生其所有（或若干）邻域解，并从中确定若干个候选解。(4)对候选解判断藐视准则是否满足？若成立，则用满足藐视准则的最佳状态y代替x成为新的当前解，即x=y，并用与y对应的禁忌对象替换最早进入禁忌表的禁忌对象，同时用y替换“best so far”状态，然后转步骤2；否则，继续以下步骤。,第三章 搜索技术,第二节 启发式搜索十五、禁忌搜索算法(Tabu Search)2、算法步骤(5)判断候选解对应的各对象的禁忌属性，选择候选解集合中非禁忌对象对应的最佳状态为新的当前解，同时，用与之对应的禁忌对象替换最早进入禁忌表的禁忌对象元素。(6)转步骤(2)#注：1)其中，邻域函数、禁忌对象、禁忌表和藐视准则构成了禁忌搜索算法的关键。2)对于邻域函数，沿用局部邻域搜索的思想，用于实现邻域搜索；3)禁忌表和禁忌对象的设置，体现了算法避免迂回搜索的特点；4)藐视准则，则是对优良状态的奖励，它是对禁忌策略的一种放松。,第三章 搜索技术,第二节 启发式搜索十六、蚁群算法1、基本原理(1)蚂蚁觅食时，在它走过的路上，留下外激素，这些外激素就象留下路标一样，留给后来“蚁”一个路径的标志。(2)后面的蚂蚁，就会沿着有外激素的路径行走（外激素越多引诱蚂蚁的能力就越强）。(3)通过正反馈机制使得更多的蚂蚁在蚁穴与食物之间的最短路径上行进，最终所有蚂蚁都在最优路径上行进。,第三章 搜索技术,第二节 启发式搜索十六、蚁群算法2、算法(1)一群蚂蚁随机从出发点出发，遇到食物，衔住食物，沿原路返回(2)蚂蚁在往返途中，在路上留下外激素标志(3)外激素将随时间逐渐蒸发（一般可用负指数函数来描述，即乘上因子e-at）(4)由蚁穴出发的蚂蚁,其选择路径的概率与各路径上的外激素浓度成正比 注：利用同样原理可以描述蚁群进行多食物源的寻食情况,第三章 搜索技术,第二节 启发式搜索十六、蚁群算法3、算法应用(1)用于重建通讯路由(2)用于求解TSP（流动货郎问题)一群蚂蚁由A点同时出发，进行漫游，倾向选较近的城市 把所有城市都游过后，返回，并留下外激素，其量与路程长度成反比 所有蚂蚁都返回后，图上留下外激素的标志进行第二轮的漫游（倾向选激素多的路径）,第三章 搜索技术,第二节 启发式搜索十六、蚂蚁算法3、算法应用(3)蚂蚁清除垃圾 蚂蚁能将巢里的垃圾或死蚂蚁,打扫成几大堆给以清除 一群蚂蚁随机出发,遇到垃圾,就将其拉走（方向也是随机的）拉垃圾时,若碰到某一堆垃圾时,就放下 放下垃圾后,再随时机进行打扫工作,第三章 搜索技术,第二节 启发式搜索十七、粒子群算法1、基本原理 模拟鸟集群飞行觅食的行为，鸟之间通过集体的协作使群体达到最优目的。一群鸟在空中飞行，每个鸟遵守以下规则：1）避免与相邻的鸟发生碰撞冲突2）尽量与自己周围的鸟在速度上保持协调和一致3）尽量试图向自己所认为的群体中靠近,第三章 搜索技术,第二节 启发式搜索十七、粒子群算法2、算法思想每个优化问题的解作为搜索空间中的一只鸟。称之为“粒子(Particle)”所有的粒子都有一个由被优化的函数决定的适应值每个粒子有一个速度决定他们飞翔的方向和距离粒子们就追随当前的最优粒子在解空间中搜索,第三章 搜索技术,第二节 启发式搜索十七、粒子群算法3、算法 初始化为一群随机粒子。然后通过叠代找到最优解。在每一次叠代中，粒子通过跟踪两个极值来更新自己。第一个就是粒子本身所找到的最优解。这个解叫做个体极值pBest.另一个极值是整个种群目前找到的最优解。这个极值是全局极值gBest。另外,也可以不用整个种群而只是用其中一部分的邻居。,第三章 搜索技术,第三节 博弈树搜索一、博弈树 若参加搜索的不只有一个主体，而是对抗性的敌我双方，则搜索的进程不仅取决于一方，而且取决于对方应付的策略，由此产生的搜索树，称为博弈树。注：博弈树很象与或树,第三章 搜索技术,第三节 博弈树搜索二、博弈树评价原则1、假定对手不会犯错误2、对手总是选择对他最有利的步子走3、自己不采取任何冒险行动4、在最坏的可能中选择最好的注：博弈树评价原则也称为极小极大原则，即在极小中取极大，因此，博弈树也称为极小极大树,第三章 搜索技术,第三节 博弈树搜索三、极小极大算法1、以甲为博弈树的树根和或节点，并把甲送入待展开节点库TB2、若TB为空，则对博弈树处理如下：1)若某个或节点的所有子与节点的值均为已知，则此或节点的值定义为所有子与结点的值中之最大者（注：赢最大、平次之、输最小）2)若某个与节点的所有子或节点的值均为已知，则此与节点的值定义为所有子或结点的值中之最小者 3)反复执行步骤1）、2），直至根节点被赋值，算法运行结束,第三章 搜索技术,第三节 博弈树搜索三、极小极大算法3、若TB不为空，则从TB任取节点n，删去n，并 1)若n已直接表现出甲之赢、输或平，则对博弈树的n节点赋以相应的值(赢、输或平)，转2;2)否则，若n为或节点，则生成n的所有子与节点，长在博弈树上，也送入TB之中，转2；3)否则，若n为与节点，则生成n的所有子或节点，长在博弈树上，也送入TB之中，转2；算法完#,第三章 搜索技术,第三节 博弈树搜索三、极小极大算法注：1)博弈的结局可能不是简单的输赢，而是有几种可能的得分，但原理一样 2)该算法并不保证一定结束，事实上，若想穷尽博弈的所有可能性，则在许多情况下不会结束 3)博弈树中的每一分叉，必须有意义，该意义是根据具体领域情况而定 4)博弈树体积可能会达到计算机根本无法处理地步，穷举战术行不通 5)对博弈树的穷举搜索到一定深度就不再向下走,第三章 搜索技术,第三节 博弈树搜索三、极小极大算法注：6)不根据最后实际计算出的输赢来评分，而是根据在一定深度处的节点的估计值来评分，即用估计值代替实际的搜索 7)计算这种估计值的函数，称为静态估值函数f，它相当于 A*算法中的函数h 8)对于表示输、赢、平的叶结点，其估计值可定义为：f(赢)=+、f(输)=-、f(平)=0,第三章 搜索技术,第三节 博弈树搜索三、极小极大算法注：9)一般情况下，f可定义为一个多项式，甚至线性函数，但若要取得较好的效果，则f往往定义为非线性的，此时，计算复杂性就增加了。10)除了确定静态估值函数外，还应尽量避免生成无用处的后代-消除冗余,第三章 搜索技术,第三节 博弈树搜索三、博弈树优化1、优化方法 通过剪枝去除冗余现象2、冗余情形 a)极大值冗余,第三章 搜索技术,第三节 博弈树搜索三、博弈树优化2、冗余情形 b)极小值冗余,1,2,3,4,5,6,min,max,max,min,f(4)=25,f(2)=10,第三章 搜索技术,第三节 博弈树搜索三、博弈树优化3、剪枝方法 a)-剪枝 将极大值冗余子树剪去的方法 b)-剪枝 将极小值冗余子树剪去的方法,第三章 搜索技术,第三节 博弈树搜索四、带剪枝的博弈树搜索算法使用静态估值函数以及-剪枝和-剪枝，形成带剪枝的博弈树搜索算法1、建立一个空的棋局栈PSi,j,其中，对每个i：PSi,1是棋局内容，PSi,2是“与”或“或”PSi,3是搜索深度，PSi,4是估计值 PSi,5是生成子节点数2、确定正整数depth为最大推理深度,第三章 搜索技术,第三节 博弈树搜索四、带剪枝的博弈树搜索算法3、建立已知结果的棋局库PB,PB的元素与PS的元素形式相同，并且每个元素的第一、第二和第四分量都已有确定的值；4、建立根节点：PS1,1=初始棋局 PS1,2=“或”PS1,3=0 PS1,4=-PS1,5=05、t=1,第三章 搜索技术,第三节 博弈树搜索四、带剪枝的博弈树搜索算法6、若PSt,1=X1,PSt,2=X2,且XPB,则(1)PSt,4=X4(2)转107、若PSt,3=depth，则(1)PSt,4=f(PSt,1)(f是估值函数)(2)转108、若PSt,1不能生成新的后代，则(1)若PSt,5=0，则PSt,4=f(PSt,1)(2)转10,第三章 搜索技术,第三节 博弈树搜索四、带剪枝的博弈树搜索算法9、生成PSt,1的一个新后代：(1)PSt,5=PSt,5+1(后代计数)(2)t=t+1(3)PSt,1=新棋局(4)PSt,2=if PSt-1,2=“或”then“与”else“或”(5)PSt,3=PSt-1,3+1(6)PSt,4=if PSt,2=“或”then-else+(7)PSt,5=0(8)转610、若t=1则算法运行结束，最后的估计值已算出,第三章 搜索技术,第三节 博弈树搜索四、带剪枝的博弈树搜索算法11、t=t-112、若PSt,2=“或”，则(1)若PSt+1,4PSt,4,则PSt,4=PSt+1,4(取极大值)，否则转8(2)若t=1，则转8(3)若PSt,4PSt-1,4,则t=t-1(剪枝)(4)转8,第三章 搜索技术,第三节 博弈树搜索四、带剪枝的博弈树搜索算法13、若PSt,2=“与”，则(1)若PSt+1,4PSt,4,则PSt,4=PSt+1,4(取极小值)，否则转8(2)若t=1，则转8(3)若PSt,4PSt-1,4,则t=t-1(剪枝)(4)转8#算法完,第三章 搜索技术,第三节 博弈树搜索四、带剪枝的博弈树搜索算法注：1)该算法是从开局先行者的立场出发的，计算所得根节点的值是对先行者前途的预测 2)该算法只给出对先行者前途的估计值，以及第一步应该怎么走，而没有给出全局棋每一步的走法 3)该算法的缺陷就是需说明是从某人的立场出发，若换一个立场，则要做一个对称的改变,第三章 搜索技术,第三节 博弈树搜索五、带剪枝的博弈树搜索算法的改进1、采用负极大值原理 兼顾双方立场，消除与或节点差别，以统一方式处理，形式上只取极大值。若一节点的估计值代表一方的前途预测，则其负值代表另一方的前途预测。对无后代的节点和搜索层次达到极限的节点，仍用静态估计函数来计算它们的估计值，对于其它节点，均令父结点的估计值为各子节点的估计值的负数的极大值，即 PSi,4=max(-PSi+1,4)(i+1遍及i的所有子节点）,第三章 搜索技术,第三节 博弈树搜索五、带剪枝的博弈树搜索算法的改进2、B*算法(1)尽早查出不合用的坏分枝，并把它剪掉(改进-剪枝)(2)合理地确定搜索的深度限制(3)每个节点设立两个估计值：乐观估计和悲观估计，且两个估计值可动态可变。,思考题,如何认识启发式搜索的基本思想？H*