Local Search

Jr Codex AI Notes

Level: Intermediate Prerequisites: Chapter 3 Time to complete: ~25 minutes

Table of Contents

1. When the Path Doesn't Matter
2. Hill Climbing
3. The Local Maximum Problem
4. Simulated Annealing
5. Genetic Algorithms
6. When to Use Local Search
7. Summary & Next Steps

1. When the Path Doesn't Matter

Every algorithm in Chapters 2-3 cared about how you got there — the path from start to goal, and its cost. Local search is for a different kind of problem: you only care about finding a good final state, and the path taken to reach it is irrelevant.

Path-Based Search (Ch.2-3)             Local Search (this chapter)
─────────────────────────────         ─────────────────────────────
  "Find the CHEAPEST ROUTE from         "Find the BEST ARRANGEMENT of
   Arad to Bucharest"                     8 queens on a chessboard so
                                            none attack each other"
  The SEQUENCE of moves matters             Only the FINAL arrangement
                                              matters — how you got
                                              there is irrelevant
─────────────────────────────         ─────────────────────────────

Local search trades the guarantee of finding the true optimum for the ability to handle vastly larger problems — it typically uses a tiny, constant amount of memory (just the current state), unlike BFS/UCS/A*'s frontier, which can grow enormous.

2. Hill Climbing

The simplest local search algorithm: start somewhere, and repeatedly move to a better neighboring state, stopping when no neighbor is better — exactly "always walk uphill."

import random
 
def hill_climbing(initial_state, get_neighbors, evaluate):
    """
    initial_state: a starting configuration
    get_neighbors: function returning a list of "nearby" states
    evaluate: function scoring a state (HIGHER is better)
    """
    current = initial_state
    current_score = evaluate(current)
 
    while True:
        neighbors = get_neighbors(current)
        best_neighbor = max(neighbors, key=evaluate)
        best_score = evaluate(best_neighbor)
 
        if best_score <= current_score:
            return current, current_score      # no improvement possible — stop
 
        current, current_score = best_neighbor, best_score

# Classic example: the 8-Queens problem — place 8 queens on a chessboard
# so no two attack each other (same row, column, or diagonal)
 
def count_attacking_pairs(board):
    """board[i] = column of the queen in row i. LOWER score is better here."""
    attacks = 0
    n = len(board)
    for i in range(n):
        for j in range(i + 1, n):
            if board[i] == board[j] or abs(board[i] - board[j]) == abs(i - j):
                attacks += 1
    return attacks
 
def get_queen_neighbors(board):
    """All boards reachable by moving ONE queen to a different row in its column."""
    neighbors = []
    n = len(board)
    for col in range(n):
        for row in range(n):
            if row != board[col]:
                new_board = board[:]
                new_board[col] = row
                neighbors.append(new_board)
    return neighbors
 
initial = [random.randint(0, 7) for _ in range(8)]
# Note: hill_climbing above maximizes; for MINIMIZING attacks, negate the score
solution, attacks = hill_climbing(
    initial, get_queen_neighbors, lambda b: -count_attacking_pairs(b)
)
print(f"Final board: {solution}, attacking pairs: {-attacks}")

3. The Local Maximum Problem

Hill climbing's core weakness: it can get stuck at a state that's better than all its immediate neighbors, but still worse than the true best solution elsewhere in the state space.

The Local Maximum Trap
─────────────────────────────────────────
  Score
    │           ╱‾‾╲              ╱‾‾‾‾╲
    │          ╱    ╲            ╱      ╲
    │         ╱ LOCAL ╲          ╱ GLOBAL  ╲
    │        ╱ MAXIMUM  ╲       ╱  MAXIMUM   ╲
    │_______╱             ╲____╱               ╲______
                State space  →

  Hill climbing starting on the LEFT peak gets stuck there —
  every neighboring state is WORSE, so it stops, never
  discovering the taller peak further to the right.
─────────────────────────────────────────

Other Related Traps
─────────────────────────────────────────
  Plateau:    a flat region where neighboring states score
               EQUALLY — hill climbing has no clear direction
               to move, and may wander or stop prematurely

  Ridge:        a sequence of local maxima that, navigated
                  carefully, lead to a higher point — but each
                  individual STEP from the ridge looks like a
                  step DOWN, tricking simple hill climbing
─────────────────────────────────────────

Common mitigations: random restarts (try hill climbing from many different starting points, keep the best result found) — a simple, often effective fix, but it doesn't guarantee escaping local maxima, just improves the odds. Sections 4-5 cover more principled solutions.

4. Simulated Annealing

Inspired by the metallurgical process of slowly cooling metal to reach a low-energy crystalline state — simulated annealing allows occasional moves to worse states, with decreasing frequency over time, specifically to escape local maxima.

import random
import math
 
def simulated_annealing(initial_state, get_neighbors, evaluate, initial_temp=100, cooling_rate=0.95, min_temp=0.01):
    current = initial_state
    current_score = evaluate(current)
    temperature = initial_temp
 
    while temperature > min_temp:
        neighbors = get_neighbors(current)
        candidate = random.choice(neighbors)      # a RANDOM neighbor, not necessarily the best
        candidate_score = evaluate(candidate)
 
        delta = candidate_score - current_score
 
        if delta > 0:
            # Always accept an IMPROVEMENT
            current, current_score = candidate, candidate_score
        else:
            # SOMETIMES accept a worse move — probability depends on how much
            # worse it is, and the current temperature
            acceptance_probability = math.exp(delta / temperature)
            if random.random() < acceptance_probability:
                current, current_score = candidate, candidate_score
 
        temperature *= cooling_rate      # gradually "cool down"
 
    return current, current_score

