Parallel Very Fast Simulated Reannealing by Temperature Block
Sandra G. Dykes and Bruce E. Rosen
Division of Mathematics, Computer Science, and Statistics
The University of Texas at San Antonio
San Antonio, Texas 78249
This work describes a parallel implementation of Very Fast Simulated Reannealing (VFSR), an advanced simulated annealing method for optimization of non-linear, multi-dimensional functions with large numbers of local minima. Parallel VFSR speed-ups on a CM-2 connection machine are reported for eight functions: De Jong's test suite, a 10-D parabolic function, and two multi-modal, highly non-linear functions. Within the test set, the function characteristic most affecting parallel VFSR performance is number of optimized function parameters. Low dimension functions profited least from parallelization, exhibiting speedups from 2 to 78 (where speedups are based on number of function evaluation cycles). Speed-ups for the three 10-D cost functions increased to 410, 823 and 1124. On a stochastic high dimensional (D=30) quartic cost function, the cycle ratio was over 19000. We present results of a systematic study of the dimensionality effect on three test functions.
Simulated annealing (SA) is a probabilistic optimization technique well-suited to multi-modal, discrete, non-linear and non-differentiable functions. SA's main strength is its statistical guarantee of global minimization, even in the presence of many local minima. The price one pays for global minimization is execution time: simulated annealing methods are notoriously slow. Hence there is mounting interest in using parallel algorithms and architectures to speed up the annealing process. This work introduces a parallel
?This work is supported in part by a grant from the University of Texas at San Antonio Faculty Research Awards and Ph.D. Strategic Fund.
implementation of the advanced simulated annealing method known as Very Fast Simulated Reannealing (VFSR), which has previously been shown to outperform standard Boltzmann and Cauchy simulated annealing algorithms [4, 6, 8], as well as standard Genetic Algorithms .
Simulated annealing is an inherently iterative algorithm, making it difficult to parallelize efficiently. In each annealing cycle a trial set of function parameters is generated stochastically from the current state and a generating distribution. This trial state may be either rejected or accepted as the new current state, depending probabilistically upon the difference in function value between the current and trial states. All trial states have a finite probability of acceptance, no matter how large their corresponding function value. However, trial states with lower function values are more likely to be accepted. Typically, the ratio of accepted to generated states is initially large, but drops rapidly in the first few annealing cycles. The search process continues for many more cycles until a global solution (or a good" approximation to it) is found. After the first few annealing cycles a low cost state is usually located. From then on, an overwhelming number of trial states are rejected and the current state is seldom changed.
Our parallel implementation of the VFSR algorithm exploits this predominate rejection of trial states. In the parallel algorithm, a block or sequence of generating temperatures is computed from the annealing schedule, starting at a current global generating temperature Tgen. Each parallel processor is assigned a unique Tgen;i from the sequence, and uses this temperature to stochastically generate a local trial state. The processors simultaneously evaluate their local cost functions and then probabilistically accept or reject their local trial states. If one or more local states are accepted, the global current state is replaced by the