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.
