Week 4 — Local Search

The constant-memory optimizer — climb the best local neighbor, stop when stuck. Why it fails and beam/search/variants fix it

  1. Hill Climbing and Local Search

    The constant-memory optimizer — climb the best local neighbor, stop when stuck. Why it fails and beam/search/variants fix it

  2. Solution Space Search and the SAT Landscape

    Stop searching states, start searching solutions — synthesis vs perturbation, the SAT landscape, and why ridge edges trap hill climbers

  3. Stochastic Hill Climbing and Simulated Annealing

    Accept bad moves on purpose — the sigmoid rule, the temperature dial, and the metallurgy metaphor that escapes local optima

  4. Genetic Algorithms

    Evolve a population of solutions — roulette selection, crossover, mutation, and why losing diversity kills the search

  5. Genetic Algorithms for TSP — Representations and Crossover

    Why naive crossover breaks tours — cycle crossover, PMX, order crossover, adjacency encoding, and the ordinal trick that makes any cut safe

  6. Ant Colony Optimization

    Simple ants, collective intelligence — pheromone trails solve TSP without any ant knowing the tour exists