[科普中国]-进化计算

起源

经过几亿年的发展，在我们的地球上，简单的细胞逐步演化形成了缤纷多彩的大自然。生物的进化过程，在很长一段时间里，并不为我们人类所知。从拉马克的进化学说到达尔文的进化论，再到孟德尔的遗传学，人类对生命进化现象的研究进入了史无前例的伟大时期。其中，达尔文的进化论是一部对人类影响深远伟大学说，根据此学说，地球生物在繁殖过程中可能会产生变异，从而形成新物种。由于资源有限，不同的物种之间产生竞争，适者生存，不适者淘汰。自然界中的生物，正是根据这种优胜劣汰的原则，不断地进化。

运用达尔文理论解决问题的思想起源于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发表的一系列关于模拟人工选择的论文大大发展了这一工作。Ingo Rechenberg在上世纪 60 年代和 70 年代初用进化策略来解决复杂的工程问题的工作使人工进化成为广泛认可的优化方法。特别是John Holland的作品让遗传算法变得流行起来。随着学术研究兴趣的增长，计算机能力的急剧增加使包括自动演化的计算机程序等实际的应用程序成为现实。比起人类设计的软件，进化算法可以更有效地解决多维的问题，优化系统的设计。

分支进化算法正是借用以上生物进化的规律，通过繁殖、竞争、再繁殖、再竞争，实现优胜劣汰，一步步逼近复杂工程技术问题的最优解。进化计算的主要分支有：遗传算法GA，遗传编程GP、进化策略ES、进化编程EP。

原理在进化算法中，从一组随机生成的出事个体出发，仿效生物的遗传方式，主要采用复制、交换、突变这三种一串操作，衍生出下一代的个体。再根据适应度的大小进行个体的优胜劣汰，提高新一代群体的质量，在经过反复多次迭代，逐步逼近最优解。从数学角度讲，进化算法实质上是一种搜索寻优的方法。

进化算法是一种基于自然选择和遗传变异等生物进化机制的全局性概率搜索算法，运用了迭代的方法。

它从选定的初始解出发，通过不断迭代逐步改进当前解，直至最后搜索到最适合问题的解。在进化计算中，用迭代计算过程模拟生物体的进化机制，从一组解（群体）出发，采用类似于自然选择和有性繁殖的方式，在继承原有优良基因的基础上，生成具有更好性能指标的下一代解的群体：

种群（population）：进化计算在求解问题时是从多个解开始的

代数（generation）：种群进化的代数，即迭代的次数

群体的规模（popsize）：一般地，元素的个数在整个进化过程中是不变的

当前解：新解的父解（parent，或称为父亲、父体等）

后代解（offspring，或称为儿子、后代等）：产生的新解

编码：计划计算常常还需要对问题的解进行编码，即通过变换将映射到另一空间（称为基因空间）。通常采用字符串（如位串或向量等）的形式

一个长度为的二进制串称为一个染色体（个体）。染色体的每一位称为基因（gene），基因的取值称为等位基因（allele），基因所在染色体中的位置称为基因位（1ocus）。

进化计算的搜索策略不是盲目搜索，也不是穷举搜索，而是以目标函数为指导的搜索方式。进化算法一般采用天然的并行结构，且借助交叉和变异产生新个体，不断产生新个体，扩大搜索范围，因此它不易于陷入局部最优点，并能以较大的概率找到全局最优点2。

应用进化计算有着极为广泛的应用，在模式识别、图象处理、人工智能、经济管理、机械工程、电气工程、通讯、生物学等众多领域都获得了较为成功的应用。如利用进化算法研究小生境理论和生物物种的形成，通信网络的优化设计，超大规模集成电路的布线，飞机外形的设计，人类行为规范进化过程的模拟。

现在，进化计算的发展非常迅速，得到了学术界的广泛认可。

如何对进化计算进行优化以及运用进化计算解决实际问题是当前研究的热点。并且一些新的算法也被提出，如约束优化进化算法，群记忆性算法（PMA），思维进化计算，交互式进化计算。