人工智能 chapter3.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第三章 搜索原理,上一章中我们研究了知识表示方法，为人工智能问题的求解打下了基础。从问题表示到问题的解决，有一个求解的过程。接下来要研究的是求解的过程，采用的基本方法包括搜索和推理。本章先介绍搜索技术，将要讨论问题求解的搜索原理，包括一些早期的搜索技术或用于解决比较简单问题的搜索原理和一些比较新的能够求解比较复杂问题的搜索原理，包括,A*,算法、遗传算法和模拟退火算法等。,1,状态图的例子：,设有三枚钱币，其排列处在“正，正，反”状态，现允许每次可翻动其中任意一个钱币，问只允许操作三次的情况下，如何翻动钱币使其变成“正，正，正”或“反，反，反”状态。,若“正面”用“,1”,表示，“反面”用“,0”,表示，则问题化成求解从初始状态（,1,1,0,）到目标状态（,1,，,1,，,1,）或,(0,0,0),的路径问题，且该路径的长度为,3,。,（,1,，,1,，,0,）,-,（,1,，,1,，,1,）或（,1,1,0,）,-(0,0,0),2,3,八数码问题（,8-puzzle problem,）,在一个,3*3,的方格棋盘上放置着,1,，,2,，,3,，,4,，,5,，,6,，,7,，,8,八个数码，每个数码占一个格，且有一个空格。这些数码可在棋盘上移动，其移动规则是：与空格相邻的数码方可移入空格。现在的问题是对于给定的初始棋局和目标棋局（如下图），给出移动的序列。,4,5,3.1,盲目搜索,盲目搜索又叫做无信息搜索，一般只适用于求解比较简单的问题。,(1),图搜索策略,(2),宽度优先搜索,(3),深度优先搜索,(4),等,代价搜索,6,图搜索策略,7,图的说明：一个图由节点的集合组成，节点之间由弧线连接。如果弧是有方向的话，则这种图称为有向图，否则称为无向图。在图搜索策略中，节点代表状态描述，弧代表操作。,图搜索,(GRAPHSEARCH),的一般过程如下：,建立一个只含有起始节点,S,的搜索图,G,，把,S,放到一个叫做,OPEN,的未扩展节点表中（简称,OPEN,表）。,建立一个叫做,CLOSED,的已扩展节点表（简称,CLOSED,表），其初始为空表。,LOOP,：若,OPEN,表是空表，则失败退出。,8,(4),选择,OPEN,表上的第一个节点，把它从,OPEN,表移出并放进,CLOSED,表中。称此节点为节点,n,，,它是,CLOSED,表中节点的编号。,(5),若,n,为一目标节点，则有解并成功退出，此解是追踪图,G,中沿着指针从,n,到,S,这条路径而得到的,(,指针将在第,7,步中设置,),。,(6),扩展节点,n,，,同时生成不是,n,的祖先的那些后继节点的集合,M,。把,M,的这些成员作为,n,的后继节点添入图,G,中。,9,(7),对那些未曾在,G,中出现过的,(,既未曾在,OPEN,表上或,CLOSED,表上出现过的,)M,成员设置一个通向,n,的指针。把,M,的这些成员加进,OPEN,表。对已经在,OPEN,或,CLOSED,表上的每一个,M,成员，确定是否需要更改通到,n,的指针方向。对已在,CLOSED,表上的每个,M,成员，确定是否需要更改图,G,中通向它的每个后裔节点的指针方向。,(8),按某一任意方式或按某个探试值，重排,OPEN,表。,(9)GO LOOP,。,10,图搜索算法中的几个重要名词,3,搜索图与搜索树,此过程生成一个明确的图,G(,称为搜索图,),和一个,G,的子集,T(,称为搜索树,),，树,T,上的每个节点也在图,G,中。搜索树是由第,7,步中设置的指针来确定的。,G,中的每个节点,(,除,S,外,),都有一个只指向,G,中一个父辈节点的指针，该父辈节点就定为树中那个节点的唯一父辈节点。,11,一般搜索过程框图,12,图搜索方法的几点分析：,图搜索过程的第,8,步对,OPEN,表上的节点进行排序，以便能够从中选出一个“最好”的节点作为第,4,步扩展用。这种排序可以是任意的即盲目的,(,属于盲目搜索,),，也可以用以后要讨论的各种启发思想或其它准则为依据,(,属于启发式搜索,),。每当被选作扩展的节点为目标节点时，这一过程就宣告成功结束。这时，能够重现从起始节点到目标节点的这条成功路径，其办法是从目标节点按指针向,S,返回追溯。当搜索树不再剩有未被扩展的端节点时，过程就以失败告终,(,某些节点最终可能没有后继节点，所以,OPEN,表可能最后变成空表,),。在失败终止的情况下，从起始节点出发，一定达不到目标节点。,13,宽度优先搜索,(breadth-first search),的定义：,如果搜索是以接近起始节点的程度依次扩展节点的，那么这种搜索就叫做宽度优先搜索,(breadth-first search),。,从图可见，这种搜索是逐层进行的；在对下一层的任一节点进行搜索之前，必须搜索完本层的所有节点。,宽度优先搜索,14,宽度优先搜索算法,如下：,(1),把起始节点放到,OPEN,表中,(,如果该起始节点为一目标节点，则求得一个解答,),。,(2),如果,OPEN,是个空表，则没有解，失败退出；否则继续。,(3),把第一个节点,(,节点,n),从,OPEN,表移出，并把它放入,CLOSED,扩展节点表中。,(4),扩展节点,n,。,如果没有后继节点，则转向上述第,(2),步。,(5),把,n,的所有后继节点放到,OPEN,表的末端，并提供从这些后继节点回到,n,的指针。,(6),如果,n,的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向第,(2),步。,15,16,宽度优先搜索方法分析：,宽度优先搜索是图搜索一般过程的特殊情况，将图搜索一般过程中的第,8,步具体化为本算法中的第,6,步，这实际是将,OPEN,表作为“先进先出”的队列进行操作。宽度优先搜索方法能够保证在搜索树中找到一条通向目标节点的最短途径；这棵搜索树提供了所有存在的路径,(,如果没有路径存在，那么对有限图来说，我们就说该法失败退出；对于无限图来说，则永远不会终止,),。例：把宽度优先搜索应用于八数码难题时所生成的搜索树，这个问题就是要把初始棋局变为如下目标棋局的问题：,17,18,19,通过该算法及,open,和,closed,表的变化过程可知，,open,表的数据结构是一个队列（,queue,），,closed,表是一个顺序表,(sequence list),，,保存了搜索路径。,该算法是完备的，即问题有解的话，则一定能找到解，且是最优解（路径最短），这是优点，缺点是搜索效率低。,20,深度优先搜索,另一种盲目,(,无信息,),搜索叫做,深度优先搜索,(depth-first search),。,下图是一个深度优先搜索示意图。分析深度优先搜索示意图可看出，在深度优先搜索中，我们首先扩展最新产生的,(,即最深的,),节点。深度相等的节点可以任意排列。,21,定义节点的深度如下：,(1),起始节点,(,即根节点,),的深度为,0,。,(2),任何其它节点的深度等于其父辈节点深度加上,1,。,对于许多问题，其状态空间搜索树的深度可能为无限深，或者可能至少要比某个可接受的解答序列的已知深度上限还要深。为了避免考虑太长的路径,(,防止搜索过程沿着无益的路径扩展下去,),，往往给出一个节点扩展的最大深度,深度界限。任何节点如果达到了深度界限，那么都将把它们作为没有后继节点处理。值得说明的是，即使应用了深度界限的规定，所求得的解答路径并不一定就是最短的路径。,22,有深度界限的深度优先搜索算法如下：,(1),把起始节点,S,放到未扩展节点,OPEN,表中。如果此节点为一目标节点，则得到一个解。,(2),如果,OPEN,为一空表，则失败退出。,(3),把第一个节点,(,节点,n),从,OPEN,表移到,CLOSED,表。,(4),如果节点,n,的深度等于最大深度，则转向,(2),。,(5),扩展节点,n,，,产生其全部后裔，并把它们放入,OPEN,表的前头。如果没有后裔，则转向,(2),。,(6),如果后继节点中有任一个为目标节点，则求得一个解，成功退出；否则，转向,(2),。,23,24,通过分析可知,open,表的数据结构是一个堆栈,(stack),这是与广度优先搜索的唯一区别，也就是说扩展生成的结点总是加入到栈顶，扩展时总是选择最新生成的结点。,特点：可能误入歧途找不到解，不是完备的，得到的解不一定是最优解（最短路径）。,25,等代价搜索,有些问题并不要求有应用算符序列为最少的解，而是要求具有某些特性的解。搜索树中每条连接弧线上的有关代价以及随之而求得的具有最小代价的解答路径，与许多这样的广义准则相符合。宽度优先搜索可被推广用来解决这种寻找从起始状态至目标状态的具有最小代价的路径问题，这种推广了的宽度优先搜索算法叫做等代价搜索算法,。,26,等代价搜索算法：,等代价搜索方法以,g(i),的递增顺序扩展其节点，其算法如下：,(1),把起始节点,S,放到未扩展节点表,OPEN,中。如果此起始节点为一目标节点，则求得一个解,;,否则令,g(S),=,0,。,(2),如果,OPEN,是个空表，则没有解而失败退出。,(3),从,OPEN,表中选择一个节点,i,，,使其,g(i),为最小。如果有几个节点都合格，那么就要选择一个目标节点作为节点,i(,要是有目标节点的话,),；否则，就从中选一个作为节点,i,。,把节点,i,从,OPEN,表移至扩展节点表,CLOSED,中。,(4),如果节点,i,为目标节点，则求得一个解。,(5),扩展节点,i,。,如果没有后继节点，则转向第,(2),步。,(6),对于节点,i,的每个后继节点,j,，,计算,g(j),=,g(i)+c(i,j),，,并把所有后继节点,j,放进,OPEN,表。提供回到节点,i,的指针。,(7),转向第,(2),步。,27,28,3.2,启发式搜索,盲目搜索的不足：效率低，耗费过多的计算空间与时间。分析前面介绍的宽度优先、深度优先搜索，或等代价搜索算法,其主要的差别是,OPEN,表中待扩展节点的顺序问题。人们就试图找到一种方法用于排列待扩展节点的顺序，即选择最有希望的节点加以扩展，那么，搜索效率将会大为提高。启发信息：进行搜索技术一般需要某些有关具体问题领域的特性的信息，把此种信息叫做启发信息。把利用启发信息的搜索方法叫做启发性搜索方法。,29,假设初始状态、算符和目标状态的定义都是完全确定的，然后决定一个搜索空间。因此，问题就在于如何有效地搜索这个给定空间。启发信息按其用途可分为下列,3,种：,(1),用于决定要扩展的下一个节点，以免像在宽度优先或深度优先搜索中那样盲目地扩展。,(2),在扩展一个节点的过程中，用于决定要生成哪一个或哪几个后继节点，以免盲目地同时生成所有可能的节点。,(3),用于决定某些应该从搜索树中抛弃或修剪的节点。在本节中，我们只讨论利用上述第一种启发信息的状态空间搜索算法，即决定哪个是下一步要扩展的节点。这种搜索总是选择“最有希望”的节点作为下一个被扩展的节点。这种搜索叫做有序搜索,(ordered search),。,启发式搜索策略,30,用来估算节点希望程度的量度，叫做估价函数,(evaluation function),。,一个节点的,希望,(promise),有几种不同的定义方法。在状态空间问题中，一种方法是估算目标节点到此节点的距离；另一种方法认为，解答路径包括被估价过的节点，并计算全条路径的长度或难度。每个不同的衡量标准只能考虑该问题中这个节点的某些决定性特性，或者对给定节点与目标节点进行比较，以决定相关特性。我们用符号,f,来标记估价函数，用,f(n),表示节点,n,的估价函数值。暂时令,f,为任意函数，以后我们将会提出,f,是从起始节点约束地通过节点,n,而到达目标节点的最小代价路径上的一个估算代价。,估价函数,31,我们用估价函数,f,来排列,GRAPHSEARCH,第,8,步中,OPEN,表上的节点。根据习惯，,OPEN,表上的节点按照它们,f,函数值的递增顺序排列。根据推测，某个具有低的估价值的节点较有可能处在最佳路径上。应用某个算法,(,例如等代价算法,),选择,OPEN,表上具有最小,f,值的节点作为下一个要扩展的节点。这种搜索方法叫做有序搜索或最佳优先搜索，而其算法就叫做有序搜索算法或最佳优先算法。可见它总是选择最有希望的节点作为下一个要扩展的节点。有序搜索,(ordered search),又称为最好优先搜索,(best-first search),。,有序搜索,有序状态空间搜索算法如下：,(1),把起始节点,S,放到,OPEN,表中，计算,f(S),并把其值与节点,S,联系起来。,(2),如果,OPEN,是个空表，则失败退出，无解。,(3),从,OPEN,表中选择一个,f,值最小的节点,i,。,结果有几个节点合格，当其中有一个为目标节点时，则选择此目标节点，否则就选择其中任一个节点作为节点,i,。,(4),把节点,i,从,OPEN,表中移出，并把它放入,CLOSED,的扩展节点表中。,(5),如果,i,是个目标节点，则成功退出，求得一个解。,32,(6),扩展节点,i,，,生成其全部后继节点。对于,i,的每一个后继节点,j,：,(a),计算,f(j),。,(b),如果,j,既不在,OPEN,表中，又不在,CLOSED,表中，则用估价函数,f,把它添入,OPEN,表。从,j,加一指向其父辈节点,i,的指针，以便一旦找到目标节点时记住一个解答路径。,(c),如,果,j,已在,OPEN,表上或,CLOSED,表上，则比较刚刚对,j,计算过的,f,值和前面计算过的该节点在表中的,f,值。如果新的,f,值较小，则,(i),以此新值取代旧值。,(ii),从,j,指向,i,，,而不是指向它的父辈节点。,(iii),如果节点,j,在,CLOSED,表中，则把它移回,OPEN,表,(7),转向,(2),，即,GO TO(2),。,宽度优先搜索、等代价搜索和深度优先搜索统统是有序搜索技术的特例。对于宽度优先搜索，我们选择,f(i),作为节点,i,的深度。对于等代价搜索，,f(i),是从起始节点至节点,i,这段路径的代价。有序搜索的有效性直接取决于,f,的选择，如果选择的,f,不合适，有序搜索就可能失去一个最好的解甚至全部的解。如果没有适用的准确的希望量度，那么,f,的选择将涉及两个方面的内容：一方面是一个时间和空间之间的折衷方案；另一方面是保证有一个最优的解或任意解。,33,34,35,A,*,算法,A,*,算法的估价函数：,让我们描述一个特别的估价函数，这个估价函数,f,使得在任意节点上其函数值,f(n),能估算出从节点,S,到节点,n,的最小代价路径的代价与从节点,n,到某一目标节点的最小代价路径的代价之总和，也就是说,f(n),是约束通过节点,n,的一条最小代价路径的代价的一个估计。因此，,OPEN,表上具有最小,f,值的那个节点就是所估计的加有最少严格约束条件的节点，而且下一步要扩展这个节点是合适的。,36,在正式讨论,A,*,算法之前，我们先介绍几个有用的记号。令,k(n,i,，,n,j,),表示任意两个节点,n,i,和,n,j,之间最小代价路径的实际代价,(,对于两节点间没有通路的节点，函数,k,没有定义,),。于是，从节点,n,到某个具体的目标节点,t,i,，,某一条最小代价路径的代价可由,k(n,t,i,),给出。我们令,h,*,(n),表示整个目标节点集合,t,i,上所有,k(n,t,i,),中最小的一个，因此，,h,*,(n),就是从,n,到目标节点最小代价路径的代价，而且从,n,到目标节点能够获得,h,*,(n),的任一路径就是一条从,n,到某个目标节点的最佳路径,(,对于任何不能到达目标节点的节点,n,，,函数,h,*,没有定义,),。,37,通常我们感兴趣的是想知道从已知起始节点,S,到任意节点,n,的一条最佳路径的代价,k(S,n),。,为此，引进一个新函数,g,*,，,这将使我们的记号得到某些简化。对所有从,S,开始可达到,n,的路径来说，,函数,g,*,定义为,g,*,(n)=k(S,n),。,其次，我们定义函数,f*,，,使得在任一节点,n,上其函数值,f,*,(n),就是从节点,S,到节点,n,的一条最佳路径的实际代价加上从节点,n,到某目标节点的一条最佳路径的代价之和，即,f,*,(n)=g,*,(n)+h,*,(n),因而,f,*,(n),值就是从,S,开始约束通过节点,n,的一条最佳路径的代价，而,f,*,(S)=h,*,(S),是一条从,S,到某个目标节点中间无约束的一条最佳路径的代价。我们希望估价函数,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,叫做启发函数。,38,定义,1:,在,GRAPHSEARCH,过程中，如果第,8,步的重排,OPEN,表是依据,f(x)=g(x)+h(x),进行的，则称该过程为,A,算法。,定义,2:,在,A,算法中，如果对所有的,x,，,h(x)h,*,(x),成立,则称,h(x),为,h,*,(x),的下界，它表示某种偏于保守的估计。,定义,3:,采用,h,*,(x),的下界,h(x),为启发函数的,A,算法，称为,A,*,算法。当,h=0,时，,A,*,算法就变为有序搜索算法。,A,*,算法是一种有序搜索算法，其特点在于对估价函数的定义上。对于一般的有序搜索，总是选择,f,值最小的节点作为扩展节点。因此，,f,是根据需要找到一条最小代价路径的观点来估算节点的，所以，可考虑每个节点,n,的估价函数值为两个分量：从起始节点到节点,n,的代价以及从节点,n,到达目标节点的代价。,A,算法和,A,*,算法的定义,39,40,41,双向搜索,搜索过程的目的是发现一条通过问题空间从初始状态到达目标状态的路径，这种搜索可以向两个方向进行：,（,1,）从初始状态开始的正向搜索；（,2,）从目标状态开始的逆向搜索。,把搜索过程描述为一套规则的应用，就比较容易描述专用的搜索算法而不涉及搜索方向。另外一种可能性是同时从初始状态正向搜索及从目标状态逆向搜索，直到这两条路径在中途某处相交接为止。这种搜索策略叫做双向搜索。,42,3.3,遗传算法,一,、遗传算法概述,二、遗传算法原理,三、遗传算法的应用,43,一、遗传算法概述,1,、,智能优化算法,2,、,基本遗传算法,3,、,遗传算法的特点,44,1,、智能优化算法,智能优化算法又称为现代启发式算法，是一种具有全局优化性能、通用性强、且适合于并行处理的算法。这种算法一般具有严密的理论依据，而不是单纯凭借专家经验，理论上可以在一定的时间内找到最优解或近似最优解。,45,常用的智能优化算法,（,1,）,遗传算法,（,Genetic Algorithm,，,简称,GA,）,（,2,）,模拟退火算法,（,Simulated Annealing,，,简称,SA,）,（,3,）,禁忌搜索算法,（,Tabu,Search,，,简称,TS,）,46,智能优化算法的特点,它们的共同特点：都是从任一解出发，按照某种机制，以一定的概率在整个求解空间中探索最优解。由于它们可以把搜索空间扩展到整个问题空间，因而具有全局优化性能。,47,遗传算法起源,遗传算法是由美国的,J.Holland,教授于,1975,年在他的专著,自然界和人工系统的适应性,中首先提出的，它是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法,。,48,遗传算法的搜索机制,遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子,(,选择、交叉和变异,),对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。,49,2,、基本遗传算法,基本遗传算法（,Simple Genetic Algorithms,，,简称,SGA,，,又称简单遗传算法或标准遗传算法），是由,Goldberg,总结出的一种最基本的遗传算法，其遗传进化操作过程简单，容易理解，是其它一些遗传算法的雏形和基础。,50,基本遗传算法的组成,（,1,）编码（产生初始种群）,（,2,）适应度函数,（,3,）遗传算子（选择、交叉、变异）,（,4,）运行参数,51,(1),编码,GA,是通过某种编码机制把对象抽象为由特定符号按一定顺序排成的串。正如研究生物遗传是从染色体着手，而染色体则是由基因排成的串。,SGA,使用二进制串进行编码。,52,几个术语,基因型：,101000111,表现型：,0.63,编码,解码,个体（染色体）,基因,53,初始种群,SGA,采用随机方法生成若干个个体的集合，该集合称为初始种群。初始种群中个体的数量称为种群规模。,54,(2),适应度函数,遗传算法对一个个体（解）的好坏用适应度函数值来评价，适应度函数值越大，解的质量越好。适应度函数是遗传算法进化过程的驱动力，也是进行自然选择的唯一标准，它的设计应结合求解问题本身的要求而定。,55,选择算子,遗传算法使用选择运算来实现对群体中的个体进行优胜劣汰操作：适应度高的个体被遗传到下一代群体中的概率大；适应度低的个体，被遗传到下一代群体中的概率小。选择操作的任务就是按某种方法从父代群体中选取一些个体，遗传到下一代群体。,SGA,中选择算子采用轮盘赌选择方法。,(3),遗传,算子,56,轮盘赌选择方法,轮盘赌选择又称比例选择算子，它的基本思想是：各个个体被选中的概率与其适应度函数值大小成正比。设群体大小为,n,，,个体,i,的适应度为,F,i,，,则个体,i,被选中遗传到下一代群体的概率为：,57,轮盘赌选择方法的实现步骤,（,1,）,计算群体中所有个体的适应度函数值（需要解码）；,（,2,）,利用比例选择算子的公式，计算每个个体被选中遗传到下一代群体的概率；,（,3,）,采用模拟赌盘操作（即生成,0,到,1,之间的随机数与每个个体遗传到下一代群体的概率进行匹配）来确定各个个体是否遗传到下一代群体中。,58,交叉算子,所谓交叉运算，是指对两个相互配对的染色体依据交叉概率,P,c,按某种方式相互交换其部分基因，从而形成两个新的个体。交叉运算是遗传算法区别于其他进化算法的重要特征，它在遗传算法中起关键作用，是产生新个体的主要方法。,SGA,中交叉算子采用单点交叉算子。,59,单点交叉运算,交叉前：,00000,|,01110000000010000,11100,|,00000111111000101,交叉后：,00000,|00000111111000101,11100,|01110000000010000,交叉点,60,变异算子,所谓变异运算，是指依据变异概率,P,m,将个体编码串中的某些基因值用其它基因值来替换，从而形成一个新的个体。遗传算法中的变异运算是产生新个体的辅助方法，它决定了遗传算法的局部搜索能力，同时保持种群的多样性。交叉运算和变异运算的相互配合，共同完成对搜索空间的全局搜索和局部搜索。,SGA,中变异算子采用基本位变异算子。,61,基本位变异算子,基本位变异算子是指对个体编码串随机指定的某一位或某几位基因作变异运算。对于基本遗传算法中用二进制编码符号串所表示的个体，若需要进行变异操作的某一基因座上的原有基因值为,0,，则变异操作将其变为,1,；反之，若原有基因值为,1,，则变异操作将其变为,0,。,62,基本位变异算子的执行过程,变异前：,00000111000,0,000010000,变异后：,00000111000,1,000010000,变异点,63,(4),运行参数,（,1,）,M,：,种群规模,（,2,）,T,：,遗传运算的终止进化代数,（,3,）,P,c,：,交叉概率,（,4,）,P,m,：,变异概率,64,SGA,的框图,产生初始群体,是否满足停止准则,是,输出结果并结束,计算个体适应度值,比例选择运算,单点交叉运算,基本位变异运算,否,产生新一代群体,执行,M/2,次,65,3,、遗传算法的特点,（,1,）群体搜索，易于并行化处理；,（,2,）不是盲目穷举，而是启发式搜索；,（,3,）适应度函数不受连续、可微等条件的约束，适用范围很广。,66,二、遗传算法原理,1,、,遗传算法的数学基础,2,、,遗传算法的收敛性分析,3,、,遗传算法的改进,67,1,、,遗传算法的数学基础,（,1,）模式定理,（,2,）积木块假设,68,模式,模式是指种群个体基因串中的相似样板，它用来描述基因串中某些特征位相同的结构。在二进制编码中，模式是基于三个字符集,(0,1,*),的字符串，符号*代表任意字符，即,0,或者,1,。,模式示例：,10*1,69,两个定义,定义,1,：模式,H,中确定位置的个数称为模式,H,的阶，记作,O(H),。,例如,O(10*1)=3,。,定义,2,：模式,H,中第一个确定位置和最后一个确定位置之间的距离称为模式,H,的定义距，记作,(H),。,例如,(10*1)=4,。,70,模式的阶和定义距的含义,模式阶用来反映不同模式间确定性的差异，模式阶数越高，模式的确定性就越高，所匹配的样本数就越少。在遗传操作中，即使阶数相同的模式，也会有不同的性质，而模式的定义距就反映了这种性质的差异。,71,模式定理,模式定理：具有低阶、短定义距以及平均适应度高于种群平均适应度的模式在子代中呈指数增长。,模式定理保证了较优的模式（遗传算法的较优解）的数目呈指数增长，为解释遗传算法机理提供了数学基础。,72,模式定理,从模式定理可看出，有高平均适应度、短定义距、低阶的模式，在连续的后代里获得至少以指数增长的串数目，这主要是因为选择使最好的模式有更多的复制，交叉算子不容易破坏高频率出现的、短定义长的模式，而一般突变概率又相当小，因而它对这些重要的模式几乎没有影响。,73,积木块假设,积木块假设：遗传算法通过短定义距、低阶以及高平均适应度的模式（积木块），在遗传操作下相互结合，最终接近全局最优解。,模式定理保证了较优模式的样本数呈指数增长，从而使遗传算法找到全局最优解的可能性存在；而积木块假设则指出了在遗传算子的作用下，能生成全局最优解。,74,2,、,遗传算法的收敛性分析,遗传算法要实现全局收敛，首先要求任意初始种群经有限步都能到达全局最优解，其次算法必须由保优操作来防止最优解的遗失。与算法收敛性有关的因素主要包括种群规模、选择操作、交叉概率和变异概率。,75,种群规模对收敛性的影响,通常，种群太小则不能提供足够的采样点，以致算法性能很差；种群太大，尽管可以增加优化信息，阻止早熟收敛的发生，但无疑会增加计算量，造成收敛时间太长，表现为收敛速度缓慢。,76,选择操作对收敛性的影响,选择操作使高适应度个体能够以更大的概率生存，从而提高了遗传算法的全局收敛性。如果在算法中采用最优保存策略，即将父代群体中最佳个体保留下来，不参加交叉和变异操作，使之直接进入下一代，最终可使遗传算法以概率,1,收敛于全局最优解。,77,交叉概率对收敛性的影响,交叉操作用于个体对，产生新的个体，实质上是在解空间中进行有效搜索。交叉概率太大时，种群中个体更新很快，会造成高适应度值的个体很快被破坏掉；概率太小时，交叉操作很少进行，从而会使搜索停滞不前，造成算法的不收敛。,78,变异概率对收敛性的影响,变异操作是对种群模式的扰动，有利于增加种群的多样性。但是，变异概率太小则很难产生新模式，变异概率太大则会使遗传算法成为随机搜索算法。,79,遗传算法的本质,遗传算法本质上是对染色体模式所进行的一系列运算，即通过选择算子将当前种群中的优良模式遗传到下一代种群中，利用交叉算子进行模式重组，利用变异算子进行模式突变。通过这些遗传操作，模式逐步向较好的方向进化，最终得到问题的最优解。,80,3,、,遗传算法的改进,遗传欺骗问题：在遗传算法进化过程中，有时会产生一些超常的个体，这些个体因竞争力太突出而控制了选择运算过程，从而影响算法的全局优化性能，导致算法获得某个局部最优解。,81,遗传算法的改进途径,（,1,）对编码方式的改进,（,2,）对遗传算子 的改进,（,3,）对控制参数的改进,（,4,）对执行策略的改进,82,对编码方式的改进,二进制编码优点在于编码、解码操作简单，交叉、变异等操作便于实现，缺点在于精度要求较高时，个体编码串较长，使算法的搜索空间急剧扩大，遗传算法的性能降低。格雷编码克服了二进制编码的不连续问题，浮点数编码改善了遗传算法的计算复杂性。,83,对遗传算子 的改进,排序选择,均匀交叉,逆序变异,（,1,）对群体中的所有个体按其适应度大小进行降序排序；,（,2,）根据具体求解问题，设计一个概率分配表，将各个概率值按上述排列次序分配给各个个体；,（,3,）以各个个体所分配到的概率值作为其遗传到下一代的概率，基于这些概率用赌盘选择法来产生下一代群体。,84,对遗传算子 的改进,排序选择,均匀交叉,逆序变异,（,1,）随机产生一个与个体编码长度相同的二进制屏蔽字,P=W,1,W,2,W,n,；,（,2,）,按下列规则从,A,、,B,两个父代个体中产生两个新个体,X,、,Y,：若,W,i,=0,，则,X,的第,i,个基因继承,A,的对应基因，,Y,的第,i,个基因继承,B,的对应基因；若,W,i,=1,，则,A,、,B,的第,i,个基因相互交换，从而生成,X,、,Y,的第,i,个基因。,85,对遗传算子 的改进,排序选择,均匀交叉,逆序变异,变异前：,3 4 8|7 9 6 5|2 1,变异前：,3 4 8|5 6 9 7|2 1,86,对控制参数的改进,Schaffer,建议的最优参数范围是：,M=20-100,，,T=100-500,，,P,c,=0.4-0.9,，,P,m,=0.001-0.01,。,87,对控制参数的改进,Srinvivas,等人提出自适应遗传算法，即,P,C,和,P,m,能够随适应度自动改变，当种群的各个个体适应度趋于一致或趋于局部最优时，使二者增加，而当种群适应度比较分散时，使二者减小，同时对适应值高于群体平均适应值的个体，采用较低的,P,C,和,P,m,，,使性能优良的个体进入下一代，而低于平均适应值的个体，采用较高的,P,C,和,P,m,，,使性能较差的个体被淘汰。,88,对执行策略的改进,混合遗传算法,免疫遗传算法,小生境遗传算法,单亲遗传算法,并行遗传算法,89,三、遗传算法的应用,1,、,遗传算法的应用领域,2,、,遗传算法的应用示例,90,1,、,遗传算法的应用领域,（,1,）组合优化 （,2,）函数优化,（,3,）自动控制 （,4,）生产调度,（,5,）图像处理 （,6,）机器学习,（,7,）人工生命 （,8,）数据挖掘,91,遗传算法应用于组合优化,随着问题规模的增大，组合优化问题的搜索空间也急剧扩大，有时在计算机上用枚举法很难甚至不可能求出其最优解。实践证明，遗传算法已经在求解旅行商问题、背包问题、装箱问题、布局优化、网络路由等具有,NP,难度的组合优化问题上取得了成功的应用。,92,2,、,遗传算法的应用示例,弹药装载问题,（,Ammunition Loading Problem,，,简称,ALP,），,就是在满足各类通用弹药运输规程和安全性的前提下，如何将一批通用弹药箱装入军用运输工具，使得通用弹药的装载效率达到最大值的问题。,应用,1,93,AGSAA,的基本原理,在弹药装载中，考虑到模拟退火算法的基本,思想是跳出局部最优解，将模拟退火思想引,入遗传算法，应用改进型遗传算法和模拟退,火算法相结合，构建自适应遗传模拟退火算,法（,AGSAA,），,从而综合了全局优化和局部搜,索的特点，为解决弹药装载这一组合优化问,题提供了新的思路。,94,AGSAA,的编码方式,AGSAA,采用二进制编码方式，每一个二进制位对应一个待装弹药箱，若为，表示该弹药箱装入运输工具，为则不装。,95,AGSAA,的解码和适应度函数,AGSAA,采用弹药装载的启发式算法来解码，解码后最终确定装入运输工具的弹药箱。适应度函数主要考虑两个方面，即载重率和积载率，对这两个因素加权，来计算适应度函数值。,96,弹药装载的启发式算法,（,1,）定位规则,（,Locating rule,）,定位规则是指用来确定当前待装弹药箱在运输工具剩余装载空间中摆放位置的规则。,（,2,）定序规则（,Ordering rule,）,定序规则是指用来确定弹药箱放入运输工具装载空间先后顺序的规则。,97,遗传算子的选择,AGSAA,的选择算子采用轮盘赌选择算子，并结合最优保存策略；变异算子采用基本位变异算子；同时，在变异运算之后，增加退火算子，以增强算法的局部搜索能力；交叉概率和变异概率为自适应概率，以提高种群的进化效率。,98,交叉算子的选择,由于,AGSAA,是采用将弹药箱的编号排列成串来进行编码的，如果个体交叉采用传统方式进行，就有可能使个体的编码产生重复基因（即一个弹药箱编号在一个个体中出现两次以上），从而产生不符合条件的个体，因此，,AGSAA,采用的是部分映射交叉算子。,99,例,1.,设,f,(,x,)=,-,x,2,+2,x,+0.5,，,求,max,f,(,x,),x,-1,2,。,应用,2,我们将通过这个简单的求最值问题来详细给出遗传算法的整个过程。,（,1,）编码和产生初始群体,首先需要确定编码的策略，也就是说如何把,-1,2,区间内的数用计算机语言表示出来。编码就是从表现型到基因型的映射，编码时要注意以下三个原则：,完备性：问题空间中所有点（潜在解）都能成为,GA,编码空间中的点（染色体位串）的表现型；,健全性：,GA,编码空间中的染色体位串必须对应问题空间中的某一潜在解；,非冗余性：染色体和潜在解必须一一对应,100,编码,我们采用二进制形式来解决编码问题，即将某个变量值代表的个体表示为一个,0,1,二进制串。串的长度取决于求解的精度，例如假设求解精度为保留六位小数，由于区间,-1,2,的长度为,3,，则必须将该区间分为,3,10,6,等分。因为,2,21,3,10,6,2,22,，所以编码所用的二进制串至少需要,22,位。,二进制串（,b,21,b,20,b,19,b,1,b,0,）,与,a,b,内实数的一一映射：,二进制串,十进制数,a,b,内实数,b,21,b,20,b,19,b,1,b,0,101,编码,转化到,-1,2,内的实数为：,例.,二进制串,a=,其对应的十进制数为：,102,产生初始群体,随机的产生一个初始群体。,pop1=,，,%a1,，,%a2,，,%a3,%a4,这里假设初始群体的个体数为,4,。,转化成,-1,2,之间的十进制数即为：,下面就需要解决每个染色体个体的适应值,pop1=1.523032,0.574022,-0.697235,0.247238,103,（,2,）定义适应函数和适应值,由于目标函数,f,(,x,),在,-1,2,内的值有正有负，所以必须通过建立适应函数与目标函数的映射关系，保证映射后的适应值非负，而且目标函数的优化方向应对应于适应值增大的方向，也为以后计算各个体的入选概率打下基础。,定义适应函数：,为了便于计算，这里的,F,min,采用了一个特定的输入值,例：,如果取,F,min,=-1,，,则,f,(,x,)=1,对应的适应值为,g,(,x,)=2,104,适应函数和适应值,上述随机产生的初始群体，取,F,min,=-1,，,则,它们的目标函数值和适应