遗传算法又叫ga算法.ppt

《遗传算法又叫ga算法.ppt》由会员分享，可在线阅读，更多相关《遗传算法又叫ga算法.ppt（37页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、关于遗传算法又叫GA算法现在学习的是第1页，共37页 自然界充满了奇迹与生机，而生命的繁衍更是自然界充满了奇迹与生机，而生命的繁衍更是奇妙无穷。人类之所以能够向其自身的演化学习奇妙无穷。人类之所以能够向其自身的演化学习以增强决策问题的能力，是因为自然演化过程本以增强决策问题的能力，是因为自然演化过程本质就是一个学习与优化的过程。这一优化过程的质就是一个学习与优化的过程。这一优化过程的目的是使生命体达到适应环境的最佳结构与效果目的是使生命体达到适应环境的最佳结构与效果。1.1 遗传算法的起源及生物学基础遗传算法的起源及生物学基础现在学习的是第2页，共37页 曾经主宰地球的恐龙由于庞大的身躯跟不曾

2、经主宰地球的恐龙由于庞大的身躯跟不上环境的变迁而灭绝；长颈鹿为了觅食而长上环境的变迁而灭绝；长颈鹿为了觅食而长长了脖子；老鼠的机敏是为了生存而挣扎的长了脖子；老鼠的机敏是为了生存而挣扎的结果；青蛙的存活则得益于其两栖式左右逢结果；青蛙的存活则得益于其两栖式左右逢源的能力；人类解放出有力的双手，得益于源的能力；人类解放出有力的双手，得益于类人猿求生的努力，而正是这一对与其它动类人猿求生的努力，而正是这一对与其它动物的不同的、不再用于进行行走的双手，使物的不同的、不再用于进行行走的双手，使人类成了这个世界的主宰。自然演化遵循着人类成了这个世界的主宰。自然演化遵循着一种奇妙的规律，这就是达尔文发现的

3、自然一种奇妙的规律，这就是达尔文发现的自然演化规律：物竟天择，适者生存。演化规律：物竟天择，适者生存。现在学习的是第3页，共37页 自然界特别是生物界神奇的进化过程是一个不自然界特别是生物界神奇的进化过程是一个不断优化的过程。近代基因遗传工程的研究成果正断优化的过程。近代基因遗传工程的研究成果正在不断揭示着这一过程的本质机理。人们为什么在不断揭示着这一过程的本质机理。人们为什么不能师法大自然，把生物学进化的一些基本概念不能师法大自然，把生物学进化的一些基本概念和机理引伸到工程问题的研究中来呢？和机理引伸到工程问题的研究中来呢？1975年，年，Holland 提出了建立基因遗传优化的计算机仿真提

4、出了建立基因遗传优化的计算机仿真遗传算法的基本概念和技巧，其本意是在遗传算法的基本概念和技巧，其本意是在人工适应系统中设计的一种基于自然演化原理人工适应系统中设计的一种基于自然演化原理搜索机制。搜索机制。现在学习的是第4页，共37页 遗传算法是基于自然选择和遗传机制，在计算机遗传算法是基于自然选择和遗传机制，在计算机上模拟自然界生物进化过程与机制的寻优搜索仿生上模拟自然界生物进化过程与机制的寻优搜索仿生智能算法，它模拟的机制是一切生命与智能的产生智能算法，它模拟的机制是一切生命与智能的产生与进化过程。它模拟达尔文的自然演化规律的原理与进化过程。它模拟达尔文的自然演化规律的原理激励好的结构，模拟

5、孟德尔的遗传变异理论在迭代激励好的结构，模拟孟德尔的遗传变异理论在迭代过程中保持已有的结构，同时寻找更好的结构。它过程中保持已有的结构，同时寻找更好的结构。它是一类自组织、自适应人工智能技术。是一类自组织、自适应人工智能技术。现在学习的是第5页，共37页 自然界的生物从其父代继承特征或性状，这种自然界的生物从其父代继承特征或性状，这种生命现象称之为遗传（生命现象称之为遗传（HeredityHeredity），研究这种生命），研究这种生命现象与机理的科学即为遗传学（现象与机理的科学即为遗传学（GeneticsGenetics）。由于）。由于有遗传作用，自然界才有稳定的物种，人们种瓜得有遗传作用，

