遗传算法详解.ppt
《遗传算法详解.ppt》由会员分享,可在线阅读,更多相关《遗传算法详解.ppt(50页珍藏版)》请在咨信网上搜索。
1、5.遗传算法遗传算法 遗传算法(遗传算法(genetic algorithms,genetic algorithms,简称简称GAGA)是是人工智能的重要分支,是基于达尔文进化论,人工智能的重要分支,是基于达尔文进化论,在微型计算机上模拟生命进化机制而发展起来在微型计算机上模拟生命进化机制而发展起来的一门新学科。它根据适者生存、优胜劣汰等的一门新学科。它根据适者生存、优胜劣汰等自然进化规则来进行搜索计算和问题求解。对自然进化规则来进行搜索计算和问题求解。对许多用传统数学难以解决或明显失效的非常复许多用传统数学难以解决或明显失效的非常复杂问题,特别是最优化问题,杂问题,特别是最优化问题,GAGA
2、提供了一个提供了一个行之有效的新途径。近年来,由于遗传算法求行之有效的新途径。近年来,由于遗传算法求解复杂优化问题的巨大潜力及其在工业控制工解复杂优化问题的巨大潜力及其在工业控制工程领域的成功应用,这种算法受到了广泛的关程领域的成功应用,这种算法受到了广泛的关注。注。5.1.1 基本遗传学基础 遗遗传传算算法法是是根根据据生生物物进进化化的的模模型型提提出出的的一一种种优优化化算算法法。自自然然选选择择学学说说是是进进化化论论的的中中心心内内容容,根根据据进进化化论论,生生物物的的发发展展进进化化主主要要由由三三个个原因,即遗传、变异和选择。原因,即遗传、变异和选择。遗遗传传是是指指子子代代总
3、总是是和和亲亲代代相相似似。遗遗传传性性是是一一切切生生物物所所共共有有的的特特性性,它它使使得得生生物物能能够够把把其其特性、性状传给后代。遗传是生物进化的基础。特性、性状传给后代。遗传是生物进化的基础。变异是指子代和亲代有某些不相似的现象,变异是指子代和亲代有某些不相似的现象,即子代永远不会和亲代完全一样。它是一切生即子代永远不会和亲代完全一样。它是一切生物所具有的共有特性,是生物个体之间相互区物所具有的共有特性,是生物个体之间相互区别的基础。引起变异的原因主要是生活环境的别的基础。引起变异的原因主要是生活环境的影响及杂交等。生物的变异性为生物的进化和影响及杂交等。生物的变异性为生物的进化
4、和发展创造了条件。发展创造了条件。选选择择决决定定生生物物进进化化的的方方向向。在在进进化化过过程程中中,有有的的要要保保留留,有有的的要要被被淘淘汰汰。自自然然选选择择是是指指生生物物在在自自然然界界的的生生存存环环境境中中适适者者生生存存,不不适适者者被被淘淘汰汰的的过过程程。通通过过不不断断的的自自然然选选择择,有有利利于于生生存存的的变变异异就就会会遗遗传传下下去去,积积累累起起来来,使使变变异异越来越大,逐步产生了新的物种。越来越大,逐步产生了新的物种。生物就是在遗传、变异和选择三种因素的综合作用过生物就是在遗传、变异和选择三种因素的综合作用过程中,不断地向前发展和进化。选择是通过遗
5、传和变异起程中,不断地向前发展和进化。选择是通过遗传和变异起作用的,变异为选择提供资料,遗传巩固与积累选择的资作用的,变异为选择提供资料,遗传巩固与积累选择的资料,而选择则能控制变异与遗传的方向,使变异和遗传向料,而选择则能控制变异与遗传的方向,使变异和遗传向着适应环境的方向发展。遗传算法正是吸取了自然生物系着适应环境的方向发展。遗传算法正是吸取了自然生物系统统“适者生存、优胜劣汰适者生存、优胜劣汰”的进化原理,从而使它能够提的进化原理,从而使它能够提供一个在复杂空间中随机搜索的方法,为解决许多传统的供一个在复杂空间中随机搜索的方法,为解决许多传统的优化方法难以解决的优化问题提供了新的途径。优
6、化方法难以解决的优化问题提供了新的途径。5.1.2 遗传算法的原理和特点 遗传算法将生物进化原理引入待优化参数形成的编码遗传算法将生物进化原理引入待优化参数形成的编码串群体中,按着一定的适值函数及一系列遗传操作对各个串群体中,按着一定的适值函数及一系列遗传操作对各个体进行筛选,从而使适值高的个体被保留下来,组成新的体进行筛选,从而使适值高的个体被保留下来,组成新的群体,新群体包含上一代的大量信息,并且引入了新的优群体,新群体包含上一代的大量信息,并且引入了新的优于上一代的个体。这样周而复始,群体中各个体适值不断于上一代的个体。这样周而复始,群体中各个体适值不断提高,直至满足一定的极限条件。此时
7、,群体中适值最高提高,直至满足一定的极限条件。此时,群体中适值最高的个体即为待优化参数的最优解。正是由于遗传算法独具的个体即为待优化参数的最优解。正是由于遗传算法独具特色的工作原理,使它能够在复杂空间进行全局优化搜索,特色的工作原理,使它能够在复杂空间进行全局优化搜索,并且具有较强的鲁棒性;另外,遗传算法对于搜索空间,并且具有较强的鲁棒性;另外,遗传算法对于搜索空间,基本上不需要什么限制性的假设(如连续、可微及单峰等)基本上不需要什么限制性的假设(如连续、可微及单峰等)。遗传算法的特点遗传算法的特点同常规优化算法相比,遗传算法有以下特点:遗传算法是对参数的编码进行操作,而非对参数本身。遗传算法
8、是从许多点开始并行操作,并非局限于一点,从而可有效防止搜索过程收敛于局部最优解。遗传算法通过目标函数计算适值,并不需要其它推导和附加信息,因而对问题的依赖性较小。遗传算法的寻优规则是由概率决定的,而非确定性的。遗传算法在解空间进行高效启发式搜索,而非盲目地穷举或完全随机搜索。遗传算法对所求解的优化问题没有太多的数学要求。遗传算法具有并行计算的特点,因而可通过大规模并行计算来提高计算速度。5.1.3 遗传算法的基本操作一般的遗传算法都包含三个基本操作:复制一般的遗传算法都包含三个基本操作:复制(reproduction)reproduction)、交叉交叉(crossover)crossover
9、)和变异和变异(mutation)mutation)。1.1.复制复制 复制(又称繁殖),是从一个旧种群(复制(又称繁殖),是从一个旧种群(old old populationpopulation)中选择生命力强的字符串(中选择生命力强的字符串(individual stringindividual string)产产生新种群的过程。或者说,复制是个体位串根据其目标函生新种群的过程。或者说,复制是个体位串根据其目标函数数f f(即适值函数)拷贝自己的过程。直观地讲,可以把目即适值函数)拷贝自己的过程。直观地讲,可以把目标函数标函数f f看作是期望的最大效益的某种量度。根据位串的适看作是期望的最
10、大效益的某种量度。根据位串的适值所进行的拷贝,意味着具有较高适值的位串更有可能在值所进行的拷贝,意味着具有较高适值的位串更有可能在下一代中产生一个或多个子孙。显然,在复制操作过程中,下一代中产生一个或多个子孙。显然,在复制操作过程中,目标函数目标函数(适值适值)是该位串被复制或被淘汰的决定因素。是该位串被复制或被淘汰的决定因素。复制操作的初始种群复制操作的初始种群(旧种群旧种群)的生成往往是随机产生的生成往往是随机产生的。例如,通过掷硬币的。例如,通过掷硬币2020次产生维数次产生维数n n4 4的初始种群如下的初始种群如下(正面正面=1=1,背面,背面=0)=0):0110101101110
11、0011000010000100010011 10011 显然,该初始种群可以看成是一个长度为五位的无符显然,该初始种群可以看成是一个长度为五位的无符号二进制数,将其编成四个位串,并解码为十进制的数:号二进制数,将其编成四个位串,并解码为十进制的数:位串位串1 1:01101 1301101 13 位串位串2 2:11000 2411000 24 位串位串3 3:01000 801000 8 位串位串4 4:10011 1910011 19 通过一个5位无符号二进制数,可以得到一个从0到31的数值x,它可以是系统的某个参数。计算目标函数或适值f(x)=x2,其结果如表6-1所示。计算种群中所有
12、个体位串的适值之和,同时,计算种群全体的适值比例,其结果示于表中。转轮法转轮法转轮法把种群中所有个体位串适值的总和看作一个轮子的圆转轮法把种群中所有个体位串适值的总和看作一个轮子的圆周,而每个个体位串按其适值在总和中所占的比例占据轮子周,而每个个体位串按其适值在总和中所占的比例占据轮子的一个扇区。按表的一个扇区。按表5 5-1-1可绘制如图的转轮。可绘制如图的转轮。复制时,只要简单地转动这个按权重复制时,只要简单地转动这个按权重划分的转轮划分的转轮4 4次,从而产生次,从而产生4 4个下一代个下一代的种群。例如对于表的种群。例如对于表5 5-1-1中的位串中的位串1 1,其适值为其适值为169
13、169,为总适值的,为总适值的14.4%14.4%。因此,每旋转一次转轮指向该位串因此,每旋转一次转轮指向该位串的概率为的概率为0.1440.144。每当需要下一个后。每当需要下一个后代时,就旋转一下这个按权重划分代时,就旋转一下这个按权重划分的转轮,产生一个复制的候选者。的转轮,产生一个复制的候选者。这样位串的适值越高,在其下代中这样位串的适值越高,在其下代中产生的后代就越多。产生的后代就越多。图图5 5-1-1 当一个位串被选中时,此位串将被完整地复制,然后将复制位串送入匹配集(缓冲区)中。旋转4次转轮即产生4个位串。这4个位串是上代种群的复制,有的位串可能被复制一次或多次,有的可能被淘汰
14、。在本例中,位串3被淘汰,位串4被复制一次。如表6-2所示,适值最好的有较多的拷贝,即给予适合于生存环境的优良个体更多繁殖后代的机会,从而使优良特性得以遗传,反之,最差的则被淘汰。2.2.交叉交叉 简单的交叉分两步实现。第一步是将新复制产生的位简单的交叉分两步实现。第一步是将新复制产生的位串个体随机两两配对;第二步是随机选择交叉点,对匹配串个体随机两两配对;第二步是随机选择交叉点,对匹配的位串进行交叉繁殖,产生一对新的位串。具体过程如下:的位串进行交叉繁殖,产生一对新的位串。具体过程如下:设位串的字符长度为设位串的字符长度为l l,在在1 1,l l1 1的范围内,随机地选取的范围内,随机地选
15、取一个整数值一个整数值k k作为交叉点。将两个配对串从第作为交叉点。将两个配对串从第k k位右边部分位右边部分的所有字符进行交换,从而生成两个新的位串。例如,在的所有字符进行交换,从而生成两个新的位串。例如,在表表6-26-2中,已知位串的字符长度中,已知位串的字符长度l l=5=5,随机选取随机选取k k=4=4,对两个对两个初始的位串个体初始的位串个体AA1 1和和AA2 2进行配对,交叉操作的位置用分隔进行配对,交叉操作的位置用分隔符符“|”表示为:表示为:AA1 1=0110|1=0110|1AA2 2=1100|0=1100|0交叉操作后产生了两个新的字符串为:交叉操作后产生了两个新
16、的字符串为:AA1 1=01100=01100 AA2 2=11001=11001 一般的交叉操作过程:一般的交叉操作过程:遗传算法的有效性主要来自于复制和交叉操作。复制虽然能够从旧种遗传算法的有效性主要来自于复制和交叉操作。复制虽然能够从旧种群中选择出优秀者,但不能创造新的个体;交叉模拟生物进化过程中群中选择出优秀者,但不能创造新的个体;交叉模拟生物进化过程中的繁殖现象,通过两个个体的交换组合,来创造新的优良个体。的繁殖现象,通过两个个体的交换组合,来创造新的优良个体。表表6-36-3列出了交叉操作之后的结果数据,从中可以看出交叉操作列出了交叉操作之后的结果数据,从中可以看出交叉操作的具体过
17、程。首先,随机配对匹配集中的个体,将位串的具体过程。首先,随机配对匹配集中的个体,将位串1 1、2 2配对,位配对,位串串3 3、4 4配对;然后,随机选取交叉点,设位串配对;然后,随机选取交叉点,设位串1 1、2 2的交叉点为的交叉点为k k=4=4,二者只交换最后一位,从而生成两个新的位串,即二者只交换最后一位,从而生成两个新的位串,即 图图5 5-2-2 交叉操作交叉操作 位串位串3 3、4 4的交叉点为的交叉点为k=2k=2,二者交换后三位,生成两个新二者交换后三位,生成两个新的位串,即的位串,即 单点交叉与多点交叉单点交叉与多点交叉 上述例子中交叉的位置是一个,称单点交叉。即指个上述
18、例子中交叉的位置是一个,称单点交叉。即指个体切断点有一处,由于进行个体间的组合替换生成两个新体切断点有一处,由于进行个体间的组合替换生成两个新个体,位串个体长度为个体,位串个体长度为l l时,单点交叉可能有时,单点交叉可能有l l1 1个不同的个不同的交叉。交叉。多点交叉是允许个体的切断点有多个,每个切断点在多点交叉是允许个体的切断点有多个,每个切断点在两个个体间进行个体的交叉,生成两个新个体。两个个体间进行个体的交叉,生成两个新个体。3.变异 尽管复制和交叉操作很重要,在遗传算法中是第一位的,但不能保证尽管复制和交叉操作很重要,在遗传算法中是第一位的,但不能保证不会遗漏一些重要的遗传信息。在
19、人工遗传系统中,变异用来防止这不会遗漏一些重要的遗传信息。在人工遗传系统中,变异用来防止这种遗漏。在简单遗传算法中,变异就是在某个字符串当中把某一位的种遗漏。在简单遗传算法中,变异就是在某个字符串当中把某一位的值偶然的(概率很小的)随机的改变,即在某些特定位置上简单地把值偶然的(概率很小的)随机的改变,即在某些特定位置上简单地把1 1变为变为0 0,或反之。当它有节制地和交叉一起使用时,它就是一种防止过,或反之。当它有节制地和交叉一起使用时,它就是一种防止过度成熟而丢失重要度成熟而丢失重要概念的保险策略。例如,随概念的保险策略。例如,随机产生一个种群,如表所示。在机产生一个种群,如表所示。在该
20、表所列种群中,无论怎样交叉,该表所列种群中,无论怎样交叉,在第在第4 4位上都不可能得到有位上都不可能得到有1 1的位串。的位串。若优化的结果要求该位是若优化的结果要求该位是1 1,显然仅靠交叉是不够的,还需要有变显然仅靠交叉是不够的,还需要有变异,即特定位置上的异,即特定位置上的0 0和和1 1之间的转变。之间的转变。变异在遗传算法中的作用是第二位的,但却是必不可变异在遗传算法中的作用是第二位的,但却是必不可少的。变异运算用来模拟生物在自然界的遗传环境中由于少的。变异运算用来模拟生物在自然界的遗传环境中由于各种偶然因素引起的基因突变,它以很小的概率随机改变各种偶然因素引起的基因突变,它以很小
21、的概率随机改变遗传基因(即位串个体中某一位)的值。通过变异操作,遗传基因(即位串个体中某一位)的值。通过变异操作,可确保种群中遗传基因类型的多样性,以使搜索能在尽可可确保种群中遗传基因类型的多样性,以使搜索能在尽可能大的空间中进行,避免丢失在搜索中有用的遗传信息而能大的空间中进行,避免丢失在搜索中有用的遗传信息而陷入局部解。根据统计,变异的概率为陷入局部解。根据统计,变异的概率为0.0010.001,即变异的频,即变异的频率为每千位传送中只变异一位。在表率为每千位传送中只变异一位。在表6-36-3的种群中共有的种群中共有2020个个字符(每位串的长度为字符(每位串的长度为5 5个字符)。期望变
22、异的字符串位个字符)。期望变异的字符串位数为数为20200.001=0.020.001=0.02(位),所以在此例中无位值的改变。(位),所以在此例中无位值的改变。从表从表6-26-2和表和表6-36-3可以看出,虽然仅进行一代遗传操作,但可以看出,虽然仅进行一代遗传操作,但种群适值的平均值和最大值却比初始种群有了很大的提高,种群适值的平均值和最大值却比初始种群有了很大的提高,平均适值由平均适值由293293变到变到439439,最大值由,最大值由576576变到变到729729。这说明随。这说明随着遗传运算的进行,种群正向着优化的方向发展。着遗传运算的进行,种群正向着优化的方向发展。遗传算法
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 遗传 算法 详解
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【可****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【可****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。