
where Aj and Bj are the minimum and maximum of the jth dimensional range. Values of yj are generated from generating temperature Tj and uniform random values uj
yj = sgn(uj ? 1
2)Tj[(1 + 1=Tj)j2uj?1j ? 1]
where yj 2 [?1; 1]: The VFSR generating distribution is defined as
gT (y) =
D
Y
j=1
1
2(jyjj + Tj) ln(1 + 1=Tj) : (3)
The main advantages of VFSR are its fast annealing time and mathematical guarantee of convergence. A detailed description of the VFSR algorithm can be found in [3, 4, 6].
4 Parallel VFSR
Figure 2 shows an overview of the parallel VFSR temperature block partitioning algorithm. In each parallel temperature block, the global generating temperature Tgen and current state xcurrent are broadcast to all processors. Each parallel processor computes a unique local Tgen;i from the VFSR annealing schedule, using the current global generating temperature as the starting point and its processor index as the annealing sequence number.
In parallel, the processors stochastically generate their local trial states xtrial;i, evaluate the corresponding local function costs and probabilistically accept or reject their local trial states. If one or more local states are accepted, the global current state is replaced by the accepted trial state whose parameters were generated at the the highest temperature Tgen;i. In addition, the acceptance temperature Taccept is lowered according to its annealing schedule and the global generation temperature is replaced by Tgen;i+1. Should no local state be accepted, the global current state remains unchanged and the global generating temperature is updated to reflect the number of rejected trial states.
5 Methods
The parallel VFSR algorithm was implemented and tested on a Connection Machine 2, attached to a SUN 4 interface. Each parallel test used 8k of the 64k parallel processors available on the CM2, and ran in exclusive mode. Sequential VFSR tests were performed
PARALLEL VFSR
Initialize acceptance temperature to high value.
Initialize generating temperatures to high values.
Initialize function parameters to random values
Calculate function cost
DO UNTIL (user specified termination)
Broadcast state and annealing temperatures
BEGIN PARALLEL
Calculate local Tgen;i
Stochastically generate local trial state
Calculate local function cost
Probabilistically accept local trial state
END PARALLEL
IF (any state accepted) THEN
Replace current state with accepted local
trial state of highest Tgen;i
Anneal generating temperature starting
from new state's Tgen;i
Anneal Taccept
ELSE
Anneal generating temperature starting
from lowest Tgen;i in block.
Aperiodically reanneal generating temperatures
END
Return function minimum
Figure 2: The parallel VFSR algorithm.
exclusively on the SUN4 computer serving as the CM 2 interface.
The probabilistic nature of simulated annealing requires multiple trials with different pseudorandom number generator seeds to produce statistically significant results. Therefore, for each test function we measured sequential and parallel VFSR performance using ten different random number generator (RNG) seeds and reported the average values. All tests used the default VFSR optimization parameter set, as supplied with sequential VFSR source [5]. VFSR has multiple exit criteria, of which the most commonly met criteria are 1) reaching sufficiently low annealing temperatures, 2) not accepting a trial state after a sufficient number of iterations, and 3) exceeding a set number of total loop iterations.