第7章 进化计算

1、计 算 智 能普通高等教育“十一五”规划教材第1章 绪论第2章 知识表示第3章 基本推理原理第4章 搜索原理第5章 模糊逻辑第6章 神经网络第7章 进化计算第8章 群体智能第9章 数据挖掘第7章 进化计算7.1遗传算法概述7.2基本遗传算法7.3遗传算法的数学理论基础7.4遗传算法的实现技术自然界中的生物对其生存环境具有优良的自适应性，各种物种在竞争的环境中生存，优胜劣汰，使得物种不断改进。生物学家和计算机学家各自从自己学科的角度出发，对其进行了机理研究和应用研究。生物学家偏重于对其进化机制的研究，提出了多种生物进化的机理，以探索生物进化的奥秘；而计算机学家则偏重于对生物进化机理及生物系统的模

2、拟，以便构成一类复杂的人工自适应系统。而计算智能的迅速发展也体现了生物学与计算机科学的相互交叉、相互渗透和相互促进。近几十年以来，人类正在将其模仿的范围延伸到了人类的自身。神经网络是人类对其大脑信息处理机制的模拟，模糊系统是人类对其思维方式的模拟，而进化计算是人类对其自然进化过程的模拟。依照达尔文的自然选择规律和孟德尔的变异理论，生物的进化是通过繁殖、变异、竞争和选择这四种基本形式来实现的。因而，如果把待解决的问题理解为对某个目标函数的全局优化，则进化计算即是建立在模拟上述生物进化过程基础上的随机搜索优化技术。进化计算(evotutionary computation，EC)也可以称之为进化算

3、法(evolutionary algorithms，EA)，它是一类模拟生物进化过程求解问题的智能技术。进化计算起源于20世纪60年代J.Holland对机器学习问题所发展的遗传算法(genetic algorithms，GA)，I.Recenberg和H.P.Schwefel用于数值优化问题的进化策略(evolution strategies，ES)及L.J.Fogel对于优化模拟系统所提出的进化规划(evolutionary programming，EP)。即： (1) 遗传算法(GeneticAlgorithm，GA) 遗传算法是建立在自然选择和自然遗传学机理基础上的迭代自适应概率性搜索

4、算法。 (2) 进化规划(EvolutionaryProgramming，EP) 进化规划主要用于预测和数值优化计算。 (3) 进化策略(EvolutionaryStrategy，ES) 进化策略主要研究经验性寻优过程，以便获得一个最优化的策略。下面将分别介绍进化策略、进化规划和遗传算法：进化策略进化策略是由德国学者I Rechenberg和H.P.Schwefel等人在1973年最先提出的一种优化算法。其主要构成技术如下。 (1)个体表示方法在进化策略中，搜索空间是一个n维空间，与此相对应，搜索点就是一个包含在n维空间中的一个n阶向量x。算法中，组成进化群体的每一个个体都是由两部分组成，其中

5、一部分是可以取连续值的向量，另一部分是一个微小的变动量。这个变动量是由n维空间的正态分布的标准偏差构成的步长和正态分布的协方差构成的回转角组成的，它们可以用来调整对个体进行变异操作时变异量的大小和方向。(2)适应度评价在进化策略中，设定每个个体的适应度就等于其所对应的目标函数值，而不再对所求优化问题的目标函数值进行任何变换处理，这主要是由于优化策略中的选择运算是按照一种确定的方式来进行的缘故，每次都是从当前群体中选择出一个或几个适应度高的个体保留到下一代群体中，这里只有个体适应度之间的大小关系比较运算，而无算术运算，所以对个体适应度是取正值还是取负值无特别要求。(3)变异算子在进化策略中，变异

6、操作是产生新个体的一种最主要的方法。如果群体中某个个体经过变异运算后得到一个新的个体，则新的个体组成的元素受到变异运算时的整体步长和个体步长的影响。(4)交叉算子在进化策略中，交叉操作只是一种辅助的搜索运算。任一群体中的两个个体随机配对，则对这两个个体进行交叉操作后会产生一个新的个体，个体中的元素可能出现3种交叉方式：无交叉、直接交叉和加权平均交叉。(5)选择算子 在进化策略中，选择操作是按照一种确定的方式来进行的。目前在进化策略中所使用的选择方法主要有如下两类：一类是从A个父代个体中选择出u个适应度最强的个体，将它们保留到子代群体中，这类选择方法记为(u，)ES进化策略；另一类是u个父代个体