6、自然界才有稳定的物种，人们种瓜得瓜，种豆得豆，之所以鱼至今还仍然会在水中遨游瓜，种豆得豆，之所以鱼至今还仍然会在水中遨游，鸟仍然在天空中飞翔都是这个缘由。自然界之所，鸟仍然在天空中飞翔都是这个缘由。自然界之所以稳定有序，持久永恒，而非天翻地覆，恐怕也得以稳定有序，持久永恒，而非天翻地覆，恐怕也得益于这一点。益于这一点。现在学习的是第6页，共37页 构成生物的基本结构与功能单位是细胞构成生物的基本结构与功能单位是细胞(Cell).(Cell).细胞中的一种微小的丝状化合物称为染细胞中的一种微小的丝状化合物称为染色体（色体（ChromosomeChromosome），生物的所有遗传信息都包），生物

7、的所有遗传信息都包含在这个复杂而又微小的染色体中。遗传信息是由含在这个复杂而又微小的染色体中。遗传信息是由基因（基因（GeneGene）组成的，生物的各种性状由其相）组成的，生物的各种性状由其相应的基因所决定，基因是遗传的基本单位。细应的基因所决定，基因是遗传的基本单位。细胞通过分裂具有自我复制的能力，在细胞分裂胞通过分裂具有自我复制的能力，在细胞分裂过程中，其遗传基因也同时被复制到下一代，过程中，其遗传基因也同时被复制到下一代，从而其性状也被下一代所继承。从而其性状也被下一代所继承。现在学习的是第7页，共37页 遗传学认为，遗传是作为一种指令遗传码封装在每个细遗传学认为，遗传是作为一种指令遗

8、传码封装在每个细胞中，并以基因的形式包含在染色体中，每个基因有其特殊胞中，并以基因的形式包含在染色体中，每个基因有其特殊的位置并控制某个特殊的性质，每个基因产生的个体对环境的位置并控制某个特殊的性质，每个基因产生的个体对环境有一定的适应性。细胞在分裂时，遗传物质有一定的适应性。细胞在分裂时，遗传物质DNA通过通过复制（复制（Reproduction）而转移到新产生的细胞中，新细胞就继承而转移到新产生的细胞中，新细胞就继承了旧细胞的基因。这正是子代与父代相象的主要原因所在。了旧细胞的基因。这正是子代与父代相象的主要原因所在。另外，在进行细胞复制时，虽然概率很小，但也可能产生某另外，在进行细胞复制

9、时，虽然概率很小，但也可能产生某些复制差错，从而使些复制差错，从而使DNA中的某些基因发生中的某些基因发生变异（变异（Mutation），产生出新的染色体。这正是为什么子代与父代相象，产生出新的染色体。这正是为什么子代与父代相象，但又不是完全一样的缘故。否则，就不叫遗传，恐怕是克但又不是完全一样的缘故。否则，就不叫遗传，恐怕是克隆（隆（Clone）了。这些新的染色体表现出新的性状。如此）了。这些新的染色体表现出新的性状。如此这般，遗传基因或染色体在遗传过程中由于各种各样的原这般，遗传基因或染色体在遗传过程中由于各种各样的原因而发生变化。因而发生变化。现在学习的是第8页，共37页 生物在其延续生

10、存的过程中，逐渐适应于其生存环境，生物在其延续生存的过程中，逐渐适应于其生存环境，使得其品质不断得到改良，这种生命现象称为进化（使得其品质不断得到改良，这种生命现象称为进化（Evolution）。）。生物的进化是以集团的形式共同进行的生物的进化是以集团的形式共同进行的，这样的团体称为种群或群体（，这样的团体称为种群或群体（Population），组成种），组成种群的单个生物称为个体（群的单个生物称为个体（Individual）。每一个生物个体。每一个生物个体对其生存环境都有不同的适应能力，这种能力称为个体对其生存环境都有不同的适应能力，这种能力称为个体的的适应度（适应度（Fitness）。达尔

