近几十年来，局部搜索算法已经在各个领域中都有着十分广泛的应用，尤其是针对一些相对复杂的优化问题。局部搜索算法作为一种比较通用的优化算法，可以被方便的应用于具体的优化问题，这也是它的一个主要的有点。迄今为止，人们已经根据不同问题提出了很多种有效的局部搜索算法，例如牛顿法，最速下降法，禁忌搜索算法等。这些算法都有着十分广泛的应用：84390

（1）最早的一种局部搜索算法是由Lin提出的K—OptRoutine，被用来解决旅行商问题(TravelingSalespersonProblem)[2][3]。

（2）1983年，一个里程碑式的局部搜索算法——模拟退火算法被Kirkpatrick，Gelatt和Vecchi提出[4]，它的出发点是基于物理中固体物质的退火过程与一般组合优化问题之间有着相似性，和以往的局部搜索算法相比，模拟退火算法最大的特点就是它允许概率的接受恶化解。模拟退火算法最早在电路设计中的优化问题得到应用，随后更多的研究者将模拟退火算法应用于其它的问题。关于模拟退火算法最近的应用，可以参见[5]。论文网

（3）1986年，Glover首先提出了禁忌搜索算法[6][7]，而且将其应用于电路设计，组合优化，机器学习的领域。

局部搜索算法在实际的应用中被认为一种简单且高效的启发式算法，因为它的原理十分容易理解，所以受到了人们越来越多的重视，被应用于物理，工程，管理学，生物信息学等领域中遇到的各种组合优化问题，它已经成为最成功和最令人瞩目的启发式算法。

最早在二十世纪50年代，人们开始对局部搜索算法开始进行研究，至今为止，局部搜索算法在人工智能、运筹学等许多领域都得到了应用。局部搜索算法是一种贪心的算法，它能对初始解附近领域的区域进行搜索，有着思路简单并且易于实现的有点，但是也正因为如此，局部搜索算法的效果受到了很多条件的影响，比如初始解的质量，领域的定义方式，这使得局部搜索算法在实际应用中很容易陷入局部最优。为了避免这一情况的发生，人们研究并提出了一些解决的方法，1、在某些特定的情况下，允许算法接受劣等的解。2、对以前已经访问过的领域进行记录，并在以后的访问过程中禁止对这些区域再次访问。3、扩大算法的搜索范围。4、用动态改变程序状态的方式来改变邻域的结构。因此，不难看出如何对领域进行定义和跳出局部最优解得研究是局部搜索算法研究的核心问题。