第8章-进化算法..

第8章进化算法遗传算法（GA）：建立在自然选择和自然遗传学基础上的迭代自适应概率性搜索算法把进化计算，特别是遗传算法机制和传统的反馈机制用于控制过程，则可实现一种新的控制——进化控制顾名思义，遗传算法是与遗传学有关的一种算法，或者说是从遗传学中汲取了某些“精华”所构成的算法。我们这里讲的GA是一种基于自然选择和基因遗传学原理的搜索算法。传统的优化方法（局部优化）共轭梯度法、拟牛顿法、单纯形方法全局优化方法漫步法（RandomWalk）、模拟退火法、GA关于优化问题比较：传统的优化方法1）依赖于初始条件。2）与求解空间有紧密关系，促使较快地收敛到局部解，但同时对解域有约束，如可微或连续。3）有些方法直接依赖于至少一阶导数；共轭梯度法隐含地依赖于梯度。全局优化方法1）不依赖于初始条件；2）不与求解空间有紧密关系，对解域，无可微或连续的要求。求解稳健，但收敛速度慢。能获得全局最优。适合于求解空间不知的情况8.1概述自然界演化过程中，生物体通过遗传、变异来适应外界环境，一代又一代地优胜劣汰，发展进化。２）自然遗传学说遗传作为一种指令遗传码封装在每个细胞中，并以基因的形式包含在染色体中，每一基因有特殊的位置并控制某个特殊的性质；每个基因产生的个体对环境有一定的适应性；基因杂交和基因突变可能产生对环境适应性更强的后代。生物遗传学基础：遗传算法中的基本概念和术语染色体——遗传物质的主要载体，指多个遗传因子的集合遗传因子——基因，控制生物性状遗传物质的功能和结构的基本单位群体——染色体带有特征的个体的集合，又称集团，集合内的个体数称群体的大小适应度——各个个体适应环境的程度选择／复制——决定以一定的概率从群体中选取若干对个体的操作交叉——把两个染色体进行换组的操作，又称重组变异——突然让遗传因子以一定的概率变化的操作8.1.2遗传算法特点与发展1、特点1）对参数编码进行操作，而不是参数本身，可以模拟生物遗传、进化机理，特别对无数值概念（只有代码概念）的优化问题有益2）直接以目标函数值作为搜索信息，对于待寻优的函数无限制，应用广泛3）同时从许多初始点开始并行操作，较大可能获得全局最优（隐含并行性）。通过目标函数计算适配值，对问题依赖性小4）使用概率搜索技术，增加了搜索灵活性，适合大规模复杂问题优化2.遗传算法的发展里程碑——JohnH.Holland在1975年的AdaptationinNaturalandArtificialAlgorithms(自然系统和人工系统的自适应性)经典之作有关GA的基本定理及数学证明。广泛应用——函数优化、组合优化、生产调度、自动控制、图象识别…GA从根本上说是一种寻优算法关键人物及重要贡献（1）J.H.Holland60年代，认识到了生物的遗传和自然进化现象与人工自适应系统的相似关系，运用生物遗传和进化的思想来研究自然和人工自适应系统的生成以及它们与环境的关系，提出在研究和设计人工自适应系统时，可以借鉴生物遗传的机制，以群体的方法进行自适应搜索，并且充分认识到了交叉、变异等运算策略在自适应系统中的重要性。70年代，理论基础的奠定。80年代，分类器系统。（2）J.D.Bagley首次提出“遗传算法”；发展遗传算子；不同阶段采用不同的概率；在个体编码上使用了双倍体的编码方法…。（3）K.A.DeJong树立遗传算法的工作框架；推荐在大多数优化问题中都较适用的遗传算法的参数；建立了五函数测试平台…。例如，对于规模在50—100的群体，经过10—20代的进化，遗传算法都能以很高的慨率找到最优或近似最优解。（4）D.J.Goldberg出版了专著《搜索、优化和机器学习中的遗传算法》(geneticalgorithmsinsearch,ptimizationandmachinelearning)。该书系统总结了遗传算法的主要研究成果，全面而完整地论述了遗传算法的基本原理及其应用。（5）L.Davis编辑出版《遗传算法手册(Handbookofgeneticalgorithms)》一书。书中包括了遗传算法在科学计算、工程技术和社会经济中的大量应用实例。推广和普及遗传算法的应用。（6）J.R.Koza提出了遗传编程(GeneticProgramming。简称GP)成功地把他提出的遗传编程的方法应用于人工智能、机器学习、符号处理等方面。8.1.3遗传算法应用函数优化、组合优化生产调度问题、自动控制机器人智能控制图像处理和模式识别人工生命遗传程序设计机器学习8.2GA的基本理论GA的核心思想源于：生物进化过程(从简单到复杂，从低级向高级)本身是一个自然的、并行发生的、稳健的优化过程。这一优化过程的日标是对环境的自适应性，生物种群通过“优胜劣汰”及遗传变异来达到进化(优化)的目的。基本思路是通过复制、交叉和变异等基本算子的作用，让种群一代一代的更新。在更新的过程中，把父辈的优良品质保留下来，而将不好的因素逐渐去掉，使得更新后的子代逐渐得到优化。适应度函数Fitness为体现染色体的适应能力，即优胜劣汰原则用来度量群体中各个个体在优化计算中有可能达到或接近于找到最优解的优良程度。适应度高的个体遗传到下一个个体的概率较大，而适应度较低的就相对小一些。对优化问题，适应度函数就是目标函数模拟自然界优胜劣汰的进化现象，把搜索空间映射为遗传空间，把可能的解编码成一个向量——染色体，向量的每个元素称为基因。通过不断计算各染色体的适应值，选择最好的染色体，获得最优解。基本操作一般的遗传算法包含有3个基本操作：复制（reproduction，或称selection）交换（crossover）变异（mutation）这3个基本操作分别模拟生物进化中的自然选择和种群遗传过程中的繁殖、交配和基因突变等现象。1）复制从旧的种群中选择适应度高的染色体，进入匹配池（缓冲区），为以后染色体交换、变异，产生新的染色体作准备。适应度值高的个体在下一代将有更多的机会繁殖一个或多个后代，而适应度值低的个体则有可能被淘汰。复制的目的在于保证那些适应度高的优良个体在进化中生存下去，但是复制不会产生新的个体。复制的依据：个体的适应度值通常的方法有：转轮法按各染色体适应度大小比例来决定其被选择数目的多少。某染色体被选的概率：Pc)()(iicxfxfPxi为种群中第i个染色体，具体的做法是：对种群的第i个个体，计算其适应值。然后求，于是该个体在下一代中的个数应为：fiiifffffNiii复制的目的在于保证那些适应度高的优良个体在进化中生存下去，但是复制不会产生新的个体。设一初始种群：含有4个个体每个个体为一个长度为5的二进制数对应的十进制数就是变量xi，适应度函数设为f(xi)=xi2如：01101，11000，01000，10011个体1234标号初始种群X值适应度f(x)=x2选择复制的概率fi/∑fi期望的复制数fi/实际得到的复制数101101131690.1440.581211000245760.4921.9723010008640.0550.220410011193610.3091.231总计11701.0004.004平均值2930.251.001最大值5760.491.972if个体1和个体4各被复制1次，个体3被淘汰，个体2被复制两次。用转轮方法进行选择49.2%14.4%30.9%5.5%令所有个体适应度之和为1，即对应一个转轮，而每个个体按其适应度值大小分占转轮的一部分。转轮转动，停止时，指针所指向的个体就是要被复制的个体。当一个个体被选中，此个体将被完整的复制送入匹配池。有的个体可能被复制1次或多次，有的可能被淘汰。个体4个体2个体3个体1其他方法1、两两竞争法从种群中随机地选择两个个体，将其中适应度较大的个体作为被复制的个体；2、基于排序的选择法首先根据目标函数的大小将个体排序，应用各个体的排序序号来计算相应的适应度。这种方法避免了在转轮法中因适应度相差太大而导致种群个体多样性损失太多的不足。2）交换复制不能创新,交换可解决染色体的创新方法:随机选择新复制产生的匹配池中的二个染色体(双亲染色体),随机指定一点或多点,进行交换,可得二个新的染色体(子辈染色体).如个体长度为10，随机选取交换位置为5——单点交换，交换点是随机选取的。染色体A11001∣11001交换11001∣00110染色体B01010∣0011001010∣11001交换前交换后另外还有双点交换：随机选取交换位置为2，7——双点交换染色体A11∣01011∣000交换11∣10110∣000染色体B10∣10110∣10110∣01011∣101交换前交换后交换可以把两个个体中优良的模式传递到子代中，使子代个体具有优于父代的性能。若交换后子代性能不佳，则会在以后的复制中将其抛弃。标号初始种群X值适应度f(x)=x2选择复制的概率fi/∑fi期望的复制数fi/实际得到的复制数101101131690.1440.581211000245760.4921.9723010008640.0550.220410011193610.3091.231总计11701.0004.004平均值2930.251.001最大值5760.491.972对该种群实施复制、交换操作if标号复制后的匹配池匹配对象(随机选取)交换点(随机选取)新种群x值f(x)=x21011013201000864211000441100125625311000121110129841410011241001018324总计1854平均值463.5最大值841匹配对象及交换点都是随机选取的遗传算法的有效性主要来自复制和交换操作，尤其交换在遗传算法中起着核心作用。个体交换就相应于不同观念的重新组合，而新的思想就是在这种重新组合中产生的，遗传搜索的作用也就在此。复制（选择）虽然从旧群种中选择出优秀者，但不能创造新的染色体模拟生物进化中的繁殖现象，通过两个染色体的组合来产生新的优良品种交叉能够创造出新的染色体，从而允许对搜索空间中的新点进行测试均匀交换模板（template）：随机产生的一个与父代个体同样长度的二进制串.1、先选出两个父代个体，2、若模板中的某位为1，则两个父代个体对应位进行交换，3、若模板中的某位为0，则两个父代个体对应位不进行交换。例：交换前交换后Individual101011001100100110011Template1001010101Individual2011001000101110001003）变异模拟生物在自然界的遗传环境中由于各种偶然因素引起的基因突变以很小的概率随机的改变一个串位的值对于二进制编码，取反操作：即将01；10通过变异，增加群体中的多样性，使搜索在尽可能大的空间进行，避免陷入局部解，获得质量较高的优化变异的概率很低，通常变异率pm取0.001-0.1在简单遗传算法中，变异就是将某个个体中某一位的值随机的进行取反操作1100110111变异1100010111变异前变异后在所有个体都相同的种群中，交换算子已经失效，出现近亲繁殖，不能产生新的个体，只有靠变异才能产生。遗传算法后期，变异算子起着决定性作用，起到恢复种群多样性的作用。例如：01101，11000，01000，10011种群总的位数=4*5=20若选Pm=0.001，则0.001*20=0.02（位）不作变异若选Pm=0.1，则0.120=2（位）有2位变异注意：变异的概率Pm很少：通常取0.001—0.1变异的位数=Pm*种群总的位数遗传算法求解实际问题时：1）首先对待优化问题的所有参数进行编码（一般采用二进制码串），将所有参数的编码串接起来得到一个字符串，每一个字符串就是一个个体（或染色体），所有个体的集合称之为种群或群体。在种群中，每一个个体都表示一个可行解。2）其次，根据优化问题构造评价个体适应能力的适应度函数。3）最后，以随机方式产生一群初始解为开始，通过使用遗传算子对每个个体进行操作组合，使初始种群一代一代的向最优解进化。简单遗传算法（GA）的基本参数①种群规模P