Local search keeps one candidate solution and repeatedly replaces it with a better one nearby. It needs three things: a way to represent a candidate, a neighborhood that says which candidates count as nearby, and an objective that scores them. A hill climber evaluates neighbors and moves to a better one until no neighbor is better. The method is old, simple, and often effective, and it is the right place to start a course on evolutionary computation. The mutation step of an evolutionary algorithm is itself a local search, and most of the field's machinery exists to fix the problem that hill climbing makes obvious: a search that only moves uphill stops at the first peak it reaches, whether or not that peak is the highest.
This topic treats local search on its own terms before populations enter the picture. It defines the variants of hill climbing and the shapes of search space that defeat them: local optima, plateaus, and ridges. It then covers the standard ways to escape: sideways moves, random restarts, simulated annealing, tabu search, and iterated local search. Each trades some of hill climbing's speed for a better chance of reaching a good solution. The last article applies hill climbing to two classic puzzles, the course's first assignment, and measures how often it succeeds.
Articles
- Hill climbing: first-improvement, steepest-ascent, first-choice, and stochastic variants, traced step by step on a small grid and measured on a 100-city tour; local optima, plateaus, and ridges, with their basins of attraction drawn; and the (1+1) evolutionary algorithm as a hill climber with a global mutation operator.
- Escaping local optima: sideways moves, random restarts, simulated annealing, tabu search, and iterated local search, compared at equal evaluation budgets, and why a population is another answer to the same problem. Includes the Boltzmann distribution behind annealing, Hajek's cooling condition worked exactly on a small example, a traced tabu search, and an interactive comparison of hill climbing and annealing.
- Hill climbing on 8-queens and the 8-puzzle: the course's first assignment rebuilt as a reproducible experiment, with success rates, the effect of sideways moves and restarts, and why plateaus and local minima defeat it on the 8-puzzle. Includes worked boards and an interactive 8-queens board that shows the heuristic value of every move.
Related topics
Local search moves across a fitness landscape, and the shape of that landscape decides whether it succeeds. Genetic algorithms replace the single candidate with a population and add recombination, which lets information from different regions of the search space combine. In information retrieval, k-means clustering is a local search of the same kind: each iteration cannot make the clustering worse, and the result depends on where it starts.
References
- Eiben, A. E., and Smith, J. E. (2015). Introduction to Evolutionary Computing, 2nd ed. Springer.
- Russell, S., and Norvig, P. (2020). Artificial Intelligence: A Modern Approach, 4th ed. Pearson.