2.5 局部搜索 (Local Search)
作为最后一个感兴趣的话题，回溯搜索并不是解决约束满足问题的唯一算法。另一种广泛使用的算法是局部搜索 (local search)，其思想极其简单但非常有用。局部搜索通过迭代改进来工作——从某个随机的值赋值开始，然后迭代地选择一个随机的冲突变量，并将其值重新分配给违反最少约束的值，直到不再存在违反约束的情况（这种策略称为最小冲突启发式 (min-conflicts heuristic)）。在这种策略下，像 \(N\)-皇后这样的约束满足问题变得非常节省时间和空间。例如，在下面 4 个皇后的例子中，我们仅迭代 2 次就找到了解：
事实上，局部搜索似乎几乎以恒定时间运行，并且不仅对于任意大 \(N\) 的 \(N\)-皇后问题，而且对于任何随机生成的 CSP 都有很高的成功概率！然而，尽管有这些优点，局部搜索既不完备也不是最优的，因此不一定会收敛到最优解。此外，存在一个临界比率，在这个比率附近使用局部搜索会变得非常昂贵：
上图显示了状态空间上目标函数的一维图。对于该函数，我们希望找到对应于最高目标值的状态。局部搜索算法的基本思想是，从每个状态开始，它们局部地向具有更高目标值的状态移动，直到达到最大值（希望是全局最大值）。
我们将介绍三种这样的算法：爬山法 (hill-climbing)、模拟退火 (simulated annealing) 和 遗传算法 (genetic algorithms)。所有这些算法也用于优化任务，以最大化或最小化目标函数。
2.5.1 爬山搜索 (Hill-Climbing Search)
爬山搜索算法（或最陡上升 (steepest-ascent)）从当前状态移动到增加目标值的相邻状态。该算法不维护搜索树，只维护状态和相应的目标值。爬山法的“贪婪”使其容易陷入局部最大值 (local maxima)（见下图），因为在局部这些点对算法来说就像全局最大值，以及高原 (plateaux)。高原可以分为“平坦”区域，在这些区域没有任何方向可以导致改进（“平坦局部最大值”），或者进展缓慢的平坦区域（“肩部”）。已经提出了爬山法的变体，如随机爬山法 (stochastic hill-climbing)，它在上升移动中随机选择一个动作。这种版本的爬山法在实践中已被证明可以收敛到更高的最大值，但代价是更多的迭代次数。
爬山法的伪代码如上所示。顾名思义，算法迭代地移动到具有更高目标值的状态，直到无法取得进展。爬山法是不完备的。另一方面，随机重启爬山法 (Random-Restart hill-climbing) 进行多次爬山搜索，每次都从随机选择的初始状态开始，这在平凡意义上是完备的，因为在某个时刻随机选择的初始状态将与全局最大值重合。
2.5.2 模拟退火搜索 (Simulated Annealing Search)
我们将介绍的第二个局部搜索算法是模拟退火。模拟退火旨在结合随机游走（随机移动到附近状态）和爬山法，以获得完备且高效的搜索算法。在模拟退火中，我们允许移动到可能降低目标值的状态。更具体地说，算法在每个状态选择一个随机移动。如果移动导致更高的目标值，则总是接受它。另一方面，如果它导致更小的目标值，则以一定的概率接受该移动。这个概率由温度参数决定，初始时温度很高（允许更多“坏”的移动），并根据某种时间表降低。如果温度降低得足够慢，那么模拟退火算法将以接近 1 的概率达到全局最大值。
2.5.3 遗传算法 (Genetic Algorithms)
最后，我们介绍遗传算法 (genetic algorithms)，它是局部束搜索的一种变体，也广泛用于许多优化任务。遗传算法从 \(k\) 个随机初始化的状态开始，称为种群 (population)。状态（或个体 (individuals)）表示为有限字母表上的字符串。为了更好地理解这个主题，让我们回顾一下课堂上介绍的 8-皇后问题。对于 8-皇后问题，我们可以用一个 1-8 的数字来表示八个个体中的每一个，代表每个皇后在列中的位置（图 4.6 中的列 (a)）。每个个体都使用评估函数（适应度函数 (fitness function)）进行评估，并根据该函数的值进行排名。对于 8-皇后问题，这是不互相攻击的皇后对的数量。
选择一个状态进行“繁殖”的概率与该状态的值成正比。我们根据这些概率选择成对的状态进行繁殖（图 4.6 中的列 (c)）。后代是通过在交叉点交叉父代字符串产生的。每个对的交叉点是随机选择的。最后，每个后代都有一定的独立概率发生随机突变。遗传算法的伪代码如下图所示。
遗传算法试图在探索状态空间并在线程之间交换信息的同时向上移动。它们的主要优势是使用了交叉，因为这允许已经进化并导致高估值的大块字母与其他这样的块结合，产生具有高总分的解。