12.Local Search

约 1594 个字 10 行代码预计阅读时间 5 分钟

1. 概述¶

做一个初始的猜测，然后在猜测的点周边，用更优解来替代猜测的点，不断迭代逼近最优解。所以局部搜索的想法就是从不准确的解作为开始，不断搜索该点周围更加接近最优的解来替代，如此重复来逼近最优解。逼近最优解不一定会在有限步骤内停止。

Local Search的结构

from Carton手写笔记

算法：

可行解作为一个起点；
在S的邻居中按照某一种规则去找到其中的一个更加接近最优解的邻居。
如果最好的邻居都比自己差，那么算法结束；否则，把当前点移动到邻居身上。

2. 顶点覆盖问题¶

问题概述：在无向图中找最小的点集，对于每一条边，至少有一个点在点集中。

构造算法：首先需要找到一个可行解，直接取所有的点为起始解。cost(S)定义为S中点的个数。S'是S的邻居，S'从S中去掉一个点得到。

案例：

Metropolis算法

相比于原来的梯度算法，红色是改动的部分。我们随机选出来一个点，如果比当前的解要好，那么正常进行替换；如果更差的话，仍旧会有一定的概率替换成新的点。相比于原来的解，cost越大替换概率越低。

T如果特别大，那么替换概率为1，如果T特别小，那么就是原来的算法，替换概率几乎为0。随着算法的推进，替换概率越小越好，也就是T越小越好。

思考算法的结束时间，一种可行的想法是当概率小到某个阈值之下就结束。

Simulated Annealing 模拟退火算法

随着算法的迭代，越来越接近最优解，所以T越来越小（模拟温度降低），上升替换概率也越来越小。

3. Hopfield Neural Networks¶

相关定义

给定有权图，如果边的权重小于零，那么两个端点有相同的状态，如果权重大于零，那么两个端点有不同的状态。权重的绝对值越大，那么这条边越重要。定义好边和坏边(好边就是满足上述条件的边) \(w_es_us_v < 0\)。

对于一个顶点，如果其好边权重大于坏边权重则称之为满足结点。

如果所有结点都是满足的，那么这个图就是稳定的。

State-flipping Algorithm

如果根本就没有一个可行解，那么这个算法就会死循环

C

ConfigType State_flipping()
{
    //从一个随机的解开始
    Start from an arbitrary configuration S;
    while ( ! IsStable(S) ) {
        u = GetUnsatisfied(S); //每次随机找一个不满足的结点
        $s_u$ = - $s_u$; //把这个结点进行变色
    }
    return S;
}