第9章 遗传算法

在对“机器能否复制自身”的问题给予肯定回答后，冯·诺依曼很自然地想让计算机（或计算机程序）复制自己和产生变异，并在某种环境中为生存竞争资源。这就会遇到前面提到的“生存本能”以及“进化和适应”的问题。可惜的是冯·诺依曼还没有研究进化问题就去世了。

其他人很快就开始继续他留下的工作。20世纪60年代初，一些研究团体开始在计算机中进行进化实验。这些研究现在统称为进化计算（evolutionary computation）。其中最为著名的是密歇根大学的霍兰德和他的同事、学生进行的遗传算法（genetic algorithms）研究。

霍兰德（图9.1）可以说是冯·诺依曼的学术徒孙。霍兰德的博士导师是哲学家、逻辑学家和计算机工程师巴克斯，巴克斯曾协助冯·诺依曼研制EDVAC，并且完成了冯·诺依曼没有完成的自复制自动机研究。在结束EDVAC的工作之后，巴克斯在密歇根大学获得了哲学教职，并成立了计算机逻辑小组，这是一个由对计算机基础以及广义信息处理感兴趣的教师和学生组成的松散团体。霍兰德到密歇根大学攻读博士学位，开始是学数学，后来转到新成立的“通信科学”系（后来改称“计算机与通信科学”），这可能是世界上第一个真正的计算机科学系。几年后，霍兰德成为系里第一个博士学位获得者，他也是世界上第一个计算机科学博士。很快他就留校成了计算机系的教授。

霍兰德在读费希尔（Ronald Fisher）的名著《自然选择的遗传理论》（The Genetical Theory of Natural Selection）时被达尔文的进化论深深吸引。同费希尔（和达尔文）一样，进化与农产养殖之间的相似也给霍兰德留下了深刻印象。但他是从计算机科学的角度来思考这种相似性：“这就是遗传算法的由来。我想到，是不是可以像繁育良种马和良种玉米那样繁殖程序。”

霍兰德的主要兴趣在于适应现象——生物如何进化以应对其他生物和环境变化，计算机系统是不是也可以用类似的规则产生适应性。他在1975年的著作《自然和人工系统的适应》（Adaptation in Natural and Artifcial Systems）中列出了一组适应性的普遍原则，并且提出了遗传算法的构想。

我第一次了解遗传算法是在密歇根大学研究生院，当时我选了霍兰德基于他的书开的一门课。我马上就被“进化的”计算机程序的思想吸引住了。（同赫胥黎一样，我的反应是：“我怎么没想到，真是太蠢了！”）

遗传算法菜谱

算法其实就是图灵说的明确程序，就好比做菜的菜谱：一步一步将输入变成输出。

对于遗传算法（GA），期望的输出就是特定问题的解。比如，你需要编写一个程序控制机器人清洁工在办公楼拾垃圾。你觉得编这个程序太费时间，就委托遗传算法替你将这个程序演化出来。因此，期望的GA输出就是能让机器人清洁工完成拾垃圾任务的控制程序。

GA的输入包括两部分：候选程序群体和适应性函数。适应性函数用来确定候选程序的适应度，度量程序完成指定任务的能力。

候选程序可以表示成位、数字或符号组成的字符串。后面我会给出一个机器人控制程序表示成数字字符串的例子。

在机器人清洁工的例子中，候选程序的适应度可以定义为机器人在给定时间内清扫的面积，这是由程序决定的，越大越好。

下面是GA菜谱。

将下面的步骤重复数代：

1．生成候选方案的初始群体。生成初始群体最简单的办法就是随机生成大量“个体”，在这里个体是程序（字符串）。

2．计算当前群体中各个个体的适应度。

3．选择一定数量适应度最高的个体作为下一代的父母。

4．将选出的父母进行配对。用父母进行重组产生出后代，伴有一定的随机突变概率，后代加入形成新一代群体。选出的父母不断产生后代，直到新的群体数量达到上限（即与初始群体数量一样）。新的群体成为当前群体。

5．转到第2步。

遗传算法的应用

前面描述GA时似乎很简单，但是遗传算法已被用于解决科学和工程领域的许多难题，甚至应用到艺术、建筑和音乐。