11、文的自然选择学说认为，。达尔文的自然选择学说认为，通过通过不同生物间的交配不同生物间的交配以及其他一些原因，生物的基以及其他一些原因，生物的基因有可能发生因有可能发生变异变异而生成一种新的生物基因，这部分而生成一种新的生物基因，这部分变异了的基因也将遗传到下一代。尽管这种变化的概变异了的基因也将遗传到下一代。尽管这种变化的概率可以预测，但具体哪一个个体发生变化却是偶然的率可以预测，但具体哪一个个体发生变化却是偶然的。现在学习的是第9页，共37页这种新的基因根据其与环境的适应程度决定其这种新的基因根据其与环境的适应程度决定其增殖能力，增殖能力，有利于生存环境的基因逐渐增多有利于生存环境的基因逐渐

12、增多，而不利于生存环境的基因逐渐减少，而不利于生存环境的基因逐渐减少。借助于。借助于这种自然的选择机制，物种将逐渐地向适应于生这种自然的选择机制，物种将逐渐地向适应于生存环境的方向进化，从而产生出越来越适应环境存环境的方向进化，从而产生出越来越适应环境的物种。不适应环境的物种，也会逐渐灭绝，销的物种。不适应环境的物种，也会逐渐灭绝，销声匿迹。这就是声匿迹。这就是“物竟天择，适者生存物竟天择，适者生存”的原理的原理。现在学习的是第10页，共37页人们对遗传与进化的特征已形成了如下的共识：人们对遗传与进化的特征已形成了如下的共识：1染色体中包含了生物的所有遗传信息（基因），染色染色体中包含了生物的

13、所有遗传信息（基因），染色体决定个体的生物特征（表现型），而表现型决定个体体决定个体的生物特征（表现型），而表现型决定个体对环境的适应度。对环境的适应度。2可以认为生物体的可以认为生物体的基因在染色体上呈线性排列基因在染色体上呈线性排列，所有所有遗传与进化过程均发生在染色体上遗传与进化过程均发生在染色体上。3生物的繁殖是由其生物的繁殖是由其基因的复制来基因的复制来完成的，完成的，交叉重组交叉重组是是有性繁殖的基因复制的基本形式。有性繁殖的基因复制的基本形式。4同源染色体之间的交叉或染色体上基因的变异（突变同源染色体之间的交叉或染色体上基因的变异（突变）产生新的物种，使生物体呈现新的性状，）产生

14、新的物种，使生物体呈现新的性状，变异是物种进变异是物种进化的根本保证化的根本保证。现在学习的是第11页，共37页5自然依据个体生物的适应度决定其在种群自然依据个体生物的适应度决定其在种群中是否存活中是否存活，对环境适应性强的基因或染色体对环境适应性强的基因或染色体经常比适应性差的基因或染色体具有更多的机会经常比适应性差的基因或染色体具有更多的机会遗传到下一代。遗传到下一代。6竞争存在于生物种群以及种群与种群之间，竞争存在于生物种群以及种群与种群之间，竞竞争是规模无限扩大趋势的生物分享有限资源争是规模无限扩大趋势的生物分享有限资源的直接结果，是物种进化的促进剂的直接结果，是物种进化的促进剂。7有

15、竞争必然有选择，自然选择是生物进化有竞争必然有选择，自然选择是生物进化的最基本规律。的最基本规律。现在学习的是第12页，共37页1.2 遗传算法遗传算法的基本原理的基本原理 遗传算法是基于自然选择和遗传机制，在计遗传算法是基于自然选择和遗传机制，在计算机上模拟生物进化机制的寻优搜索仿生智能算算机上模拟生物进化机制的寻优搜索仿生智能算法，它模拟的机制是一切生命与智能的产生与进法，它模拟的机制是一切生命与智能的产生与进化过程。化过程。在自然界的演化过程中，生物体通过遗传（传在自然界的演化过程中，生物体通过遗传（传宗接代、后代和双亲非常相像）、变异（后代与双宗接代、后代和双亲非常相像）、变异（后代与

