对于问题求解，局部搜索算法先从问题的一个可能解出发，在该解的临近域中，寻找一个符合某种标准的解（例如使目标函数的值最大或最小），用这个解取代原来的解，继续迭代，直到总迭代次数达到预设的上限，或在一定次数的连续迭代中，可能解一直未能得到改进，或在当前的迭代中，得到的可能解明显为最优解。

       通常情况下，局部搜索算法是不完备的，即不能保证找到问题的解（最优解）。其原因正在于算法的“局部”性。首先，算法本身不提供回溯机制，因此不能保证对整个解空间进行搜索；其次，每次迭代时，只是依据有限的局部（临近域）信息来选择下一个解，这样很容易使算法陷入局部的最优解中。

      于是，很自然的一个问题是，是否存在有完备的局部搜索算法？如果从问题的原因入手去寻找答案似乎是不可能的。因为如果在算法中引入回溯机制，那就不成为局部搜索算法了，并且相应的算法效率也必将大大降低；同样也更加不可能在每次迭代时，对整个解空间的解进行比较。耶鲁大学的Fang和Palo Alto研究中心的Ruml提出了一个完备的局部搜索算法框架，这种方法另辟蹊径，将原初的问题进行转换（当然必须保证转换后问题的解不变），并且巧妙地选择目标函数，使得在问题的解空间中，对应于新的目标函数，只存在全局的最优解而不存在局部的最优解。这样，只要每次迭代都能改进原有的解，我们就让迭代一直进行下去，那么得到的局部搜索算法也就是完备的了。

      新的问题是，Fang和Ruml的方法以SAT问题为例，但对其它问题，我们又该如何对问题进行转换，如何选择目标函数使得局部最优解不存在？似乎没有通用的方法。