局部搜索法

局部搜索法：

从搜索空间找一个解并评估其质量，将其定义为当前解；

变换当前解为一个新解并评估它的值；

如果新解优于当前解则替换当前解，否则放弃新解；

重复上述步骤直到找不到新解。

思考：

1.为什么要用局部搜索法？

2.为什么能用局部搜索法？（靠什么得到最优解）

3.应用局部搜索法的关键问题（必要性，可行性）（局部与枚举其实差不多）

答：

1.任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。例如，对于n个元素的排序问题，当n=1时，不需任何计算。n=2时，只要作一次比较即可排好序。n=3时只要作3次比较即可，…。而当n较大时，问题就不那么容易处理了。一般认为，NP完全问题的算法复杂性是指数级的。当问题规模达到一定程度时，要想直接解决一个规模较大的问题，有时是相当困难的。局部搜索算法的基本思想是在搜索过程中，始终选择当前点的邻居中与离目标最近者的方向搜索。局部搜索法是一种启发式搜索方法，有优先搜索的目标，期望在此指针下能够更快地找到最优解决方案。

2．

现实问题中，往往有多个局部的极值点。

一般的局部搜索算法一旦陷入局部极值点，算法就在该点处结束，这时得到的可能是一个糟糕的结果。解决的方法就是每次并不一定选择邻域内最优的点，而是依据一定的概率，从邻域内选择一个点。指标函数优的点，被选中的概率大，指标函数差的点，被选中的概率小。

考虑归一化问题，使得邻域内所有点被选中的概率和为1。

3.

关键问题是要注意局部陷阱。

还有起始点问题：

一般的局部搜索算法是否能找到全局最优解，与初始点的位置有很大的依赖关系。

解决的方法就是随机生成一些初始点，从每个初始点出发进行搜索，找到各自的最优解。再从这些最优解中选择一个最好的结果作为最终的结果。