2
$\begingroup$

What is the difference between Simulated Annealing and Monte-Carlo Simulations? Is Simulated Annealing a specific type of Monte-Carlo simulation, or are they completely separate techniques?

$\endgroup$
4
$\begingroup$

Monte Carlo simulation is a method for computing a function. Simulated annealing is an optimization heuristic. Other than that, the only common thread behind these two methods is the use of randomness.

In Monte Carlo simulation, we are aiming at computing some quantity $A$ by finding an easily samplable random variable $X$ whose expectation is $A$. We estimate $A$ by averaging many samples of $X$. More sophisticated versions of this are rejection sampling and MCMC.

Simulated annealing is a heuristic for optimizing an objective function $f$ over a domain $D$. We start with an arbitrary point $x \in D$, and then try making local changes which improve the value of $f$; this is local search. In simulated annealing, we also allow making local changes which worsen the value of $f$, with some small probability. The probability is smaller the more the change makes $f$ worse.

$\endgroup$
  • $\begingroup$ Some people here qr.ae/TWN8jd state that SA is an instance of a MC method. What do you have to say about these statements? $\endgroup$ – nbro May 13 at 15:28
  • $\begingroup$ It depends on what you consider Monte Carlo. It’s really up to you - there’s no formal definition. $\endgroup$ – Yuval Filmus May 13 at 16:31
0
$\begingroup$

Simulated Annealing is closely related to Markov-Chain Montecarlo, and the Metropolis algorithm. The main difference is that MCMC aims to generate samples that respect and underlying distribution, while SA aims to find the maximum of a function. The similarity is that in both cases you want to visit the parts of the function that have the high values with higher frequency, but in SA you actually want to converge and in a way "get stuck" in a peak, while with MCMC you want sometimes to sample the other parts of the function too as you aim to visit every part of the function with a frequency proportional to the value. Algorithmically this is achieved in SA with the "annealing schedule" which shrinks the movement radius of the random walk over time in order to zero in a local maxima.

$\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.