终极算法【5】——进化学派
在霍德.利普森位于康奈尔大学的创意机器实验室中，奇形怪状的机器人正在学习爬行和飞行。这些机器人并不是人类工程师设计出来的，而是进化来的，和地球上生命多样性产生的过程一样。
使这些机器人进化的算法，是19世纪由查尔斯.达尔文发明的。那时他不觉得这是一种算法，部分原因在于当时缺少一个关键的子程序。一旦1953年詹姆斯.沃森和弗朗西斯.克里克提供了该子程序，进化就会进入第二个阶段：该进化是在计算机中而不是活体中进行，而且会比活体进化快10亿倍。该子程序的提倡者是约翰.霍兰德。
和许多其他早期的机器学习研究者一样，霍兰德开始时研究的是神经网络。在密歇根大学读研究生时，他阅读了罗纳德.费雪的经典著作《自然选择的遗传理论》。在该著作中，同时作为现代统计学奠基人的费雪，提出了关于进化的第一套数学理论。霍兰德认为该理论遗漏了进化论的精华，费雪孤立地看待每个基因，但是有机体的适应度就是它所有函数的复值函数。如果基因都是独立的，它们变量的相对频率会快速收敛至最大适应点，然后从此保持均衡。但如果基因相互作用，进化（追求最大适应度）就要复杂得多。
随着霍兰德的创作渐渐为人所知，遗传算法的关键输入就是一个适应度函数。给定一个特定程序和某个设定的目标，适应度函数会给程序打分，反映它与目标的契合度。
适应度函数将人在这个过程中扮演的角色概括化了。但和人的角色相比，更为微秒的部分是自然的角色。开始，是一群适应力不那么强的个体（可能是完全随机的个体）遗传算法得找出变量，然后这些变量依据适应度而被选择。DNA依据碱基对的序列对机体进行编码，同理，我们也可以依据一串二进制数字对程序进行编码。变量，无论在DNA序列中，还是在位串中，都可通过几种方法产生。最简单的方法就是点突变，即随意翻转位串中的一个比特值，或者改变一段DNA中的单个基本碱基。但对霍兰德来说，遗传算法的真正威力在于更为复杂的东西：性。
有性生殖包括在父亲和母亲的染色体之间进行材料交换，这个过程称作染色体交叉。这个过程会产生两条新的染色体，一条染色体交叉点的一边是母亲的染色体，另外一边则是父亲的染色体，另外一条相反。
遗传算法通过模拟这个过程发挥作用。它为每一代中两个适应力最强的个体进行配对，通过随机交叉父母位串点中的一点，让每对父母生出两个后代。将点突变应用到新的位串后，算法让这些点突变在其虚拟世界中释放。每个点突变都会反馈适应度得分，然后重复这个过程。每一代都会比前一代的适应度更高，当达到理想的适应度或者时间用尽时，这个过程就会结束。
和费雪梳理的简单模型相比，遗传算法有了很大的进步。通过一组方程来充分体现自然选择很困难，但将自然选择表达为一种算法又是另外一回事，而且这样还能够阐明许多其他棘手的问题。为什么一些物种会突然出现在化石记录中？能够证明这些物种是渐渐由早期物种进化而来的证据在哪里？1972年，尼尔斯.埃尔德雷奇和史蒂芬.杰伊.古尔德提出进化过程由一系列“间断平衡”组成，长期的停滞与短暂的快速变化相互交替，就像寒武纪爆发那样。
我们应注意遗传算法和多层感知器的差异程度。反向传播会在任何给定时间坚持单一假设，而且这个假设会渐渐改变，直到其适应某个局部最优值。遗传算法会在每一步中考虑整个群体的假设，而由于交叉行为，这些假设可以从这一代跨到下一代。将初始权值设为小的随机值后，反向传播才会确定继续进行下去。相反，遗传算法则充满随机选择：该使哪些假设成立并进行交叉（适应度更高的假设更有可能成为备选对象），该在哪里对两个字符串进行交叉，该使哪些比特的信息发生突变。反向传播为了预先设定的网络结构掌握权值；密集度更大的网络更为灵活，但掌握起来也更困难。除了通用式外，遗传算法不会对它们即将学习的结构进行预先假设。
因为这个原因，和反向传播相比，遗传算法陷入局部最优值困境的可能性更小，而且原则上也更有可能找到真正新颖的东西，但遗传算法分析起来也要难得多。
遗传算法的灵活之处就在于，每个字符串都暗含指数数量的构造块，被称为“基模”，因此该研究比它看起来的还要高效的多。这是因为字符串比特的每个子集都是一个基膜，代表可能合适的性能组合，而一个字符串有指数数量的子集。我们可以用这样的方法来代表基模，也就是用“*”来代替字符串中不属于该字符串的比特。相反，在群体中，一个特定的基模可能由许多不同的字符串来表示，而且每当这时，这些基模都会受到隐式评估。假设在下一代中仍然成立的概率与其适应度成正比，那会怎样？霍兰德表明，在这种情况下，和平均值相比，在某代中表示基模的字符串适应度越高——我们能期望的——在下一代中看到这些表示字符串的数量也越多。那么虽然遗传算法暗地里对字符进行操纵，它也会找到基模更大的可能性。随着时间的流逝，适应度更高的基模会主导群体。
在开始的几十年，遗传算法的阵营主要由约翰.霍兰德、他的学生、这些学生的学生组成。大约在1983年的时候，遗传算法解决的最大问题就是学会控制天然气管道系统。不过，大概同样的时间段，神经网络回归了，人们对进化计算的兴趣也开始浓厚起来。
霍兰德的学生中较为出色的是约翰.科扎。1987年，他在意大利参加会议，飞回加利福尼亚时，有一瞬间他突然醒悟了。我们要不要对成熟的计算机程序进行进化，而不是发展相对简单的东西。科扎称他的方法为“遗传编程”，在这个方法中，我们通过随机交换程序树的两棵子树，来对两棵程序树进行交叉。我们可以测量程序的适应度（或缺乏适应度），方法就是通过其输出值与训练数据中的准确值之间的差距来判断。
遗传编程的第一次成功是在1995年，也就是成功设计了电子电路。下一个里程碑于2005年到来，当时美国专利及商标局为一项专利颁奖，该专利根据遗传学设计，是工厂的优化系统。
演化新论者和联结学派重要的共同点是：他们都因为受到自然启发而设计了学习算法，不过后来分道扬镳了。演化新论者关注的是学习架构，对他们来说，通过参数优化来对演化的架构进行微调，这是次重要的事情。相反，联结学派更喜欢用一个简单、手工编写的结构，加上许多连接行为，然后让权值学习来完成所有工作。这就是机器学习版本关于先天和后天的争论，而且双方都有很好的论据。
在先天与后天的争论中，两方都没有完整的答案，关键在于找到如何将两方结合起来。终极算法既不是遗传编程，也不是反向传播，但它得包含这两者的重要部分：结构学习和权值学习。
“鲍德温效应”是由J.M.鲍德温于1986年提出来的。在鲍德温进化中，初次掌握的行为，之后会变成天生的本领。
进化寻求好的结构，而神经学则填满这些结构：这样的结合是我们走向终极算法最简单的一步。
机器学习的目标是尽可能找到最好的学习算法，利用一切可能的方法，而进化和大脑不可能提供学习算法。进化的产物有很多明显的错误。
与联结学派及演化新论者相反，符号学派和贝叶斯学派不相信“法自然”的说法。他们想从基本原理中找出学习算法该做什么，而且也包括我们人类。符号学派和贝叶斯学派想指出，弄明白“我们该怎样学习”也可以帮助我们了解人类如何学习，因为这两者大概不会完全不相关（远非如此）。特别指出的是，对于生存有重要意义、已经经历很长一段时间进化的行为应该就是最优的。
在20世纪八九十年代，联结主义者占支配地位，但现在贝叶斯学者的数量正在上升。最优学习是贝叶斯学派的中心目标，而且他们肯定自己已经找到了实现这个目标的方法。请看下章......
参考文献：
终极算法. [美] Pedro Domingos 著. 黄芳萍 译