身体的智能：6.3进化计算的起源

大约与Rechenberg在欧洲发明进化计算同时，其他科学家也开始探索在计算机上进行进化仿真的可能性。澳大利亚生物学家Alex Fraser就是其中之一，在其1957年发表的一篇论文所描述的计算机实验中，基因组以二进制数字串表示（Fraser

1957），就像在“Methinks”例子中，一个字符串（即一个句子）代表了一个可能的答案。差不多同一时间，德国生物数学家Hans Bremermann介绍了一种计算机算法，其虚拟的基因组能产生后代（Bremermann，1958；进化算法更完整的历史见Fogel，

1998）。

这些处理进化的工具，即符号或者数字串，代表了问题的各种解决方案，并且每个字符串基于它解决问题的满意程度被指定了一个适应度的方法，在美国计算机科学家John Holland（他在20世纪70年代使用计算机模拟自然进化）的努力下，这个方法发展成所谓的遗传算法。遗传算法这个术语现在经常被认为是所有进化算法的代名词。Holland还有他以前的学生及David Goldberg把注意的焦点放在抽象对象的进化上，如计算机程序、国际象棋或跳棋的游戏策略，还有一些一般性的最优化问题。这类问题的例子包括寻找网络中的最短路径、最大化可装入箱子的包裹数量等。

进化算法中一个有趣的特例是Stanford大学计算机科学家John Koza提出的。

他将遗传规划作为遗传算法的扩展。在他的方案里，基因组已不简单是针对具体问题的字符串，如“Methinks”例子中的字母，而是更精致的，像计算机程序一样能对一些更复杂的事物编码。扩大种群规模有助于提高找到给定问题更好解决方案的可能性，但是对大量候选方案的进化需要时间和计算能力。Koza投入了部分他以前经商（生产第一代刮奖彩票）赚得的资本，组成了他私用的威力巨大的计算机群，用于演示遗传规划的巨大威力。最近，Koza引入与人竞争的设计思路作为评价某一进化算法优劣的基准，如果它能得到和人类迄今所得到的解决方案同样好，甚至更好的方案，那么这一算法就是一个好算法。遗传规划已经被成功用于设计计算机程序和电路（见Koza有关遗传规划的系列丛书，Koza等，1992，1994，1999，2003），它被证明在一些人类所拥有较少经验的领域应用时特别有用，如为量子计算机开发的算法（Spector，2004）。进化而来的计算机程序是敏感的，只要有一个比特不对，程序就不会运行。因此，任意地变异字符串中的0和1会导致程序不起任何作用，适应度为零。零适应度对人工进化而言完全没有任何意义，因为如果种群中每个个体适应度都为零，则无法判断哪些个体要更好一些，应该繁衍后代，哪些个体比较差，应该被淘汰。所以，Koza在他的算法中修改了变异过程，所以变异过程总是

产生能运行的程序（这里细节问题并不重要）。

遗传规划的一个重要特点是基因组的大小不是固定的（即基因组的编码信息多少是可变的），如果我们想提高进化智能体的复杂度，这是一个很重要的特性。但是，如我们马上就要了解的，基因组的大小绝不是增加智能体复杂度的唯一途径。最重要的是基因组中的基因如何相互作用以促使智能体不断生长，而非整个基因组的大小或者基因数目。

进化策略、遗传算法以及遗传规划是进化计算的三个主要分支。