人工智能时代：破解人机共存密码（套装共10册）

既然我们的目标是尽可能设计出最好的垃圾邮件过滤器，和老老实实模拟真正的自然选择相反，我们可以大大方方地作弊，方法就是通过改变算法来适应我们的需求。遗传算法能够频繁作弊的方法，就是允许有永不灭亡的东西（现实生活中却不存在，太糟了）。在那种方法中，适应力很强的个体不仅会在它那一代中为了繁殖而竞争，还会跟它的“儿子”“孙子”“重孙”等竞争，只要在群体中还保留有其中一个适应力最强的个体。相反，在现实世界中，适应能力强的个体能做到最好的，也就是将其一半的基因传给许多孩子，而每个孩子的适应能力可能不会那么高，因为遗传了父母另外一方的基因。不朽性避免了这样的倒退，而且如果幸运，能让算法更快地达到理想的适应力。当然，既然历史上最适合生存的人类都是通过其后代的数量来衡量的，比如成吉思汗（当今200个人中就有一个人是他的后代）。现实世界中没有永生这一说，也许也没那么糟糕。

如果我们想对一整套而不只是一个垃圾邮件过滤规则进行进化，我们可以用含有n×20 000个比特的字符串（每个规则有20 000个，和之前一样，假设数据里有1万个不同的词）来代表有n个规则的规则集。有些词会用“00”来表示，那些包含这些词的规则实际上会从规则集中消失，因为这些规则不会和任何邮件相匹配，这和我们之前看到的一样。如果一封邮件和规则集中的任何规则都匹配，那么它就被分类成垃圾邮件，否则就是合法邮件。我们还可以把适应度当作正确分类邮件的百分数，但为了防止过拟合，我们可能想从这个百分数中扣除与规则集中和活性条件相称的处罚比例。

我们甚至可以做得更好，方法就是允许过渡概念的规则进行进化，然后将这些规则在运行时串起来。例如，我们可以对这样的规则进行进化：如果邮件包含“贷款”一词，那么这是一封诈骗邮件；如果这封邮件是诈骗邮件，那么它就是垃圾邮件。既然一个规则的结果不再总是“垃圾邮件”，这需要引入规则字符串中的额外比特的信息来代表它们的结果。当然，计算机不会按照字面引用“诈骗”这个词，它只会找出任意的比特串来表示这个概念，但这对实现我们的目标已经起到很好的作用。霍兰德称类似这样的规则集为“分类器系统”，是他建立的机器学习部落中的一匹“驮马”：演化新论。和多层感知器一样，分类器系统会面临赞誉分布问题——过渡概念的规则适应度是什么？另外，霍兰德设计出所谓的“桶队算法”（bucketbrigade algorithm）来解决这个问题。即便如此，分类系统和分层感知器相比，其应用范围要窄得多。

和费雪梳理的简单模型相比，遗传算法有了很大的进步。达尔文悲叹自己的数学能力不行，但如果他晚生一个世纪，他可能又会希望自己有很强的编程能力。的确，通过一组方程来充分体现自然选择很困难，但将自然选择表达为一种算法又是另外一回事，而且这样还能阐明许多其他棘手的问题。为什么一些物种会突然出现在化石记录中？能够证明这些物种是渐渐由早期物种进化而来的证据在哪里？1972年，尼尔斯·埃尔德雷奇和史蒂芬·杰伊·古尔德提出进化过程由一系列“间断平衡”组成，长期的停滞与短暂的快速变化相互交替，就像寒武纪爆发那样。这个问题引起激烈的讨论，“间断平衡”理论的批评家将其命名为“跳跃式进化”，而埃尔德雷奇和古尔德则反驳称，渐进主义就是“匍匐式进化”。遗传算法的经验会对支持“跳跃式进化”的一方有利。如果你运行10万代遗传算法，然后每隔

1000代观察群体的数量，那么适应度与时间的曲线图可能看起来会像高低错落的楼梯，图形突然上升，然后是随着时间慢慢变长的平台期。要弄明白为什么也不难。一旦算法达到适应度的局部最大值（适应度中的峰值），算法会在这一点停很长时间，直到某次幸运的变异或者交叉，让处于坡上的个体等到更高的峰顶，在这一点上该个体会进行大量繁殖，然后和过往的每一代来爬上这个坡。当前的峰值越高，该过程发生前的那段时间就越长。当然，自然选择比这还要复杂：一个原因就是，环境可能会变化，要么是自然上的改变，要么是因为其他有机体自身进化了。另外，处于峰值的有机体可能会突然发现，对于再次进化，它面临巨大的压力。因此，虽然有用，当前的遗传算法还远远不是故事的结局。

探索_：利用困境

我们应注意遗传算法和多层感知器的差异程度。反向传播会在任何给定时间坚持单一假设，而且这个假设会渐渐改变，直到其适应某个局部最优值。遗传算法会在每一步中考虑整个群体的假设，而由于交叉行为，这些假设可以从这一代跨到下一代。将初始权值设为小的随机值后，反向传播才会确定继续进行下去。相反，遗传算法则充满随机选择：该使哪些假设成立并进行交叉（适应度更高的假设更有可能成为备选对象），该在哪里对两个字符串进行交叉，该使哪些比特的信息发生突变。反向传播为了预先设定的网络结构掌握权值；密集度更大的网络更为灵活，但掌握起来也更困难。除了通用式以外，遗传算法不会对它们即将学习的结构进行预先假设。

