Local Search¶

约 656 个字 48 行代码 9 张图片预计阅读时间 5 分钟

引入¶

旨在找到问题的近似解。

定义一个邻域（Neighborhood），在邻域中进行搜索，一步步逼近全局最低点。

alt text

Framework of Local Search¶

Local
- 在可解集中定义邻域
- 局部最优解就是邻域内的最优解
Search
- 先从可行的解决方案开始，然后在附近寻找更好的解决方案
- 如果没有改进的可能，则达到局部最优

定义以下：

\(S ～ S'\): \(S'\) is a neighboring solution of \(S - S'\) can be obtained by a small modification of \(S\).
\(N(S)\) is the neighborhood of \(S\) – the set \(\{ S': S ～ S' \}\).

C
SolutionType Gradient_descent()
{   Start from a feasible solution S in 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;
}

经典案例：顶点覆盖问题¶

顶点覆盖问题：给定一个无向图 \( G = (V, E) \)。找到 \( V \) 的一个最小子集 \( S \)，使得对于每条边 \( (u, v) \in E \)，\( u \) 或 \( v \) 在 \( S \) 中。

可行解集：所有顶点
cost(S) = |S|
S ~ S': S'可以由S（加上或）删除一个点

alt text

The Metropolis Algorithm¶

C
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 probability e^{\delta cost/kT}, let S = S’;
            else  break;
        }
    }
    return S;
}

Note

对于case 1，有一定概率可以跳出local optimum得到正确解。但是对case 0，有可能在加1和减1之间无限震荡……
当（温度）T很高时，上坡的概率几乎为1，容易引起底部震荡；当T接近0时，上坡概率几乎为0，接近原始的梯度下降法。
温度的设计是关键！

Simulated Annealing¶

温度逐渐降低。设计出一个温度表： Cooling schedule: \(T = \{ T1 , T2 , … \}\)

经典问题：Hopfield Neural Networks¶

Graph \(G = (V, E)\) with integer edge weights \(w\) (positive or negative).

If \(w_e < 0\), where \(e = (u, v)\), then \(u\) and \(v\) want to have the same state (+1 or -1);
If \(w_e > 0\), then \(u\) and \(v\) want different states.

我们易知满足条件的边满足\(w_eS_uS_v < 0\)。满足此条件的称为好边，反之坏边。点\(u\)是满足的如果关联好边的权重大于坏边的权重。

Problem: To maximize \(\Phi\).
Feasible solution set FS : configurations
S ~ S': S' can be obtained from S by flipping a single state

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

每一个步骤都增加了好边的权重。

Note

每一个局部最优解都是稳定的。所以不一定是全局最优解。

如何证明最多需要边的权重次翻转？

alt text

经典问题：The Maximum Cut Problem¶

Maximum Cut problem: Given an undirected graph \(G = (V, E)\) with positive integer edge weights \(w_e\), find a node partition \((A, B)\) such that the total weight of edges crossing the cut is maximized.

Note

所有边都是正整数！

Problem: To maximize \(w(A, B)\).
Feasible solution set \(FS\) : any partition of \((A, B)\)
\(S ～ S'\): \(S'\) can be obtained from \(S\) by moving one node from \(A\) to \(B\), or one from \(B\) to \(A\).

转化为Hopfield Neural Networks：团内接坏边，团外接好边（因为好边的权重大于坏边）

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