next up previous

4.1.4 SA Computational Considerations     continued...

SA is an intrinsically sequential algorithm, due to its recursive structure. Some possible parallel designs (reviewed by Arts and Korst [2]) have been developed, making use of the idea of multiple trial parallelism, in which several different trial solutions are simultaneously generated, evaluated and tested on individual processors. Whenever one of these processors accepts its solution, it becomes the new one from which others are generated. Although such an approach results in N times as many solutions being investigated per unit time (where N is the number of processors), it is found that the total (elapsed) time required for convergence is not proportionally reduced. This is due to the fact that the instantaneous concurrent efficiency h, which in this context can be defined as

where is the time taken for a new solution to be accepted by the serial or parallel algorithm, varies as the search progresses. It is initially only about , because the vast majority of the solutions generated are accepted, and, therefore, N-1 of the processors are redundant. As the annealing temperature is reduced (and the solution acceptance probability falls), increases, approaching 100% as T nears zero. However, the overall incentive for parallelizing the optimization scheme is not great, especially as in many instances the problem function evaluation procedure can be multitasked with much greater ease and effect.