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.

$\endgroup$
0
$\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."

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