应用之广泛从下面这些问题可见一斑：通用电气将GA用于飞行器的部分自动化设计，洛斯阿拉莫斯国家实验室用GA分析卫星图像，约翰·迪尔（John Deere）公司将GA用于自动化生产线的调度，德州仪器（Texas Instruments）则用GA来设计计算机芯片。GA还在2003年的电影《指环王：王者归来》（The Lord of the Rings：The Return of the King）中被用于生成逼真的动画马匹，为电影《特洛依》（Troy）生成逼真的演员替身动画特效。许多制药公司用GA来辅助发现新药。GA也被一些金融组织用于各种场合：识别交易欺诈（伦敦股票交易所）、分析信用卡数据（第一资本金融公司，Capital One）、预测金融市场和优化证券投资组合（第一象限公司，First Quadrant）。20世纪90年代，互动式遗传算法创造的艺术作品在巴黎蓬皮杜中心（Georges Pompidou Center）等多个博物馆展出。这些只是遗传算法应用的一小部分例子。

进化的罗比，易拉罐清扫机器人

下面我们用一个更详细的简单例子来进一步阐释GA的主要思想。我有一个叫“罗比”的机器人，它的世界（用计算机模拟，但是很脏乱）是二维的，到处是丢弃的易拉罐。我将用遗传算法为罗比进化出一个“脑”（即控制策略）。

罗比的工作是清理它的世界中的空易拉罐。罗比的世界由10×10的100个格子组成（图9.2）。罗比在位置（0，0）。我们可以假设周围围绕着一堵墙。许多格子中散落着易拉罐（不过每个格子中的易拉罐不会多于一个）。

罗比不是很聪明，看得也不远，他只能看到东南西北相邻的4个格子以及本身所在格子中的情况。格子可以是空的（没有罐子），或者有一个罐子，或者是墙。例如，在图9.2中，罗比位于格子（0，0），看到当前格子是空的，北面和西面是墙，南面的格子是空的，东面的格子中有一个罐子。

每次清扫工作罗比可以执行200个动作。动作可以是以下7种：往北移动、往南移动、往东移动、往西移动、随机移动、不动、收集罐子。每个动作都会受到奖赏或惩罚。如果罗比所在的格子中有罐子并且收集起来了，就会得到10分的奖赏。如果进行收集罐子的动作而格子中又没有罐子，就会被罚1分。如果撞到了墙，会被罚5分，并弹回原来的格子。

显然，罗比尽可能地多收集罐子，别撞墙，没罐子的时候别去捡，得到的分数就最高。

这个问题很简单，人工为罗比设计一个好策略可能也不是很难。不过，有了遗传算法我们就可以什么也不用干，我们只需要等着计算机替我们进化出来。下面我们用遗传算法来为罗比进化出一个好策略。

第1步是搞清楚我们想要进化的到底是什么。也就是说，策略具体指的是什么？一般来说，策略指的是一组规则，规则给出了在各种情形下你应当采取的行动。对于罗比，它面对的“情形”就是它看到的：当前格子以及东南西北四个格子中的情况。对于“在各种情形下怎么做”的问题，罗比有7种可能选择：北移、南移、东移、西移、随机移动、不动、收集罐子。因此，罗比的策略可以写成它可能遇到的所有情形以及面对每种情形应当采取的行动。

有多少种可能的情形呢？罗比可以看到5个格子（当前格子、东、南、西、北），每个格子可以标为空、罐和墙。这样就有243种可能情形。其实还没有这么多，因为有许多不可能的情形，例如当前位置不可能是墙，也不可能四面都是墙，等等。不过，因为我们很懒，不想费劲找出所有不可能的情形，因此我们会列出所有243种情形，只要知道其中一些永远也不会遇到就行了。

表9-1是一个策略的例子——只是策略的局部，完整策略太长了，不方便列出来。

罗比在图9.2中的情形是：

要知道下一步怎么做，罗比只需要查看策略表，查到对应的行动是往西移动。因此它往西移动一格，结果一头撞到墙上。

我没说这是一个好策略。寻找好策略不关我的事；这事归遗传算法管。

我写了一个遗传算法程序来进化罗比的策略。算法中，群体中每个个体都是一个策略——与各种可能情形相对应的行动列表。也就是说，对于表9—1中的策略，GA用来演化的个体就是最右侧243个行动依次列出的列表：

字符串中第1个行动（这里是向北移动）对应第1种情形（“空空空空空”），第2个行动（这里是向东移动）对应第2种情形（“空空空空罐”），依次往后。这样就不用明确列出与动作对应的情形；GA记得各情形的排列顺序。例如，假设罗比观察到情形如下：

GA根据内建知识知道是情形2。通过查询策略表可以得知位置2上的行动是往东移动。罗比往东移动一格，然后又观察周围情形；GA再次查询表上的相应行动，反复进行。

我的GA是用C语言写的。这里我不写出具体程序，只解释其工作原理。

1．生成初始群体。初始群体有200个随机个体（策略）。

