局部搜索

阅读信息

180 词  2 分钟  本页总访问量 加载中...

Introduction

1. General idea: Start with a feasible solution and search a better one within the neighborhood. A local optimum is achieved if no improvement is possible.

2. Metropolis Algorithm: Simulate behavior of a physical system. If \(S'\) is no better than \(S\), it still has a probability of \(exp\left(-\frac{\Delta cost}{kT}\right)\) (generated by Boltzmann distribution) to move to \(S'\).

Gibbs-Boltzmann function: The probability of finding a physical system in a state with energy \(E\) is proportional to \(e^{-E/kT}\), where \(T > 0\) is temperature and \(k\) is a constant.

SolutionType Metropolis() {
    Define constants k and T;
    Start from a feasible solution S;
    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 exp(-d_cost / (kT)), let S = S_;
            else break;
        }
    }
    return S;
}

Examples

Vertex Cover

Given a graph \(G = (V, E)\), find a minimum subset of nodes \(S\) such that for each \((u, v) \in E\), either \(u\) or \(v\) (or both) are in \(S\).

Neighbor relation: \(S'\) denotes neighbors of \(S\) if \(S'\) can be obtained from \(S\) by adding or deleting a single node. Each vertex cover \(S\) has at most \(n\) neighbors.

Sol.1 Gradient descent

Start with \(S = V\). If there is a neighbor \(S'\) that is a vertex cover and has lower cardinality, replace \(S\) with \(S'\). Otherwise, terminate the algorithm.

Algorithm terminates after at most \(n\) steps.

Cons:

• Small steps: local optimum, but not always global optimum.
• Large steps: longer running time.

Sol.2 Other strategies

• Metropolis Algorithm
• Greedy Algorithms
• Randomized Algorithms
• Local Search (k-exchange / hill climbing)
• LP Relaxation + Rounding
• Branch and Bound (Exact Search)

Hopfield Neural Networks

Problem: Graph \(G = (V, E)\) with integer edge weights \(w\) (positive or negative). Assign states \(s_u=\pm 1\) to nodes. If \(w_{uv} < 0\), then \(u\) and \(v\) want to have the same state; if \(w_{uv} > 0\) then \(u\) and \(v\) want different states.

Def. "good": With respect to a configuration \(S\), edge \(e = (u, v)\) is good if \(w_e \times s_u \times s_v < 0\).

Def. "satisfied": With respect to a configuration \(S\), a node \(u\) is satisfied if the weight of incident good edges is greater than the weight of incident bad edges, i.e.

\[\sum_{v: e_{uv} \in E} w_e s_u s_v \le 0\]

Def. "stable": A configuration is stable if all nodes are satisfied.

In general, there may be no configuration that respects the requirements imposed by all the edges.

Goal: Find a stable configuration (an assignment of the state \(s_u\) to each node \(u\)), if such a configuration exists.

Sol. State-flipping algorithm

Repeated flip state of an unsatisfied node.

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

Will it always terminate?

Thm.: The state-flipping algorithm terminates with a stable configuration after at most \(W = \sum_e | w_e |\) iterations.

Proof

Def potential function \(\Phi(S)=\sum_{e\text{ is good}}|w_e|\).

When \(u\) flips state:

• all good edges incident to \(u\) become bad;
• all bad edges incident to \(u\) become good;
• all other edges remain the same.

Therefore,

