Other Local Search Heuristics

• Stochastic First-Ascent Hill-Climbing

  • Evaluate possible changes at random
  • Apply the first one that leads “uphill”
  • Stop when a fix amount of “unsuccessful” attempts to change the current candidate

• Simulated Annealing

  • Similar idea, but also apply “downhill” changes with a probability that is proportional to the change in score
  • Use a temperature to control amount of random downhill steps
  • Slowly “cool” temperature to reach a regime where performing strict uphill moves

Previous slide

Next slide

Back to first slide

View graphic version