Comp360 Notes for Local Search

Local search attempts to find an optimal solution $S\ast$ to a problem Q by making “local improvements” to the current solution.

Let S be the initial solution
while $\exists S' \in \text{ Neighborhood}(S) \text{ with cost}(S') < \text{cost}(S)$
Set $S \leftarrow S'$

Clearly the choice of “neighbor” is key. There is a trade-off in that bigger neighborhoods may give better solutions, but will take longer to search. (Time vs. Quality)

If the state space is finite then LS terminates. Each iteration gives a strictly better solution so the alg. cannnot cycle. The algorithm terminates in (at most) exponential time for optimization versions of NP-complete problems.

But, even if LS terminates in polytime, we (typically) have no guarantees on the quality of the solution.

Max Cut

Given a cut (S, V-S), let the neighborhood of S be those cuts that differ in one vertex. If x has more neighbors on the LHS than the RHS, it should switch sides. I.e. local improvement.

Yields local optima ($\nexists$ better solutions in neighborhood).

Max Sat

Satisfy as many clauses as possible in a SAT instance.

LS starts with any T/F assignment of ${ x, x_2, \dots, x_n}$ and switches the assignments $(x_i \rightarrow {\bar x_i}$ or ${\bar x_i} \rightarrow x_i)$ if it increases the # of satisfied clauses.

TSP

Given a tour T, its neighborhood consists of any tour that differs in exactly 2 edges. Again, this may not stop at an optimal solution. A 3-way swap will fix this, but those take longer to search and even thenn you may need 4-swaps, etc. ($\text{n-swaps} \rightarrow \text{optimal}$)

Minimum Spanning Trees

A spanning tree $T’$ is in the neighborhodd of $T$ if they differ in exactly 1 edge. (1-swap)

Cut Property of MST: Let $T\ast$ be the MST (distinct edge weights). The $e \in T\ast$ iff $\exists$ cut $\delta(Se)$ s.t. $e$ is the deepest edge in $\delta(Se)$

And so we can say:

Lemma By the Cut property, for any $T=T_o$:
  • $T_i \in \text{Neighborhood}(T_{i-1})$
  • $\text{cost}(T_i) < \text{cost}(T_{i-1})$
  • $T_k = T\ast$

Proof

Take $e \in T\ast - T$.
Add $e$ to $T$
This creates a cycle $C$.

$\exists f \in C$ s.t. $\text{cost}(f) > \text{cost}(e)$. Otherwise $\nexists Se$ s.t. $e$ is the cheapest edge in $\delta (Se)$

Set $T’ = T + e - f$. Then this is a spanning tree and $\text{cost}(T’) < \text{cost}(T)$. Repeast.

So if T is not a MST there $\exists$ an improving move. So Local Search ends with a MST.

Simulated Annealing

LS can get stuck in a local optima. To avoid this, S.A. allows us to sometimes move to a worse neighbor.

Let $S$ be the intial solution
Take $S' \in \text{Neighborhood}(S)$
If $\text{cost}(S') < \text{cost}(S)$ then set $S \leftarrow S'$
If $\text{cost}(S') \ge \text{cost}(S)$ then set $S \leftarrow S'$ with small probability.

e.g.

$\text{Prob} = \frac{1}{e^{\frac{1}{T}(\text{cost}(S')-\text{cost}(S))}}$
T="temperature"
if T=0 we have LS

Again SA gives no guarantees but it works well on some problems.

Written on October 30, 2014