局部搜索

昔孟母，择邻处

局部搜索（Local Search）是一种常用的优化方法，主要用于求解大规模的优化问题，尤其是那些解空间较大且不容易通过全局搜索找到最优解的问题。局部搜索算法从一个初始解出发，在当前解的邻域中不断进行探索，以寻找更好的解，直到满足某些停止条件。

具体来说，局部搜索的基本流程包括以下几个步骤：

1. 初始化：选择一个初始解。
2. 邻域搜索：通过某种方式生成当前解的邻域解，即在当前解的基础上进行微小的改变，得到一组相似的解。
3. 选择最优邻域解：从邻域解中选择一个“更优”的解，作为新的当前解。
4. 迭代：重复邻域搜索和选择最优邻域解的步骤，直到满足停止条件（如达到最大迭代次数、解的改进达到一定程度等）。

局部搜索通常用于求解 组合优化问题 （如旅行商问题、图着色问题等），尤其在搜索空间庞大的情况下，它通过聚焦在较小的局部区域内进行搜索，能够在较短的时间内找到一个较好的解，尽管该解不一定是全局最优。

局部搜索的一些常见变种包括：

• 爬山算法（Hill Climbing）：一种简单的局部搜索方法，通过选择邻域中最好的解逐步优化，直到没有更好的解为止。
• 模拟退火（Simulated Annealing）：在爬山算法的基础上引入了随机性，允许接受较差的解，从而避免陷入局部最优解。
• 禁忌搜索（Tabu Search）：通过维护一个禁忌表来记录已经访问过的解，防止算法反复访问已探索过的区域，从而提高搜索效率。

局部搜索的优点是计算效率高、实现简单，但其缺点是容易陷入局部最优解(到达了山谷而不是山底)。

局部搜索的框架

局部性(Locality)

• 需要在neighborhood中进行搜索，即在可行集中的邻域进行搜索

• 需要保证局部最优是 自身邻域 的全局最优

搜索

• 从一个可行解开始，每一次迭代都会在当前解的邻域中选择一个更好的解

• 达到局部最优当且仅当邻域内没有更好的解

伪代码

S $\sim$ S' : S' is a neighboring solution of S, whree S' can be obtained by a {==slight modification==} of S.

即对S进行一次小的改变，得到S'。

N(S): neighborhood of S – the set { S': S $\sim$ S' }.

SolutionType Gradient_descent()
{   Start from a feasible solution S  FS ;
    MinCost = cost(S);
    while (1) {
        S’ = Search( N(S) ); /* find the best S’ in N(S) */
        CurrentCost = cost(S’);
        if ( CurrentCost < MinCost ) {
            MinCost = CurrentCost;    S = S’;
        }
        else  break;
    }
    return S;
}

点集覆盖问题

{==Vertex Cover Problem==}

给定一个无向图$G=(V,E)$，以及一个正整数$K$，是否存在V的一个子集$C$，使得$C$中点的个数不超过$K$，且对于每一条边$(u,v)$ $\in$ $E$，至少有一个端点在$C$中。

{==Vertex cover problem (optimization)==}

在点集覆盖问题的基础上，找到最小的点集覆盖。

在这一问题中

• Feasible solution($\mathcal{FS}$): 所有点集覆盖的集合
• Cost(S) = |S|
• S $\sim$ S'

在点集覆盖中，每一个点集覆盖S至多有|V|个邻居，即N(S)的大小是有限的。

• search: Start from S = V; delete a node and check if S' is a vertex cover with a smaller cost.

Example

Case0,是正确的，依次删去所有点，最后得到的是空集，是一个点集覆盖。

Case1,是错误的，因为删除了一个点后，我们将最优解删去了；

改进

如果我们可以容忍暂时的代价升高，有可能会遇到代价降低更好的情况

SolutionType Metropolis()
{   Define constants k and T;
    Start from a feasible solution S in FS ;
    MinCost = cost(S);
    while (1) {
        S’ = Randomly chosen from N(S); //Adding is allowed
        CurrentCost = cost(S’);
        if ( CurrentCost < MinCost ) {
            MinCost = CurrentCost;    S = S’;
        }
        else {
            With a probability, let S = S’;
            else  break;
        }
    }
    return S;
}

模拟退火

基于玻尔兹曼分布，我们可以将Metropolis算法描述如下：

• 初始化：随机选择一个可行解 $S$，设 $S$ 的能量为 $E(S)$，并确定一个温度 $T$；

• 不断进行如下步骤：

(1) 随机选择 $S$ 的一个邻居 $S'$（可以按均匀分布随机选择）；

