4.3.1进化计算概述资料文件与下载

       进化计算（Evolutionary Computation,EC）是在达尔文（Darwin）的进化论和孟德尔（Mendel）的遗传变异理论的基础上产生的一种在基因和种群层次上模拟自然界生物进化过程与机制的问题求解技术。它主要包括

    遗传算法（Genetic Algorithm，GA）

    进化策略（Evolutionary Strategy,ES）

    进化规划（Evolutionary Programming,EP）

    遗传规划（Genetic Programming,GP）四大分支。

    其中，第一个分支是进化计算中最初形成的一种具有普遍影响的模拟进化优化算法。

    1.进化计算及其生物学基础

     进化计算是一种模拟自然界生物进化过程与机制进行问题求解的自组织、自适应的随机搜索技术。它以达尔文进化论的“物竟天择、适者生存”作为算法的进化规则，并结合孟德尔的遗传变异理论，将生物进化过程中的繁殖（Reproduction）、变异（Mutation）、竞争(Competition）和选择（Selection）引入到了算法中。

      自然界生物进化过程是进化计算的生物学基础，它主要包括遗传(Heredity)、变异(Mutation)和进化(Evolution)理论。

     ① 遗传理论

     遗传是指父代（或亲代）利用遗传基因将自身的基因信息传递给下一代（或子代），使子代能够继承其父代的特征或性状的这种生命现象。正是由于遗传的作用，自然界才能有稳定的物种。

    在自然界，构成生物基本结构与功能的单位是细胞（Cell）。

    细胞中含有一种包含着所有遗传信息的复杂而又微小的丝状化合物，人们称其为染色体（Chromosome）。

    在染色体中，遗传信息由基因（Gene）所组成，基因决定着生物的性状，是遗传的基本单位。

    染色体的形状是一种双螺旋结构，构成染色体的主要物质叫做脱氧核糖核酸(DNA)，每个基因都在DNA长链中占有一定的位置。

    一个细胞中的所有染色体所携带的遗传信息的全体称为一个基因组(Genome)。

    细胞在分裂过程中，其遗传物质DNA通过复制转移到新生细胞中，从而实现了生物的遗传功能。

    ② 变异理论

   变异是指子代和父代之间，以及子代的各个不同个体之间产生差异的现象。变异是生物进化过程中发生的一种随机现象，是一种不可逆过程，在生物多样性方面具有不可替代的作用。引起变异的主要原因有以下两种：

   杂交，是指有性生殖生物在繁殖下一代时两个同源染色体之间的交配重组，即两个染色体在某一相同处的DNA被切断后再进行交配重组，形成两个新的染色体。

    复制差错，是指在细胞复制过程中因DNA上某些基因结构的随机改变而产生出新的染色体。

    ③ 进化论

    进化是指在生物延续生存过程中，逐渐适应其生存环境，使得其品质不断得到改良的这种生命现象。遗传和变异是生物进化的两种基本现象，优胜劣汰、适者生存是生物进化的基本规律。

     达尔文的自然选择学说认为：在生物进化中，一种基因有可能发生变异而产生出另一种新的生物基因。这种新基因将依据其与生存环境的适应性而决定其增殖能力。

        一般情况下，适应性强的基因会不断增多，而适应性差的基因则会逐渐减少。通过这种自然选择，物种将逐渐向适应于生存环境的方向进化，甚至会演变成为另一个新的物种，而那些不适应于环境的物种将会逐渐被淘汰。

     2.进化计算的产生与发展

     进化计算自20世纪50年代以来，其发展过程大致可分为三个阶段。

     ①  萌芽阶段

     这一阶段是从20世纪50年代后期到70年代中期。20世纪50年代后期，一些生物学家在研究如何用计算机模拟生物遗传系统中，产生了遗传算法的基本思想，并于1962年由美国密执安（Michigan）大学霍兰德（Holland）提出。1965年德国数学家雷切伯格（Rechenberg）等人提出了一种只有单个个体参与进化，并且仅有变异这一种进化操作的进化策略。同年，美国学者弗格尔（Fogel）提出了一种具有多个个体和仅有变异一种进化操作的进化规划。1969年美国密执安（Michigan）大学的霍兰德（Holland）提出了系统本身和外部环境相互协调的遗传算法。至此，进化计算的三大分支基本形成。

      ② 成长阶段

      这一阶段是从20世纪70年代中期到80年代后期。1975年，霍兰德出版专著《自然和人工系统的适应性（Adaptation in Natural and Artificial System）》，全面介绍了遗传算法。同年，德国学者施韦费尔（Schwefel）在其博士论文中提出了一种由多个个体组成的群体参与进化的，并且包括了变异和重组这两种进化操作的进化策略。1989年，霍兰德的学生戈尔德伯格（Goldberg）博士出版专著《遗传算法----搜索、优化及机器学习（Genetic Algorithm----in Search Optimization and Machine Learning）》，使遗传算法得到了普及与推广。

     ③ 发展阶段

     这一阶段是从20世纪90年代至今。1989年，美国斯坦福（Stanford）大学的科扎（Koza）提出了遗传规划的新概念，并于1992年出版了专著《遗传规划----应用自然选择法则的计算机程序设计（Genetic Programming :on the Programming of Computer by Means of Natural Selection）》该书全面介绍了遗传规划的基本原理及应用实例，标志着遗传规划作为计算智能的一个分支已基本形成。

    3.进化计算的基本结构

     进化计算尽管有多个重要分支，并且不同分支的编码方案、选择策略和进化操作也有可能不同，但它们却有着共同的进化框架。

    若假设P为种群(Population，或称为群体)，t为进化代数， P(t)为第t代种群 , 则进化计算的基本结构可粗略描述如下：