Local Search for CSP

Simulated annealing probabilistically allows moves to worse states to escape local minima, inspired by the annealing process in metallurgy. The probability of accepting a worse move is controlled by a temperature parameter that gradually decreases according to a cooling schedule.

• Algorithm: Start with a high temperature (high probability of accepting bad moves). Randomly select a neighbor. Always move if it's better; if worse, move with probability e^(-ΔE/T).
• Cooling: Slowly reduce temperature, making the search more greedy over time.
• Advantage: Asymptotically converges to a global optimum given a slow enough cooling schedule.

Tabu search enhances local search by using memory to avoid cycling and explore new regions of the search space. It maintains a tabu list—a short-term memory of recently visited states or moves—which are forbidden for a certain number of iterations.

• Core Mechanism: Even if a move is the best available, it is prohibited if it's on the tabu list (unless it meets an aspiration criterion, like finding a new global best).
• Memory Structures: Can include long-term memory to intensify search in promising areas or diversify into unexplored ones.
• Use Case: Effective for complex combinatorial optimization problems like vehicle routing and job-shop scheduling.

Genetic algorithms are a population-based metaheuristic inspired by natural selection. They maintain a set of candidate solutions (a population) and evolve them over generations using selection, crossover (recombination), and mutation operators.

• Process: 1) Evaluate fitness (e.g., inverse of conflict count). 2) Select parent solutions biased by fitness. 3) Crossover parents to produce offspring. 4) Mutate offspring randomly. 5) Form new population.
• Strength: Explores multiple areas of the search space in parallel, good for rugged landscapes.
• Representation: Requires encoding a CSP assignment as a chromosome (e.g., a string of values).

WalkSAT is a prominent local search algorithm specifically for the Boolean Satisfiability Problem (SAT). It combines a greedy hill-climbing component with random walks. At each step, it picks an unsatisfied clause and flips the truth value of a variable within that clause.

• Variable Choice: With probability p, flip a random variable in the clause. With probability 1-p, flip the variable in the clause that minimizes the number of newly unsatisfied clauses (the break count).
• Noise Parameter: The p parameter balances greediness and randomness.
• Performance: One of the most effective stochastic algorithms for hard random SAT instances and real-world benchmarks.

Hill climbing is the foundational optimization paradigm that underpins local search for CSPs. It operates as follows:

• Start with a complete, random assignment (which likely violates constraints).
• Iteratively make a small, local change to the assignment (e.g., changing one variable's value).
• Accept the change only if it improves the objective function (e.g., reduces the total number of constraint violations). The algorithm gets stuck in local optima—states where no single change yields improvement, but a better global solution may exist. Advanced techniques like random restarts or simulated annealing are used to escape these plateaus.

Backtracking search is a complete search algorithm that contrasts sharply with local search. It is a systematic, depth-first exploration of the search space:

• It builds assignments incrementally, one variable at a time.
• Before assigning a value, it checks consistency with existing assignments (constraint propagation).
• If a variable has no legal values left, it backtracks to the previous variable and tries a different value. While guaranteed to find a solution if one exists, it can be slow for large problems. Local search is often preferred when an approximate or 'good enough' solution is acceptable and runtime is critical.

A Constraint Optimization Problem (COP) generalizes a CSP by adding an objective function to be minimized or maximized. The goal is no longer just to find a feasible solution, but the best feasible solution according to a metric (e.g., cost, profit, distance). Local search is exceptionally well-suited for COPs. Algorithms like hill climbing or simulated annealing can directly use the objective function to guide improvements. For example, in a vehicle routing problem, a local search would iteratively tweak routes to minimize total travel distance while respecting all delivery constraints.

Simulated annealing is a probabilistic local search algorithm designed to escape local optima, making it more robust than basic hill climbing for complex CSPs and COPs. It is inspired by the annealing process in metallurgy.

• It occasionally accepts moves that worsen the objective function (increase conflicts).
• The probability of accepting a bad move is controlled by a temperature parameter, which gradually decreases over time.
• Early in the search, with high temperature, it explores the search space widely.
• As temperature cools, it converges to a (hopefully global) optimum, behaving more like greedy hill climbing. This provides a principled trade-off between exploration and exploitation.