进化计算综述.docx

进化计算综述1. 什么是进化计算 在计算机科学领域，进化计算（Evolutionary Computation）是人工智能（Artificial Intelligence），进一步说是智能计算（Computational Intelligence）中涉及到组合优化问题的一个子域。其算法是受生物进化过程中“优胜劣汰”的自然选择机制和遗传信息的传递规律的影响，通过程序迭代模拟这一过程，把要解决的问题看作环境，在一些可能的解组成的种群中，通过自然演化寻求最优解。2. 进化计算的起源 运用达尔文理论解决问题的思想起源于20世纪50年代。20世纪60年代，这一想法在三个地方分别被发展起来。美国的Lawrence J. Fogel提出了进化编程（Evolutionary programming），而来自美国Michigan 大学的John Henry Holland则借鉴了达尔文的生物进化论和孟德尔的遗传定律的基本思想，并将其进行提取、简化与抽象提出了遗传算法（Genetic algorithms）。在德国，Ingo Rechenberg 和Hans-Paul Schwefel提出了进化策略（Evolution strategies）。 这些理论大约独自发展了15年。在80年代之前，并没有引起人们太大的关注，因为它本身还不够成熟，而且受到了当时计算机容量小、运算速度慢的限制，并没有发展出实际的应用成果。到了20世纪90年代初，遗传编程（Genetic programming）这一分支也被提出，进化计算作为一个学科开始正式出现。四个分支交流频繁，取长补短，并融合出了新的进化算法，促进了进化计算的巨大发展。 Nils Aall Barricelli在20世纪六十年代开始进行用进化算法和人工生命模拟进化的工作。Alex Fraser发表的一系列关于模拟人工选择的论文大大发展了这一工作。1 Ingo Rechenberg在上世纪 60 年代和 70 年代初用进化策略来解决复杂的工程问题的工作使人工进化成为广泛认可的优化方法。2特别是John Holland的作品让遗传算法变得流行起来。3 随着学术研究兴趣的增长，计算机能力的急剧增加使包括自动演化的计算机程序等实际的应用程序成为现实。4比起人类设计的软件，进化算法可以更有效地解决多维的问题，优化系统的设计。5 3. 进化计算的分支 进化计算的主要分支有：遗传算法GA ，遗传编程GP、进化策略ES、进化编程EP。下面将对这4个分支依次做简要的介绍。1 遗传算法（Genetic Algorithms）：遗传算法是一类通过模拟生物界自然选择和自然遗传机制的随机化搜索算法，由美国John Henry Holand教授于1975年在他的专著Adaptation in Natural and Artificial Systems中首次提出。6它是利用某种编码技术作用于称为染色体的二进制数串，其基本思想是模拟由这些串组成的种群的进化过程，通过有组织地然而是随机地信息交换来重新组合那些适应性好的串。遗传算法对求解问题的本身一无所知，它所需要的仅是对算法所产生的每个染色体进行评价，并根据适应性来选择染色体，使适应性好的染色体比适应性差的染色体有更多的繁殖机会。2 遗传编程（Genetic Programming）：遗传编程的思想是Stanford大学的John R.Koza在1992年出版专著Genetic Programming中提出的。7 由自计算机出现以来，计算机科学的一个重要目标即是让计算机自动进行程序设计，即只要明确地告诉计算机要解决的问题，而不需要告诉它如何去做，遗传编程便是该领域的一种尝试。8 它采用遗传算法的基本思想，但使用一种更为灵活的表示方式分层结构来表示解空间。这些分层结构的叶节点是问题的原始变量，中间节点则是组合这些原始变量的函数，这样的每一个分层结构对应问题的一个解，也可以理解为求解该问题的一个计算机程序。遗传编程即是使用一些遗传操作动态的改变这些结构以获得解决该问题的一个计算机程序。3 进化策略（Evolution Strategies）：1964年，由德国柏林工业大学的Ingo Rechenberg等人提出。在求解流体动力学柔性弯曲管的形状优化问题时，用传统的方法很难优化设计中描述物体形状的参数，而利用生物变异的思想来随机地改变参数值获得了较好的结果。随后，他们便对这一方法进行了深入的研究，形成了进化计算的另一个分支进化策略。9进化策略与遗传算法的不同之处在于：进化策略直接在解空间上进行操作，强调进化过程中从父体到后代行为的自适应性和多样性，强调进化过程中搜索步长的自适应性调节，主要用于求解数值优化问题；而遗传算法是将原问题的解空间映射到位串空间之中，然后再施行遗传操作，它强调个体基因结构的变化对其适应度的影响。4 进化编程（Evolutionary Programming）：由美国Lawrence J. Fogel等人在20世纪60年代提出。他们在研究人工智能时发现，智能行为要具有能预测其所处环境的状态，并且具有按照给定的目标作出适当的响应的能力。在研究中，他们将模拟环境描述成是由有限字符集中符号组成的序列。4. 进化计算的原理 进化算法是一种基于自然选择和遗传变异等生物进化机制的全局性概率搜索算法，运用了迭代的方法。它从选定的初始解出发，通过不断迭代逐步改进当前解，直至最后搜索到最适合问题的解。在进化计算中，用迭代计算过程模拟生物体的进化机制，从一组解（群体）出发，采用类似于自然选择和有性繁殖的方式，在继承原有优良基因的基础上，生成具有更好性能指标的下一代解的群体种群（population）：进化计算在求解问题时是从多个解开始的代数（generation）：种群进化的代数，即迭代的次数群体的规模（popsize）：一般地，元素的个数在整个进化过程中是不变的当前解：新解的父解（parent，或称为父亲、父体等）后代解（offspring，或称为儿子、后代等）：产生的新解编码：计划计算常常还需要对问题的解进行编码，即通过变换将映射到另一空间（称为基因空间）。通常采用字符串（如位串或向量等）的形式一个长度为的二进制串称为一个染色体（个体）。染色体的每一位称为基因（gene），基因的取值称为等位基因（allele），基因所在染色体中的位置称为基因位（1ocus）。进化计算的基本结构：确定编码的形式并生成搜索空间，选择遗传算子的类型和所有的参数值；设置代数；随机初始化种群 ；计算每个个体的适应值 ；while（不满足终止准则）do t=t+1；由P(t-1)进行重组操作生成群体P(t)； 对P(t)进行变异操作生成群体P(t)，计算其中每个个体的适应值 对 进行选择操作生成群体， 其中Q代表P(t-1)的某个子集或空集； 5. 进化计算的应用 进化计算有着极为广泛的应用，在模式识别、图象处理、人工智能、经济管理、机械工程、电气工程、通讯、生物学等众多领域都获得了较为成功的应用。如利用进化算法研究小生境理论和生物物种的形成，通信网络的优化设计，超大规模集成电路的布线，飞机外形的设计，人类行为规范进化过程的模拟。6. 进化计算的最新进展 现在，进化计算的发展非常迅速，得到了学术界的广泛认可。如何对进化计算进行优化以及运用进化计算解决实际问题是当前研究的热点。并且一些新的算法也被提出，如约束优化进化算法10，群记忆性算法（PMA）11，思维进化计算12，交互式进化计算13.7. 进化计算的重要人物、会议、刊物重要人物： John Henry Holland、Lawrence J. Fogel、Ingo Rechenberg 、Hans-Paul Schwefel、Kalyanmoy Deb、David E. Goldberg、John Koza、Peter Nordin、Peter J. Fleming、Carlos M. Fonseca、Lee Graham、R. V. Rao会议：遗传与进化计算会议（GEEC，Genetic and Evolutionary Computation Conference），智能计算与进化计算国际学术会议（ICEC，International Conference of Intelligence Computation and Evolutionary Computation），国际遗传算法会议（ICGA，International Conference on Genetic Algorithms）刊物： IEEE Transactions on Evolutionary Computation、 Evolutionary Computation电子信息库：ENCORE（Evolutionary Computation Repository Network）参考文献：1 Fraser AS (1958). Monte Carlo analyses of genetic models. Nature 181 (4603): 2089. DOI:10.1038/181208a0. PMID 135041382 Rechenberg, Ingo (1973) (in German). Evolutionsstrategie Optimierung technischer Systeme nach Prinzipien der biologischen Evolution (PhD thesis). Fromman-Holzboog.3 Holland, John H. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press. ISBN 0-262-58111-6.4 Koza, John R. (1992). Genetic Programming. MIT Press. ISBN 0-262-11170-5.5 Jamshidi M (2003). Tools for intelligent control: fuzzy controllers, neural networks and genetic algorithms. Philosophical transactions. Series A, Mathematical, physical, and engineering sciences 361 (1809): 1781808. DOI:10.1098/rsta.2003.1225. PMID 129526856 Holland, John H. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press. ISBN 0-262-58111-6.7 Koza, John R. (1992). Genetic Programming. MIT Press. ISBN 0-262-11170-5.8 金金宝，吴萍(2009)：遗传编程在符号回归中的应用，计算机数学与工程，Vol.37，No.5，13页 9 冯萍，谷文祥，曲爽(2005)：浅析遗传算法与进化策略，长春大学学报，Vol.