16、双亲又不完全相像）来适应外界环境，一代又一代地亲又不完全相像）来适应外界环境，一代又一代地优胜劣汰、繁衍进化。优胜劣汰、繁衍进化。现在学习的是第13页，共37页 GA GA则模拟了上述进化现象，它把搜索空间（所求则模拟了上述进化现象，它把搜索空间（所求问题的解的隶属空间）映射为遗传空间，即把每一个问题的解的隶属空间）映射为遗传空间，即把每一个可能的解编码为一个向量（二进制或十进制数字或字可能的解编码为一个向量（二进制或十进制数字或字符串），称为一个染色体或个体，向量的每个元素称符串），称为一个染色体或个体，向量的每个元素称为基因，所有染色体组成为基因，所有染色体组成群体或种群群体或种群，并按预

17、定的，并按预定的目标函数（或某种评价指标）对每个染色体进行评目标函数（或某种评价指标）对每个染色体进行评价，据其评价结果给出一个适应度值。价，据其评价结果给出一个适应度值。现在学习的是第14页，共37页 算法开始时先算法开始时先随机地产生一些染色体（即所求随机地产生一些染色体（即所求问题的侯选解）问题的侯选解），计算其适应度，计算其适应度，据适应度大小对据适应度大小对诸染色体进行选择、交叉（杂交）、变异等遗传诸染色体进行选择、交叉（杂交）、变异等遗传操作操作，剔除适应度低（性能不佳、不适宜环境生存剔除适应度低（性能不佳、不适宜环境生存）的染色体，留下适应度高（性能优良、适宜环境）的染色体，留下

18、适应度高（性能优良、适宜环境生存）的染色体，从而得到新的群体生存）的染色体，从而得到新的群体。由于新群体。由于新群体的成员是上一代群体的优秀者，继承了上一代的优的成员是上一代群体的优秀者，继承了上一代的优良性能，因而明显优于上一代。良性能，因而明显优于上一代。GAGA就是这样反复地就是这样反复地操作，向着更优解的方向进化，直到满足某种预定操作，向着更优解的方向进化，直到满足某种预定的优化收敛指标。的优化收敛指标。现在学习的是第15页，共37页1.3 遗传算法的几个基本概念遗传算法的几个基本概念 个体个体 种群和种群规模种群和种群规模 适应度函数适应度函数 生物群体中的染色体，设计向量映射到遗传

19、生物群体中的染色体，设计向量映射到遗传空间中的一个编码串。具体地说，就是一个侯选空间中的一个编码串。具体地说，就是一个侯选解。解。一个生物群体就是一个种群，其中的生物个体的一个生物群体就是一个种群，其中的生物个体的总数目就是种群规模。编码串总数目。总数目就是种群规模。编码串总数目。适应度是生物个体适应环境生存的能力大小，适应度是生物个体适应环境生存的能力大小，或评价个体性能优劣的指标，与染色体之间存在一或评价个体性能优劣的指标，与染色体之间存在一定的关系。定的关系。现在学习的是第16页，共37页1.4 遗传算法的基本算子遗传算法的基本算子 选择（选择（SelectionSelection）算子

20、）算子 选 择 算 子 又 称 为 繁 殖、再 生 或 复 制（选 择 算 子 又 称 为 繁 殖、再 生 或 复 制（Reproduction）算子，它是用以模拟生物界去劣存）算子，它是用以模拟生物界去劣存优的自然选择现象。它从旧种群中选择出适应性强优的自然选择现象。它从旧种群中选择出适应性强（适应度高）的某些个体（染色体），放入匹配（适应度高）的某些个体（染色体），放入匹配（交配或配对）集（交配或配对）集（Mating Pool），为通过染色体），为通过染色体交叉和变异产生新的种群作准备。适应度越高的染交叉和变异产生新的种群作准备。适应度越高的染色体被选择的可能性越大，其遗传基因在下一代种

21、色体被选择的可能性越大，其遗传基因在下一代种群中的分布就越广，其子孙（后代）在下一代出现群中的分布就越广，其子孙（后代）在下一代出现的数量就越多。的数量就越多。现在学习的是第17页，共37页 选择是遗传算法中的最主要的算子（机制），也选择是遗传算法中的最主要的算子（机制），也是影响遗传算法性能的最主要的因素。但选择只能是影响遗传算法性能的最主要的因素。但选择只能从旧的种群中选择出优秀者，而不能创造出新的染从旧的种群中选择出优秀者，而不能创造出新的染色体。选择压（色体。选择压（Selection Pressure）描述了选择算）描述了选择算子挑选种群中不同个体做母体的概率大小的差子挑选种群中不同

