I'm trying to understand whats the difference between simulated annealing and running multiple greedy hill-climbing algorithms.

As of my understandings, greedy algorithm will push the score to a local maximum, but if we start with multiple random configurations and apply greedy to all of them, we will have multiple local maximums. Then we choose the max of them.

Will this reproduce the same as simulated annealing?


The method you describe is called random restart hill climbing (or sometimes shotgun hill climbing), and it is a different algorithm from simulated annealing.

Yes, generally as the number of iterations $k$ increases both methods will eventually give a location $w_i$ which reaches a global optimum $w^*$. This is for the simple reason that both incorporate random search. That is, a random restart (hill climbing) or random move (simulated annealing) can turn out to coincide with a global optimum. Nevertheless, here are two important differences:

  1. random restart hill climbing always moves to a random location $w_i$ after some fixed number of iterations $k$. In simulated annealing, moving to random location depends on the temperature $T$.
  2. random restart hill climbing will move to the best location in the neighbourhood in the climbing phase. In simulated annealing, the location is selected randomly, you always move if it's better than your current location but with some probability related to $T$ you may move even if it's worse.

Simulated annealing is a somewhat more complicated algorithm, and depends on the temperature schedule which determines $T$ at iteration $k$. If the temperature $T$ is set to a very small constant value then the simulated annealing becomes like stochastic hill climbing. If $T$ is set to a very large constant value, then simulated annealing becomes like random search. The way you select the temperature schedule determines how you navigate between these two different type of behaviour.

tldr: these are different algorithms, but they use similar ideas to incorporate random sampling into search.

  • 1
    $\begingroup$ The main difference (in strategy) between greedy search and simulated annealing is that greedy search will always choose the best proposal, where simulated annealing has a probability (using a Boltzman distribution) of rejecting this and choosing a worse proposal. This helps the algorithm find a global optimum by jumping out of local optimum. Temp and other parameters are just a secondary advantage (or disadvantage) of SA. $\endgroup$ – Jon Jun 1 '18 at 16:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.