\[\Phi(S') = \Phi(S) - \sum_{\substack{e \in E \\ e \text{ is bad}}} |w_e|+ \sum_{\substack{e \in E \\ e \text{ is good}}} |w_e|.\]

Since \(\Phi(S)<W\) and \(\Phi(S)\) increases by at least 1 after each flip, the algorithm terminates at most \(W\) iterations.

Any local maximum in the state-flipping algorithm to maximize \(\Phi\) is a stable configuration.

Maximum Cut Problem

Given an undirected graph \(G = (V, E)\) with positive integer edge weights \(w_e\), find a cut \((A, B)\) such that the total weight of edges crossing the cut \(w(A,B)\) is maximized. The total weight is defined as:

\[w(A,B)\triangleq \sum_{u\in A,v\in B}w_{uv}\]

Sol. Local search

Given a cut \((A, B)\), move one node from \(A\) to \(B\), or one from \(B\) to \(A\) if it improves the solution.

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

How good is this local optimum?

Thm.: Let \((A, B)\) be a locally optimal cut and let \((A^*, B^*)\) be an optimal cut. Then \(w(A, B) \ge 1/2 \sum_e w_e \ge 1/2 w(A^*, B^*)\).

Proof

Since \((A,B)\) is a local optimal, for any \(u\in A\),

\[\sum w_{uv}\le \sum_{\text{move }u\text{ to B}}w_{uv}.\]

Summing up all \(u\in A\):

\[ 2 \sum_{\{u,v\} \subseteq A} w_{uv} = \sum_{u \in A} \sum_{v \in A} w_{uv} \leq \sum_{u \in A} \sum_{\text{move }v\text{ to B}} w_{uv} = w(A, B). \]

Similarly,

\[ 2 \sum_{\{u,v\} \subseteq A} w_{uv}\le w(A, B). \]

Therefore,

\[ w(A^*, B^*) \leq \sum_{\{u,v\} \subseteq A} w_{uv} + \sum_{\{u,v\} \subseteq B} w_{uv} + w(A, B) \leq 2w(A, B) \]

Homework

E.g. K-Center

We are given a set of sites \(S = \{s_1, s_2, \cdots, s_n\}\) in the plane, and we want to choose a set of \(k\) centers \(C = \{c_1, c_2, \cdots, c_k\}\) so that the maximum distance from a site to the nearest center is minimized. Here $ c_i $ can be an arbitrary point in the plane.

A local search algorithm arbitrarily chooses \(k\) points in the plane to be the centers, then

• (1) divide \(S\) into \(k\) sets, where \(S_i\) is the set of all sites for which \(c_i\) is the nearest center; and
• (2) for each \(S_i\), compute the central position as a new center for all the sites in \(S_i\).

If steps (1) and (2) cause the covering radius to strictly decrease, we perform another iteration, otherwise the algorithm stops.

When the above local search algorithm terminates, the covering radiuss of its solution is at most 2 times the optimal covering radius.

• T
• F

---

F.

E.g. K-Center

K-center problem: Given $ N $ cities with specified distances, one wants to build $ K $ warehouses in different cities and minimize the maximum distance of a city to a warehouse.

Which of the following is false?

• A. Given any constant $ \alpha > 1 $, unless P = NP, otherwise the $ K $-center problem cannot be approximated within the factor $ \alpha $ if the graph $ G $ admits an arbitrary distance function.
• B. If the graph $ G $ obeys metric distance, then there is a 2-approximation algorithm for the $ K $-center problem.
• C. The $ K $-center problem can be solved optimally in polynomial time if $ K $ is a given constant.
• D. If the graph $ G $ obeys Euclidean distance, then there exists a PTAS for the $ K $-center problem.

---

D.

True or false

In local search, if the optimization function has a constant value in a neighborhood, there will be a problem.

T.

---

In Metropolis Algorithm, the probability of jumping up depends on T, the temperature. When the temperature is high, it'll be close to the original gradiant descent method.

F.

---

For an optimization problem, given a neighborhood, if its local optimum is also a global optimum, one can reach an optimal solution with just one step of local improvements.

F.

Choice

Consider the Minimum Degree Spanning Tree problem: Given a connected undirected graph \(G(V, E)\), find a spanning tree \(T\) whose maximum degree over its vertices is minimized over all spanning trees of \(G\). The problem can be shown to be NP-hard by reduction from the Hamiltonian Path Problem. On the other hand, we can use local search to design approximating algorithms. Denote \(d(u)\) as the degree of vertex \(u\) on a tree \(T\). Consider the following algorithm:

1. Find an arbitrary spanning tree \(T\) of \(G\).
2. If there's some edge \(e \in E(G)\setminus E(T)\) with endpoints \(u, v\), and there's some other vertex \(w\) on the path between \(u, v\) on \(T\) such that \(\max\{d(u), d(v)\} + 1 < d(w)\), then we replace an edge \(e'\) incident to \(w\) on \(T\) with \(e\), i.e. \(T := T \cup \{e\}\setminus\{e'\}\).
3. Repeat Step (2) until there's no edge to replace.

It can be shown that this algorithm will terminate at a solution with maximum vertex degree \(OPT + O(\log |V|)\). To show the algorithm will terminate in finite steps, a useful technique is to define a nonnegative potential function \(\phi(T)\) and to show \(\phi(T)\) is strictly decreasing after each step. Which of the following potential functions below satisfies the above requirements?

• A. \(\phi(T) = \sum_{v \in V} d(v)\).
• B. \(\phi(T) = \sum_{(u,v) \in E(T)} \max\{d(u), d(v)\}\).
• C. \(\phi(T) = \sum_{u \in V} \sum_{v \in V, v \neq u} \sum_{w \in V, w \neq u,v} \max\{d(u), d(v), d(w)\}\).
• D. \(\phi(T) = \sum_{v \in V} 3^{d(v)}\).

---

D. In B and C, \(w\) may not directly contribute to the potential.

Choice

Scheduling Job Problem: There are \(n\) jobs and \(m\) identical machines (running in parallel) to which each job may be assigned. Each job \(j = 1, \cdots, n\) must be processed on one of these machines for \(t_j\) time units without interruption. Each machine can process at most one job at a time. The aim is to complete all jobs as soon as possible; that is, if job \(j\) completes at a time \(C_j\) (the schedule starts at time 0), then we wish to minimize \(C_{max} = max_{j=1,\cdots,n} C_j\). The length of an optimal schedule is denoted as \(OPT(C_{max})\).

Local Search Algorithm: Start with any schedule; consider the job \(l\) that finishes last; check whether or not there exists a machine to which it can be reassigned that would cause this job to finish earlier. If so, transfer job \(l\) to this other machine. The local search algorithm repeats this procedure until the last job to complete cannot be transferred. An illustration of this local move is shown in following figure.

Which of the following statement is false?

• A. \(OPT(C_{max}) \geq \sum_{j=1}^{n} t_j / m\)
• B. When transferring a job, if we always reassign that job to the machine that is currently finishing earlier, then no job is transferred twice.
• C. Upon the termination of the algorithm, the algorithm may return a schedule that has length at least \(2OPT(C_{max})\)
• D. Suppose that we first order the jobs in a list arbitrarily, then consequently assign each job to the machine that is currently of earliest completion time, the schedule obtained cannont be improved by the local search procedure.

---

C. "At least" should be no more than.

E.g.

Spanning Tree Problem: Given an undirected graph $ G = (V, E) $, where $ |V| = n $ and $ |E| = m $. Let $ F $ be the set of all spanning trees of $ G $. Define $ d(u) $ to be the degree of a vertex $ u \in V $. Define $ w(e) $ to be the weight of an edge $ e \in E $.

We have the following three variants of spanning tree problems:

• (1) Max Leaf Spanning Tree: find a spanning tree $ T \in F $ with a maximum number of leaves.
• (2) Minimum Spanning Tree: find a spanning tree $ T \in F $ with a minimum total weight of all the edges in $ T $.
• (3) Minimum Degree Spanning Tree: find a spanning tree $ T \in F $ such that its maximum degree of all the vertices is the smallest.

For a pair of edges $ (e, e') $ where $ e \in T $ and $ e' \in (G - T) $ such that $ e $ belongs to the unique cycle of $ T \cup e' \(, we define **edge-swap**\) (e, e') $ to be $ (T - e) \cup e' $.

Here is a local search algorithm:

T = any spanning tree in F;
while (there is an edge-swap(e, e') which reduces Cost(T)) {
    T = T - e + e';
}
return T;

Here Cost(T) is:

• the number of leaves in $ T $ in Max Leaf Spanning Tree;
• or is the total weight of $ T $ in Minimum Spanning Tree;
• or else is the maximum degree of $ T $ in Minimum Degree Spanning Tree.

Which of the following statements is TRUE?

• A. The local search always return an optimal solution for Max Leaf Spanning Tree
• B. The local search always return an optimal solution for Minimum Spanning Tree
• C. The local search always return an optimal solution for Minimum Degree Spanning Tree
• D. For neither of the problems that this local search always return an optimal solution

---

B.