22、个体做母体的概率大小的差异。选择压过大，会造成几个较好可行解（不异。选择压过大，会造成几个较好可行解（不一定是近似全局最优解）迅速占领了整个种群一定是近似全局最优解）迅速占领了整个种群；选择压过小，则会使算法呈现出纯粹的随机；选择压过小，则会使算法呈现出纯粹的随机徘徊行为。徘徊行为。现在学习的是第18页，共37页 选择有多种方法，如适应度比例法、顺序法、适选择有多种方法，如适应度比例法、顺序法、适应度函数的尺度变换、杰出者选择（应度函数的尺度变换、杰出者选择（Elitist Selection）。其中，适应度比例法是比较普遍采用）。其中，适应度比例法是比较普遍采用的策略，其缺陷是易造成选择压过

23、大或过小。的策略，其缺陷是易造成选择压过大或过小。适应度比例选择法又称轮转法，它把种群中的所适应度比例选择法又称轮转法，它把种群中的所有染色体适应度的总和看作一个轮子的圆周，而每有染色体适应度的总和看作一个轮子的圆周，而每个染色体按其适应度在总和中所占的比例占据轮子个染色体按其适应度在总和中所占的比例占据轮子的一个扇区片。每次染色体的选择可看作轮子的一的一个扇区片。每次染色体的选择可看作轮子的一次随机转动，它转到哪个扇区停下来，哪个扇区对次随机转动，它转到哪个扇区停下来，哪个扇区对应的染色体就被选中。尽管应的染色体就被选中。尽管 这种选择方法是随机的这种选择方法是随机的，现在学习的是第19页，

24、共37页但它与各染色体适应度成比例。这是因为适但它与各染色体适应度成比例。这是因为适应度大的染色体占据轮子扇区面积大，被选应度大的染色体占据轮子扇区面积大，被选中的概率就高（机会多），而适应度小的染中的概率就高（机会多），而适应度小的染色体占据的扇区面积小，被选中的概率就低色体占据的扇区面积小，被选中的概率就低（机会少）。（机会少）。12345687910M现在学习的是第20页，共37页举例：举例：现在学习的是第21页，共37页 交叉（交叉（CrossoverCrossover，又称杂交）算子，又称杂交）算子 选择算子虽然能够从旧种群中选择出优秀者，但不能创选择算子虽然能够从旧种群中选择出优秀

25、者，但不能创造新的染色体，因此，遗传算法的开创者提出了交叉算子。造新的染色体，因此，遗传算法的开创者提出了交叉算子。交叉算子是用于模拟生物进化过程中的繁殖杂交现象，它通交叉算子是用于模拟生物进化过程中的繁殖杂交现象，它通过两个染色体的交叉组合来产生新的染色体，即在匹配集中过两个染色体的交叉组合来产生新的染色体，即在匹配集中任选两个染色体（又称双亲），随机地选择一个交叉点（称任选两个染色体（又称双亲），随机地选择一个交叉点（称为单点交叉、单点杂交），通过交换双亲染色体交叉点右边为单点交叉、单点杂交），通过交换双亲染色体交叉点右边的部分，从而得到两个新的染色体（后代）。交叉的结果，的部分，从而得到

26、两个新的染色体（后代）。交叉的结果，有可能使各个个体的优点互相补充而产生更优的后代。由于有可能使各个个体的优点互相补充而产生更优的后代。由于交叉算子能够创造新的染色体，从而允许测试产生于搜索空交叉算子能够创造新的染色体，从而允许测试产生于搜索空间中的新点，它体现了自然界信息交换的思想。间中的新点，它体现了自然界信息交换的思想。现在学习的是第22页，共37页现在学习的是第23页，共37页 变异（变异（MutationMutation）算子）算子 选择和交叉算子实现了遗传算法的大范围搜索过选择和交叉算子实现了遗传算法的大范围搜索过程，而变异的目的在于增强遗传算法搜索最优解的程，而变异的目的在于增强

