Simulated annealing with restart preserves one or a few high-quality states found during optimization. When progress becomes stuck, it resumes from one of those advantageous positions, resetting the descent or exploring another region. section 17.1.5
Use the variant to address failure modes in ordinary simulated annealing:
- A fast cooling schedule can trap the search away from the global minimum. section 17.1.5
- A lucky early visit to an excellent state can be lost after later uphill moves, especially while the temperature remains high. section 17.1.5 section 18.1
- Small update steps may make escapes from local minima too rare, while random sampling can slow local convergence. section 17.1.5
A practical implementation records the best state or a small collection of the best states across iterations. On stagnation, it randomly selects one saved state and continues the annealing process, comparing later solutions with the current best. section 17.1.5 section 18.1
Figure 18.1 An example of a scenario where simulated annealing would find a promising (Pi), or even good (Qi) solution in an early stage (as suggested by the temperature of the system, Ti, still close to T0): since all transitions, even uphill, are likely accepted when the temperature is high, the algorithm might move away from the sweet spot in the cost function landscape, and possibly never find its way back.
Visualizes how high-temperature transitions can carry the search away from a promising or good position and prevent it from returning. section 18.1
