How to generate neighbors for simulated annealing

I am learning about simulated annealing algorithm and want to create a general purpose one for optimizing continuous functions.

The problem I have is how to generate the neighbor points as candidates. Random shift of steps is one strategy available in literature, but it seems more applicable for discrete problems.

What are the strategies for generating neighbor points for this type of application?

1 Answer

The standard approach is to pick a trial sample either (i) randomly in a ball of given radius centered at the current sample, or (ii) randomly drawn from a Gaussian centered at the current sample and with a standard deviation chosen like you would draw the radius in the previous option.

There are better methods (e.g., drawing from ellipses), but this is a good enough starting point.

• Thank you for your answer! I presume that the (i) ball radius or (ii) standard deviation should decrease as the 'temperature' goes down to progressively favor local search – Tianxun Zhou Feb 11 at 1:20
• Yes, that is correct. You usually use a temperature schedule of the kind $T_k=T_0/k^\alpha$ where $k$ is the iteration number and $\alpha$ could be something like 1/2 or 1/4. – Wolfgang Bangerth Feb 11 at 16:40