13
$\begingroup$

Given a fast-stepping Local Search (such as Simulated Annealing or Late Acceptance), which reheating approach is proven to work well?

Generally speaking, reheating works like this: if [a condition is met] then we [take action] to increase the chance of selecting moves as winning steps. But the devil is in the details. So let's split that up:

Reheating condition

When do we check the condition? At the end of every step iteration? Or at every move iteration (so every selected move) for a step?

And what do we check?

  • The best score hasn't improved for X time
  • Or, the best score hasn't improved for X step iterations
  • Or, the best score hasn't improved for X selected moves evaluated

Reheating action

In Simulated Annealing we increase the temperature. But how?

  • By a configured increasement
  • By a relative increase
  • To the starting temperature
  • ...

In Late Acceptance we increase the late score. Again, which way is proven to work well?

$\endgroup$
8
$\begingroup$

This is where automatic algorithm configuration and design comes to the rescue. In my experience, different combinations of strategies work equally fine, at least when combined with other components that have a stronger impact in the algorithm (see my work at [1]); it could even be that in certain cases reheating is not necessary.

However, following the list of questions:

1) When to check the condition: after every evaluation of a candidate solution. Checking after every accepted move might work fine at the beginning of the search, less so when you already are in a local optimum.

2) What to check: relying on time is probably not a good idea, since this is going to be inconsistent across different machines (at the same time, you can evaluate fewer solutions on a slower machine), but all the possibilities you list are valid, and there are many more possible ones (e.g. the acceptance rate in the last X moves falls below a certain threshold). If you want to test only a few solutions, I suggest reheating after X moves evaluated, or after X consecutive rejected moves.

3) How to increase the temperature: again, there are many possibilities. To keep things simple, you can reheat to the initial temperature, keeping in mind that a "low" value is better than a "high" one, because high values may promote an excessive exploration, and the search will fail to converge for a lot of time. In general, in my experiments with SA I have observed that the better performing algorithms exhibit a strong intensification from the beginning; reheating to high temperature values may bring you very far from good areas of the solution space, because you will accept too many worsening moves.

4) Late Acceptance Hill-Climbing (LAHC) can fit in the SA template, so many of the considerations done for SA apply also here. However, LAHC has fewer parameters and is also very robust, so it is easier to tune.

Anyway, the final settings will depend on the problem, the specific instances, and the other settings of the algorithm (cooling scheme, but also e.g. the running time you allow). In my experiments the temperature was usually updated after some long intervals, but with a strong cooling. But again, for your problem, YMMV.


[1] Alberto Franzin, Thomas Stützle. "Revisiting Simulated Annealing: a Component-Based Analysis". Computers and Operations Research, 2019; 104, 191-206. https://doi.org/10.1016/j.cor.2018.12.015

| improve this answer | |
$\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.