12 Local Search¶
从一个可行解开始，我们在它的邻域内寻找更好的解，如果邻域内没有更好的解了，那么我们就称这个解是一个 local optimum (局部最优解)
我们的算法大纲如下，找到邻域，cost(S) 以及从S到S’的方法
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;
}
12.1 The 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\).
- Feasible solution set: all the vertex covers
- \(\text{cost} (S) = |S|\)
- Start from \(S = V\); delete a node and check if \(S'\) is a vertex cover with a smaller cost.
我们可以看到 gradient descent 在有些情况下得不到最优解。
Metropolis算法：相比于原来的梯度算法，红色是改动的部分。我们随机选出来一个点，如果比当前的解要好，那么正常进行替换；如果更差的话，仍旧会有一定的概率替换成新的点。相比于原来的解，cost越大替换概率越低。
思考算法的结束时间，一种可行的想法是当概率小到某个阈值之下就结束，或者直接设定一个上界最多往差的地方跳有限次。
这样我们就可以不一定会被困在局部最优中了。
SolutionType Metropolis()
{
Define constants k and T;
Start from a feasible solution S in FS ;
MinCost = cost(S);
while (i<10000) {
S’ = Randomly chosen from N(S);
CurrentCost = cost(S’);
if ( CurrentCost < MinCost ) {
MinCost = CurrentCost; S = S’;
}
else {
With a probability e^(-deltacost/kT) let S = S’ and i++;
else break;
}
}
return S;
}
这个算法从哪里来
这个概率来自于玻尔茨曼分布，其中那个T代表温度，温度越高说明点更容易跳出去，就像分子更活跃。
Simulated Annealing 模拟退火算法：我们模拟一个退火的过程，慢慢降低T的大小，这样我们上升替换概率也越来越小。
12.2 Hopfield Neural Networks¶
Definition¶
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; if \(w_e > 0\) then \(u\) and \(v\) want different states.
也就是说给你一个有权图，边的权重小于0，端点的状态一样；边的权重大于0，端点的状态不一样。（端点的状态由1和-1来表示）
Output: A configuration \(S\) of the network – an assignment of the state \(s_u\) to each node \(u\) 我们要输出的是这个图的状态图。
很显然，不是每个有权图都有这样的 configuration，于是我们定义如果 \(w_es_us_v<0\)，那么称这一条边是 “好的” （对应的就是上面符合要求的情况），反之则被称为 “坏的” 。
接着我们定义一个点是满足要求的 (satisfied)，如果这个点所连的好边的权重绝对值之和大于等于坏边的权重绝对值之和。
如果所有的点都是满足要求的 (satisfied)，那么称这个 configuration 是稳定的 (stable)
那么如果我们有以上定义，那么Hopfield network 是否一定有一个 stable configuration，如果有，那么我们应当如何找到？
State-flipping Algorithm¶
ConfigType State_flipping()
{
Start from an arbitrary configuration S;
while ( ! IsStable(S) ) {
u = GetUnsatisfied(S);
su = - su;
}
return S;
}
算法描述：我们从任意的 configuration 开始，如果当前的 configuration 不是 stable 的，那么我们找到一个不满足要求的点，将其状态反向，直到这个 configuration 稳定为止
Claim: The state-flipping algorithm terminates at a stable configuration after at most \(W = \sum_e|w_e|\) iterations.
Proof: 考虑一个势能函数 \(\Phi(S)=\sum_{e\ \text{is good}}|w_e|\)
当 \(u\) 的状态发生反转的时候 (从 \(S\) 变为 \(S'\))
- 所有的与 \(u\) 相连的好边全部转换为坏边
-
所有的与 \(u\) 相连的坏边全部转换为好边
-
其他边未受到影响
那么
注意上式的好边和坏边均与 \(u\) 相连，而 \(u\) 是不满足要求的，所以坏边的权重绝对值之和是大于好边的权重绝对值之和的，所以 \(\Phi(S)\) 是单增的，同时由于每条边的权重是整数，所以 \(\Phi(S)\) 每次循环都会至少增加1，而 \(\Phi(S)\) 至多增加到 \(W\)，所以这样的循环至多 \(W\) 次
回到 Local Search, 这个问题的几个要素如下：
- Problem: To maximize \(\Phi\)
- Feasible solution set: configurations
- \(S\sim S'\): \(S'\) can be obtained from \(S\) by flipping a single state
这样的算法找到的 local maximum 一定满足 \(S\) 是一个 stable configuration。
对于这个算法的时间复杂度，因为权值可以很大，所以这是一个伪多项式时间复杂度算法
12.3 Maximum Cut Problem¶
12.3.1 Problem and Solution¶
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.
- Problem: To maximize \(\Phi(S)=\sum_{e\ \text{is good}}|w_e|\) 【我们分别定义A，B阵营的点为1和-1即可】【回忆一下，好边的值是负的】
- Feasible solution set: any partition \((A,B)\)
- \(S\sim S'\): \(S'\) can be obtained from \(S\) by moving one node from \(A\) to \(B\), or one from \(B\) to \(A\).
这就是 Hopfield Neural Network 的一种特殊情况，所有的 \(w_e\) 都是正数，所以我们还是使用上面的那个算法，这样我们得到的局部最优和最佳的情况的差距是多少呢？
Claim: Let \((A, B)\) be a local optimal partition and let \((A^*, B^*)\) be a global optimal partition. Then \(w(A, B) \ge 1/2\ w(A^*, B^*)\).
Proof: 因为 \((A,B)\) 是局部最优的分割，那么对于 \(\forall u\in A\)
否则我就将这个点从 A 移到 B
那么对于所有 \(u\in A\)，我们将式子加起来，得到
从而可以得到
（第一个不等号是因为最佳的情况小于所有边之和）
12.3.2 Improvement¶
和 Hopfield Neural Network 问题一样，我们计算时间复杂度的时候，都会因为权值过大而导致不是多项式时间的问题，但是我们可以找到一个FPTAS的算法。
Big-improvement-flip: Only choose a node which, when flipped, increases the cut value by at least
注意这里的 \(w(A,B)\) 代表的是当前状态下的 \(w(A,B)\)
Claim 1: Upon termination, the big-improvement-flip algorithm returns a cut \((A, B)\) so that
Proof: 对于 \(\forall u\in A\)
如果大于，算法的循环还会继续（因为这个点是不满足要求的）
那么对于所有 \(u\in A\)，我们将式子加起来，得到
从而可以得到
Claim 2: The big-improvement-flip algorithm terminates after at most \(O(n/\varepsilon \log W)\) flips.
Proof: 每次 \(\Phi(S)\) 都要扩大到原来的 \(1+\frac{2\epsilon}{|V|}\) 倍，所以迭代的次数最多为
12.3.3 一些思考¶
对于 Local search 来说，怎么样的Local才是好的？
解的邻域需要大一点，要避免被困在一个较差的局部最优之中，但是解的邻域也不能太大，因为我们需要保证算法的效率。
一个构建邻域的思路是将一次反转改为多次反转，比如说我们每次循环从k次反转中找到最优的那一个，显然这样的方法时间复杂度太可怕了
有一个更好的构建邻域【邻域更广，但是寻找的时间复杂度是多项式级别的】的方法：[Kernighan-Lin 1970] K-L heuristic
第一步我们改变一个点的状态，选择最优的那一个，时间复杂度是 \(O(n)\)，得到的解为 \((A_1,B_1)\) 反转的点为 \(v_1\)
第二步建立在第一步的基础上，我们再翻转一个点选择这 \(n-1\) 个情况中最优的那一个，时间复杂度就是 \(O(n-1)\)，得到的解为 \((A_2,B_2)\)，反转的点为 \(v_2\)
...
最后一步都反转过来了，所以与一开始是等价的
那么 \((A,B)\) 的邻域是 \((A,B)=\{(A_1,B_1),...,(A_{n-1},B_{n-1})\}\)，时间复杂度是 \(O(n^2)\)，我们接着从这些邻域中找最大的哪一个，这样我们的邻域变大了，同时也不会导致搜索邻域的时间复杂度太大。
12.4 Bipartite Matching¶
评论区
对你有帮助的话请给我个赞和 star =>
欢迎跟我探讨！！！