7、和其产生的A个子代个体合并在一起，并从中选择u个适应度最高的个体保存到子代群体中，这类方法记为(u+)ES进化策略。根据算法中所采用的具体选择方法不同，也就产生了不同类型的进化策略。目前常用的进化策略如下。 (1+1)ES：爬山法。 (1,1)ES：随机搜索法。 (1+u)ES：邻接搜索法。 (1，u)ES：邻接搜索法。 (u+)ES：保留最优个体的多点搜索法。 (u，)ES：多点搜索法。进化规划进化规划方面的论文是美国JFLawrence、L.J.Fogel、A.J.Owens和M.J.Walsh等人在1966年发表的，其基本思想是源于对自然界中生物进化过程的一种模仿。其构成技术与进化策略的

8、构成技术相类似，主要内容如下。(1)个体表示方法在进化规划中，搜索空间是一个n维空间，与此相对应，搜索点就是一个包含在n维空间中的一个M阶向量x。算法中，组成进化群体的每一个个体x就直接用这个M维向量来表示。(2)适应度评价 在进化规划中，个体适应度是由它所对应的目标函数通过某种比例变换而得到的，这种比例变换是为了既保证各个个体的适应度总取正值，又维持各个个体之间的竞争关系。(3)变异算子 在标准的进化规划中，变异操作使用的是高斯变异算子。一个个体经变异运算后得到的新的个体会产生一个增量，这个增量是均值为o、方差为1的正态分布的随机变量。(4)选择算子 在进化规划中，选择操作是按照一种随机的竞

9、争方式来进行的。它的基本过程是先将父代个体和经过一次变异运算后产生的子代个体合并在一起，然后从每一个个体集合A中选取Q个个体，比较它们之间适应度的大小，以其中适应度比A高的个体数目作为个体X的得分，最后按照得分作降序排列，选择前J个个体作为进化过程的下一代群体。遗传算法遗传算法是计算数学中用于解决最优化的搜索算法，是进化算法的一种。进化算法最初是借鉴了进化生物学中的一些现象而发展起来的，这些现象包括遗传、突变、自然选择以及杂交等。遗传算法通常实现为一种计算机模拟。对于一个最优化问题，一定数量的候选解（称为个体）的抽象表示（称为染色体）的种群向更好的解进化。传统上，解用二进制表示（即0和1的串）

10、，但也可以用其他表示方法。进化从完全随机个体的种群开始，之后一代一代发生。在每一代中，整个种群的适应度被评价，从当前种群中随机地选择多个个体（基于它们的适应度），通过自然选择和突变产生新的生命种群，该种群在算法的下一次迭代中成为当前种群。进化算法的两个主要特点是群体搜索策略及群体中个体之间的信息交换。进化计算的三个主要分支虽然着眼于自然界中生物进化的不同背影，是由不同的研究人员独立地开发出来的，但它们之间有着很多相似之处，可统一于一个基本框架之内。下面给给出进化计算的统一算法描述： （1）进化代数计数器t初始为0。 （2）随机产生初始种群p(t)，并计算p(t)的适应度。 （3）对p(t)作重

11、组操作，得到p(t)。 （4）对p(t)作变异操作，得到p(t)。 （5）计算p(t)的适应度。 （6）从p(t)或p(t) p(t)中作选择复制操作，得到下一代p(t+1). （7）算法结束条件判断：若p(t+1)不满足指定的结束条件，则tt+1，转到第(3)步，继续进行进化操作过程；若p(t+1)满足指定的结束条件，则输出当前最优个体，算法结束。这三种进化计算方法都具有下述一些共同的基本特点：（1）算法的操作对象都是由多个个体组成的一个集合，即群体。（2）每个个体都有一个对系统环境的适应度，这个适应度是算法对每个个体优劣程度的一种度量。（3）算法都要进行选择或复制操作，以便能够将当前群体中

