2
$\begingroup$

I've coded a personal version for the simulated annealing problem, and I was wondering why, (other than by analogy to the physics), the probability is $$ p = e^{-\dfrac{\Delta \text{length}}{T}}$$ (assuming we're applying to the TSP problem, so the parameter is here the length of the circuit).

Is there any way to explain why this law and not another? Is this one optimal?

$\endgroup$
1
$\begingroup$

This formula can more insightfully be written as

$$ p = \frac{1}{e^{\dfrac{\Delta E}{T}}}$$

where, in the context of SA, $\Delta E$ is the difference between the "energy" (or quality) of two possible solutions and $T$ is the temperature (which is either a constant or a function of the input size).

So, the higher the energy difference $\Delta E$, the smaller the probability $p$. In the context of SA, if the cost of the current solution is greater than the cost of the new solution, then you replace the current solution with the new solution. However, if the cost of the current solution is smaller than the new solution, then you do not automatically discard the new solution. More concretely, with probability $p$, you accept the new worse solution. This the stochastic action taken by SA. So, the higher the diffence between the costs of the current and new solutions, the smaller the probability of accepting the new worse solution.

The Boltzman distribution only happens to capture this idea of accepting new worse solutions, provided that they are not extremely worse than the current solution. In theory, you can use other (similar) distributions.

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