title: Parallel Simulated Annealing Using an Adaptive Resampling Interval.
abstract: 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 Chuet 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.
authors.affiliation: Department of Computer Science, the University of Chicago, Chicago, Illinois, USA.
authors.forename: Zhihao
authors.initials: Z
authors.lastname: Lou
authors.affiliation: Department of Statistics, Department of Ecology and Evolution, Department of Molecular Genetics and Cell Biology, Institute of Genomics and Systems Biology, the University of Chicago, Chicago, Illinois, USA.
authors.forename: John
authors.initials: J
authors.lastname: Reinitz
keywords: MPI; Rastrigin function; evolutionary computation; global optimization; parallel algorithm; stochastic optimization