12、具有较高适应度的个体更多地保留到下一代群体中。（4）算法都通过个体重组、变异等进化操作，以及对个体所加入的一些微小变动来增进群体的多样性。（5）算法所模拟的生物进化过程都是一个反复迭代的过程。在群体的这个迭代进化过程中，个体的适应度和群体中所有个体的平均适应度都不断地得到改进，最终可得到一个或几个具有较高适应度的个体，它们就对应了问题的最优解或近似最优解。（6）算法所模拟的进化过程均受到随机因素的影响，所以它们不易陷入局部最优点，并都能以较大的概率找到全局最优点。（7）算法都具有天然的并行结构，均适合于在并行机或局域网环境中进行大规模复杂问题的求解。由于进化算法具备上述的这些特点，使得它能够帮

13、助用户解决复杂系统的优化问题，特别是能够解决一些利用其他方法难以解决或根本无法解决的问题。上述的这些特点同时也说明了进化算法是一类全局优化自适应概率搜索技术，它不依赖于具体问题的种类，具有广泛的应用价值。目前，这三种进化算法仅在实现方面存在着一些差别，并且这些差别正在逐渐地缩小，而遗传算法作为进化计算理论体系的中心，其理念和方法也是在不断地完善和进步。7.1遗传算法概述遗传算法是一种借鉴生物界自然选择和进化机制发展起来的高度并行、随机、自适应搜索算法。简单而言，它使用了搜索技术，将种群代表一组问题解，通过对当前种群施加选择、交叉和变异等一系列遗传操作，从而产生新一代的种群，并逐步使种群进化到包

14、含近似最优解的状态。由于其思想简单，易于实现以及表现出来的健壮性，遗传算法赢得了许多应用领域特别是近年来在问题求解、优化和搜索、机器学习、智能控制、模式识别和人工生命等领域取得了许多令人鼓舞的成就。以遗传算法为核心的进化算法已与模糊系统理论、人工神经网络等一起成为计算智能研究中的热点，受到了广泛的关注。1960年，美国密歇根(University of Michigan)大学的心理学教授、电子工程学与计算机科学教授John.H.Holland和他的同事与学生开始进行基因遗传算法和选择问题的数学方法分析和基本理论的研究，1962年提出了遗传算法，1967年，Holland的学生J.D.Bagle

15、y在博士论文中讨论了遗传算法在博弈中的应用，首次使用了遗传算法这一术语，并采用了复制、交叉、变异、倒位等遗传操作手段进行国际象棋的对弈研究，这些都与后来遗传算法中使用的算子和方法相类似，到了60年代末期，遗传算法已经形成了数学框架，能够实现简单形式上的计算。1975年，Holland教授的专著自然界和人工系统的适配出版，标志着遗传算法的创立。该书第一次系统地论述了遗传算法的基本理论与方法，提出了遗传算法的基本定理模式定理(schema theory)，从而奠定了遗传算法的理论基础。 模式定理揭示了群体中优良个体（较好模式）的样本数将以指数规律增长，确认了结构重组遗传操作对获得隐并行性的重要性，

16、从理论上保证了遗传算法是一个可以寻求最优可行解的优化过程。该书的出版标志着遗传算法得到了正式承认，Holland也被视为遗传算法的创始人。同年，在该校的Kenneth博士论文中，将GA应用于解决优化问题，1983年，他的一名学生Goldberg博士将这个理论成功的应用到煤气管道的模拟系统上。1985年，在美国举行了第一次遗传算法国际学术会议。1991年D.Whitey在他的论文中提出了基于领域交叉的交叉算子（Adjacency based crossover），这个算子是特别针对用序号表示基因的个体的交叉，并将其应用到了TSP问题中，通过实验对其进行了验证。D.H.Ackley等提出了随即迭代

17、遗传爬山法（Stochastic Iterated Genetic Hill-climbing，SIGH）采用了一种复杂的概率选举机制，此机制中由m个“投票者”来共同决定新个体的值（m表示群体的大小）。实验结果表明，SIGH与单点交叉、均匀交叉的神经遗传算法相比，所测试的六个函数中有四个表现出更好的性能，而且总体来讲，SIGH比现存的许多算法在求解速度方面更有竞争力。H.Bersini和G.Seront将遗传算法与单一方法（simplex method）结合起来，形成了一种叫单一操作的多亲交叉算子（simplex crossover），该算子在根据两个母体以及一个额外的个体产生新个体，事实上他

