这两天看了一些局部搜索的内容，笔记如下。
- 梯度下降法
最简单的一种方法，对给定的解，搜索其邻域解，若邻域中有更优的解（根据给定的评估函数评定），则移动至该邻域解，继续寻找，直至找不到为止。此时，就找到了局部最优解。 方法非常简单，但是缺陷也很明显，即陷入到局部最优解之后无法跳出。
- 模拟退火算法
算法框架与第一种没有差别。 简单描述一下，该方法增加了根据概率跳出局部最优的特性，即当陷入局部最优之后，以一定概率使其可以往比当前最优解更差的解转移，从而跳出局部最优。 这还不是模拟退火。只是简单增加了概率跳出的特性。这一特性增加也同样存在缺陷，即对于全局最优解，也存在一定概率跳出，从而使得求解过程不稳定。 模拟退火算法，是要求概率根据算法进行过程中，逐步降低其跳出局部最优的概率，使其越来越趋于稳定。对于物理过程来说，这个概率是
e^(-E/kT) 其中T表示温度，可见当温度降低时，其概率缩小，而温度升高时，形态也处于不稳定状态。模拟退火算法正是模拟了这一过程。 当然这种算法也存在问题，即对于某些情况下，也不易达到全局最优。例如，解空间中仅有两个局部最优，其中一个是全局最优，那么模拟退火似乎并不一定总能进入到全局最优解当中。
总的来说，局部搜索的方法，就是依赖于对解空间进行按邻域搜索。对算法的优化或者调整，之前是按照概率进行跳出，除此之外，主要的改进还是针对邻域的选择上。这在算法设计上有比较多的说明。不过我想前面提出的基本上也足够我使用了。另外，其实也可以把一些多项式时间可解的优化问题，当作是邻域选择的特例，因为它找到了某种邻域选择方案，使其在多项式时间内直接确定的求解。