This course is run at the The University of Nottingham within the School of Computer Science & IT. The course is run by Graham Kendall (EMAIL : gxk@cs.nott.ac.uk)
As we have seen in previous lectures, hill climbing suffers from problems
in getting stuck at local minima (or maxima). We could try to overcome these
problems by trying various techniques.
· We could try a hill climbing algorithm using different starting points.
· We could increase the size of the neighbourhood so that we consider more of the search space at each move. For example, we could try 3-opt, rather than a 2-opt move when implementing the TSP.
Unfortunately, neither of these have proved satisfactory in practice when using
a simple hill climbing algorithm.
Simulated annealing solves this problem by allowing worse moves (lesser quality) to be taken some of the time. That is, it allows some uphill steps so that it can escape from local minima.
Unlike hill climbing, simulated annealing chooses a random move from the neighbourhood
(recall that hill climbing chooses the best move from all those available -
at least when using steepest descent (or ascent)).
If the move is better than its current position then simulated annealing will always take it. If the move is worse (i.e. lesser quality) then it will be accepted based on some probability. This is discussed in the next section.
| Previous Page | Index Page | Next Page |
Last Updated : 26/01/2002