3
$\begingroup$

Context and Problem

In the Wikipedia page for Simulated Annealing they state

The simulation can be performed either by a solution of kinetic equations for density functions[2][3] or by using the stochastic sampling method.[1][4] The method is an adaptation of the Metropolis–Hastings algorithm

I've read this in some papers as well, but none ever seems to make the connection between the two.

Metropolis-Hastings PseudoCode for Reference

Here's the Metropolis-Hastings pseudocode to sample from $\pi(x)$ using a proposal $p(x'\mid x_t)$. I can't really see how this relates to Simulated Annealing.

  1. Choose starting point $x_0$
  2. Until convergence:
    1. Sample a candidate $x'\sim q(x'\mid x_t)$
    2. With probability $A(x', x_t)$ accept $x_{t+1} = x'$, otherwise set $x_{t+1}=x_t$ where $$ A(x', x_t) = \min\left(\frac{\pi(x')}{\pi(x_t)}\frac{q(x_t\mid x')}{q(x'\mid x_t)}\right) $$

How is MH, which is a method for sampling from a distribution, the same as a method used to find the global optimum ofa function?

$\endgroup$
  • $\begingroup$ The two are related, they differ in how the accept/reject new samples. SA uses an additional temperature parameter which changes the acceptance/rejection rate throughout the iterations. $\endgroup$ – user2974951 Mar 9 at 11:37
  • $\begingroup$ @user2974951 do you mind expanding that? $\endgroup$ – Euler_Salter Mar 9 at 11:45
  • 1
    $\begingroup$ Did I expand enough? $\endgroup$ – user2974951 Mar 20 at 8:35
2
$\begingroup$

Simulated annealing is a meta-heuristic algorithm used for optimization, that is finding the minimum/maximum of a function. Metropolis-Hastings is an algorithm used for exploring a function (finding possible values/samples).

Both algorithms are stochastic, generating new points to move to at random. Where they differ is in their acceptance/rejection criterion. Both algorithms move to a new random point with a certain probability, which is based on the difference (or the ratio) of the current and new proposed point in the search space.

Metropolis-Hastings moves to a new point based on the ratio of the current point and a new proposed random point $\min(\frac{new}{old},1)$, with some additional stuff for asymmetric distributions). If this ratio is bigger than 1 (the new point has higher likelihood than the current point) then it will move to this new point immediately. Otherwise, if the new point has lower likelihood, the algorithm will move to this point with some probability - based on the ratio. In this case the algorithm will generate a random value between 0 and 1, if the ratio is smaller than this values then it will reject the new point, else it will accept the new point.

Simulated annealing has an additional parameter (temperature) which scales the difference by a certain amount $\exp(\frac{new-old}{T})$. When the temperature is very high the difference won't have any meaningful impact on the decision (which will evaluate to something greater than 1), so the algorithm will always accept any new point, which means it will move at random. When the temperature is very low the criterion will evaluate to ~0 for worse points, so the algorithm will move deterministically, only accepting better solutions.

| cite | improve this answer | |
$\endgroup$

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.