跳转至

12:Local Search

我想从一个非常有名的算法——模拟退火——来引入这个话题。模拟退火的描述是这样的：

模拟退火

假设有一只喝醉的兔子，在一维的山上游走。起初的时候遇到更高的地方就会往上走，随着渐渐酒醒，逐渐冷静下来，不再接受更高的地方。

这个兔子爬高的过程就是本次要介绍的局部搜索(Local Search)。这事实上是近似算法的很重要的一类，它的大致思想就是希望通过不断取局部最优解从而达到全局最优解。

在接下来的介绍中，将会涉及一些平凡的定义，列举如下：

定义

  • Neighbor Relation: 两个解称为邻居当且仅当一者可以在一步内转化为另一者，记为 \(S\sim S'\)
  • Neighborhood: 指某个解的所有邻居的集合，记为 \(\{S':S\sim S'\}\)

此时，我们有一种最朴素的局部搜索做法，我们称之为梯度下降法(gradient descent)，也就是每次取所有邻居里最优的解，若比当前优，则转移，直到邻居中没有比当前优的。

接下来，我们通过几个问题来逐步深入研究局部搜索。

The Vertex Cover Problem

问题描述

给定一张无向图，选取最少的点，使得每条边都至少有一个端点被选取。

定义解 \(S\) 为选点的集合，代价是点集合的大小。我们从 \(S=V\) 开始，不断删去点来得到 \(S'\)，若删去后仍满足条件，那么令 \(S=S'\)。这就是梯度下降的做法。

但是这个做法很容易掉进一个局部优解但是全局劣的解中难以退出，比如我们以菊花图为例，如果我第一步就删去了中心节点，那么就直接掉入了 \(n-1\) 个点的劣解，按梯度下降的方式永远不可能再得到最优解——只保留中心点。

此时，我们提出一个新的想法，要是我们能够在取邻居的时候，就算邻居都劣于当前解，仍以一定概率取邻居。这样我们就有可能跳出当前局面，重新找全局最优解。该做法称为 The Metropolis Algorithm，伪代码如下：

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); 
        CurrentCost = cost(_S);
        if ( CurrentCost < MinCost ) {
            MinCost = CurrentCost;    S = _S;
        }
        else {
            With a certain probability, let S = _S;
            else break;
        }
    }
    return S;
}

代码中的 certain probability 通常会取 \(e^{-\frac{\Delta cost}{kT}}\)，这就是模拟退火，模拟了物理场景中温度 \(T\) 不断降低从而达到一个稳定态的过程。至于为什么是这个值，事实上这与统计物理相关，我们可以简单理解为活化能，物质总是希望趋向能量较低的状态，因此随着温度降低，物体能够自动地找到整个解空间中最低的那个。

Hopfield Neural Networks

接下来我们讨论另外一个问题。

问题描述

给定一张无向带权图，每个点可以赋点权为 \(s_u=\pm 1\)，求所有边中权值乘上其端点后为负数的，求和最小是多少。（边权有正有负）

此处将问题简化了，课件中是用一种感性地方式让这个题变得合理。它说的是：在这张图中，边代表着与两个点状态相关的事件。

  • 如果 \(w>0\)，那么我们希望两边状态不同；
  • 如果 \(w<0\)，那么我们希望两边状态相同；
  • \(|w|\) 代表着我们希望该要求被满足的强烈程度。

如此一来我们便能更好地认识这个题目。显而易见的是，我们不可能让所有边都得到满足。因此我们尝试找这个边权乘上点权之和最小是多少。然而事实上，这个问题是比较难的，我们先从一些定义入手。

definitions

  • 好边(good edge)：我们称一条边 \(e=(u,v)\) 是好的，当且仅当 \(w_es_us_v<0\)，也就是被满足了；
  • 满足点(satisfied node)：我们称一个点 \(u\) 是被满足的，当且仅当与之相邻边权乘上点权的和非正，即 \(\sum_{v:e=(u,v)\in E}w_es_us_v\leq 0\)；
  • 稳定态(stable)：我们定义一种赋值状态稳定，当所有点都被满足。

那么我们现在就能得到一个求稳定态的算法：每次找一个不满足的点，将其状态翻转。

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

我们可以分析每次翻转后，\(\sum_{e\,is\,good} s_us_vw_e\) 一定会变小，因为翻转一个点相当于翻转了与之相邻的边的正负，要是该点原先未满足，则在翻转前边权乘点权和应当大于零，因此翻转后小于零，总的和是减小的。并且至少减少 \(1\)，那么由于上界是由 \(\sum|w_e|\) 给出，所以该算法必然会停止，复杂度也就是 \(O(\sum|w_e|)\)。事实上这个想法可以被正式地写成势能分析的过程，不过我觉得比较简单没有必要。

然后我们从局部搜索的视角来看这个做法，很显然，如果我们把邻居定义成翻转一个点后得到的状态，那么我们得到的局部最大值应当是一种稳定态。同样，我们所得到的稳定态也一定是局部的一个最优解，此时翻转任何一个点都会导致答案更劣。这样我们在此处使用模拟退火就能得到一个比较好的结果。

一个不幸的消息是，目前仍然没有找到针对该问题的多项式时间算法，甚至是难以在多项式时间内找到一种稳定布局。

