允许犯错启发式

如果视角给问题带来了很多个局部最优点，那么前面两类启发式就很难发挥作用。根据假设，任何“艰难”问题，包括治疗疾病、设计政策，等等，都有崎岖景观。否则，就可以直接登上“富士山”之巅，轻松地解决问题，然后为进步沾沾自喜了。当视角创造了一个崎岖景观时，就需要使用一个更加复杂、更加“久经世故”的启发式。在崎岖景观中，一味强调向上攀登的启发式会陷入困境，特别是在一个拥有大量局部高峰的崎岖景观中，“唯上”型启发式经常会“卡死”。防止陷入局部高峰的一个办法是，每隔一段时间向下爬一次。然而问题是，爬下一个小小的局部高峰再重新开始，这也许是一个好主意，但是如果已经爬上了一个很大的局部高峰呢？那就不行了。

一个更加复杂、更加“久经世故”的启发式会往山下走几步看看，这看起来似乎是在“犯错”，但是它也不会往山下走太多步。对于这种启发式，我们称之为允许犯错启发式。使用最广泛的一种允许犯错启发式是模拟退火算法（simulated annealing）。这种启发式的另一个名称是Metropolis算法，它是由圣塔菲研究所学者尼克·麦特罗博利斯（Nick Metropolis）发明的。

错误究竟怎么产生效益呢？这里的逻辑非常微妙，值得好好研究一下。考虑到很少会遇到新的、完全意想不到的直觉，必须花一些时间好好分析一下模拟退火算法的逻辑。而在正式开始之前，应该注意到，这种算法的核心是“模拟”一种自然现象，也就是玻璃和金属的退火，并将其内在逻辑应用于难题解决。为了生产出钢铁，要先将铁矿石加热，然后缓慢冷却，也就是“退火”，使分子排列整齐，从而变成钢。加热会使东西分子起来，而冷却则使分子对齐。运用这种方法来解决难题，正是启发式可转移性的一个很好的例子。

在大多数情况下，模拟退火算法与拓扑启发式有些类似。它在当前的解决方案附近搜索新的解决方案，如果发现了一个更好的解决方案，就转向这个更好的。但有的时候，当它发现了一个更糟糕的解决方案时，也会转向那个解决方案。是否接受更糟糕的解决方案取决于某个特定的温度计划（temperature schedule）。说到底，这个计划制度就是温度不断下降的一个列表。可以把它想象为密歇根州从8月到1月的日平均气温表。它从温暖的27℃慢慢下降到冰点甚至更低。当温度比较高的时候，允许算法出错，也就是可以接受更糟糕的新解决方案，只要它们没有差得太离谱。这就是说，在一开始，模拟退火算法可以接受除了最大错误之外的所有错误，这样一来，它在搜索时就能够遍历整个解决方案空间。同时，由于它拒绝价值大幅度降低，所以模拟退火算法还能够趋向于那些具有更好解决方案的区域。

随着温度的降低，模拟退火算法变得越来越不能“容忍”更差的解决方案。可以这样想象，进入秋天后，随着天气越来越冷，要求越来越严格，而到了寒冷的冬天，就变成非常严格了。到了12月份气温非常低时，这种算法就很少接受更差的解决方案了。最后到了1月份，当温度下降到谷底，就只有价值更高的新解决方案才会被接受。也就是在这一点上，模拟退火算法退化成为爬山启发式（一种拓扑启发式），并在一个局部最优点上稳定下来。

接受新解决方案规则的形式化描述看起来非常复杂，但是要掌握它的内在逻辑完全不难。计算机科学家和物理学家所依赖的是一个包含了自然常数（e=2.718 28）的概率函数，当它提高到某个值时就接受新的解决方案。⁹幸运的是，只需将接受一个新解决方案的概率写成价值降幅（Decrease）与温度（Temp）的线性函数，也可以把握同样的逻辑。为了尽可能简单地说明这一点，假设所有价值函数的取值范围都介于0～100之间。有了这个假设，就把变量价值降幅的取值范围限定在了0～100之间。然后，将接受新的解决方案的概率写成如下百分比形式。