18、的交叉结果与对三个个体用选举交叉产生的结果一致。同时，文献还将三者交叉算子与点交叉、均匀交叉做了比较，结果表明，三者交叉算子比其余两个有更好的性能。国内也有不少的专家和学者对遗传算法的交叉算子进行改进。2002年，戴晓明等应用多种群遗传并行进化的思想，对不同种群基于不同的遗传策略，如变异概率，不同的变异算子等来搜索变量空间，并利用种群间迁移算子来进行遗传信息交流，以解决经典遗传算法的收敛到局部最优值问题2004年，赵宏立等针对简单遗传算法在较大规模组合优化问题上搜索效率不高的现象，提出了一种用基因块编码的并行遗传算法（Building-block Coded Parallel GA，BCPGA

19、）。该方法以粗粒度并行遗传算法为基本框架，在染色体群体中识别出可能的基因块，然后用基因块作为新的基因单位对染色体重新编码，产生长度较短的染色体，在用重新编码的染色体群体作为下一轮以相同方式演化的初始群体。2005年，江雷等针对并行遗传算法求解TSP问题,探讨了使用弹性策略来维持群体的多样性,使得算法跨过局部收敛的障碍,向全局最优解方向进化。遗传算法是多学科结合与渗透的产物,已经发展成一种自组织、自适应的综合技术,广泛应用在计算机科学、工程技术和社会科学等领域。进入了90年代后，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究都成了十分热门的课题。尤其是遗传算法的应用研究显得格外活跃，不但

20、它的应用领域扩大，而且利用遗传算法进行优化和规则学习的能力也显著提高，同时产业应用方面的研究也在摸索之中。此外，一些新的理论和方法在应用研究中亦得到了迅速的发展，这些无疑均给遗传算法增添了新的活力。遗传算法的应用研究已从初期的组合优化求解扩展到了许多更新、更工程化的应用方面。随着应用领域的扩展，遗传算法的研究出现了许多引人注目的新动向，其研究工作主要集中在以下几个方面：一是基础理论，包括进一步发展遗传算法的数学基础,从理论和试验研究它们的计算复杂性。在遗传算法中,群体规模和遗传算子的控制参数的选取非常困难,但它们又是必不可少的试验参数。在这方面,已有一些具有指导性的试验结果。遗传算法还有一个过

21、早收敛的问题,怎样阻止过早收敛也是人们正在研究的问题之一。二是基于遗传算法的机器学习，这一新的研究课题把遗传算法从历来离散的搜索空间的优化搜索算法扩展到具有独特的规则生成功能的崭新的机器学习算法。这一新的学习机制对于解决人工智能中知识获取和知识优化精炼的瓶颈难题带来了希望。其中，分类系统属于基于遗传算法的机器学习中的一类，包括一个简单的基于串规则的并行生成子系统、规则评价子系统和遗传算法子系统。分类系统被人们越来越多地应用在科学、工程和经济领域中，是目前遗传算法研究中一个十分活跃的领域。三是遗传算法正日益和神经网络、模糊推理以及混沌理论等其它智能计算方法相互渗透和结合，这对开拓21世纪中新的智

22、能计算技术将具有重要的意义。其中，遗传神经网络包括连接权、网络结构和学习规则的进化。遗传算法与神经网络相结合，正成功地用于从时间序列分析来进行财政预算。在这些系统中，训练信号是模糊的，数据是有噪声的，一般很难正确给出每个执行的定量评价。如果采用遗传算法来学习，就能克服这些困难，显著提高系统性能。Muhlenbein分析了多层感知机网络的局限性，并猜想下一代神经网络将是遗传神经网络。四是并行处理的遗传算法的研究十分活跃。这一研究不仅对遗传算法本身的发展，而且对于新一代智能计算机体系结构的研究都是十分重要的。由于遗传算法在操作上具有高度的并行性,许多研究人员都在探索在并行机和分布式系统上高效执行遗

23、传算法的策略。对分布并行遗传算法的研究表明,只要通过保持多个群体和恰当控制群体间的相互作用来模拟并行执行过程,即使不使用并行计算机,也能提高算法的执行效率。五是遗传算法和另一个称为人工生命的崭新研究领域正不断渗透。所谓人工生命即是用计算机模拟自然界丰富多彩的生命现象，其中生物的自适应、进化和免疫等现象是人工生命的重要研究对象，而遗传算法在这方面将会发挥一定的作用。六是遗传算法和进化规划（Evolution Programming，EP）以及进化策略（Evolution Strategy，ES）等进化计算理论日益结合。EP和ES几乎是和遗传算法同时独立发展起来的，同遗传算法一样，它们也是模拟自然

