What is this step for in the Simulated Annealing algorithm?

Question

Both Wikipedia and this site describe a similar step in the Simulated Annealing algorithm, which I've picked out here:

Wikipedia:

  if P(e, enew, temp(k/kmax)) > random() then   // Should we move to it?
    s ← snew; e ← enew                          // Yes, change state.

Yuval Baror, regarding the Eight Queens puzzle:

If moving the queen to the new column will reduce the number of attacked 
queens on the board, the move is taken. Otherwise, the move is taken only 
with a certain probability, which decreases over time. 
Hence early on the algorithm will tend to take moves even if they 
don't improve the situation. Later on, the algorithm will only make moves 
which improve the situation on the board.

My question is: what does this random move achieve?

Answer 1

The purpose is to avoid settling at a localised best solution and instead try and find the global best solution See here: http://en.wikipedia.org/wiki/Local_minimum

You allow a random amount of movement that may initially make your position worse in the hope of finding a better overall solution than the one you would find by only taking steps that improve you position.

The "annealing" part of the name is that the amount of movement allowed to worse positions is decreased over time.

Answer 2

To only take the solutions that improve the situation is termed 'greedy', and means you find the local optima.