图9.3是一个随机群体示意图。每个个体策略有243个“基因”。每个基因是一个介于0和6之间的数字，代表一次动作（0=向北移动，1=向南移动，2=向东移动，3=向西移动，4=不动，5=捡拾罐子，&nbsp；6=随机移动）。在初始群体中，基因都随机设定。程序中用一个伪随机数发生器来进行各种随机选择。

重复后面的步骤1000次。

2．计算群体中每个个体的适应度。在我的程序中，是通过让罗比执行100次不同的清扫任务来确定策略的适应度。每次将罗比置于位置（0，0），随机撒一些易拉罐（每个格子至多1个易拉罐，格子有易拉罐的概率是50%）。然后让罗比根据策略在每次任务中执行200个动作。罗比的得分就是策略执行各任务的分数。策略的适应度是执行100次任务的平均得分，每次的罐子分布都不一样。

3．进化。让当前群体进化，产生出下一代群体。即重复以下步骤，直到新群体有200个个体。

（a）根据适应度随机选择出一对个体A和B作为父母。策略的适应度越高，被选中的概率则越大。

（b）父母交配产生两个子代个体。随机选择一个位置将两个数字串截断；将A的前段与B的后段合在一起形成一个子代个体，将A的后段与B的前段个体合在一起形成另一个子代个体。

（c）让子代个体以很小的概率产生变异。以小概率选出1个或几个数，用0到6的随机数替换。

（d）将产生的两个子代个体放入新群体中。

4．新群体产生200个个体后，回到第2步，对新一代群体进行处理。

神奇的是，从200个随机的策略出发，遗传算法就能产生出让罗比顺利执行任务的策略。

种群规模（200）、迭代次数（1000）、罗比在一次任务中的动作数量（200）以及计算适应度的任务数量（200）都是我设定的，有些随意。用其他参数也能产生出好的策略。

你现在肯定很想知道遗传算法得出的结果。不过，我得向你坦白，在运行程序之前我还是克服了懒惰，自己设计了一个“聪明的”策略，这样我就能知道GA和我比起来谁干得更好。我为罗比设计的策略是：“如果当前位置有罐子，就捡起来。否则，如果旁边格子有罐子，就移过去。（如果有几个罐子，预先设定罗比向哪个移动。）否则，随机选择一个方向移动。”

这个策略其实不是很聪明，罗比有可能会围着空格子绕圈子，总也找不到易拉罐。

我用10000个清扫任务测试了这个策略，结果（每个任务的）平均分约为346。每个任务最初有大约50%的格子有罐子，也就是50个易拉罐，因此最高可能的分数约为500，这样看我的策略还不是很接近最优。

GA能有这么好的成绩吗？会不会更好？运行一下就知道了。取最后一代中适应度最高的个体，也用10000个不同的任务进行测试。结果平均分约为483——几乎是最优了！

GA演化的策略是如何解决这个问题的

问题是这个策略是如何做到的？它为什么能比我的策略做得更好？GA又是如何将它演化出来的？

将我的策略记为M, GA生成的策略记为G。下面是这两个策略的基因组。

M：6563536562523532526563536561513531512523532521513 53151656353656252353252656353656050353050252353252050 3530501513531512523532521513531510503530502523532520503 5305065635356252353252656353656151353151252353252151353 151656353656252353252656353454

G：254355153256235251056355461151336154151034156110550 1500520302562561322523503251120523330540552312550513361 541506652641502665060122644536056315202564310543546324 0435033415325025325135235204515013015621343625235322313 5051260513356201524514343432

仅仅从策略的基因组看不出其中的运作。我们可以知道其中一些基因的意义，例如当前位置有罐子的情形，对第2种情形（“空空空空罐”），两个策略的动作都是5（清扫罐子）。M对这种情形总是动作5，但G并不总是这样。例如下面这种情形：

动作就是3（往西移动），罗比在这种情形下不会捡罐子。这不太好，不过G总体上还是比M好。

关键之处不在于单个的基因，而在于各个基因之间的相互作用，就像真正的基因一样。而且同真正的基因一样，很难确定各种相互作用是如何影响整体上的行为或适应度。

相较于观察一个策略的基因，观察其具体的行为——也就是它们的表型——会更有意义。我编了一个程序来演示罗比在采用某个给定策略时的行动，然后对罗比在采用策略M和策略G时的行为进行观察。我发现这两个策略在许多情形中的行为类似，但策略G有两个小技巧，让它比策略M表现得更好。

首先来看看当前位置和四周都没有罐子的情形。如果罗比采用策略M，它就会随机选择一个方向移动。但如果它采用的是策略G，它就会往东移动，直到遇到墙为止。然后它会往北移动，就这样逆时针围着格子边缘移动，直到发现罐子。图9.4可以看到罗比的轨迹（虚线）。