(2) 如果 $E(S') \leqslant E(S)$，则接受 $S'$ 作为新的解；

(3) 如果 $E(S') > E(S)$，则以概率 $e^{-(E(S')-E(S))/kT}$ 接受 $S′$ 作为新的解；如果接受了则更新解，继续下一轮迭代，否则保持原解 $S$，继续迭代。

直观地说，Metropolis算法就是在当前解S的邻居中随机选择一个解S′，如果S′的能量更低则接受，否则以一定概率接受一个更差的解——这就使得我们有可能跳出一个局部最优解。当然有一个注意的问题是，我们上面没有写算法的停止点，实际上进行到一个满意的结果中断算法即可。Metropolis等人证明了他们的算法具有如下性质

Hopfield 神经网络

Hopfield神经网络是一种全连接的反馈神经网络，于1982年由J.Hopfeld教授提出;Hopfield神经网络有一个能量函数，如果能将能量函数与一个优化问题绑定，那么Hopfield神经网络就可以用来解决这个优化问题，例如旅行商问题

Definition

1. Hopfield 神经网络可以抽象为一个无向图 $G = (V, E)$，其中 $V$ 是神经元的集合，$E$ 是神经元之间的连接关系，并且每条边 $e$ 都有一个权重 $w_e$，这可能是正数或负数：

2. Hopfield 神经网络的一个状态 (configuration) 是指网络中每个神经元 (即图的顶点) 的状态的一个取值，倾向值能为 1 或 -1。我们记顶点u的状态为 $s_u$。

3. 如果对于边 $e = (u, v)$，我们定义 $c_e = w_e s_u s_v$，我们希望$c_e < 0$

4. 我们将上述条件的边称为“好”的 (good)，而称为“坏”的 (bad)。

5. 如果我们一点是“满意的” (satisfied)，当且仅当它所连接的所有点中，好边的权重绝对值大于等于坏边的，即

$$\sum_{(u,v) \in E} w_{e(u,v)} s_v s_u < 0,$$

反之，如果不满足这一条件，我们称其为“不满意的” (unsatisfied)。

6.最后，我们称一个构型是“稳定的（stable）”，当且仅当所有的点都是满意的

局部搜索算法

如果要设计一个局部搜索算法，我想我们有一个非常简单直接的方式。在这一问题中，我们自然地就会定义一个构型的邻居就是将其中一个点的状态取反得到的新构型，然后我们就可以设计一个局部搜索算法了：我们从一个随机初始构型开始，然后检查每个点是否满意，如果有不满意的点，我们就翻转这个点的状态（那么这个点自然就变得满意了），然后继续检查，直到所有的点都满意为止。 如果这个算法会停止 ，那么停止的时候我们得到的就是一个稳定构型：因为所有点都满意了;

我们称为状态翻转算法（State flipping algorithm）：

ConfigType State_flipping()
{
    Start from an arbitrary configuration S;
    while ( ! IsStable(S) ) {
        u = GetUnsatisfied(S);
        su = - su;
    }
    return S;
}

最大割问题 (Max Cut)

最大割问题也是一个经典的 NP 困难问题，在这一问题中，我们希望将一个边权全为正的无向图 $G = (V, E)$ 的顶点集合 $V$ 分成两个集合 $A$ 和 $B$（这时的解记为 $(A, B)$），使得割边的权重和最大，其中割边的含义就是一条边的两个端点分别在 $A$ 和 $B$ 中，即我们要最大化

局部算法与最优解的关系

在最大割问题中，我们可以证明局部搜索算法的最优解和全局最优解之间的关系：局部搜索算法给出的局部最优解最差也不会低于最优解的一半

即

设 $(A, B)$ 是如上局部搜索算法得出的一个局部最优解，$(A^∗, B^∗)$ 是最优解，则

优化

事实上在控制迭代次数引起的复杂度时非常常用（这里就是求 $\Phi(S)$ 的局部最优值需要的迭代次数可能太多）。我们要求算法在找不到一个能对解有 “比较大的提升” 的时候就停止，即使当时的解不是局部最优解：

当我们处于解 $w(A, B)$ 时，我们要求下一个解的权重至少要增大$\dfrac{2\varepsilon}{n}w(A, B)$，其中 $n$ 是图 $G$ 的顶点数。对于这一算法，我们有如下结论：

设 $(A, B)$ 是如上局部搜索算法得出的一个解，$(A^∗, B^∗)$ 是最优解，则

并且这一算法会在 $O(\dfrac{n}{\varepsilon} \log W)$ 次状态翻转后停止，其中 $W$ 是所有边的权重之和