I was asked in an exam wether we could improve the SA algorithm by keeping a memory of the best N solutions (so far).
I couldn't find any examples of this being done in practice.
I could only think that we could use this to avoid areas that seem to converge to higher energy levels, and thus complete the search faster.
Is this correct? Are there any other benefits in using memory?
The short answer is, surprisingly, no.
The usual "plain vanilla" SA algorithm keeps track of one best known solution and ultimately returns that. What would be the advantage in keeping track of N-1 additional ones? Remember that a lot of those others are likely to be close to the best known optimum anyway. So what would you do with them?
Restart strategies use the best known solution and restart the chain from there if the algorithm finds itself stuck in an area where the solution is significantly worse than the best known. I suppose that you could pick one of them at random. I don't know if anyone has ever looked into this.
A more common strategy, if you have memory, is to run multiple chains in parallel. This has the additional advantage that it works extremely well on parallel hardware.
Another area worth mentioning is genetic algorithms, which can be thought of as a variant of simulated annealing. This inherently uses a set of solutions rather than one, and solutions are both mutated like SA, and cross-bred.
I would agree with your answer. Also, the memory could help when you are stuck in a local minimum and you already visited a deeper minimum.