27、遗传算法搜索最优解的能力。变异算子用以模拟生物在自然的遗传环境中能力。变异算子用以模拟生物在自然的遗传环境中由于各种偶然因素引起的基因突变，它以很小的概由于各种偶然因素引起的基因突变，它以很小的概率随机地改变遗传基因（表示染色体的数字串的某率随机地改变遗传基因（表示染色体的数字串的某一位）的值。在染色体以二进制编码的系统中，它一位）的值。在染色体以二进制编码的系统中，它随机地将染色体的某一个基因由随机地将染色体的某一个基因由1变成变成0或由或由0变为变为1。现在学习的是第24页，共37页 如果只有选择和交叉算子，而没有变异算子，则如果只有选择和交叉算子，而没有变异算子，则无法在初始基因组合以外

28、的空间进行搜索，从而使无法在初始基因组合以外的空间进行搜索，从而使进化过程的早期就陷入局部解而终止进化过程，使进化过程的早期就陷入局部解而终止进化过程，使解的质量受到很大限制。通过变异算子可以确保群解的质量受到很大限制。通过变异算子可以确保群体中遗传基因类型的多样性，以使搜索能在尽可能体中遗传基因类型的多样性，以使搜索能在尽可能大的空间中进行，避免丢失在搜索中有用的遗传信大的空间中进行，避免丢失在搜索中有用的遗传信息而陷入局部解，从而获得质量较高的优化解。变息而陷入局部解，从而获得质量较高的优化解。变异算子是个体空间到个体空间的随机映射，其作用异算子是个体空间到个体空间的随机映射，其作用方式为

29、独立地以概率方式为独立地以概率P Pm m改变个体分量取值。称改变个体分量取值。称P Pm m为变异概率。为变异概率。现在学习的是第25页，共37页 遗传算法的上述三个基本算子：选择、交叉遗传算法的上述三个基本算子：选择、交叉和变异算子，各有其功能。单纯利用选择可找和变异算子，各有其功能。单纯利用选择可找到局部最优值，变异可以使搜索空间遍及整个到局部最优值，变异可以使搜索空间遍及整个空间，而交叉结果依赖于初始分布。因此，一空间，而交叉结果依赖于初始分布。因此，一个完整的遗传算法应当是选择、交叉和变异运个完整的遗传算法应当是选择、交叉和变异运算共同构成的。算共同构成的。现在学习的是第26页，共3

30、7页1.5 遗传算法实现举例遗传算法实现举例 假设一个快餐店追求的目标是最高的利润，要达假设一个快餐店追求的目标是最高的利润，要达到这一目标，必须选择适当的经营策略。一种可能到这一目标，必须选择适当的经营策略。一种可能的策略是对以下三个问题作出决策。的策略是对以下三个问题作出决策。1)每盘炒米粉的价格是每盘炒米粉的价格是5元还是元还是10元元 2)与炒米粉配套的饮料是非常可乐还是椰子汁与炒米粉配套的饮料是非常可乐还是椰子汁 3)提供快速还是排队慢速服务提供快速还是排队慢速服务 以下介绍用遗传算法来解决这个决策问题的方法以下介绍用遗传算法来解决这个决策问题的方法和过程。和过程。现在学习的是第27

31、页，共37页 （1）把问题的可能解表示为染色体数字串（问）把问题的可能解表示为染色体数字串（问题编码）题编码）由于这个问题有三个决策变量，其取值为是或否由于这个问题有三个决策变量，其取值为是或否，可以用，可以用1或或0来表示，于是可以用三位的二进制数字来表示，于是可以用三位的二进制数字表征一种可能的经营策略，解的搜索空间为表征一种可能的经营策略，解的搜索空间为23=8，即，即有有8种经营策略可供选择。表种经营策略可供选择。表3给出了其中快餐店经理给出了其中快餐店经理已知的已知的4种经营策略（初始解）。表中数字串的第一位种经营策略（初始解）。表中数字串的第一位取取0表示价格高，表示价格高，1表示

