In the paper, a novel problem-independent parallel realisation of the simulated annealing (SA) algorithm is proposed. By employing speculative computation, concurrency is introduced into the inherently sequential algorithm. This is achieved by predicting the acceptance of each generated move before the move is evaluated. Based on this prediction, subsequent moves can be proposed and evaluated before decisions on whether to accept or reject preceeding moves are made. To preserve the sequential decision nature of SA, all moves subsequent to a prediction that is eventually proved wrong are discarded. A simple and effective prediction mechanism using previous move statistics is developed. Efficient realisation of the parallel SA algorithm on a ring multiprocessor architecture is described. Analytical and simulation performance results are presented. These results indicate that the authors' parallel SA is best implemented on a coarse to medium grain multiprocessor system. Factors affecting performance in actual implementations are also discussed.
References
-
-
1)
-
Rutenbar, R., Kravitz, S.: `Layout by annealing in a parallel environment', Proc. IEEE Int. Conf. Computer Design, 1986, p. 434–437.
-
2)
-
D. Abramson
.
A very high speed architecture for simulated annealing.
IEEE Comput.
,
5 ,
27 -
36
-
3)
-
R.H.J.M. Otten ,
L.P.P.P. van Ginneken
.
(1989)
The annealing algorithm.
-
4)
-
M. Marchesi ,
G. Molinari ,
M. Repetto
.
A parallel simulated annealingalgorithm for the design of magnetic structures.
IEEE Trans. Magn.
,
5 ,
3439 -
3442
-
5)
-
Sohn, A.: `Parallel speculative computation of simulated annealing', Proc. IEEE Int. Conf. Parallel Processing, 1994, 3, p. 8–11.
-
6)
-
E. Aarts ,
F. de Bont ,
J. Habers ,
P. van Laarhoven
.
Parallel implementationsof the statistical cooling algorithm.
Integration
,
209 -
238
-
7)
-
F. Witte ,
R. Chamberlain ,
M. Franklin
.
Parallel simulated annealing usingspeculative computation.
IEEE Trans. Parallel and Distrib. Syst.
,
4 ,
483 -
494
-
8)
-
S. Kirkpatrick ,
C.D. Gelatt ,
M.P. Vecchi
.
Optimization by simulated annealing.
Science
,
4598 ,
671 -
680
-
9)
-
K. Wong ,
Y. Wong
.
Short-term hydrothermal scheduling, part 2: Parallelsimulated annealing approach.
IEE Proc., Gener., Transm. Distrib.
,
5 ,
502 -
506
-
10)
-
Greening, D.: `Simulated annealing with errors', 1995, PhD thesis, UCLA.
-
11)
-
D. Greening
.
Parallel simulated annealing techniques.
Physica D: Nonlinear Phenomena
,
293 -
306
-
12)
-
Y. Kim ,
M. Kim
.
A step-wise-overlapped parallel annealing algorithm on amessage-passing multiprocessor system.
Concurrency, Prac. Exp.
,
2 ,
123 -
148
-
13)
-
P. Roussel-Ragot ,
G. Dreyfus
.
A problem independent parallel implementationof simulated annealing: Models and experiments.
IEEE Trans. Comput.-Aided Des.
,
8 ,
827 -
835
http://iet.metastore.ingenta.com/content/journals/10.1049/ip-cdt_19960469
Related content
content/journals/10.1049/ip-cdt_19960469
pub_keyword,iet_inspecKeyword,pub_concept
6
6