4.10 Local search and optimisation

Work through these

• Explain the shift from finding a path to finding a state

  Some problems do not care how you got there, only where you end up, and that changes what an algorithm needs to remember. Dropping the path is what makes these methods usable on enormous spaces.

• Read a state-space landscape and write an objective function for it

  Picturing the possible states as a landscape whose height is the quality of each one, and writing the function that gives that height. Getting the objective right matters more than the search method.

• Run hill climbing and diagnose its three failures: local maxima, ridges and plateaux

  Always stepping to a better neighbour is simple and gets stuck three characteristic ways: at a false peak, on a narrow ridge, and on a flat region. Recognising which one you are in tells you what to do next.

• Apply simulated annealing, and say why accepting a worse move on purpose works

  Accepting a worse move with a probability that falls over time lets the search escape false peaks early and settle later. The physical analogy it is named after makes the schedule intuitive.

• Run local beam search with k states

  Keeping several candidate states and spreading effort among them, which is more robust than one search and cheaper than many independent ones. The number of states carried is the tuning knob.

• Apply a genetic algorithm: population, fitness, selection, crossover, mutation

  Treating candidate solutions as a population that reproduces, with fitter members more likely to contribute and occasional random change. It is a general-purpose method with a distinctive vocabulary.

• Solve n-queens with each method and compare what they cost

  Applying each method to the same classic puzzle makes their costs directly comparable. It is the exercise that stops these methods being four names on a list.