Naturalselectionisamechanismforgeneratinganexceedinglyhighdegreeofimprobability.
自然选择就是能生成极不可能之事的机制。
——RonaldFisher（费舍）
从生物学里找计算的模型，一直是人工智能的研究方向之一，学术上大致有两条传承的脉络：一条源自麦卡洛克和皮茨的神经网络，演化到今天成了深度学习；另一条则源自冯诺伊曼的细胞自动机，历经遗传算法、遗传编程，其中一条支线最后演变成了今天的强化学习。
1.霍兰德和遗传算法
霍兰德准备动手写关于代数和逻辑的博士论文时，遇见了在哲学系任教的伯克斯（AuthurBurks）。伯克斯是密执安大学的哲学博士，1941年25岁时博士毕业去了宾夕法尼亚大学的摩尔学院，加入美国最早的计算机之一ENIAC的研制。冯诺伊曼当时想把整个ENIAC团队招安到普林斯顿高等研究院，ENIAC团队的头儿工程师毛彻里（JohnMauchly）被老冯所不喜，老冯看中的是ENIAC的工程骨干埃克特（JohnPresperEckert），但埃克特不愿背叛毛彻里。于是冯诺伊曼挖到了ENIAC项目早期真正的灵魂人物数学家、逻辑学家古德斯丁（HermanGoldstine），伯克斯随着古德斯丁加入到普林斯顿高等研究院团队，先是做老冯的助手，后来参与了美国最早几台计算机的研发。
霍兰德的博士论文题目是CyclesinLogicalNets。伯克斯也写过本小册子《逻辑网络理论》（TheoryofLogicalNets）。所谓“逻辑网络”，当时是个模糊的概念。麦卡洛克和皮茨的神经网络模型也称为逻辑网络，因为皮茨本人是逻辑学票友。冯诺伊曼的细胞自动机也是逻辑网络。伯克斯是老冯细胞自动机遗著的编者，霍兰德受老师伯克斯的影响也是自然的。他们学生的博士论文多少都和细胞自动机有关。20世纪50年代是逻辑学逐渐离开哲学，向其他学科渗透的时代，逻辑是一股风气，什么人都喜欢和逻辑沾点边，就像当下的人工智能或深度学习。
有意思的是，在麦卡锡执笔的达特茅斯会议的计划书里，有一节“神经网络”。其中，霍兰德的名字和麦卡洛克、皮茨、明斯基和罗切斯特等人的名字并列。晚年他回忆说当时确实收到了达特茅斯会议的邀请，但那个夏季他要在密执安教课，就没去，读研究生时找到份夏季工作不容易。估计当时谁也没觉得那个会后来变得如此重要。霍兰德为未能参会颇为遗憾，认为是他个人的重大损失。可不是嘛，那个会的参会者都可自居AI的创始人。
霍兰德认为达特茅斯会后AI基本就是符号派一统天下了。学习，或者用霍兰德的话说“可适应”（adaptation）作为人工智能的一个重要分支，要到好多年后才翻过盘来。霍兰德说他自己的思想被学界逐渐接受，是在他的学生都出了名之后。美国的师生关系和中国确有不同，美国是学生毕业后，自立门户，大部分还是接着原来的东西继续做，也可以跨越式发展；但在中国，大部分是等着接老师的班儿，老师是院士，就扶持学生当院士，老师是校长，学生接着做校长，一旦一个“重点实验室”建立，小佬坐等大佬死后接班升大佬。
霍兰德在回顾自己的研究生涯时说，如果一个人在早期过深地进入一个领域，可能会不利于吸收新的思想。对于霍兰德来说，进化论和遗传学是新思想，幸运的是他的老师伯克斯也是跨界人才，鼓励交叉学科的研究。对霍兰德影响最大的一本书是英国统计学家费舍（RonaldFisher）的《自然选择的遗传理论》（TheGeneticalTheoryofNaturalSelection）。无神论者道金斯（RichardDawkins）称费舍是达尔文之后最伟大的生物学家。费舍把孟德尔的遗传理论和达尔文的自然选择结合起来。霍兰德由此得到启发：进化和遗传是族群学习的过程，机器学习可以此为模型。
染色体（chromesome）是遗传的基本单位。以人为例，人有两性，男性第23对染色体呈X-Y，而女性只有X。两性交配导致人类染色体的交叉（crossover）。在进化过程中，部分基因还会变异（mutation）。环境会保留某类基因的族群，而淘汰掉其他的。
遗传算法就是模拟种群（population）的进化过程。其结构大致如下所示。
(1)随机生成初始群体。
(2)主循环（停机的标准可以是迭代次数，或者适应度达到某种要求）。
a)执行策略，计算当前群体中所有个体的适应度；
b)从当前群体中，选择精英作为下一代的父母；
c)将选出的精英父母配对；
d)以极小概率将子代变异；
e)将子代个体添加到新群体中。
从以上过程中，我们可以理解进化中“优胜劣汰”的算法含义。伴随20世纪80年代后期神经网络的复兴，遗传算法也作为一种受生物学启发（biology-inspired）的算法，得到更多的认可，同时也有更多的实际应用。1985年第一次遗传算法国际会议召开，这个学科算是有了自己的共同体。1997年IEEE开办了《进化计算杂志》（IEEETransactionsonEvolutionaryComputation），遗传算法也算是进入主流了吧。
2.遗传编程
在遗传算法中，种群是数据，更进一步的想法是：如果种群变成程序的话，进化是不是仍然可行呢？霍兰德的学生寇扎（JohnKoza）在1987年给出了一个思路，并把它命名为“遗传编程”（GeneticProgramming）。
遗传编程的结构和遗传算法差不多，一组程序就一个特定的问题给出解答，按照执行结果的好坏给所有程序排序。程序本身也是数据，自然也可以修改。在遗传编程里，变异就是对程序做微小调整。交叉和配对就是将两个表现优异的程序互相嫁接。寇扎后来还引入了“基因重复”（duplication）和“基因删除”（deletion）等生物学概念，以提升遗传编程的效率。
遗传算法本身就需要大量的数据，遗传编程需要的数据量自然更大，这对计算能力提出了新的需求。并行计算机公司ThinkingMachines在20世纪90年代初曾经尝试用超级计算实现大规模的遗传编程，公司创始人希利斯（DannyHillis，明斯基的学生）在1994年的TED会议上演讲的题目是“BacktotheFuture”，他颇为自得地谈起用遗传编程自动学会排序算法。但没过多久，ThinkingMachines就倒闭了。1999年时，寇扎搭建了一个1000个节点的集群，每个节点是Pentium-II（奔腾-2），那时搭建集群的软硬件技术统称Beowulf，是当下Hadoop和Spark的先驱。
遗传算法的稳定性一直就是研究课题，遗传编程的数学性质自然更加复杂。寇扎等人给国际机器学习大会的投稿多次被拒，理由是遗传编程的性能常常还不如一些简单的搜索算法，在大规模的实际问题上无法实用。现在看，这一点也不惊人，其实如果没有算力的大幅提升，眼下红得发紫的各种深度学习也无法实用。寇扎联合遗传算法的人马开办了“遗传与进化计算会议”（GeneticandEvolutionaryComputingConference）。
1995年，寇扎利用遗传编程做布尔电路优化，取得成功，算是遗传编程可实用的一个里程碑。寇扎1999年创业，公司名就叫“遗传编程”。公司是研究型公司，主要为政府和企业提供关于遗传编程的咨询服务。
寇扎说遗传编程是“发明机器”（inventingmachines），有了遗传编程就不需要其他人工智能了，他的理由是人工智能的目的是生产有智能的程序，这不正是遗传编程干的吗？听起来有道理，但遗传编程的理论基础一直欠缺。
遗传算法和遗传编程这一脉，在神经网络处于低谷时，虽然也受到波及，但并没有像神经网络那样备受打击。而神经网络咸鱼翻身后，也没有爬得那么高。
3.强化学习
巴托在麻省大学的第一个博士生就是萨顿（RichardSutton），萨顿本科在斯坦福大学学的是心理学，研究动物怎么适应环境一直是他的兴趣。和老师霍兰德不同，巴托和萨顿关心更原始但也更抽象的可适应性。比如，一个刚出生的孩子，怎么学会对环境的适应。在监督式学习中，目标是清楚的。但婴儿不知道目标是什么，不知道自己要什么。通过与外部世界的不断交互，婴儿受到奖励或惩罚，由此强化对外部世界的认知。
强化学习的另一个理论基础是动态规划。贝尔曼（RichardE.Bellman）在20世纪50年代就发明了动态规划。萨顿和巴托也承认在强化学习早期，受到动态规划的启发。巴托一度在他的强化学习讨论班上让研究生分工研读贝尔曼的经典著作《动态规划》（DynamicProgramming）（Bellman，1957）。班上数学好的学生不知所云，算法课里不都有一章讲动态规划嘛，如果强化学习就是动态规划，那还有啥意思？近30年后，当强化学习被用来解决围棋这样复杂的问题之后，当年班上的学生们才体会到巴托的初衷。但“三十年太久，只争朝夕”，这几乎是一个人学术生涯的全部。巴托几年前就已经退休了，学生们也到了人生的强弩之末。愚公移山，现在是当时学生们的孩子们的天下，他们赶上好时候了。
在计算能力的约束下，强化学习的环境不宜太复杂。萌芽期的强化学习的例子都是游戏，如贝尔曼的“老虎机”和塞缪尔（ArthurSamuel）的跳棋。游戏的环境相对容易定义，在棋类比赛中，环境就是对手和规则。强化学习被用来下围棋不是偶然的。
如果整个世界是完全随机的，那么强化学习就要失效。学还是不学对结果没有什么影响。巴托和萨顿有时也把强化学习称为“享乐主义”（hedonistic），也即学习系统想最大化环境对自己的某种反馈。“享乐主义”这个说法来自于另一位先行者克劳福（HarryKlopf）的一本书名《享乐主义的神经元》（HedonisticNeuron）。“享乐主义”和道金斯的“自私的基因”异曲同工，目的是为类生物（biology-inspired）系统建立基本公理。
遗传算法和强化学习有一个共同点：效果要等到多步以后才能看到，这是和监督式学习的主要不同。这就需要尽可能多地访问所有的状态，这样效率就会受到影响。蒙特卡洛模拟是一种减少状态空间搜索的有效办法。最近也有人利用深度学习来压缩需要表示的状态空间数目。这还有点意思，本来强化学习初衷是探索生物体学习的模型，现在神经网络又成了强化学习的工具。当状态空间很大时，强化学习可以和蒙特卡洛方法或深度神经网络结合。
2017年7月7日，DeepMind宣布将在萨顿的“新巢”加拿大阿尔伯塔大学开办联合实验室，这是DeepMind第一次在英国以外设立研究机构。经过多年耕耘，萨顿已经把阿尔伯塔大学建成了强化学习的基地，和计算机系里崇尚游戏的几个教授天作之合，使强化学习在围棋、德州扑克、电玩等领域势不可挡。萨顿的阿尔伯塔之于强化学习，就像辛顿的多伦多之于深度学习，杨立昆（YannLeCun）的纽约大学之于卷积神经网络。可惜巴托已经退休，强化学习在其发源地美国麻省大学已经无人继承。
萨顿1979年到麻省大学跟随巴托和阿比卜，由此开创强化学习。他一直认为强化学习是理解智能的关键。维纳的控制论自问世从没进入过主流，现在更无人问津了。在整个人工智能的各个分支里，大概只有强化学习还留有点儿控制论的影子。
如果从写作的角度看，强化学习更像是第一人称叙述，Agent就是“我”，外部世界（包括他人）都是“环境”。监督式学习更像是第三人称叙述，作者在用一只上帝的眼睛洞察世界，对错分明。第一人称的学习要比第三人称的学习更本质。罗素（StuartRussell）和诺维格（PeterNorvig）在他们那本权威且无所不包的人工智能大部头教科书《人工智能：一种现代方法》里说“可以认为强化学习包含了全部人工智能”（ReinforcementlearningmightbeconsideredtoencompassallofAI）。这不无道理。
4.计算向自然学习还是自然向计算学习
哈佛大学的理论计算机科学家、图灵奖获得者瓦连特（LeslieValiant）曾经从计算的角度研究过机器学习和进化，他把进化当作学习的特例。利夫纳特和帕帕季米特里乌认为有性繁殖不太容易达到最优点，而无性繁殖才更像是优化算法，他们把遗传算法比作有性繁殖，模拟退火算法比作无性繁殖。
如果说遗传算法是微观地向生物内部机制学习的话，强化学习则是更为宏观地向自然学习。瓦连特的方法企图把微观和宏观整合起来，为学习提供一个更为基础的数学框架。
5.计算理论与生物学
无论是遗传算法、深度学习还是强化学习，都缺乏计算理论的基础。生物学激发的学科都是模拟自然，它们都不需要解释，不需要了解内部原理，只要能查看输出结果，就够了。数学大概是所有学科中离生物学最远的学科。
模型A：说出最大的自然数；
模型B：定义快速增长的函数；
模型C：说出康托序数（Cantorordinalnumbers）。
参考文献指南
AdaptationinNaturalandArtificialSystems:AnIntroductoryAnalysiswithApplicationstoBiology,ControlandArtificialIntelligence（Holland，1975）是遗传算法的原创著作。GeneticAlgorithmsinSearch,OptimizationandMachineLearning（Goldberg，1989）是教科书体例，容易上手，尽管出版日期较早，但仍有参考价值。GeneticProgramming:AParadigmforGeneticallyBreedingPopulationsofComputerProgramstoSolveProblems（Koza，1990）是遗传编程的原创著作，是斯坦福大学计算机系的内部技术报告，可免费获取。GeneticProgramming:OntheProgrammingofComputersbyMeansofNaturalSelection（Koza，1992）是基1990年报告的正式出版物，后来分别在1994年、1999年和2003年出版了第二卷、第三卷和第四卷，每卷都主打某一类应用问题。
ReinforcementLearning:AnIntroduction（Suttonetal.，1998）是强化学习的原创著作，也可作为教科书，该书2017年出了第二版，第一版和第二版的初稿在网上可免费获取。强化学习的教科书里最爱用的Q-Learning，是ChrisWatkins1989年在他的剑桥博士论文里提出的。
IntroductiontoMachineLearning（Kubat，2015）是一本非常可读的机器学习导论，并且有中译本，最后一章是“强化学习”。周志华的《机器学习》最后一章也是“强化学习”。罗素（StuartRussell）和诺维格（PeterNorvig）合著的人工智能经典大部头教科书，全书由7篇组成，“强化学习”是“学习”一篇里的最后一章。这大概说明强化学习比较“新”，或者“火”得比较晚吧。