1
$\begingroup$

Not sure if this is the right place, but I was wondering if someone could briefly explain to me the differences & similarities between simulated annealing and deterministic annealing?

I know that both methods are used for optimization and both originate from statistical physics with the intuition of reaching a minimum energy (cost) configuration by cooling (i.e. slowly reducing the temperature in the Boltzmann distribution to calculate probabilities for configurations).

Unfortunately, Wikipedia has no article about deterministic annealing and the one about simulated annealing does not mention any comparison.

This resource has a brief comparison section between the two methods, however, I do not understand why the search strategy of DA is

based on the steepest descent algorithm

and how

it searches the local minimum deterministically at each temperature.

Any clarification appreciated.

Improve this question
$\endgroup$
3
  • $\begingroup$ In that article that you mention, they say that "Stochastic search based on the Metropolis algorithm". However, although I am familiar with SA, I don't recall having read that anywhere (but my memory isn't that good). So, even though SA may have been based on or inspired by another algorithm/method, that information isn't probably very useful, unless you are already familiar with the Metropolis algorithm. Similarly, although I am not familiar with DA, I suspect that, generally, it may not be very relevant if it's based on the steepest descent algorithm or not, as long as you know how DA works. $\endgroup$
    – nbro
    Jun 11, 2020 at 13:31
  • $\begingroup$ Furthermore, in the introduction section of the original paper that introduced DA, the authors say k-means is a "steepest descent" algorithm, in the sense that k-means always moves in some space that decreases the cost function (so it can be trapped in a local minimum). Again, I am familiar with k-means, but I've never heard of this interpretation, even though it kind of makes sense to me. So, DA is a "steepest descent" algorithm in the sense that it always moves in some search space so that to decrease the cost (or loss), but it probably can get trapped in a local minimum. $\endgroup$
    – nbro
    Jun 11, 2020 at 13:51
  • 1
    $\begingroup$ Thanks for you comment. After some time I came to an insightful explanation as well. $\endgroup$
    – Tinu
    Jul 19, 2020 at 16:14

1 Answer 1

Reset to default
1
$\begingroup$

After diving deeper into the material I am able to answer my own question:

Simulated Annealing tries to optimize a energy (cost) function by stochastically searching for minima at different temparatures via a Markov Chain Monte Carlo method. The stochasticity comes from the fact that we always accept a new state $c'$ with lower energy ($\Delta E < 0$), but a new state with higher energy ($\Delta E > 0$) only with a certain probability

$$p(c \to c') = \text{min}\{1, \exp(-\frac{\Delta E}{T}) \},$$ $$\Delta E = E(c') - E(c).$$

Where we used the Gibbs distribution $p(c) = \frac{1}{Z}\text{exp}(\frac{-E(c)}{T})$ to calculate probabilities for each state, with $Z$ being the partition sum. The temperature $T$ plays the role of a scaling factor for the probability distribution. If $T \to \infty $ we have a uniform distribution and all states are equally possible. If $T \to 0$ we have a Dirac delta function around the global optimum. By starting with a high $T$, sampling states and gradually decreasing it, we can make sure to sample enough states from the state space and accepting energetic higher states in order to escape local minima on the way to the global optimum. After sampling long enough while slowly decreasing the temperature, we theoretically arrive at the global optimum.

Deterministic Annealing on the other hand directly minimizes the free energy $F(T)$ of the system deterministically at each temperature, e.g. by Expectation-Maximization (EM-algorithm). The intuition behind it is that we like to find an optimum at a high temperature (where it is easier to find one because there are fewer local minima), accept this as intermediate solution, lower the temperature, thus scaling the cost function such it is more peaked around it's optima (making optimization a bit more difficult) and start deterministically looking for an optimum again. This is repeated until the temperature is low enough and we (hopefully) found a global solution to our problem. Major drawback is that there is no guarantee to arrive at a global optimum in contrast to simulated annealing. The whole idea of scaling the energy function is based on the concept of homotopy: "Two continuous functions [...] can be "continuously deformed" into each other."

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .