什么是进化算法？

不是所有进化都与生物有关。20世纪50年代，计算机学家就创造了基于生物学原理的算法，但是与细胞中发现的分子结构并没有关联。到20世纪70和80年代，密歇根大学的约翰·霍兰和他的学生对这类算法进行了深入研究。其中一些程序的表现非常类似生物进化，虽然它们只不过是计算机软件。这类算法的存在证明了进化过程并不仅限于生命系统。它们也揭示了进化、学习和计算的密切关联。

进化算法的细节各不相同，但都遵循以下6条原理：

1．它们都包含可能对某件事有用的信息（信息体）的多个拷贝。通常这些信息表示的是对某个问题的试探性解答。2.这些信息体是“一代一代的”。每一代都有源自前一代的新拷贝。

3．信息体从一代到下一代之间会随机变化。结果使得群体成员并不完全一样。

4．所有变化的范围和幅度都很小。不受约束的大的随机变化没有用。

5．在每一代中，一些信息体复制得更加频繁。

6．必须有一致的标准来根据各信息体所编码的信息决定哪些信息体可以复制以及有多频繁。

算法是遵循特定顺序的逻辑步骤。进化算法有一个特点：它们包含图6.2所示的循环过程。

算法的第1步是生成初始信息体结构，通常是随机生成；可以将其视为试探性答案，不需要很好。第2步是评估。根据某个标准对所有信息结构进行评估。评估是必须的，而且非随机。第2到第5步反复进行，从随机变化中捕捉有用的信息并累积。第5步是新信息的来源。由于只有最差的结构被替换，就算所有突变拷贝都比父代差，系统整体也不会“滑坡”。总的效应是累积能提高成绩的随机引入的信息。如果在某一轮循环中没有出现改善，也没有关系；总会有一些循环改善。（根据选择标准）反复基于每一代最好的进行改进来实现长远的改变。一旦达到预先设定的目标或时间，程序就输出最好的结果然后停止。

只要所评估的对象发生变异，这个通用方案就能为许多问题产生出“性能”越来越强（评估成绩越来越好）的结构。事实上任何编码信息的体系都能作为进化算法的基础。计算机科学家给出了许多这样的例子，这一章探讨其中两个。同样，对性能的评估以及选择复制的信息体的规则也很多。一致性是关键，并且第5步生成的变异体不能与父代差别太大。如果新的变异体与前代差别太大，就很难带来改善。另一方面，如果变化太小，也什么都不会发生——每一代基本都与前代一样。

有适量的变异，每一代就有合理的可能产生出一些性能强于前代的信息体。一旦出现，有更好评估成绩的信息就能传递给后代。通过反复执行这个策略，整个信息体群体针对目标问题就会变得越来越好。

图6.2给出的方案通过突变复制并留下最好的信息体确保每一代都不会差于前代。这个特性并不是必须的。在许多应用中，如果突变率不是太高，群体中所有成员都可以突变，算法仍然能正常工作。要产生出程序员自己也没有想到的变异，变异至少在一些方面必须是随机的。

进化算法的一个子类称为遗传算法，因为它们细致模仿了生物进化。信息被编码为符号的线性序列；并且群体中的所有成员都有低突变率。突变会随机改变单个符号（例如，随机从1变成0或从0变成1），并且通常会加入交换机制，在信息体群体的不同成员之间交换信息子集（类似于生物中的有性繁殖和基因重组）。还有一些生物学机制也会被用到，比如复制或删除序列中的一段。

遗传算法有一个共性就是突变率有“最佳击球点”。如果变化机制太保守，变化就会很慢，如果突变太快，系统就会掉进随机的混乱，不能保留前代的记忆。如果突变率被调节到合适的值，群体就能迅速进化，每个成员携带的信息都能越来越符合评估标准的要求。下面我们通过两个例子来了解遗传算法的工作原理。

例1：最多1，一个很简单的问题

这个计算机程序将1和0组成的任意序列转换成全1序列——对于人来说很简单，但对于不知道如何识别“1”的计算机来说并不容易。这个问题清晰地揭示了遗传算法的工作原理。图6.3描绘了一个遗传算法，可以在没有明确告知计算机如何“识别”0和1的情况下完成这个任务。为了简单起见这个例子中的序列只有10位，但完全可以是任何长度。

在这个算法中重复2、4和5步骤的循环就是图6.2中进化算法特有的循环。重复步骤2和3的循环为每一代生成10个尝试结构。举个具体的例子：假设算法的初始输入是1001000100（1024种可能的01序列中的一个）。表6.1记录了从这个序列开始的一次计算的过程。最终的输出就是所预期的1111111111。