因为这个原因，和反向传播相比，遗传算法陷入局部最优值困境的可能性较小，而且原则上也更有可能找到真正新颖的东西，但遗传算法分析起来也要难得多。我们怎么知道，遗传算法会得出有意义的结果，而不是像众所周知的酒鬼那样到处晃悠？问题的关键在于要从构建模块的角度去考虑。字符串比特的每个子集都可能会对有用的构造块进行编码，当我们将两个字符串进行交叉时，这些构造块会聚集到一起，形成一大块构造块，反过来这个大构造块又会变成“磨坊中的谷物”。霍兰德喜欢用警方提供的画像来解释构造块的力量。在计算机还没出现的年代，警局的拼图师能够很快将嫌疑人的画像拼在一起，方法就是在采访中让目击者从画有典型嘴型的一组纸带中挑选嘴巴，然后用同样的方法选出眼睛、鼻子、下巴等。只有10个构造块，每个构造块有10个选择，这个系统会虑及100亿张脸，比地球上的总人口还要多。

在机器学习中，和计算机科学的其他领域一样，没有什么比得到这种对你有利而非有害的组合爆炸更好的东西了。遗传算法的灵活之处就在于，每个字符串都暗含指数数量的构造块，被称为“基模”，因此该研究比它看起来的还要高效得多。这是因为字符串比特的每个子集都是一个基模，代表可能合适的性能组合，而一个字符串有指数数量的子集。我们可以用这样的方法来代表基模，也就是用“\*”来代替字符串中不属于该字符串的比特。如110这个字符串中包含以下基模：\*\*\*、\*\*0、1\*\*、\*10、11\*、1\*0，以及110。每选一个不同的比特，我们就得到一个不同的基模，因为每个比特我们有两个选择（包含或不包含），那么我们就有2ⁿ个基模。相反，在群体中，一个特定的基模可能由许多不同的字符串来表示，而且每当这时，这些基模都会受到隐式评估。假设在下一代中仍成立的概率与其适应度成正比，那会怎样？霍兰德表明，在这种情况下，和平均值相比，在某代中表示基模的字符串适应度越高——我们能期望的——在下一代中看到这些表示字符串的数量也越多。那么，虽然遗传算法暗地里对字符进行操纵，它也会找到基模更大的可能性。随着时间的流逝，适应度更高的基模会主导群体，所以不像醉汉那样，遗传算法能找到回家的路。

机器学习中最重要的问题之一（也是关于生命最重要的问题之一），就是探索—利用困境。如果已经找到能发挥作用的东西，你还会继续找吗？还是做新的尝试会更好，知道这样可能会浪费时间，但也许会找到更好的办法？你想做牛仔还是农民？想自己开一家公司，还是管理一家已经成立的公司？想用情专一，还是三心二意？中年危机意味着把多年的时间花费在利用某种东西之后，会极度渴望探索新事物。一时冲动之下，你飞到拉斯韦加斯，准备赌光你毕生的积蓄，变成百万富翁。你进入赌场，然后面对一排老虎机。你要在能给你平均回报最多的那台机器上玩，但你不知道是哪台。那么你就得每台都试，次数够了才能弄明白。但如果花太多时间来做这个，你就把钱浪费在会输的那台机器上。相反，如果操之过急，选了一台前几轮碰巧让你手气不错的机器，但实际上并不是让你获得回报最多的一台，那么今晚剩下的时间你就会把钱浪费在这台机器上。这就是探索—利用困境。每次你玩的时候，要么你就选择重复目前为止发现的最好的一把，这样就能给你最好的回报，要么就试试其他几把，这样能够让你知道怎样才能赢得更多。利用两台老虎机，霍兰德表明最优策略就是每次抛一个偏币，在这个策略中，随着你进行这些步骤，和原来的硬币相比，这时的硬币会呈指数偏倚（如果这种方法对你不起作用，别指控我。记住最后赢的总是赌场）。一台老虎机看起来越好，你就越应该玩它，但也别完全放弃另外一台，毕竟另外一台也有可能会让你赢得更多。

遗传算法就像一群赌徒中的元凶，同时在市里的每个赌场玩老虎机。如果两个基模包含相同的比特量而且至少有一个比特的值不同，那么这两个基模就会互相竞争，例如\*10和\*11，而n个互相竞争的基模就像n台老虎机一样。每个互相竞争的基模集都是一个“赌场”，遗传算法会同时弄清楚每个“赌场”中会赢的机器，依据的是最优策略：以成倍增长的频率去玩看起来赢得越来越多的机器。太聪明了！

在《银河系漫游指南》中，外来种族为了回答终极问题，造了一台巨大的超级计算机，过了很长时间，计算机吐出“42”这个数字。