Maximum Cut Problem

问题描述

给定一张无向正边权图，将点染色，求所有两端颜色不同的边的权值和最大是多少。

事实上这个问题就是 Hopfield Neural Networks 问题的一个特殊情况：所有边权保证为正。

那我们挪用之前 Hopfield Neural Networks 问题的解法，在局部搜索的视角下，只要我们能够找到稳定态，我们就能通过模拟退火来得到更优的解。但是我们此处更关心的，是我们在这种特殊情况下，找稳定态的这个算法得到的结果有多好？以及我们是否可以做到更快，比如说 polylog？最后我们尝试去找一种更好的方式来求稳定态，从而得到更好的解。

How good is this local optimum?

要衡量一个近似算法的好坏，就要求我们计算近似比。我们先给出结论，这个做法是 2-近似的。下面给出具体证明。

proof

我们定义 \(W(A,B)\) 为当前稳定态的染色状态的答案，\(A\) 中的染白色，\(B\) 中染黑色。\(W(A^*,B^*)\) 代表全局的最优解。首先由稳定态，我们翻转任何一个点的颜色，答案会变得更劣，即对于一个点 \(u\) 与 \(A\) 中相邻点的边权和小于 \(B\) 中相邻点的边权和。

\[ \forall u\in A,\sum_{v\in A}w_{u,v}<\sum_{v\in B}w_{u,v} \]

那么同理我们可以得到：

\[ \forall u\in B,\sum_{v\in B}w_{u,v}<\sum_{v\in A}w_{u,v} \]

现在我们将所有 \(A\) 中的点相邻边权和加起来，相当于是两倍的 \(A\) 中的边权和，有：

\[ 2\sum_{u,v\in A}w_{u,v}=\sum_{u\in A}\sum_{v\in A}w_{u,v}<\sum_{u\in A}\sum_{v\in B}w_{u,v}=W(A,B) \]

同理，有：

\[ 2\sum_{u,v\in B}w_{u,v}=\sum_{u\in B}\sum_{v\in B}w_{u,v}<\sum_{u\in B}\sum_{v\in A}w_{u,v}=W(A,B) \]

然后考虑最终答案一定不大于所有边权和：

\[ W(A^*,B^*)\leq \sum_{u,v\in A}w_{u,v}+\sum_{u,v\in B}w_{u,v}+W(A,B)< 2W(A,B) \]

事实上，如今对于这个问题，我们已经能够做到 1.1382-近似了，这个值似乎是 \(\min_{0\leq \theta\leq\pi}\frac{\pi}{2}\frac{1-\cos\theta}{\theta}\)。

如果能够证明 P=NP，则会有一个 \(\frac{17}{16}-\)近似的算法。

May NOT in polynomial time

之前我们说过，我们没法找到多项式时间内求稳定态的算法。但是在最大割问题这种特殊情况下，我们可以稍加改进来得到一个多项式时间内的解法。核心思想就是，如果翻转的提升不够大我们也不进行翻转。比如说，对于当前答案 \(W(A,B)\)，如果翻转的提升不到 \(\frac{2\epsilon}{n}W(A,B)\)，我们也不进行翻转。对于该算法，我们有如下两个结论：

  • 该算法是 \((2+\epsilon)-\)近似的；
  • 该算法最多的翻转次数为 \(O(\frac{n}{\epsilon}\log W)\)

前者的证明过程和之前类似，不再赘述。我们来证明它的时间是多项式内的：

proof

也就是说，每次翻转我们答案至少提升至 \((1+\frac{2\epsilon}{n})\) 倍；同时我们有 \(\forall x\geq 1,(1+\frac{1}{x})^x\geq 2\)。我们把 \(\frac{n}{2\epsilon}\) 带入 \(x\)，那么当 \(\epsilon\) 取小值的时候显然是有 \((1+\frac{2\epsilon}{n})^{\frac{n}{2\epsilon}}\geq 2\) 的，也就是说每 \(\frac{n}{2\epsilon}\) 次翻转，答案至少提升 \(2\) 倍，而答案最多是 \(W=\sum{w_e}\) 的，所以最多翻转次数为 \(O(\frac{n}{\epsilon}\log W)\)。

Try a better local

接下来我们尝试找更好的局部最优解，从而提升通过模拟退火得到全局最优解的概率。当然，我们会付出相应的时间的代价。

优化局部搜索解，关键在于优化邻居的选取。此前我们邻居是在当前状态下只翻转一个点。于是我们考虑翻转 \(k\) 个点。但是不难发现，如果考虑翻转 \(k\) 个点的最优解，复杂度应当与组合数相关，也就是指数级的，虽然这个局部解会比较优秀，但是我们无法承受这样的时间代价。

于是我们有一种新的算法，K-L 启发式算法(K-L heuristic)。它的做法是，每次在当前未翻转的所有点中选一个最优的点翻转，这样做 \(n\) 次会得到 \(n\) 个邻居，此时再从这 \(n\) 个邻居中选一个最优的。这种做法兼顾了时间和邻居的范围，每一次都能有 \(n\) 个邻居供给选择，因此也更容易找到最优解。同时，朴素实现下，时间复杂度也只有 \(O(n^2)\)，如果加入数据结构应该还能做到更快求出这 \(n\) 个邻居。