随机局部搜索（random local search），理学-计算机科学技术-计算机科学理论-算法-随机算法，一种通过随机决策来避免陷入局部最优解的解决组合优化问题的启发式方法。局部搜索指的是从一个候选解出发，反复搜索当前解在候选解空间中的邻域并用更优解取代当前解，直至无法改进（当前解已是局部最优解）或者达到指定迭代次数。局部搜索具有简单、灵活及易于实现等优点，因此作为一种简单且高效的启发式算法被广泛地应用于计算机科学、数学、运筹学、工程学、生物信息学等很多领域。另一方面，局部搜索的缺点也是显而易见的，即算法容易陷入局部最优而无法找到全局最优解，且解的质量与初始解和邻域的结构密切相关。为了避免上述缺点，很多局部搜索算法通过随机决策来产生或者选择候选解，这类局部搜索算法都可以称之为随机局部搜索。比较常见的随机局部搜索算法有模拟退火、禁忌搜索、爬山法等。随机局部搜索在一些NP完全问题已经取得了成功的应用：比如可满足性问题、最小顶点覆盖问题等。随机局部搜索算法中的核心问题主要包括几个方面：如何定义相邻关系；如何评估两个邻居解的好坏；如何跳出局部最优解；如何在多样性和探索性之间进行平衡。