page 3  (6 pages)
to previous section2
4to next section

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 CM-2, 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 SUN-4 computer serving as the CM- 2 interface.

The probabilistic nature of simulated annealing requires multiple trials with different pseudo-random 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.