Solving Optimization Problems by Parallel Recombinative Simulated Annealing on a Parallel Computer

Publication Type
Journal contribution
Authors
Karl Kurbel, Bernd Schneider, Kirti Singh
Year of publication
1998
Published in
IEEE Transactions on Systems, Man, and Cybernetics, Part B
Band/Volume
28/3
Page (from - to)
454-461
Abstract

In this paper, parallel recombinative simulated annealing (PRSA), a hybrid method with features of simulated annealing and genetic algorithms, is examined. PRSA inherits the global convergence property from simulated annealing and the parallelism property from genetic algorithms. PRSA was implemented on a monoprocessor system as well as on a transputer. The algorithm, its parallel implementation, and its application to an NP-hard problem, namely standard cell placement in very large scale integration (VLSI) chip design, are described. PRSA was run for a large range of test cases. Since its performance depends on many parameters, the effects of parameter variations are studied in detail. Some important parameters are migration of individuals to other transputer nodes and selection strategies for constructing new populations. In comparison with simulated annealing and genetic algorithms, PRSA was found to produce better solutions.

Involved persons

Involved institutions