32、价格低；第二位取表示价格低；第二位取0表示椰表示椰子汁，取子汁，取1 表示非常可乐；第三位取表示非常可乐；第三位取0表示排队慢速表示排队慢速服务，取服务，取1 表示快速服务。表示快速服务。现在学习的是第28页，共37页现在学习的是第29页，共37页 a)求各染色体的适应度。求各染色体的适应度。这个问题中，一个染色体的适应度假设恰好是其这个问题中，一个染色体的适应度假设恰好是其二进制数字串等价的十进制数，也是对应的经营策略二进制数字串等价的十进制数，也是对应的经营策略的利润。的利润。现在学习的是第30页，共37页 b)选择进入交叉集的染色体选择进入交叉集的染色体 由表由表4可见，所有染色体串的适

33、应度的总和是可见，所有染色体串的适应度的总和是12，数字串，数字串110的适应度是的适应度是6，占适应度总和的，占适应度总和的1/2，也，也就是说该串被选中的机会有两次，其概率为就是说该串被选中的机会有两次，其概率为1/2；串；串011，001，010 被选中的概率分别为被选中的概率分别为3/12=1/4，1/12，2/12=1/6。按前述的适应度比例法，选择进入交叉集的。按前述的适应度比例法，选择进入交叉集的染色体串及其适应度值见表染色体串及其适应度值见表5所示。所示。现在学习的是第31页，共37页现在学习的是第32页，共37页 从表从表5可知，选择算子的作用确实是改进了种群可知，选择算子的

34、作用确实是改进了种群的平均适应度，使其由原来的的平均适应度，使其由原来的3提高到了提高到了4.25，最，最坏的适应度由原来的坏的适应度由原来的1改进为改进为2，性能最差的染，性能最差的染色体已从种群中删除。但是，选择不能创造新色体已从种群中删除。但是，选择不能创造新的染色体，为了改进这一缺点，寻找搜索空间的染色体，为了改进这一缺点，寻找搜索空间内的新的检测点，必须进行交叉操作。内的新的检测点，必须进行交叉操作。现在学习的是第33页，共37页 c)交叉操作交叉操作 这里采用单点交叉算子进行交叉操作，随这里采用单点交叉算子进行交叉操作，随机产生的交叉点是机产生的交叉点是2，从交叉集中任取一对染色，

35、从交叉集中任取一对染色体如体如011和和110，互换它们的第，互换它们的第3位，得到子孙（后位，得到子孙（后代）染色体代）染色体010和和111，其中，其中111是交叉算子操作创是交叉算子操作创造出的新的染色体。因为本例中交叉概率为造出的新的染色体。因为本例中交叉概率为0.5，交叉集中剩下两个染色体不再参加交叉操作，而交叉集中剩下两个染色体不再参加交叉操作，而与交叉操作后得到的子孙一起作为下一代种群的与交叉操作后得到的子孙一起作为下一代种群的成员。由此得到第一次交叉操作后的第一代种群成员。由此得到第一次交叉操作后的第一代种群，如表，如表6中所示中所示 现在学习的是第34页，共37页现在学习的是

36、第35页，共37页 显然，经过交叉操作，种群中产生了新的染色体显然，经过交叉操作，种群中产生了新的染色体（个体）（个体）111，而且其适应度最高，即性能最优。，而且其适应度最高，即性能最优。d)对新一代种群的适应度进行评价对新一代种群的适应度进行评价 经过交叉操作，在新一代（第经过交叉操作，在新一代（第1代）种群中，最代）种群中，最优染色体的适应度由原来的优染色体的适应度由原来的6提高到了提高到了7，其对应，其对应的代码串是的代码串是111，表示一种优化的经营策略，即低，表示一种优化的经营策略，即低价格销售炒米粉，配套供应的饮料为非常可乐，而价格销售炒米粉，配套供应的饮料为非常可乐，而且通过快速服务可获得最高利润且通过快速服务可获得最高利润7元，即数字串元，即数字串111的适应度。平均适应度由原来的的适应度。平均适应度由原来的3提高到了提高到了4.25，最，最坏适应度由原来的坏适应度由原来的1提高到了提高到了2，整个种群的适应度，整个种群的适应度在总体上得到了提高，被优化了。在总体上得到了提高，被优化了。现在学习的是第36页，共37页感谢大家观看感谢大家观看现在学习的是第37页，共37页