分享
分销 收藏 举报 申诉 / 122

类型人工智能-chapter.ppt

  • 上传人:w****g
  • 文档编号:14633274
  • 上传时间:2026-10-23
  • 格式:PPT
  • 页数:122
  • 大小:1.84MB
  • 下载积分:10 金币
  • 配套讲稿:

    如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。

    特殊限制:

    部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。

    关 键  词:
    人工智能 chapter
    资源描述:
    单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第三章 搜索原理,上一章中我们研究了知识表示方法,为人工智能问题的求解打下了基础。从问题表示到问题的解决,有一个求解的过程。接下来要研究的是求解的过程,采用的基本方法包括搜索和推理。本章先介绍搜索技术,将要讨论问题求解的搜索原理,包括一些早期的搜索技术或用于解决比较简单问题的搜索原理和一些比较新的能够求解比较复杂问题的搜索原理,包括 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,图的说明:一个图由节点的集合组成,节点之间由弧线连接。如果弧是有方向的话,则这种图称为有向图,否则称为无向图。在图搜索策略中,节点代表状态描述,弧代表操作。,图搜索(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,则,它们的目标函数值和适应值分别为:,f(pop1)=1.226437,1.318543,-1.380607,0.933350,g(pop1)=2.226437,2.318543,0,1.933350,105,(3)确定选择标准,用适应值比例来作为入选概率。,设给定的规模为,n,的群体,pop=,a,1,a,2,.,a,n,,,个体,a,i,的适应值为,g,(,a,i,),,,则其入选概率为,上述随机产生的初始群体,它们的入选概率分别为:,p(pop1)=g(pop1)/sum(g(pop1),=0.343675,0.357892,0,0.298433,106,产生种群,(4)产生种群,将入选概率大的个体选入种群,淘汰概率小的个体,并用概率最大的个体补入种群,得到与原群体大小同样的种群。,newpop1=,,,%a1,,,%a2,,,%a2,%a4,在上述随机产生的初始群体中,淘汰掉,a,3,,,再加入,a,2,,,得到新的种群:,107,交叉,(5)交叉,交叉也就是将一组染色体上对应基因段的交换得到新的染色体,然后得到新的染色体组,组成新的群体,。,将前面得到的,newpop1,的四个个体两两配对,重复的不配对,进行交叉(可以在任一位进行交叉):,新的群体,jchpop1,108,变异,(6)变异,变异就是通过一个小概率改变染色体位串上的某个基因,。,现把,jchpop1,中第,3,个个体中的第,9,位改变,就产生了变异,得到了新的群体,pop2,:,pop2=,然后重复上述的选择、交叉、变异,直到满足终止条件为止,109,终止条件,(7)终止条件,遗传算法的终止条件有两类常见条件:,采用设定最大(遗传)代数的方法,一般可设定为,50代,此时就可能得出最优解此种方法简单易行,但可能不是很精确,根据个体的差异来判断,通过计算种群中基因多样性测度,即所有基因位相似程度来进行控制,110,遗传算法作为一种对生物进化现象进行仿真的程序,取得了人工遗传的模拟效果,具有自适应性。在遗传算法的结构中遗传操作和选择机制是两个重要的因素,其联系可用遗传算法=遗传操作+选择过程这个逻辑关系来表示。如果一个应用问题不能求得目标函数的全局最优值,而只能或只希望求一定意义下的满意解,这时,可供选择的方法之一自然是遗传算法,因为遗传算法比其他算法有更多的优势。可喜的是,近年来遗传算法在商业应用方面取得了一系列重要成果。遗传算法的商业应用五花八门,覆盖面甚广,比如通用电器公司的计算机辅
    展开阅读全文

    开通VIP折扣优惠下载文档

    提示  咨信网声明:本文档由用户上传并分享,仅供学习交流、研究之用,未经授权,严禁复制、发行、汇编、翻译或网络传播等,侵权必究。

    咨信网小贴示:
    1、浏览或下载可查看了解,请点击【咨信网告知】。
    2、下载文件中如有侵权或不适当内容,将立即纠正。
    3、如果因为网速或其他原因下载失败请重新下载,重复下载[60天内]不扣币。
    4、开具发票登录电脑端申请,请点击【索取发票】。

    咨信网客服组:【微信客服】

    自信AI创作助手
    关于本文
    本文标题:人工智能-chapter.ppt
    链接地址:https://www.zixin.com.cn/doc/14633274.html

    Copyright ©2010-2026   All Rights Reserved  宁波自信网络信息技术有限公司 版权所有   |  客服电话:0574-28810668    微信客服:咨信网客服    投诉电话:18658249818   

    违法和不良信息举报邮箱:help@zixin.com.cn    文档合作和网站合作邮箱:fuwu@zixin.com.cn    意见反馈和侵权处理邮箱:1219186828@qq.com   | 证照中心

    12321jubao.png12321网络举报中心 电话:010-12321  jubao.png中国互联网举报中心 电话:12377   gongan.png浙公网安备33021202000488号  icp.png浙ICP备2021020529号-1 浙B2-20240490   


    关注我们 :微信公众号  抖音  微博  LOFTER               

    自信网络  |  ZixinNetwork