Improvements Of Basic Local Search
Issue: How to move more quickly to successively lower plateaus?
Idea: Introduce uphill moves (“noise”) to escape from long plateaus (or true local minima).
Noise strategies:
a) Simulated Annealing
(Kirkpatrick et al. 1982)
b) Biased Random Walk
(Selman, Kautz , and Cohen 1993)