Local Search and Its Improvements

Idea: Movement Across the Solution Landscape

Imagine the "landscape" of the solution space: each solution is a point, its "height" is the value of the objective function. We want to find a deep valley (minimum). Local search is a "descent across the landscape": we start from an arbitrary point and iteratively move to a "neighboring" point with a better value. Simple and fast—but easy to get stuck in a "local valley" that is not the global minimum. Improvements (Tabu Search, VNS, Large Neighborhood Search) allow us to "escape" from such traps.

Basic Local Search

Components:

• Initial solution s (random or greedy)
• Neighborhood function N(s) = set of "neighboring" solutions
• Improvement criterion (first improvement or best improvement)

Algorithm:

1. Current solution s = s₀
2. While N(s) contains a better solution s':
   • s ← s' (first improvement: take the first better one; best improvement: the best among all)
3. Return s (local optimum)

Neighborhood selection is a key issue: a small neighborhood → fast iteration but weak improvement. Large → slow but high-quality improvement.

2-opt for TSP: The Classic

2-opt neighborhood: remove 2 edges from the tour and rebuild. For the route a→b→c→d→e→a: remove (b,c) and (d,e), add (b,d) and (c,e)—restructuring.

Number of pairs of edges: $C_n^2 = O(n^2)$. Each iteration: $O(n^2)$ operations.

2-opt algorithm:

1. For each pair of edges (i, j):
   • Compute the improvement from replacing two edges
   • If improvement > 0: do the swap, restart
2. Stop: no 2-opt improvement (2-opt optimum)

Practice: 2-opt often gives tours that are 3-5% off the optimum. For a 1000-city problem works in seconds.

3-opt: remove 3 edges—O(n³) operations. Better quality, more expensive.

Lin-Kernighan (LK): adaptive k-opt with "smart" candidate selection. Best-known TSP heuristic. Gives tours within 0.5-1% from optimum. Used in the LKH (Lin-Kernighan-Helsgott) program—industry standard.

Variable Neighborhood Search (VNS)

Problem of basic LS: getting stuck at a local optimum. VNS solves this with multiple neighborhoods:

VNS Algorithm:

Define $N_1$, $N_2$, ...,$N_k$ (with $N_1 \subseteq N_2 \subseteq ... \subseteq N_k$).

1. s = s₀ (initial solution)
2. While time has not expired: a. i = 1 b. While $i \leq k$:
   • $s' = \text{random_neighbor}(N_i(s))$
   • $s'' = \text{local_search}(s')$
   • If $f(s'') < f(s)$: $s = s''$, $i = 1$ (found an improvement—start over)
   • Else: $i++$ (move to a wider neighborhood)

Idea: if local search gets stuck in $N_1$-optimum, "jump" randomly into the $N_2$ neighborhood and descend again. If a local optimum there—$N_3$ and so on.

Tabu Search

Motivation: basic LS may "oscillate" between several solutions. Tabu Search prohibits recently visited solutions.

Tabu Search Algorithm:

1. $s = s_0$, TabuList = ∅, BestSolution = $s_0$
2. While not stopping criterion:
   • Find the best solution $s' \in N(s) \setminus \text{TabuList}$
   • If $s'$ is absent → allow Tabu (aspiration)
   • $s \leftarrow s'$
   • If $f(s) < f(\text{BestSolution})$: BestSolution = $s$
   • Add $s$ to TabuList (remove oldest if the list is full)

Aspiration criterion: allow tabu transition if it improves BestSolution. This lets us "accept" a good solution even if it is forbidden.

Parameters:

• Length of TabuList: usually $\sqrt{n}$ or $n$. Too small—oscillation. Too big—search too restricted.
• What to store: the solution itself (memory intensive) or just the "move" (variable shift)

Detailed Example: 2-opt for 5-city TSP

Cities: A(0,0), B(2,0), C(2,2), D(0,2), E(1,1). Initial tour: A→B→C→D→E→A.

Length: $|AB| + |BC| + |CD| + |DE| + |EA| = 2 + 2 + 2 + \sqrt{2} + \sqrt{2} = 6 + 2\sqrt{2} \approx 8.83$.

2-opt check (pair of edges AB and CD): replace with AC and BD.

AC: $\sqrt{4+4} = 2\sqrt{2}$. BD: $\sqrt{4+4} = 2\sqrt{2}$. New tour: A→C→B→D→E→A.

Length: $|AC| + |CB| + |BD| + |DE| + |EA| = 2\sqrt{2} + 2 + 2\sqrt{2} + \sqrt{2} + \sqrt{2} = 2 + 6\sqrt{2} \approx 10.49$. Worse.

2-opt check (pair BC and DE): replace with BD and CE.

New tour: A→B→D→C→E→A (reversed subroute C→D).

Length: $2 + 2\sqrt{2} + 2 + \sqrt{2} + \sqrt{2} = 4 + 4\sqrt{2} \approx 9.66$. Worse than the original.

Result: the initial tour A→B→C→D→E→A is 2-opt optimal for these cities.