Lecture 12 | Local Search
这个东西本质上也是近似算法，得到的是局部最优解（找碗的最低点的例子）
这个算法在不同问题下的的框架相对固定，代码比较简单
Framework of Local Search
-
Local
- Define neighborhoods in the feasible set
- A local optimum is a best solution in a neighborhood
-
Search
- Start with a feasible solution and search a better one within the neighborhood
- A local optimum is achieved if no improvement is possible
Neighbor Relation
LS的关键是定义什么是邻居
\(S \sim S'\) : \(S'\) is a neighboring solution of \(S – S'\) can be obtained by a small modification of S.
\(N(S)\): neighborhood of \(S\) – the set \({ S': S \sim S' }\).
下面是Local Search的框架
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;
}
The Vertex Cover Problem
Vertex cover problem: Given an undirected graph G = (V, E).
Find a minimum subset S of V such that for each edge (u, v) in E, either u or v is in S.
就是在图里面找出一个最小点集，使得每一个边至少有一个顶点在这个点集里面
首先，我们需要生成一个初始解作为起点，而且需要是可行解
我们可以将整个点集作为起点
目标函数就是点集的大小
邻居即相对于当前的集合有一点点改动的集合，我们可以定义邻居为n-1个元素的集合
、
由上图可见，当局部最优解很多的时候，就很难找到全局最优解，这种情况下LS就不太适合用
The Metropolis Algorithm
我们跳进局部最优解就跳不出来了，导致找不出全局最优解
我们可以改进算法，当进入局部最优解时也能有概率跳出来
SolutionType Metropolis()
{ Define constants k and T;
Start from a feasible solution S 属于 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^xxxxx, let S = S’;
else break;
}
}
return S;
}
与原LS算法有两处不同，一个是 \(S’\) 从选最优的邻居改成随机选，一个是如果到达局部最优解有概率跳出去
上面的e^xxx是 \(e^{-\Delta cost/(kT)}\)，cost是当前解与邻居中最优解的差值的绝对值
如果从邻居中随机选的比当前更优我们就更新，否则就计算一下要不要跳过去
cost越大越不要跳（这说明邻居中的最优解太差了），cost小一点可以考虑跳过去
下面的 \(kT\) 是超参，人为设定的，越大越会跳
k一般设定不会变，表示全局；T在具体情况会变化，代表局部。一般会逐渐变小以收敛
Hopfield Neural Networks
给一个图，每个图有个权重 \(w\)，每个点有个 \(s\)，后者只有 \(+1,-1\)
\(w>0\)就说明这条边两个点的 \(s\) 不一样，反之则一样；其绝对值越大越优先实现该需求
可见，被满足的边一定会有 \(w_es_us_v<0\)，我们说这边 \(good\) 的，反之这是 \(bad\) 的
对于一个顶点，其所属的好边的 \(w\) > 坏边的 \(w\)，则这是 这是 \(satisfied\) 的
如果一个图所有顶点都 \(satisfied\) 了，那么就说这个图是 \(stable\) 的
State-flipping Algorithm
邻居定义为一个点s翻转一次的解
找出没被满足的点，反转，循环
ConfigType State_flipping()
{
Start from an arbitrary configuration S;
while ( ! IsStable(S) ) {
u = GetUnsatisfied(S);
su = - su;
}
return S;
}
如果没有stable的状态就会一直翻下去，但是我们可以证明每个图都有stable的状态，而且反转次数有上界，反转次数是所有 \(w\) 绝对值之和
The Maximum Cut Problem.
需要看PPT