Parallel simulated annealing using an adaptive resampling interval

• We parallelize simulated annealing by resampling states periodically.
• The interval between resamplings affects the success rate greatly.
• We get near 90% efficiency on 192 processors from the best resampling interval.
• We can control the resampling interval adaptively using the adoption rate.
• The adaptive results are comparable to using hand tuned resampling intervals.

This paper presents a parallel simulated annealing algorithm that is able to achieve 90% parallel efficiency in iteration on up to 192 processors and up to 40% parallel efficiency in time when applied to a 5000-dimension Rastrigin function. Our algorithm breaks scalability barriers in the method of Chu et al. (1999) by abandoning adaptive cooling based on variance. The resulting gains in parallel efficiency are much larger than the loss of serial efficiency from lack of adaptive cooling. Our algorithm resamples the states across processors periodically. The resampling interval is tuned according to the success rate for each specific number of processors. We further present an adaptive method to determine the resampling interval based on the adoption rate. This adaptive method is able to achieve nearly identical parallel efficiency but higher success rates compared to the fixed interval one using the best interval found.