Local Search

Hill climbing, min-conflicts, simulated annealing, restarts, and experimental methods for optimization spaces where paths do not matter.

Path search preserves alternative routes because the sequence of actions matters. Many optimization problems care only about a final configuration: a low-conflict timetable, a compact layout, or a valid arrangement of queens. Local search keeps one candidate state, or a small set of candidates, and repeatedly moves to a neighboring solution.

Its memory use is small and its practical reach can be enormous. Its central limitation is equally important: local search usually cannot prove that its answer is globally optimal or that no solution exists.

Problem Model

A local-search problem needs:

a complete candidate representation;
a neighborhood function N(s);
an objective function;
a move policy;
a stopping rule.

The neighborhood defines which solutions are easy to reach from one another. For N-Queens, a state can store one row per column and a neighbor can move one queen. For a timetable, a neighbor might move one class or swap two time slots.

If legal solutions occupy disconnected regions and the move operator cannot cross between them, no amount of tuning will find the missing region.

Hill Climbing

Hill climbing repeatedly selects an improving neighbor:

def hill_climb(initial, neighbors, score):
    current = initial

    while True:
        candidates = list(neighbors(current))
        if not candidates:
            return current

        best = max(candidates, key=score)
        if score(best) <= score(current):
            return current

        current = best

This version maximizes a score. A cost-minimizing version reverses the comparison.

Hill climbing is fast, simple, and memory-light, but an objective landscape may contain:

a local optimum, better than every neighbor but not globally best;
a plateau, where neighbors have equal value;
a ridge, where improvement requires an awkward sequence of moves;
a shoulder, a flat region with an improving exit.

Allowing a limited number of sideways moves can cross a plateau but may create cycles. Record recent states or cap sideways moves.

Random Restarts

Run hill climbing from many random initial states and retain the best result. If one run succeeds with probability p, all k runs fail with probability (1-p)^k, assuming independent starts.

Restarts are a principled way to trade time for reliability. They do not repair a poor representation or a neighborhood that makes good states unreachable.

Min-Conflicts

Min-conflicts specializes local search for constraint problems:

begin with a complete assignment;
choose a variable in conflict;
assign the value causing the fewest conflicts;
repeat until solved or the budget ends.

from random import Random

def queen_conflicts(rows, column, candidate_row):
    conflicts = 0
    for other_column, other_row in enumerate(rows):
        if other_column == column:
            continue
        same_row = candidate_row == other_row
        same_diagonal = (
            abs(candidate_row - other_row)
            == abs(column - other_column)
        )
        conflicts += same_row or same_diagonal
    return conflicts

def min_conflicts_queens(n, max_steps=10_000, seed=0):
    if n < 4:
        raise ValueError("use n >= 4 for this experiment")

    rng = Random(seed)
    rows = [rng.randrange(n) for _ in range(n)]

    for step in range(max_steps + 1):
        conflicted = [
            column for column, row in enumerate(rows)
            if queen_conflicts(rows, column, row) > 0
        ]
        if not conflicted:
            return {"rows": rows, "steps": step}

        column = rng.choice(conflicted)
        scores = [
            queen_conflicts(rows, column, row)
            for row in range(n)
        ]
        best_score = min(scores)
        best_rows = [
            row for row, score in enumerate(scores)
            if score == best_score
        ]
        rows[column] = rng.choice(best_rows)

    return None

solution = min_conflicts_queens(50, seed=8)
assert solution is not None
assert all(
    queen_conflicts(solution["rows"], column, row) == 0
    for column, row in enumerate(solution["rows"])
)

Random tie breaking avoids deterministic loops. Unlike backtracking, min-conflicts repairs complete but inconsistent assignments. It can solve huge, loosely constrained instances, but it generally cannot prove unsatisfiability.

The code uses the same one-row-per-column representation as backtracking. This permits a meaningful comparison: the model remains fixed while the search policy changes. Backtracking builds a consistent partial assignment and can prove failure; min-conflicts begins complete, repairs violations, and returns no proof when its step budget expires.

Search Landscapes

An objective function compresses a complex state into one number. That compression loses information. Two N-Queens states with five attacking pairs may have very different escape routes, yet ordinary hill climbing treats their score equally.

The fitness landscape is induced jointly by representation, neighborhood, and objective:

changing the encoding changes which candidates exist;
changing moves changes which candidates are adjacent;
changing the score changes which directions appear improving.

This is why optimizer comparisons must hold the problem model fixed. A better representation can matter more than a more elaborate move policy.

