1701066520
复杂 [:1701064770]
1701066521
第9章 遗传算法
1701066522
1701066523
在对“机器能否复制自身”的问题给予肯定回答后，冯·诺依曼很自然地想让计算机（或计算机程序）复制自己和产生变异，并在某种环境中为生存竞争资源。这就会遇到前面提到的“生存本能”以及“进化和适应”的问题。可惜的是冯·诺依曼还没有研究进化问题就去世了。
1701066524
1701066525
其他人很快就开始继续他留下的工作。20世纪60年代初，一些研究团体开始在计算机中进行进化实验。这些研究现在统称为进化计算 [127] （evolutionary computation）。其中最为著名的是密歇根大学的霍兰德和他的同事、学生进行的遗传算法（genetic algorithms）研究。
1701066526
1701066527
霍兰德（图9.1）可以说是冯·诺依曼的学术徒孙。霍兰德的博士导师是哲学家、逻辑学家和计算机工程师巴克斯，巴克斯曾协助冯·诺依曼研制EDVAC，并且完成了冯·诺依曼没有完成的自复制自动机研究。在结束EDVAC的工作之后，巴克斯在密歇根大学获得了哲学教职，并成立了计算机逻辑小组，这是一个由对计算机基础以及广义信息处理感兴趣的教师和学生组成的松散团体。霍兰德到密歇根大学攻读博士学位，开始是学数学，后来转到新成立的“通信科学”系（后来改称“计算机与通信科学”），这可能是世界上第一个真正的计算机科学系。几年后，霍兰德成为系里第一个博士学位获得者，他也是世界上第一个计算机科学博士。很快他就留校成了计算机系的教授。
1701066528
1701066529
1701066530
1701066531
1701066532
▲图9.1 霍兰德（圣塔菲研究所版权所有，经许可重印）
1701066533
1701066534
霍兰德在读费希尔（Ronald Fisher）的名著《自然选择的遗传理论》（The Genetical Theory of Natural Selection）时被达尔文的进化论深深吸引。同费希尔（和达尔文）一样，进化与农产养殖之间的相似也给霍兰德留下了深刻印象。但他是从计算机科学的角度来思考这种相似性：“这就是遗传算法的由来。 [128] 我想到，是不是可以像繁育良种马和良种玉米那样繁殖程序。”
1701066535
1701066536
霍兰德的主要兴趣在于适应现象——生物如何进化以应对其他生物和环境变化，计算机系统是不是也可以用类似的规则产生适应性。他在1975年的著作《自然和人工系统的适应》（Adaptation in Natural and Artifcial Systems）中列出了一组适应性的普遍原则，并且提出了遗传算法的构想。
1701066537
1701066538
我第一次了解遗传算法是在密歇根大学研究生院，当时我选了霍兰德基于他的书开的一门课。我马上就被“进化的”计算机程序的思想吸引住了。（同赫胥黎一样，我的反应是：“我怎么没想到，真是太蠢了！”）
1701066539
1701066540
复杂 [:1701064771]
1701066541
遗传算法菜谱
1701066542
1701066543
算法其实就是图灵说的明确程序，就好比做菜的菜谱：一步一步将输入变成输出。
1701066544
1701066545
对于遗传算法（GA），期望的输出就是特定问题的解。比如，你需要编写一个程序控制机器人清洁工在办公楼拾垃圾。你觉得编这个程序太费时间，就委托遗传算法替你将这个程序演化出来。因此，期望的GA输出就是能让机器人清洁工完成拾垃圾任务的控制程序。
1701066546
1701066547
GA的输入包括两部分：候选程序群体和适应性函数。适应性函数用来确定候选程序的适应度，度量程序完成指定任务的能力。
1701066548
1701066549
候选程序可以表示成位、数字或符号组成的字符串。后面我会给出一个机器人控制程序表示成数字字符串的例子。
1701066550
1701066551
在机器人清洁工的例子中，候选程序的适应度可以定义为机器人在给定时间内清扫的面积，这是由程序决定的，越大越好。
1701066552
1701066553
下面是GA菜谱。
1701066554
1701066555
将下面的步骤重复数代：
1701066556
1701066557
1.生成候选方案的初始群体。生成初始群体最简单的办法就是随机生成大量“个体”，在这里个体是程序（字符串）。
1701066558
1701066559
2.计算当前群体中各个个体的适应度。
1701066560
1701066561
3.选择一定数量适应度最高的个体作为下一代的父母。
1701066562
1701066563
4.将选出的父母进行配对。用父母进行重组产生出后代，伴有一定的随机突变概率，后代加入形成新一代群体。选出的父母不断产生后代，直到新的群体数量达到上限（即与初始群体数量一样）。新的群体成为当前群体。
1701066564
1701066565
5.转到第2步。
1701066566
1701066567
复杂 [:1701064772]
1701066568
遗传算法的应用
1701066569