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
1701066570
前面描述GA时似乎很简单，但是遗传算法已被用于解决科学和工程领域的许多难题，甚至应用到艺术、建筑和音乐。
1701066571
1701066572
应用之广泛从下面这些问题可见一斑：通用电气将GA用于飞行器的部分自动化设计， [129] 洛斯阿拉莫斯国家实验室用GA分析卫星图像， [130] 约翰·迪尔（John Deere）公司将GA用于自动化生产线的调度， [131] 德州仪器（Texas Instruments）则用GA来设计计算机芯片。 [132] GA还在2003年的电影《指环王：王者归来》（The Lord of the Rings：The Return of the King）中被用于生成逼真的动画马匹， [133] 为电影《特洛依》（Troy）生成逼真的演员替身动画特效。 [134] 许多制药公司用GA来辅助发现新药。 [135] GA也被一些金融组织用于各种场合：识别交易欺诈 [136] （伦敦股票交易所）、分析信用卡数据 [137] （第一资本金融公司，Capital One）、预测金融市场 [138] 和优化证券投资组合 [139] （第一象限公司，First Quadrant）。20世纪90年代，互动式遗传算法创造的艺术作品 [140] 在巴黎蓬皮杜中心（Georges Pompidou Center）等多个博物馆展出。这些只是遗传算法应用的一小部分例子。
1701066573
1701066574
复杂 [:1701064773]
1701066575
进化的罗比，易拉罐清扫机器人
1701066576
1701066577
下面我们用一个更详细的简单例子 [141] 来进一步阐释GA的主要思想。我有一个叫“罗比”的机器人，它的世界（用计算机模拟，但是很脏乱）是二维的，到处是丢弃的易拉罐。我将用遗传算法为罗比进化出一个“脑”（即控制策略）。
1701066578
1701066579
罗比的工作是清理它的世界中的空易拉罐。罗比的世界由10×10的100个格子组成（图9.2）。罗比在位置（0，0）。我们可以假设周围围绕着一堵墙。许多格子中散落着易拉罐（不过每个格子中的易拉罐不会多于一个）。
1701066580
1701066581
罗比不是很聪明，看得也不远，他只能看到东南西北相邻的4个格子以及本身所在格子中的情况。格子可以是空的（没有罐子），或者有一个罐子，或者是墙。例如，在图9.2中，罗比位于格子（0，0），看到当前格子是空的，北面和西面是墙，南面的格子是空的，东面的格子中有一个罐子。
1701066582
1701066583
1701066584
1701066585
1701066586
▲图9.2 罗比的世界。10×10的格子，散落着一些易拉罐
1701066587
1701066588
每次清扫工作罗比可以执行200个动作。动作可以是以下7种：往北移动、往南移动、往东移动、往西移动、随机移动、不动、收集罐子。每个动作都会受到奖赏或惩罚。如果罗比所在的格子中有罐子并且收集起来了，就会得到10分的奖赏。如果进行收集罐子的动作而格子中又没有罐子，就会被罚1分。如果撞到了墙，会被罚5分，并弹回原来的格子。
1701066589