24、界生物进化机制的智能计算方法，即同遗传算法具有相同之处，也有各自的特点。目前，这三者之间的比较研究和彼此结合的探讨正形成热点。总之，遗传算法的研究热点将集中于以下方面：收敛性证明；新型高效的遗传算子设计；遗传算法与局部优化算法的结合；遗传算法在各领域的应用研究；软计算与计算智能中的遗传算法。遗传算法的基本思想源于达尔文所创立的自然选择学说。详见P164在自然界中，生物群体的繁殖过程隐含着自然优化的机制，复杂的生物群体在自身繁衍的过程中不断的进化。大多数生物体是通过自然选择和有性生殖这两种基本过程进行演化。自然选择决定了群体中哪些个体能够存活并繁殖，即表现为遗传算法中的选择操作;有性生殖保证后代

25、基因的混合和重组，即表现为遗传算法中的交叉操作。 达尔文的自然选择学说认为，生物要生存下去，就必须进行生存斗争。在生存斗争中具有有利生存的个体易存活，产生的后代也多;反之就少。达尔文把这种在生存斗争中适者生存，不适者淘汰的过程叫自然选择。遗传和变异是决定生物进化的内在因素，正是生物的遗传特性使生物界的物种能保持相对的稳定。而变异特性使生物个体产生新的性状，形成新的物种，推动了生物的进化和发展。虽然人们还未完全揭开遗传和进化的奥秘，既没有完全掌握其机制，也不完全清楚染色体编码和译码过程的细节，更不完全了解其控制方式，但遗传和进化的以下几个特点却是一个共识： 1.生物的所有遗传信息都在其染色体中，

26、染色体决定了生物的性状。 2.染色体是由基因及其有规律的排列构成的，遗传和进化过程都发生在染色体上。 3.生物的繁殖过程是由其基因的复制过程来完成的，即选择操作(选择操作算子、选择算子)。 4.通过相同位置上的染色体之间的交叉或染色体的变异会产生新的物种，使生物呈现新的性状，表现为新的个体。 5.对环境适应性好的基因或染色体比适应性差的基因或染色体有更多的机会遗传到下一代。遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染

27、色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择（selection）个体，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉（crossover）和变异（muta

28、tion），产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。7.2基本遗传算法基本遗传算法(simple genetic algorithm，SGA)也称做标准的遗传算法或简单遗传算法，其可以由编码方法、个体评价函数、初始种群、群体大小、选择算子、交叉算子、变异算子、算法终止条件等八个方面定义。具体来说，编码方法为固定长度的二进制编码，个体评价函数值要求为非负数，初始种群随机产生，仅使用选择、交叉和变异三种遗传算子，选择方法为赌轮选择，交叉方法为单店交叉，变异方法为基本位变异，

29、算法终止条件为指定的迭代次数或找到（已知的）最优解。另外，SGA还允许群体内有相同的个体存在。遗传算法的一般算法遗传算法是基于生物学的，理解或编程都不太难。下面是遗传算法的一般算法：创建一个随机的初始状态初始种群是从解中随机选择出来的，将这些解比喻为染色体或基因，该种群被称为第一代，这和符号人工智能系统的情况不一样，在那里问题的初始状态已经给定了。评估适应度对每一个解(染色体)指定一个适应度的值，根据问题求解的实际接近程度来指定(以便逼近求解问题的答案)。不要把这些“解”与问题的“答案”混为一谈，可以把它理解成为要得到答案，系统可能需要利用的那些特性。繁殖(包括子代突变)带有较高适应度值的那些

30、染色体更可能产生后代(后代产生后也将发生突变)。后代是父母的产物，他们由来自父母的基因结合而成，这个过程被称为“杂交”。下一代 如果新的一代包含一个解，能产生一个充分接近或等于期望答案的输出，那么问题就已经解决了。如果情况并非如此，新的一代将重复他们父母所进行的繁衍过程，一代一代演化下去，直到达到期望的解为止。并行计算 非常容易将遗传算法用到并行计算和群集环境中。一种方法是直接把每个节点当成一个并行的种群看待。然后有机体根据不同的繁殖方法从一个节点迁移到另一个节点。另一种方法是“农场主/劳工”体系结构，指定一个节点为“农场主”节点，负责选择有机体和分派适应度的值，另外的节点作为“劳工”节点，负

