零基础学启发式算法（2）-局部搜索(Local Search)和爬山算法(Hill Climbing)

一、局部搜索（Local Search）

    局部搜索是一种近似算法（Approximate algorithms），是一种简单的贪心搜索算法。从一个候选解开始，持续地在其邻域中搜索，直至邻域中没有更好的解。

    邻域动作是一个函数，通过这个函数，对当前解s，产生其相应的邻居解集合。例如：对于一个bool型问题，其当前解为：s = 1001，当将邻域动作定义为翻转其中一个bit时，得到的邻居解的集合N(s)={0001,1101,1011,1000}，其中N(s) ∈ S。同理，当将邻域动作定义为互换相邻bit时，得到的邻居解的集合N(s)={0101,1001,1010}.

二、局部搜索算法的步骤描述如下：

 对于一个优化问题：

    其中，f(x) 为目标函数。搜索可以理解为从一个解移动到另一个解的过程，令 s(x) 表示通过移动得到的一个解，S(x) 为从当前解出发所有可能的解的集合 (邻域)。

1. 初始化一个可行解 x。

2. 该算法每次从当前解的邻域解空间中选择一个最好邻居作为下次迭代的当前解，直到达到一个局部最优解(local optimal solution)。在当前解的邻域内选择一个移动后的解 s(x)，使得 f(s(x))