Local Search

The fundamental mechanism of a local search algorithm. It starts with an initial candidate solution and repeatedly moves to a neighboring solution that improves the value of an objective function (e.g., lower cost, higher score).

• Process: Current State → Evaluate Neighbors → Select Better Neighbor → Move.
• Termination: Stops when no better neighbor exists (a local optimum).
• Example: In the Traveling Salesperson Problem, a neighbor might be created by swapping two cities in the tour; the algorithm moves to this new tour if it is shorter.

Defines the set of potential next moves from any given solution. The neighborhood function is a critical design choice that determines the algorithm's granularity and connectivity of the search space.

• Types: Common structures include k-opt swaps (for permutations), bit flips (for binary strings), or small perturbations (for continuous values).
• Impact: A large neighborhood allows bigger jumps but is costly to evaluate. A small neighborhood is efficient but may lead to slow progress.
• Key Concept: The landscape of local optima is directly shaped by how neighborhood is defined.

The simplest local search strategy is Hill Climbing (or gradient ascent/descent), which greedily moves to the best neighboring state. Its primary limitation is convergence to a local optimum—a solution better than all its neighbors but not necessarily the best globally.

• Problem: The algorithm gets "stuck" on plateaus or at the peak of a small hill in the fitness landscape.
• Consequence: Solution quality is highly dependent on the initial state. This makes pure hill climbing non-robust for complex problems.
• Mitigation: Advanced metaheuristics like Simulated Annealing or Tabu Search are designed to escape local optima.

To overcome the local optimum problem, metaheuristics introduce mechanisms that allow temporary moves to worse states or prevent cycling.

• Simulated Annealing: Probabilistically accepts worse moves based on a "temperature" parameter that cools over time, enabling escape from early local traps.
• Tabu Search: Maintains a short-term memory (tabu list) of recently visited states, forbidding returns to them to force exploration.
• Iterated Local Search: Performs a strong perturbation to escape a local optimum, then applies local search again from the new point.

Local search operates on a complete solution representation, unlike tree search which builds solutions incrementally. The entire candidate (e.g., a full schedule, a complete circuit layout) is evaluated and modified at each step.

• Contrast with Constructive Search: Algorithms like A* build a solution path step-by-step. Local search always works with a complete, though potentially suboptimal, configuration.
• Implication: It requires a method to generate an initial solution (often random or via a greedy heuristic) to begin the improvement process.
• Advantage: This representation is often more memory-efficient, as it stores only the current state and its neighborhood, not an entire search tree.

Local search excels in large, complex optimization problems where finding a provably optimal solution is intractable, but a good, feasible solution is required quickly.

• Typical Use Cases: Vehicle routing, facility location, chip placement (VLSI), job shop scheduling, and neural network weight tuning.
• Key Trade-off: Sacrifices completeness (guarantee of finding a solution if one exists) and optimality for speed and scalability.
• Engineering Choice: Selected when search spaces are too vast for systematic methods and when solution quality can be traded for computational resources.

A foundational local search algorithm and a specific, greedy instance of the broader local search family. It iteratively moves to the best neighboring state that improves the objective function, stopping when no better neighbor exists. This makes it highly susceptible to local optima and plateaus.

• Key Mechanism: Always selects the steepest ascent (or descent).
• Primary Limitation: Cannot escape local maxima/minima once found.
• Relation to Local Search: Hill Climbing is a strategy for performing local search, whereas Local Search is the general paradigm.

A probabilistic local search metaheuristic inspired by metallurgy. It improves upon basic hill climbing by occasionally accepting worse solutions with a probability that decreases over time according to a cooling schedule. This allows the algorithm to escape local optima.

• Core Innovation: Introduces controlled randomness via the Metropolis criterion.
• Cooling Schedule: The temperature parameter controls exploration (high temp) vs. exploitation (low temp).
• Use Case: Effective for complex optimization landscapes where global optima are hidden among many local optima.

A metaheuristic local search algorithm that uses memory to guide exploration. It maintains a tabu list of recently visited solutions or moves, preventing the search from cycling back to them for a short period. This forces exploration of new regions of the search space.

• Memory Structures: Beyond the tabu list, may use aspiration criteria to override tabu status for exceptionally good solutions.
• Strategic Goal: Diversification (exploring new areas) and intensification (thoroughly searching good areas).
• Application: Widely used in scheduling, routing, and other combinatorial optimization problems.

The formal representation of all possible configurations (states) of a problem and the operators (actions) that define transitions between them. It is the abstract environment in which search algorithms, including local search, operate.

• Components: A set of states S, a start state s0 ∈ S, a set of goal states G ⊆ S, and a successor function.
• Neighborhood Relation: In local search, the successor function defines the neighborhood of a given state—the set of states reachable by a single operator application.
• Criticality: The structure and size of the state space directly determine the difficulty of the search problem.

A problem where the goal is to find the best solution from a set of feasible solutions, as measured by an objective function. Local search is a primary algorithmic approach for solving hard optimization problems, especially when an exact, globally optimal solution is computationally infeasible.

• Formal Definition: Find x* ∈ X that minimizes (or maximizes) f(x), where X is the feasible region.
• Local vs. Global Optimum: A local optimum is a solution better than all its immediate neighbors; a global optimum is better than all feasible solutions.
• Heuristic Nature: Local search provides high-quality, but not guaranteed optimal, solutions efficiently.

A high-level, problem-independent algorithmic framework designed to guide underlying heuristic methods. Local search is a core concept, and algorithms like Simulated Annealing and Tabu Search are metaheuristics that orchestrate the local search process to overcome its limitations.

• Key Principle: Provide a general strategy for exploring the search space, not a problem-specific recipe.
• Examples: Genetic Algorithms, Ant Colony Optimization, and Iterated Local Search are other metaheuristics.
• Role: They manage the trade-off between exploration (searching new areas) and exploitation (refining good solutions), which is the central challenge in local search.