Local Search

Hill-climbing

• Simple hill climbing
  Generate successors until one is found better than current node
• Stochastic hill climbing
  Random selection among the uphill moves
• First-choice hill climbing

Simulated annealing

Local beam search

? Initially: k random states
? Next: determine all successors of the k current states ? If any successor is a goal → finished
? Else, select k best from successors and repeat

• Major difference from random-restart hill climbing
  ? k best across all successors of k states rather than one best successor from each of k states
  ? Allows more effort to be allocated to promising regions

Genetic algorithms

a variant of stochastic beam search in which successor states are generated by combining two parent states rather than by modifying a single state.

123.png

Like beam searches, GAs begin with a set of k randomly generated states, called the population.