31、责重新组合、变异和适应度函数的评估。术语说明由于遗传算法是由进化论和遗传学机理而产生的搜索算法，所以在这个算法中会用到很多生物遗传学知识，下面是我们将会用来的一些术语说明：一、染色体(Chronmosome)染色体又可以叫做基因型个体(individuals),一定数量的个体组成了群体(population),群体中个体的数量叫做群体大小。二、基因(Gene)基因是串中的元素，基因用于表示个体的特征。例如有一个串S1011，则其中的1，0，1，1这4个元素分别称为基因。它们的值称为等位基因(Alletes)。三、基因地点(Locus)基因地点在算法中表示一个基因在串中的位置称为基因位置(Gen

32、e Position)，有时也简称基因位。基因位置由串的左向右计算，例如在串 S1101 中，0的基因位置是3。四、基因特征值(Gene Feature)在用串表示整数时，基因的特征值与二进制数的权一致；例如在串 S=1011 中，基因位置3中的1，它的基因特征值为2；基因位置1中的1，它的基因特征值为8。五、适应度(Fitness)各个个体对环境的适应程度叫做适应度(fitness)。为了体现染色体的适应能力，引入了对问题中的每一个染色体都能进行度量的函数，叫适应度函数. 这个函数是计算个体在群体中被使用的概率。例如：用遗传算法求f(x)=x*x函数的最大值，x0，31。详见P166Holl

33、and提出的遗传算法属于启发式随机搜索方法。Holland遗传算法通常也称为标准遗传算法或简单遗传算法（a simple genetic algorithm，SGA）。包括如下五个基本要素： 解空间的编码与解码。遗传算法对问题的求解，不是直接在解空间上搜索，而是在个体空间上进行搜索，编码方式的选择，将对算法的性能产生很大的影响。 初始种群的设定。遗传算法的搜索过程是初始种群的演化过程。 适应度函数的设计。适应度是对个体进化质量的一种评价度量，它通常仅依赖于解的行为及其与种群的关系，一般以目标函数或费用函数的形式来表示。个体的适应度是演化过程中进行选择的依据。 遗传过程设计。遗传过程的基本操作是

34、选择、杂交和变异。选择策略的确定是依据优胜劣汰的选择机制，使适应度较大的个体有较高的存活率。较大的选择压力使优良的个体具有较高的复制数目，从而使算法收敛速度较快，但容易出现过早收敛的现象。 控制参数设定。控制参数主要包括种群的规模、不同遗传的操作的概率、算法执行的最大代数以及其他一些辅助性的控制参数。由于遗传算法没有利用目标函数的梯度等信息，从而无法用传统的方法来判定算法的收敛与否来终止算法。常用的方法是通过控制参数来实现算法的终止。SGA的算法描述详见P168一般遗传算法的算法过程如下：1.进化代数计数器初始化:t02.随机产生初始群体P(t);3.评价群体P(t)的适应度;4.个体交叉运算

35、:5.个体变异运算6.评价群体P(t)的适应度;7.对群体P(t)进行选择运算:8.终止条件判断。不满足t+ 1t转到第4步，继续进化过程，满足输出当前最优个体，算法结束。补充资料：进化编程又称为进化规划（Evolutionary Planning），是由福格尔（Fogel）在1962年提出的一种模仿人类智能的方法。他们为有限状态机的演化而提出进化规划来预测问题。这些状态机的状态变换表是通过对应的离散有界集上进行的均匀随机变异来修改的。进化编程根据正确预测的符号数来度量适应值。通过变异，为父代群体中的每个机器状态产生一个子代。父代和子代中最好的部分被选择生存下来。进化编程的机理与表示进化编程的

36、过程，可理解为从所有可能的计算机程序形成的空间中，搜索具有高的适应度的计算机程序个体。在进化编程中，可能有几百或几千个计算机程序参与遗传进化。进化编程最初由一随机产生的计算机程序群体开始，这些计算机程序由适合于问题空间领域的函数所组成，这样的函数可以是标准的算术运算函数、标准的编程操作、逻辑函数或由领域指定的函数。群体中每个计算机程序个体是用适应度来评价的，该适应值与特定的问题领域有关。进化编程的步骤进化编程可繁殖出新的计算机程序以解决问题，它分为三个步骤： (1) 产生出初始群体，它由关于问题（计算机程序）的函数随机组合而成。 (2) 迭代完成下述子步骤，直至满足选种标准为止：(a) 执行群