对于表6.1中给出的每一轮计算（迭代），在复制输入字母生成输出时，有0、1或2位被随机选中翻转（0变成1或1变成0）。也就是说每次复制字符时有10%的可能产生变化。为了方便起见，表中列出了每个变体的1的计数。每一轮结束后将计数值最高的字串（粗体）选出来作为下一轮迭代的输出。例如，迭代2那一列所有字串都是从迭代1中计数值为5的字串产生的。这次实验用了5个回合（迭代）输出10个1的字串。其他实验解决这个问题的回合数不一定相同。每次实验的细节都会有所不同，因为变化（突变）是随机的，但最终的输出总是由10个1组成的序列。1的“来源”是将一些0变成1的随机翻转。这个过程也会随机地将1变成0，但这些变化在选择过程中被舍弃了。

表6.1中的运行过程总共生成了50个01字串。反复试验表明平均约为60个。如果不是对现有的字串进行细微的改动，而是每次都生成全新的字串，则大约需要50个回合（总共500个字串）才能产生出全为1的10符号字串。因此，搜索10个1组成的字串时，进化算法比简单的随机搜索大约快10倍。对于更长的字串，节省的时间会更多；表6.2体现了这一点。表中第1行就是这里讨论的例子。

1千比特没有多少信息，然而如果完全依赖随机，要生成编码这么多信息的特定字串，所需的时间远远大于已知宇宙中原子数量乘以以纳秒（10亿分之一秒）计的宇宙年龄。这意味着如果宇宙中的原子每纳秒生成1比特，在宇宙存在的时间内都不可能产生所期望的字串。因此我们可以确定不可能随机生成1000个1组成的字串。然而用最多1算法却很容易。这展现了复杂引擎的魔力。

要把效率提高到如此高的程度，突变率的设置很重要，必须依据字串长度进行优化。当突变率接近1/n时（n为输入字串的长度）通常能表现出最优性能。图6.4描绘了字串长度为100比特时突变率的影响。

最大1问题很简单，人们不会想要用进化算法来解决它，但这个问题很好地揭示了进化算法的工作原理，很适合用来入门。

例2：塔尔塔罗斯

丹·阿什洛克和他的学生研究了能优化格子板上虚拟推土机行为的程序。这个游戏名为塔尔塔罗斯，最初由阿斯拓洛·特勒于1993年提出，当时他是卡内基·梅隆大学的研究生。图6.5中给出了一个例子。推土机的任务是将箱子推到格子板的边和角上。推土机没有传感器，一次只能推一个箱子。推土机一次走一步，每步有3个动作可选。推土机可以前进一格（F）、左转（L）或右转（R）。命令组成的序列，例如FFRFL，就是决定推土机行为的控制序列。这个序列指令推土机依次前进两格（FF），然后右转（R），然后前进一格（F），然后左转（L）。在塔尔塔罗斯中推土机和箱子不能同时占据一个格子，两个箱子也不能在同一个格子。如果推土机往前进入一个有箱子的格子，箱子就沿推土机前进方向被“推移”一格，除非前面被另一个箱子或墙挡住。如果动作要求推土机推多个箱子或墙，什么也不会发生，算法会继续执行控制序列的下一个命令。

遗传算法能产生出用有限步获得高分的控制序列（6×6的板子一般80步）。每推一个箱子到墙边得1分，墙角的箱子得2分，中间的箱子得0分。图6.6给出了6×6的板子和6个箱子的4次不同结果。这个游戏的板子至少要3×3，并且箱子数量远远少于格子数量。也可以有多台推土机。

这个游戏有2个不同版本。在简单版本的塔尔塔罗斯中，要为给定的初始状态（例如图6.5）进化出最佳答案。在第2个版本中，推土机的行为要能够对随机的初始状态都能表现得很好。无论哪个版本，都是生成多个控制字串，用板子进行测试，选出最好的进行突变然后再次测试。

如果使用固定的初始状态，突变后运行一次就能够对控制字串的表现进行评估；算法如果运行足够长时间总能找到最优的控制字串。如果用随机生成的板子测试控制字串，则需要生成多个板子进行一系列测试，然后计算控制字串的平均得分。完成测试后，选出平均表现最好的控制字串作为基础生成新的字串。突变可以是简单改变控制字串的一个字符，也可以包含其他变化策略，比如选择性复制和/或交叉（也称为重组）。无论哪种情形，都需要维持一个控制字串群体，并且将表现好的控制字串作为后代字串的“父母”。应用这个算法会逐渐发现越来越好的控制字串（分数越来越高）。对于所有的遗传算法，新信息和变革的来源都是对个体的（微小）随机变化进行选择。

如果板子的状态随机生成，游戏会很难，如果给推土机增加记忆和传感器可以显著改善性能。结果表明，推土机记住之前的动作会很有用，例如是否推动了箱子，或者推了无法移动的箱子，或者推到了墙。增加记忆和传感器会让算法更加复杂，但分数也会更高。