局部搜索

在计算机科学中，局部搜索是解决最优化问题的一种元启发式算法。局部搜索从一个初始解出发，然后搜索解的邻域，如有更优的解则移动至该解并继续执行搜索，否则返回当前解。局部搜索的优点是简单、灵活及易于实现，缺点是容易陷入局部最优且解的质量与初始解和邻域的结构密切相关。常见的改进方法有模拟退火、禁忌搜索等。

局部搜索广泛应用于计算机科学（主要是人工智能）、数学、运筹学、工程学、生物信息学中各种很难找到全局最优解的计算问题。

应用

对于某些计算起来非常复杂的最优化问题，比如各种NP完全问题，要找到最优解需要的时间随问题规模呈指数增长，因此诞生了各种启发式算法来退而求其次寻找次优解。局部搜索就是其中的一种方法。

局部搜索算法可以用来解决以下问题：

1. 最小顶点覆盖问题：寻找图中包含最少顶点的覆盖。
2. 旅行商问题：寻找图中经过所有顶点的最短回路。
3. 布尔可满足性问题：寻找满足一组子句的变量赋值。

描述

局部搜索算法从一个候选解开始，反复探索其邻域，并移动到邻域中的最后解。所以要使用局部搜索算法必须首先在搜索空间中定义邻域。比如，在最小顶点覆盖问题中，一个覆盖的邻域可以是只改变一个顶点能够到达的另一种覆盖；在布尔可满足性问题中，一个变量赋值的邻域可以是只改变一个变量的值能到达的所有赋值。对于同一个问题可以有很多种邻域的定义。如果一个局部优化算法将邻域定义为只改变 k 个成分能够到达的解，那么这个算法可以称为 k-opt。

通常，每个候选解的邻域包含多个解。所谓局部搜索，就是只根据邻域中的信息来决定移动方向。如果选择的是最大化目标函数的解，那么这种局部搜索算法又可以叫做爬山算法。当邻域中已经没有比当前最优的解的时候，局部搜索就困在了局部最优解。

为了离开局部最优解，可以使用很多种方法，包括在不同的初始值重复整个算法，或者使用更复杂的策略如模拟退火。

局部搜索可以设计成在运行足够长时间后终止，或者连续n步没有改善时终止。所以局部搜索是一种任一时间算法：即便它运行中被强行中止，也能返回正确的解。

局部搜索是典型的近似算法，因为它找到的解不一定是最优的。即便没有中断算法执行，也可能因为陷入局部最优而无法找到更好的解。

对于某些问题，可以定义一个非常大的邻域，甚至是指数级大小的邻域，只要在邻域中能够高效地找到最优解。这样的算法叫做大规模邻域搜索。

参见

局部搜索属于以下领域：

• 启发式算法
  • 元启发式算法
• 最优化
  • 随机最优化

局部搜索包括以下话题：

• 爬山算法
• 模拟退火
• 禁忌搜索

参考资料

• Battiti, Roberto; Mauro Brunato; Franco Mascia. Reactive Search and Intelligent Optimization. Springer Verlag. 2008. ISBN 978-0-387-09623-0. （原始内容存档于2012-03-16）. 
• Hoos, H.H. and Stutzle, T. (2005) Stochastic Local Search: Foundations and Applications, Morgan Kaufmann.
• Vijay Arya and Naveen Garg and Rohit Khandekar and Adam Meyerson and Kamesh Munagala and Vinayaka Pandit, (2004): Local Search Heuristics for k-Median and Facility Location Problems （页面存档备份，存于互联网档案馆）, Siam Journal of Computing 33(3).