第8章-进化算法...ppt

1、第八章进化算法，遗传算法：一种基于自然选择和自然遗传学的迭代自适应概率搜索算法。利用进化计算，特别是遗传算法机制和传统的反馈机制，可以实现一种新的控制进化控制。顾名思义，遗传算法是一种与遗传学相关的算法，或者是从遗传学中提取一些“精华”而形成的算法。我们在这里讨论的遗传算法是一种基于自然选择和遗传原理的搜索算法。传统优化方法(局部优化)、共轭梯度法、拟牛顿法、单纯形法、全局优化法、随机游走法、模拟退火法、遗传算法，对于优化问题，与传统优化方法相比，1)依赖于初始条件。2)它与解空间密切相关，这使得它能快速收敛到局部解，但同时它对解域有约束，如可微性或连续性。3)一些方法至少直接依赖于一阶导数；

2、共轭梯度法隐含地依赖于梯度。全局优化方法，1)独立于初始条件；2)与解空间没有密切关系，对解域没有微分或连续的要求。解决方案是稳健的，但收敛速度很慢。可以获得全局优化。它适用于解决未知空间的情况。在8.1中，在自然进化的过程中，生物体通过遗传和变异来适应外部环境，优胜劣汰，一代一代地发展和进化。根据自然遗传理论，遗传被封装在每个细胞中作为一种指令遗传密码，并以基因的形式包含在染色体中，每个基因都有一个特殊的位置并控制着一种特殊的属性；每个基因产生的个体对环境都有一定的适应性；遗传杂交和突变可能会产生更能适应环境的后代。生物遗传学基础：遗传算法中的基本概念和术语染色体遗传物质的主要载体是指多个遗

3、传因子的集合，遗传因子基因是控制生物性状的功能和结构的基本单位，以及具有染色体特征的个体的集合，也称为群体，集合中个体的数量是群体的大小，适应性：每个个体对环境的适应程度。选择复制决定了以一定概率从群体中选择几对个体的操作。也称重组突变使遗传因素以一定概率突然改变的操作。8.1.2遗传算法的特点和发展，1 .特征1)参数编码的操作，而不是参数本身，可以模拟生物遗传和进化的机制。对于没有数值概念(只有代码概念)的优化问题尤其有益。2)目标函数值被直接用作搜索信息，并且对被优化的函数没有限制，这被广泛使用。3)并行操作同时从许多初始点开始，这有可能实现全局优化(隐式并行)。自适应值由目标函数计算，

4、它对问题的依赖性很小。4)概率搜索技术增加了搜索的灵活性，适用于大规模复杂问题的优化。2)遗传算法的发展，1975年约翰霍兰德的经典著作自然和人工算法中的适应，遗传算法的基本定理和数学证明。遗传算法广泛应用于功能优化、组合优化、生产调度、自动控制和图像识别等领域，从根本上说是一种优化算法、关键人物和重要贡献。(1)20世纪60年代，霍兰德认识到生物遗传与自然进化现象和人工适应系统的相似关系，并运用生物遗传和进化的思想研究了自然和人工适应系统的产生及其与环境的关系。在研究和设计人工适应系统时，可以借鉴生物遗传的机理，采用分组方法进行自适应搜索，充分认识到交叉和变异在适应系统中的重要性。20世纪7

5、0年代，奠定了理论基础。20世纪80年代，分类系统。(2)巴格利首先提出了“遗传算法”；开发遗传算子；不同阶段(3)建立了遗传算法的工作框架；推荐适合大多数优化问题的遗传算法参数；建立了五功能测试平台。例如，对于一个50，100的种群，经过1020代的进化，遗传算法可以高效地找到最优或近似最优解。(4)戈德堡发表了专著搜索、优化和机器学习中的遗传算法。本书系统总结了遗传算法的主要研究成果，全面、完整地论述了遗传算法的基本原理和应用。(5)戴维斯编辑出版了遗传算法手册。该书包含了大量遗传算法在科学计算、工程技术和社会经济中的应用实例。推广和普及遗传算法的应用。(6)科萨提出了遗传规划。GP已经成

