I am using simulated annealing (SA) for an NP-hard combinatorial optimisation problem.

1) I am testing over a range of problem instances in which the objective values can be in the 100's or in the 10000's depending on the size of the problem. All pseudocode I see for SA seems to determine probability using something like:

$$p = exp \{(cost(current) - cost(proposed))/T\}$$

However, across my problem instances, the scale of the typical cost difference varies greatly.

Wouldn't it make more sense to define the difference in proportional terms, so scale-invariant?

$$p = exp \Big\{\frac{(cost(current) - cost(proposed))}{cost(current)} \frac{1}{T} \Big\}$$

Thus, the worsening of solution quality is in percentage terms rather than absolute difference. Is this a standard technique in SA and does it have a name?

2) I observe that when the temperature is high in early stages that a lot of time is burnt a long way from the best encountered solution, before the lowering temperature forces us back down again. This is partly because the cost difference for poorer proposed solutions is computed relative to the current solution (so with high acceptance probability, and most proposed solutions being worse, we could climb without bound). Why not make the cost difference relative to best encountered/known, so acceptance probability declines the higher we climb?

$$p = exp \Big\{\frac{(cost(bestEncountered) - cost(proposed))}{cost(bestEncountered)} \frac{1}{T} \Big\}$$

Is this a standard technique in SA and does it have a name?

3) Suppose we have a fixed time/computational budget, we kept track of best encountered (instead of just returning the last), and so we favoured exploration rather than quality of the solution in the last iteration.

Would we then favour constant temperature $T$ instead of reducing it over time? This way we would continue exploration even towards the end of the computational budget.

  • $\begingroup$ Please, split this post into multiple ones: one for each question! $\endgroup$ – nbro May 18 '20 at 9:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.