这种围着绕圈的策略不仅让罗比不会撞墙（如果用策略M，随机移动时有可能会撞墙），而且搜索罐子的效率也比随机移动要高。

另外，遗传算法通过策略G还发现了一个巧妙的技巧，它在一些特定的情形中不会去捡当前格子中的罐子。

例如图9.5（a）给出了一种情形。在这种情形下，如果罗比采用策略M，它会捡起当前格子里的罐子，向西移动，然后捡起新的格子里的罐子[图9.5（b）—图9.5（d）]。由于罗比只能看见相邻格子的情形，因此当前它看不到余下的一堆罐子。它只能随机移动，直到碰巧遇到余下的罐子。

再看看策略G在同样情形中的表现（图9.6）。罗比没有去捡当前位置上的罐子，而且是直接向西移动[图9.6（b）]。然后它捡起了一堆罐子中最西边的罐子[图9.6（c）]。前面没有捡的罐子现在成了路标，罗比根据这个可以“记住”返回去有罐子。接下来它就会把这一堆罐子都捡起来[图9.6（d）—图9.6（k）]。

我知道我的策略不完美，但也没想到会有这种办法。进化可能聪明得多，GA经常会让我们感到意外。

遗传学家经常用“敲除突变（knockout mutations）”的办法来验证关于基因功能的理论，其实就是用遗传工程的方法阻止所研究的基因转录，再看对机体会有何影响。这里我也可以用这种方法。我将策略G中与这个技巧对应的基因敲掉：将所有与“当前格子中有罐子的”情形相对应的基因都换成“清扫罐子”。这会使得策略G的平均分从最初的483降到443，因此证明了我在前面的猜测，策略G之所以成功，部分就是因为这个技巧。

GA是如何演化出好的技巧的

下一个问题是，GA是如何从随机的群体演化出像策略G这样好的策略的呢？

要回答这个问题，我们可以看一看策略是如何一代一代改进的。图9.7中画出了每一代中最佳策略的适应度。你可以看到最好的适应度最开始是小于0的，前300代提高得很快，此后的提高要慢一些。

第1代有200个随机生成的策略，可以想象它们都很糟糕。最好的策略适应度才-81，最糟糕的到了-825。（可能这么低吗？）

我用几个任务测试了一下罗比采用这一代中最糟糕的策略时的行为。在一些环境设定中，罗比移动了几步就卡住了，之后在整个任务过程中都停止不动。在一些情况下，则不停地撞墙，直到任务结束。有时候则一直不断地去捡罐子，虽然当前位置上没有罐子。显然这些策略在进化过程中很快就会被淘汰掉。

我也测试了一下这一代中最好的策略，还是很糟糕，比最差的好不了多少。不过比起来它还是有两个优点：不那么容易一直撞墙了，而且偶尔碰到罐子的时候还能把罐子捡起来！作为这一代中最好的策略，它有很大的机会被选中用来繁殖！一旦被选中，它的子代就会继承这些优点（同时也会继承许多缺点）。

到第10代，群体中最佳策略的适应度已经变成正数了。这个策略经常会停滞不动，有时候还会在两个格子之间不停地来回移动。但基本不怎么撞墙，同第1代的前辈一样，偶尔也会捡罐子。

GA就这样不断改进最佳适应度。到200代时，最好的策略已经具有向罐子移动并捡起罐子这个最重要的能力——至少大部分时候是这样。不过，如果周围没有罐子，它也会浪费很多时间用来随机游走，这一点同策略M相似。到250代时，做得已经和策略M一样好了；等到了400代，适应度超过了400分，这时的策略如果少做一些随机移动，就能和策略G一样好。到800代时，GA发现了将罐子留作相邻罐子的路标的技巧，到900代时，沿着围墙转的技巧就基本完善了，到1000代时会进一步做些修正。

虽然罗比机器人的例子相当简单，但它与实际应用的GA区别已不是很大。同罗比的例子一样，在实际应用中，GA经常能演化出有用的答案，但是很难看出为什么会有用。这是因为GA找到的好答案与人类想出的相当不同。美国国家航空航天局（NASA）的遗传算法专家罗恩（Jason Lohn）曾这样说：“进化算法是探索设计死角的伟大工具。你向具有25年工业经验的专家展示（你的设计），他们会说‘哦，这个真的能有效？’……我们经常发现进化出来的设计完全无法理解。”

罗恩的设计也许是无法理解，但的确能有效。2004年，罗恩和他的同事因为用GA设计出了新的NASA航天器天线被授予“人类竞争”奖（Human Competitive Award）。这表明GA的设计改进了人类工程师的设计。