Sample-Sort Simulated Annealing

Abstract

A simulated annealing (SA) algorithm called Sample-Sort that is artificially extended across an array of samplers is proposed. The sequence of temperatures for a serial SA algorithm is replaced with an array of samplers operating at static temperatures and the single stochastic sampler is replaced with a set of samplers. The set of samplers uses a biased generator to sample the same distribution of a serial SA algorithm to maintain the same convergence property. Sample-Sort was compared to SA by applying both to a set of global optimization problems and found to be comparable if the number of iterations per sampler was sufficient. If the evaluation phase dominates the computational requirements, Sample-Sort could take advantage of parallel processing.