6、功地将他的遗传编程方法应用到人工智能、机器学习、符号处理等领域。8.1.3遗传算法应用、功能优化、组合优化生产调度问题、自动控制机器人智能控制图像处理和模式识别人工生命遗传编程机器学习，8.2遗传算法的核心思想来源于：生物进化过程(从简单到复杂，从低级到高级)本身就是一个自然、并行和鲁棒的优化过程。这个优化过程的日常标准是对环境的适应性，生物种群通过“适者生存”和遗传变异达到进化(优化)的目的。基本思想是通过复制、交叉和变异等基本算子的作用，一代一代地更新种群。在更新过程中，父母的优良品质被保留，不良因素被逐渐去除，从而使更新后的后代逐渐优化。适应度函数，以反映染色体的适应性，即适者生存的原则

7、来衡量种群中每个个体在优化计算中可能达到或接近找到最优解的优良程度。体能高的个体更有可能遗传给下一个个体，而体能低的个体相对较小。对于优化问题，适应度函数是目标函数，它模拟自然界优胜劣汰的进化现象，将搜索空间映射到遗传空间，并将可能的解编码到一个向量染色体中，向量的每个元素称为基因。通过不断计算每条染色体的适应值，选择最佳染色体，得到最优解。通用遗传算法包括三个基本操作：繁殖、选择、交叉和变异，模拟生物进化和繁殖中的自然选择，群体遗传过程中的交配和基因变异。(1)复制：从旧群体中选择适应性强的染色体，进入匹配池(缓冲区)，为染色体交换、突变和新染色体的产生做准备。适应值高的个体在下一代有更多机

8、会繁殖一个或多个后代，而适应值低的个体可能被淘汰。复制的目的是确保适应性强的优秀个体在进化中生存，但复制不会产生新的个体。复制的基础：个体的适应值通常的方法是：轮法，它根据每条染色体的适应率来确定所选染色体的数量。染色体被选择的概率：PC和Xi是种群中的第一条染色体。具体方法是计算群体中第一个个体的适应值。那么，下一代的个体数应该是：复制的目的是确保那些适应性强的优秀个体在进化中生存，但复制不会产生新的个体。让我们假设一个初始种群：有四个个体，每个个体都是长度为5的二进制数。相应的十进制数是变量xi，适应度函数设置为f (xi)=xi2，例如01101、11000、01000、10011、1

9、2 3 4、1和4各复制一次，3消除，2复制两次。由轮方法选择的49.2%、14.4%、30.9%、5.5%，使得所有个体的适合度之和为1，这对应于一个轮，并且每个个体根据其适合度值占该轮的一部分。当滚轮旋转并停止时，指针指向的个体就是要复制的个体。选择个人后，该个人将被完全复制并发送到匹配的池中。有些人可能被复制一次或多次，而有些人可能被淘汰。个人4，个人2，个人3，个人1，其他方法1。成对竞争方法从群体中随机选择两个个体，并将适应度较大的个体作为复制个体；2.基于排序的选择方法首先根据目标函数的大小对个体进行排序，然后应用每个个体的排序序号计算相应的适应度。该方法避免了轮方法中因适应度差异

10、过大而导致种群个体多样性损失过大的不足。2)交换、复制不能创新，但交换可以解决染色体创新。方法：从由新的复制产生的匹配池中随机选择两条染色体(父母的染色体)，随机指定一个或多个点，并交换它们以获得两条新的染色体(后代染色体)。如果单个长度为10，交换位置随机选择为5个单点交换，交换点随机选择。染色体A 1100111001交换1100100110染色体b010100110 0101011001，交换前后也有两点交换：随机选择交换位置为2，7两点交换，染色体a11011000交换111011000染色体b 101011011011011001100111111。如果交换后孩子的表现不好，他们将在