37、体中的每个程序，根据它解决问题的能力，给它指定一个适应值。 (b) 应用变异等操作创造新的计算机程序群体。 (3) 在后代中适应值最高的计算机程序个体被指定为进化编程的结果。进化编程的基本过程如下图所示。进化计算的三种算法(遗传算法、进化策略和进化编程)都是模拟生物界自然进化过程而建立的鲁棒性计算机算法。在统一框架下对三种算法进行比较，可以发现它们有许多相似之处，同时也存在较大的差别。 1、进化策略和进化编程都把变异作为主要搜索算子，而在标准的遗传算法中，变异只处于次要位置。 2、交叉在遗传算法中起着重要作用，而在进化编程中却被完全省去，在进化策略中与自适应结合使用，起了很重要的作用。 3、标

38、准遗传算法和进化编程都强调随机选择机制的重要性，而从进化策略的角度看，选择（复制）是完全确定的。 4、进化策略和进化编程确定地把某些个体排除在被选择（复制）之外，而标准遗传算法一般都对每个个体指定一个非零的选择概率。 与传统优化方法相比，遗传算法的优点是：群体搜索；不需要目标函数的导数；概率转移准则。GA的基础理论主要以收敛性分析为主，即群体收敛到优化问题的全局最优解的概率。GA的核心任务是维持群体的可进化性。GA的缺陷主要在于不能保证收敛至全局最优解。另外，在传统的GA中，“爬坡”能力和对问题解空间的覆盖能力是影响提高算法品质的一对主要矛盾。GA的五大要素是：参数编码。评价编码的五个原则是：

39、 不冗余：即从编码到解的映射应该是一对一的； 合法性：即对编码的任意排列都对应着一个解； 完备性：即任意解都对应着一个编码； Lamarckian性质：即某个基因的等位基因的含义不依赖于其它基因； 因果性：即由于变异带来的基因型空间中的小扰动在表现型空间中也对应着小扰动。初始群体的设定。适应度函数的设计。适应度代表了染色体的强壮性。遗传操作的设计。这将涉及到选择、交叉、变异。其中，选择是GA的关键，它体现了自然界中适者生存的思想；交叉使GA具备原始性，一点交叉不利于长距模式的保留和重组，而且位串末尾的重要基因总是被交换，所以在实际中多用两点交叉；变异可以改变染色体的结构和物理性状。控制参数的设

40、定。有： 位串长度L：L越长，所表示的精度就越高，但所用的时间也就越长。一般取1030 群体规模n：规模越大，可以防止在成熟前就提高收敛，但运行比较慢。一般取20200 交叉概率Pc：过高则新的基因结构引入得快，但优良基因段又容易丢失，但过低搜索又阻滞。一般取0.61 变异概率Pm：过高小则基因位过早丢失后，不容易恢复，但过大又会变成随机搜索。一般取0.0050.01遗传算法的特点 遗传算法具有十分顽强的鲁棒性，这是因为比起普通的优化搜索方法，它参与了许多独特的方法和技术，归纳起来，主要有以下几个方面： (1)遗传算法的处理对象不是参数本身，而是对参数集进行了编码的个体。此编码操作使得遗传算法

41、可直接对结构对象进行操作，而不存在求导和函数连续性的限定。 (2)遗传算法是参与同时处理前提中多个个体的方法，即同时对搜索空间中的多个解进行评估。更形象地说，遗传算法是并行地爬多个峰。这一特点使遗传算法具有较好的全局搜索功能，减少了陷于局部最优解的风险。同时，这使得遗传算法本身也十分易于并行化和全局优化能力。 (3)在标准遗传算法中基本不用搜索空间的知识或其它辅助信息而仅用适应度函数值来评估个体，并在此基础上进行遗传操作，需要着重提出的是，遗传算法的适应度函数不仅不受连续可微的约束，而且其定义域可以任意设定。 (4)遗传算法不是采用确定性原则，而是采用概率的变迁规则来指导它的搜索方向，遗传算法采用概率仅仅是作为一种工具来引导其搜索过程朝着搜索空间的更优化的解区域移动。因此，它虽然看起来它是一种盲目搜索方法，但实际上有明确的搜索方向。因为GA在采用概率化的优化方法