接受一个更糟糕的解决方案的概率＝（温度－价值降幅）%

如果温度等于90华氏度，那么大多数新的解决方案（除了那些非常不好的）都将会被接受。这意味着搜索不会止步于崎岖景观的某些小山丘上。随着温度的不断降低，算法越来越不“愿意”接受更差的解决方案。假设温度等于50华氏度，某个新的解决方案导致价值下降40（价值降幅等于40），那么算法只有10%的概率会接受这个新的解决方案。这很容易理解，因为这个新的解决方案确实是相当糟糕的。如果价值降幅等于1，那么算法有49%的概率会接受该解决方案。因此，这个算法接受小错误，但不接受大错误。最终，当温度下降到0华氏度时，它就只接受更好的新解决方案了。¹⁰

不过，模拟退火算法虽然很强大，但它也不是万能的。我们必须牢记“天下没有免费的午餐定理”。没有任何一个算法在所有问题上都比所有其他算法更好。但是，模拟退火算法并不只是一个简单的算法，它其实是一个算法“家族”的总称。只要改变冷却温度表，就能改变算法，从而部分解决“午餐成本高昂”的问题。

模拟退火算法无疑是一个非常有价值的计算搜索算法，但是它似乎离日常生活中的问题有点远。说人们在篮球场上进行求导计算，也许有一些道理的，但是说人们在篮球场上应用冷却温度表，那就可能有点与现实脱节了。但是在真实世界中，确实有很多人一直在运用类似模拟退火算法的启发式，只不过，通常不说他们在“模拟退火”。而称他们在举行“头脑风暴”会议。¹¹

“头脑风暴”确实是在模拟“模拟退火”。要说明这一点，不妨考虑一群面临一个重大难题的人，比如说，如何为一个大城市设计地标性的音乐大厅。在8月份的时候，他们可能会首先抛出许多解决方案。不难想象，“由于在高温季节”，这个团队愿意容忍很多错误。到了10月份，他们可能会将某个解决方案列为主要备选方案，同时只考虑至少与当前这个解决方案一样好的其他方案。如果是这样，就可以认为他们在使用模拟退火算法，它有一个冷却温度表。在这个解决问题的过程接近终点时，可以假设为1月份，这时他们就只能接受改进。如果是这样，他们其实是在进一步降低算法的温度。虽然这个团队从来不记录温度，也从来不会把常数e放入某个次方中去计算，但是他们确实变得越来越有鉴别力。他们在“退火”。

个人也经常使用模拟退火算法的启发式。例如，要决定去哪里度假，开始时会想象所能去的任何地方。然后，会变得不那么愿意考虑新的、不能令人动心的替代方案。最终，除非能够改进目前已有的最好的方案，否则我们不会考虑任何其他方案。虽然我们在“退火”，但是可能无法做到以正确的速度“冷却”下来。我们可能“冷却”得太快，导致过早锁定方案；也可能会花费太多的时间来处理各种可能的备选方案。

允许错误启发式在为难度较高的问题找到较好的解决方案时的强大威力，恰恰体现了多样性启发式和多样性视角的优势。即使某个不同的启发式或视角让人找到了一个更糟糕的新解决方案，但从长远的角度来看，这个糟糕的新解决方案也可能是有益的，因为它可以防止我们陷入局部最优点。这里并不是说所有不好的解决方案都是有益的，但是在很多时候，一个价值较低的新解决方案可能会指向一个更好的解决方案。当然关键是，即使走上了一条不如当前解决方案所指的道路，也总是可以追溯每个步骤。但是，任何一个人，或者至少是一个曾经丢掉过车钥匙的人都知道，再走一遍走过的路并不像听起来那么容易。所以，还是要足够小心，一路上时刻注意留下一些可以追踪的痕迹。