群体启发式

群体启发式可以同时搜索多个解决方案。例如，进化就可以被认为是一种群体启发式。可以这么想象，存在着一个由各种各样解决方案组成的群体，也就是由各成员组成的物种，而且，群体中的某些成员繁殖的后代比其他成员更多。如果繁殖率与某种“性能”有关，比如说速度或稳健性，那么随着时间的推移，该群体应该会朝着改善该性能特征的方向进化。我在密歇根大学的同事约翰·霍兰德（John Holland）开发了一种叫作遗传算法的群体启发式，它模拟了基于进化中的群体搜索。大量证据表明，遗传算法是一个很好的通用型搜索启发式，就像进化一样。¹²

在深入研究遗传算法之前，先来考虑一种更简单的同样基于群体搜索的启发式，它被称为蚂蚁算法。在这个启发式中，一群蚂蚁被随机地“扔进”一个景观中，每只蚂蚁都“降落”在一个解决方案上，并对这个解决方案进行评估，然后应用拓扑启发式或梯度启发式在邻域搜索局部更优的解决方案。随着时间的推移，每只蚂蚁都不断找到更好的解决方案，直到陷入局部最优点为止。到目前为止，蚂蚁算法还只能算是“有多个副本”的拓扑启发式或梯度启发式。

当这些蚂蚁到处爬过之后，就可以了解到景观的哪些区域具有更高的价值，于是群体启发式就能够利用这些信息。这是通过“空运”来实现的。那些位于相对较低价值解决方案上的蚂蚁，会被“空运”到位于高价值解决方案的那些蚂蚁附近。最后，一旦所有的蚂蚁都聚集到了同一个地方，搜索就停止，并让蚂蚁们在山顶“聚餐”。

为了更好地说明这种算法，下面举一个例子。想象一下，这些蚂蚁正试图找到美国大陆地区的最高点。蚂蚁会随机降落在茫茫大地上，然后开始攀爬。不久之后，直升机就会开始将漫游在俄亥俄州、印第安纳州和艾奥瓦州的蚂蚁转运到加利福尼亚州、科罗拉多州和怀俄明州。最后，甚至连阿勒格尼山和大雾山的蚂蚁也会被空运到西部。当启发式停止工作的时候，虽然不能保证所有的蚂蚁都“安坐”在惠特尼山⁽⁴⁾上，但是可以确保它们会停留在海拔相当高的地方。

遗传算法就是在蚂蚁算法的基础上构建而成的，不过，遗传算法不是将一个解决方案，也就是一只蚂蚁空运过去，使它变得与另一个解决方案相同。遗传算法是让不同解决方案相互“配对”。让不同解决方案“配对”的含义只不过是让一个解决方案的若干部分与另一个解决方案的若干部分结合起来。假设，我们正在考虑应该把哪些香料放入什锦饭。如果不考虑价格因素，那么可能的香料组合数量将超过1 000种。如果香料之间以复杂的方式相互作用，那么要找到最好的香料组合并非易事。

在这个问题上，将采用一个显而易见的视角。用一个由“0”和“1”组成的字符串对每种香料组合进行编码。例如，如果不使用红辣椒粉，那么就给红辣椒粉分配一个“0”；如果使用卡宴辣椒，就给它分配一个“1”。通过这种方法，可以把每一种香料组合编码为一个字符串。

假设举办了一个有四位厨师参加的烹饪比赛，每个厨师都使用不同的香料组合，如表2-1所示。

表2-1　最好的什锦饭菜谱

接下来将展示如何让凯蒂的菜谱和诺厄的菜谱相互“配对”。要做到这一点，首先可以把这些香料字符串想象为什锦饭的“DNA”。当诺厄的菜谱与凯蒂的菜谱相互“配对”时，“生下来的后代”菜谱其中一部分DNA来自诺厄的菜谱，另一部分则来自凯蒂的菜谱。可以给这一个“后代”菜谱取名为纳塔莉（见表2-2）。这个菜谱结合了诺厄的前半部分什锦饭DNA和凯蒂的后半部分什锦饭DNA。为了更容易看清这一点，将诺厄的什锦饭DNA用粗体字表示。

表2-2　通过组合现有菜谱来创建一个新菜谱

我们当然希望，“后代”解决方案会成为很好的解决方案，因为它们能够将好的解决方案组合在一起。如果凯蒂和诺厄都有很好的什锦饭DNA，那么每个香料字符串也必定包含着很好的香料组合。通过将凯蒂的部分菜谱和诺厄的部分菜谱结合起来，将有可能创造出一个综合了凯蒂与诺厄菜谱中好的部分的更优菜谱。这些“好的部分”也就是约翰·霍兰德所说的“构建模块”或“基本构件”。在理想情况下，让不同解决方案相互“配对”可以将这些构建模块结合起来，从而找到更好的解决方案。例如一家设计椅子的公司已经有了一个不舒适但坚固的椅子原型，同时还有一个舒适但不坚固的椅子原型。那么，通过让这两个原型进行“配对”，该公司可能会设计出一种坚固而舒适的椅子。当然，它也可能会设计出一种既不舒适也不坚固的椅子，这就是“繁殖”的风险。

为了最大限度地减少“生下不良后代”，也就是减少低价值的解决方案出现的风险，遗传算法必须有一个选择算子（selection operator）。这个选择算子会将低价值的“后代”淘汰出去，不允许它们参与配对。这种选择会创造出一个有利于更好解决方案的偏向。另外，遗传算法也允许“突变”，即随机改变香料组合。“突变”与“配对”一起，保持了群体的多样性。选择算子能够将好的保留下来，并将不好的驱逐出去。

遗传算法能够同时利用多样性和个体性能或绩效。只有在解决方案是有价值和多样性的时候，“配对”才能发挥作用。如果解决方案是不好的，那么“配对”就只会围绕可能的解决方案空间做无意义的随机游走。如果解决方案缺乏多样性，那么“配对”则不可能产生任何新的东西。