Local optima are also neighborhood-relative. A timetable may be locally optimal under single-class moves but improvable under a two-class swap. Expanding the neighborhood can expose exits, though evaluating more moves raises each iteration’s cost.

Annealing

Hill climbing cannot cross a valley because it rejects every worse move. Simulated annealing sometimes accepts a worse candidate.

For minimization, define:

Δ = cost(candidate) - cost(current)

Accept improvements. Accept a worsening move with probability:

exp(-Δ/T)

At high temperature T, broad exploration is likely. As temperature falls, the method becomes conservative.

from math import exp

def anneal(initial, random_neighbor, cost, schedule, rng):
    current = best = initial

    for temperature in schedule:
        if temperature <= 0:
            break

        candidate = random_neighbor(current, rng)
        delta = cost(candidate) - cost(current)

        if delta <= 0 or rng.random() < exp(-delta / temperature):
            current = candidate

        if cost(current) < cost(best):
            best = current

    return best

Cooling too quickly behaves like hill climbing. Cooling too slowly wastes computation. Practical schedules lose the strongest convergence guarantee, so they must be evaluated empirically.

Tabu Search

Tabu search permits non-improving moves but keeps a short memory of recent moves or attributes. A tabu list prevents immediate reversal and helps the search leave cycles. An aspiration rule may allow a tabu move when it produces a new best-known solution.

Tabu tenure is a trade-off. A short tenure may not prevent cycling; a long tenure can forbid useful regions. Storing complete states is expensive, so implementations often store move attributes such as “class A moved from slot 2 to slot 5.” This compact memory can also forbid moves that would lead to genuinely different states.

Unlike simulated annealing, tabu search accepts moves by a deterministic ranking plus memory rather than a temperature-dependent probability. Both methods can cross worsening terrain, but their experimental parameters and failure modes differ.

Move Design

Useful neighborhoods balance:

reachability — can important regions be reached?
locality — does a move make a meaningful small change?
cost — can neighbors and objective changes be computed cheaply?
validity — do moves preserve hard constraints?

Incremental evaluation is often decisive. If one timetable move affects only two rooms and three constraints, recomputing the whole score is unnecessary.

Larger or adaptive moves can escape ridges. A hybrid may use small moves normally and occasional structured jumps.

Restart Study

For each n, run min-conflicts under a fixed step budget across at least 30 seeds. Record success rate, steps among successful runs, and total constraint evaluations. A failed run followed by a restart is not equivalent to one longer run: restarting discards the current basin and samples a new part of the landscape.

Use censored results honestly. If ten runs hit the budget, do not compute mean steps using only the successful twenty and report it as overall runtime. Report the failure count and budget separately, or count failed runs at the budget when estimating consumed work.

Hybrid Search

Local search can refine solutions produced elsewhere. A constructive heuristic creates a feasible timetable, local search improves preferences, and exact search repairs a small difficult subset. Similarly, A* may find a route and a local optimizer may then smooth or shorten it under additional geometric costs.

Hybridization should preserve an evaluation boundary. Measure the initializer, local phase, and repair phase separately so improvement can be attributed. A complex pipeline that beats a weak baseline does not reveal which component helped.

Evaluation

Stochastic optimization requires repeated trials. Report:

success rate;
best, median, and worst objective;
objective evaluations;
runtime and memory;
seeds and parameters;
convergence over time;
constraint violations.

Compare methods under equal evaluation budgets. One iteration that examines 1,000 neighbors is not equivalent to one iteration examining a single random neighbor.

Applications

timetabling;
layout design;
route improvement;
controller tuning;
feature selection;
approximate planning;
large constraint repair;
resource allocation.

Common Mistakes

Calling the best observed state “optimal.”
Using a neighborhood that disconnects the space.
Reporting one favorable seed.
Mixing hard violations with optional preferences.
Cooling without calibrating objective differences.
Recomputing global scores after a local move.
Omitting a clear stopping condition.

Exercises

Draw a landscape containing a plateau, ridge, local optimum, and global optimum.
Implement random-restart hill climbing for N-Queens.
Compare backtracking and min-conflicts on satisfiable and unsatisfiable cases.
Test three cooling schedules under the same evaluation budget.
Design two neighborhoods for timetabling and explain their reachability.
Add incremental conflict updates to a local solver and measure the speedup.
Compare one long min-conflicts run with several shorter restarts.
Add sideways-move limits to hill climbing and measure plateau escape.
Construct two states with equal conflict count but different best moves.