11、以后的复制中被丢弃。复制和交换操作在此群体上执行，匹配的对象和交换点是随机选择的。遗传算法的有效性主要来自复制和交换操作，特别是交换在遗传算法中起着核心作用。个体交换对应于不同思想的重组，新思想在这种重组中产生，遗传搜索的作用就在这里。尽管优秀的染色体是从旧物种中选出的，但新的染色体不能被创造出来来模拟生物进化中的生殖现象。新的染色体可以通过两个染色体的组合来产生新的优良品种，从而允许在搜索空间中测试新的点。统一交换模板：随机生成一个与父个体长度相同的二进制字符串。2.如果其中一个模板为1，则交换两个父模板的对应位；3.如果其中一个模板为0，则不交换两个父模板的相应位。例如：交换前，交换后，个

12、体1010100101001001模板100101010101个体201001000101 100100，3)突变，模拟自然界遗传环境中各种偶然因素引起的基因突变，随机改变字符串位置值的概率很小。对于二进制编码，反向操作：大约01；10通过变异，增加了种群的多样性，使得搜索在尽可能大的空间内进行，避免陷入局部最优解，获得高质量优化变异的概率很低。通常，突变率pm为0.001-0.1。在简单的遗传算法中，变异是随机否定某个个体的值，1100110111变异110010111，在变异之前，变异。在遗传算法的后期，变异算子在恢复种群多样性中起着决定性的作用。，例如：01101，11000，01000

13、，10011人口总数位数=4*5=20。如果选择Pm=0.001，则0.001*20=0.02(数字)不会发生突变。如果选择Pm=0.1，那么0.120=2(数字)将有2个数字。注：Pm突变的概率很小：通常取0.0010.1突变位数=Pm*人口总数位数。用遗传算法解决实际问题时，1)首先对待优化问题的所有参数进行编码(一般使用二进制编码串)，并将所有参数连接起来得到一个串，每个串是一个个体(或染色体)，所有个体的集合称为种群或种群。在群体中，每个个体代表一个可行的解决方案。2)其次，根据优化问题，构造适应度函数来评价个体的适应性。3)最后，从随机产生一组初始解开始，用遗传算子对每个个体进行操作

14、和组合，使初始种群一代代进化到最优解。简单遗传算法(GA)的基本参数，参与群体规模进化的染色体总数P:父母与子女之间不同数量的染色体的代沟G:无重叠G=1；有重叠的0 G 1选择方法：轮法，精英选择方法和竞争法。在： Pc时，汇率通常为600%，在：pm时，变化率通常为0.1%。算法流程，1)问题描述，在遗传算法中，问题的解用字符串表示，1)如何选择合适的字符串编码来表示问题？2)如何排列字符串以方便编码和解码？目前使用的字符串编码主要包括二进制、十进制、浮点数等编码形式；2)初始群体通常以随机方式产生；3)适应度函数f的确定要求所有个体的适应度必须为正或零。它用于衡量群体中的每个个体在优化计

15、算中可能达到或接近找到最优解的优秀程度。体能高的个体更有可能遗传给下一个个体，而体能低的个体相对较小。对于优化问题，适应度函数是目标函数。在遗传算法中，要求适应度函数是非负的，且越大越好。实际优化问题的目标函数不一定满足这一条件，因此应进行自适应变换。4)收敛标准，常用的标准有：1)指定迭代次数。2)当多次连续获得的种群中的最优解没有变化时，认为算法收敛。5)遗传算法的基本流程，遗传算法的思想是确定个体进行复制、交叉和变异，一代群体经过选择复制、交叉和变异后会产生新一代群体。重复上述步骤，直到满足某些要求。摘要：示例，解决方案：(1)确定适当的编码，并将问题的可能解决方案表示为染色体编号字符串。由于变量X的取值范围为0，31和25=32，变量X用5个无符号二进制数表示，形成一个染色体数串，函数f(x)=-x2 31x 10被设置为在0，31 (x为(2)生成初始种群和用随机方法生成4条染色体(个体)的区间内找到其最大值；(3)计算适应值和选择概率，00001，11100，01000，10011；(3)计算适应值和选择概率；(4)选择进入交换的染色