Key Local Search Techniques

Why This Matters

Local search techniques form the backbone of practical combinatorial optimization—they're how you actually solve problems when exact methods become computationally intractable. You're being tested on understanding the fundamental trade-off every optimizer faces: exploitation (improving the current solution) versus exploration (escaping to find better regions). Each technique in this guide represents a different strategy for balancing this trade-off, and exam questions will probe whether you understand why a particular method works, not just what it does.

These techniques demonstrate core principles like neighborhood structures, acceptance criteria, memory mechanisms, and population dynamics. When you encounter an FRQ asking you to recommend an optimization approach or analyze algorithm behavior, you need to connect the problem characteristics to the right technique. Don't just memorize algorithm names—know what makes each one effective and when it fails.

---

Gradient-Free Climbing Methods

These techniques improve solutions by examining neighboring candidates and moving toward better ones. The core mechanism is iterative neighborhood evaluation without requiring derivative information.

Hill Climbing

• Greedy neighbor selection—moves only to solutions that improve the objective function, making it fast but myopic
• Local optima trapping is the critical weakness; the algorithm terminates when no improving neighbor exists
• Variants matter: steepest ascent evaluates all neighbors and picks the best; simple hill climbing accepts the first improvement found

Local Search with Restarts

• Multiple independent runs from different starting points help overcome the single-trajectory limitation of basic hill climbing
• Diversification through randomization—each restart samples a new region of the solution space
• Embarrassingly parallel structure makes this technique ideal for distributed computing environments

---

Temperature and Probability-Based Escape

These methods accept worse solutions with some probability, allowing escape from local optima. The key insight is that controlled randomness enables global exploration.

Simulated Annealing

• Metallurgy-inspired cooling schedule—the temperature parameter $T$ decreases over time, reducing the probability of accepting worse moves
• Acceptance probability follows $P(\Delta E) = e^{-\Delta E / T}$, where $\Delta E$ is the cost increase
• Convergence guarantees exist under specific cooling schedules; sufficiently slow cooling theoretically finds the global optimum

Guided Local Search

• Penalty-augmented objective function—adds costs to solution features that appear too frequently in local optima
• Dynamic landscape modification effectively "fills in" local optima valleys, pushing the search toward unexplored regions
• Feature-based memory tracks which solution components to penalize, requiring problem-specific feature definitions

---

Memory-Enhanced Search

These techniques use explicit memory structures to guide exploration and prevent cycling. Memory transforms local search from memoryless wandering into strategic navigation.

Tabu Search

• Short-term memory (tabu list) forbids recently visited solutions or moves, preventing immediate cycling
• Aspiration criteria override tabu status when a forbidden move leads to the best-ever solution
• Long-term memory structures enable intensification (focusing on promising regions) and diversification (exploring neglected areas)

Iterated Local Search

• Perturbation-based escape—after reaching a local optimum, applies a controlled "kick" to the solution before restarting local search
• Perturbation strength is critical: too weak returns to the same optimum; too strong becomes random restart
• Acceptance criteria for the new local optimum can incorporate history, creating implicit memory

---

Neighborhood Structure Manipulation

These approaches systematically vary how "neighbors" are defined to escape local optima. Changing the neighborhood changes what counts as a local optimum.

Variable Neighborhood Search

• Systematic neighborhood switching—when stuck in one neighborhood structure, switches to a different (usually larger) one
• Nested structure: local search uses small neighborhoods for efficiency; shaking uses larger neighborhoods for escape
• Deterministic vs. stochastic variants exist; the basic VNS uses random shaking followed by deterministic descent

---

Population-Based Methods

These techniques maintain multiple candidate solutions simultaneously, using collective information to guide search. Population diversity enables parallel exploration of the solution space.

Genetic Algorithms

• Evolution-inspired operators: selection favors fit individuals, crossover combines parent solutions, mutation introduces variation
• Schema theory suggests GAs efficiently search by implicitly evaluating building blocks shared across solutions
• Premature convergence occurs when population diversity collapses; maintaining diversity is a key design challenge

Particle Swarm Optimization

• Swarm intelligence model—each particle tracks its personal best position and the global best across the swarm
• Velocity update combines inertia, cognitive component (toward personal best), and social component (toward global best)
• Continuous-space native—originally designed for $\mathbb{R}^n$; requires adaptation for discrete combinatorial problems

Ant Colony Optimization

• Pheromone-based communication—artificial ants deposit pheromone on solution components, biasing future construction
• Evaporation mechanism prevents convergence to suboptimal solutions by gradually reducing old pheromone trails
• Construction-based rather than improvement-based; ants build solutions incrementally using probabilistic rules

---

Quick Reference Table

---

Self-Check Questions

1. Which two techniques use explicit memory structures to guide search, and how do their memory mechanisms differ?

2. If you're solving a problem where the objective function is expensive to evaluate but you have access to parallel computing, which technique would you recommend and why?

3. Compare and contrast how Simulated Annealing and Variable Neighborhood Search escape local optima—what is the fundamental difference in their approach?

4. An FRQ describes a routing problem where solutions are naturally constructed edge-by-edge. Which population-based method is best suited for this structure, and what mechanism allows it to learn from previous solutions?

5. Explain why Iterated Local Search requires careful tuning of perturbation strength—what happens if the perturbation is too weak? Too strong?