AI学习笔记（三）

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.

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