但这台计算机还指出，外星人不知道问题是什么，所以他们又造了一台更大的计算机来弄明白这个问题是什么。这台计算机（也称“行星地球”）很遗憾地在持续了几百万年的计算，即将完成的几分钟前，被摧毁了，因为要为空间高速公路让路。现在我们只能猜那个问题是什么了，可能会是：你打算玩哪台老虎机？

程序的适者生存法则

在开始的几十年，遗传算法的阵营主要由约翰·霍兰德、他的学生、这些学生的学生组成。大约在1983年的时候，遗传算法解决的最大问题就是学会控制天然气管道系统。不过，大概同样的时间段，神经网络回归了，人们对进化计算的兴趣也开始浓厚起来。关于遗传算法的第一次会议于1985年在匹兹堡举行，遗传算法的寒武纪大爆发也正在进行中。其中的一些变体尝试更加接近地模拟进化（毕竟基本遗传算法仅对进化进行了非常粗略的模拟）而其他变体则从不同方向模拟，利用让达尔文困惑的计算机科学概念来跨越进化论观点。

霍兰德的学生中较为出色的是约翰·科扎。1987年，他在意大利参加会议，飞回加利福尼亚时，有一瞬间他突然醒悟了。我们要不要对成熟的计算机程序进行进化，而不是发展相对简单的东西，如“如果……那么……”规则以及天然气管道控制？如果那是目标，为什么还要继续用字符串来表示呢？程序就像是一棵子程序调用树，所以最好还是直接穿过那些子树，而不是将它们硬塞到字符串中，而且当你随机取点穿过这些子树时，会冒着将很好的程序摧毁的风险。

例如，假设你想进化一个程序，根据行星到太阳的距离D来计算该行星的运行周期T。根据开普勒第三定律，T是D的立方的开平方，乘以一个常数C，该常数的值取决于你使用的时间和距离单位。遗传算法应该像开普勒那样，通过查看第谷·布拉赫关于行星运行的数据，就可以发现这个规律。在科扎的方法中，D和C是程序树上的叶子，而将其结合起来的运算，比如乘法运算和求平方根运算，就是内部节点。以下程序树能准确计算出T（见图5–2）。

科扎称他的方法为“遗传编程”，在这个方法中，我们通过随机交换程序树的两棵子树，来对两棵程序树进行交叉。例如，将这两棵树的高亮节点交叉，就会产生能够计算出T的程序，这个程序为其中的一棵子树（见图5–3）。

我们可以测量程序的适应度（或缺乏适应度），方法就是通过其输出值与训练数据中的准确值之间的差距来判断。例如，如果程序说地球的周期是300天，这就意味着要从其适应度中减掉65。以一群随机程序树作为开头，遗传编程利用交叉、变异、生存来渐渐进化出更好的程序，直到满意为止。

当然，计算行星的周期是一个很简单的问题，仅仅涉及乘法和平方根运算。一般情况下，程序树包含全面的编程结构，例如“如果……那么……”陈述、循环、递归。更能解释“遗传编程用来做什么”的例子就是，弄明白机器人需要按照什么顺序来行动，以达到某个目标。比如我让办公机器人从走廊的柜子里拿一个订书机。机器人可进行大量的动作，例如，走到走廊中、开门、拿起某个物品等。这些动作反过来可以由各种小动作组成，比如机器人的手向物品移动，或者在各种不同的点抓住物品。每个行为是否可能会被执行，取决于之前行为的结果，也可能需要被重复多次等。这个挑战在于要组合这些动作和子动作的正确结构，以及每个动作的参数，例如，手要移动多长的距离。机器人的“原子性”动作以及每个动作的结合为开端，遗传编程能够组合一个复杂的动作，并达到理想目标。通过这种方法，许多研究人员已经为机器人足球运动员制定了策略。

对程序树而不是字符串进行交叉得出的一个结果就是，生成的程序可以任意大，这让学习活动变得更加灵活。然而，整体的趋势就是会变得膨胀，因为随着进化持续的时间变长（也称为“适者生存”），树也会越长越大。演化新论者可以从这个事实中获取安慰：人类编写的程序之间并没有什么不同（微软的Windows系统：4500万行的代码和计算），而且人造代码也不会允许这样一种简单的方法：将复杂性处罚添加到适应度函数中就可以了。

遗传编程的第一次成功是在1995年，也就是成功设计了电子电路。以一堆电子元件为开端，例如，晶体管、电阻器、电容器，科扎的系统为了一台低通滤波器，彻底改造之前的一个专利设计（这是一个电路图，其用途之一就是加强舞蹈音乐中的低音）。自那以后，他就开始对专利设备进行改造，成打地改造出其他设备。下一个里程碑于2005年到来，当时美国专利及商标局为一项专利颁奖，该专利根据遗传学设计，是工厂的优化系统。如果图灵测试愚弄的是专利审查员而不是谈话高手，那么2005年1月25日，就是一个可载入史册的日子。

科扎的自信在这样一个不以谦逊著称的领域显得尤为突出。他将遗传编程当作一台会发明东西的机器，当作21世纪的硅版爱迪生。他和其他演化新论者相信，它可以掌握一切程序，这让他们进入了终极算法的争夺赛中。2004年，他们创立一年一度的“人类竞争奖”