局部搜索算法

7.6.2 局部搜索算法

到目前为止，我们在本书中已经见到多种局部搜索算法，包括 HILL-CLIMBING（第 4.3.1 节）和SIMULATED-ANNEALING（第4.3.2节，图4.14）。这些算法可以直接应用于可满足性问题，倘若我们能选择出正确的评价函数。因为目标是寻找满足每个子句的一个赋值，统计未满足子句的数量的评价函数将负责这项工作。实际上，这正是CSP中（第5.3节）MIN-CONFLICT算法采用的度量。所有这些算法涉足完全赋值空间，每次翻转一个符号的真值。该赋值空间通常包括很多局部极小点，为了避开局部极小值，需要采用不同形式的随机方法。近年来，人们做了大量实验以便找到贪婪性和随机性之间的良好平衡点。

WALKSAT（图7.17）是从所有的这类工作中涌现出来的最简洁有效的算法之一。算法在每次迭代中选择一个未得到满足的子句并从该子句中选择一个符号对其进行翻转操作。它在两种方法中随机选择一个来挑选要翻转的符号：(1)“最小冲突”步骤，最小化新状态下未满足语句的数量，以及(2)“随机行走”步骤，随机挑选符号。

图7.17 通过随机翻转变量值的方法检验可满足性的WALKSAT算法。算法存在多种版本

WALKSAT 是否真的可行？显然，如果它返回一个模型，那么输入语句确实是可满足的。如果它返回failure会怎么样呢？不幸的是，对于这种情况，我们无法断定语句是否不可满足，或者我们需要给算法更多的时间。我们可以试图把max-flips设置为无穷大。如果那样的话，很容易证明WALKSAT最终将返回一个模型（如果存在），倘若概率p＞0。这是因为总是存在引向可满足赋值的翻转序列，而且最终随机行走步骤将生成那样的序列。哎呀，如果max-flips无穷大，而且语句是不可满足的，那么算法永远不会终止！

这表明，在我们期望存在解时，诸如WALKSAT这样的局部搜索算法是最有用的——例如，第三章和第五章中讨论的问题通常是有解的。另一方面，局部搜索算法无法每次都检验出蕴涵判定所需要的不可满足性。例如，智能体无法用局部搜索来可靠地证明wumpus世界中的某个方格是安全的。相反，它可以说：“我对此考虑了一个小时，无法给出该方格不安全的某个可能世界。”如果通常局部搜索算法在寻找某个存在的模型时确实很快，智能体可能进行调整，假设未能找到模型意味着不可满足性。当然，这不等同于证明，而且当智能体把它自己的生命作为赌注压在上面之前，它需要三思而后行。