Why "Cooling" Works
─────────────────────────────────────────
  HIGH temperature (early on):   accepts worse moves often —
                                   explores broadly, escapes local
                                   maxima easily

  LOW temperature (later on):      accepts worse moves rarely —
                                     behaves more like plain hill
                                     climbing, fine-tuning near a
                                     good solution already found
─────────────────────────────────────────

The trade-off: simulated annealing is more likely to find the true global maximum than plain hill climbing, but takes longer and introduces randomness — running it twice can produce different results, unlike hill climbing's deterministic (if potentially suboptimal) behavior.

5. Genetic Algorithms

Inspired by biological evolution — maintain a population of candidate solutions, and repeatedly combine and mutate the best ones to produce better offspring over many "generations."

import random
 
def genetic_algorithm(population, fitness_fn, crossover_fn, mutate_fn, generations=100):
    for generation in range(generations):
        # Evaluate FITNESS of every candidate in the population
        scored = [(fitness_fn(individual), individual) for individual in population]
        scored.sort(reverse=True, key=lambda x: x[0])      # best first
 
        # SELECTION — keep the fittest half as "parents"
        parents = [individual for _, individual in scored[:len(scored) // 2]]
 
        # CROSSOVER — combine pairs of parents to produce a new generation
        next_generation = parents[:]      # elitism: keep the best parents directly
        while len(next_generation) < len(population):
            parent1, parent2 = random.sample(parents, 2)
            child = crossover_fn(parent1, parent2)
            if random.random() < 0.1:      # MUTATION — small random chance of change
                child = mutate_fn(child)
            next_generation.append(child)
 
        population = next_generation
 
    best_fitness, best_individual = max(
        (fitness_fn(ind), ind) for ind in population
    )
    return best_individual, best_fitness

# Applying this to 8-Queens — reusing count_attacking_pairs from Section 2
 
def queens_fitness(board):
    """HIGHER is better — invert attacking pairs count."""
    max_possible_attacks = 28      # C(8,2) — the worst possible board
    return max_possible_attacks - count_attacking_pairs(board)
 
def queens_crossover(parent1, parent2):
    """Combine: first half from parent1, second half from parent2."""
    midpoint = len(parent1) // 2
    return parent1[:midpoint] + parent2[midpoint:]
 
def queens_mutate(board):
    """Randomly move ONE queen to a different row."""
    board = board[:]
    col = random.randint(0, len(board) - 1)
    board[col] = random.randint(0, len(board) - 1)
    return board
 
initial_population = [[random.randint(0, 7) for _ in range(8)] for _ in range(20)]
best_board, best_fitness = genetic_algorithm(
    initial_population, queens_fitness, queens_crossover, queens_mutate
)
print(f"Best board found: {best_board}, fitness: {best_fitness}/28")

The Genetic Algorithm Cycle
─────────────────────────────────────────
  Population  →  Evaluate Fitness  →  Select Best  →  Crossover
       ▲                                                    │
       └──────────────── Mutate ◄──────────────────────────┘
                  (repeat for many generations)
─────────────────────────────────────────

Genetic algorithms explore multiple candidate solutions simultaneously (the population), unlike hill climbing/simulated annealing's single current state — this parallelism, combined with crossover's ability to combine good "traits" from different candidates, can escape local maxima more effectively for certain problem structures.

6. When to Use Local Search

Decision Guide
─────────────────────────────────────────
  Need the ACTUAL PATH/sequence of actions
      → path-based search instead (Ch.2-3: BFS/DFS/UCS/A*)

  Only need a GOOD FINAL STATE, state space is HUGE
  (e.g. optimizing a schedule with millions of possible arrangements)
      → local search (this chapter)

  Willing to accept a possibly-SUBOPTIMAL but GOOD-ENOUGH answer,
  in exchange for handling MUCH larger problems with LESS memory
      → local search, especially simulated annealing or genetic
        algorithms if hill climbing gets stuck too easily
─────────────────────────────────────────

7. Summary & Next Steps

Key Takeaways

• Local search cares only about finding a good final state, not the path to reach it — enabling it to handle vastly larger problems with minimal memory compared to Chapters 2-3's path-based search.
• Hill climbing always moves to the best neighboring state, but can get permanently stuck at a local maximum, plateau, or ridge.
• Simulated annealing allows occasional worse moves, with decreasing probability over time ("cooling"), specifically to escape local maxima that trap plain hill climbing.
• Genetic algorithms maintain and evolve a whole population of candidate solutions via selection, crossover, and mutation — exploring multiple regions of the state space simultaneously.

Concept Check

1. Why is local search's memory usage so much lower than BFS or A*'s?
2. Why does simulated annealing accept worse moves early on but rarely later?
3. What's the key structural difference between genetic algorithms and hill climbing/simulated annealing, in terms of how many candidate solutions are considered at once?

Next Chapter

→ Chapter 5: Adversarial Search & Game Playing

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index