A Massively Scalable Parallel Simulated Annealing Algorithm

Simulated annealing algorithm is a powerful general purpose stochastic optimization algorithm that relies only on the value of the cost function being optimized. However, existing parallelizations of the simulated annealing algorithm all provide limited speedup. This dissertation presents a parallel simulated annealing algorithm using an adaptive resampling interval. The algorithm gives a speedup of 170 using 192 processor cores when applied to a 5000-dimension Rastrigin function. It also achieves a speedup of more than 40 using 128 cores on two systems biology problems. In addition, this dissertation proposes an algorithm to study the structure of the search space based on the density of states. The results provide information on setting the parameters of the annealing algorithm for the problem being optimized.