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

Publikations-Art

Zeitschriftenbeitrag

Autoren

Karl Kurbel, Bernd Schneider, Kirti Singh

Erscheinungsjahr

1998

Veröffentlicht in

IEEE Transactions on Systems, Man, and Cybernetics, Part B

Band/Volume

28/3

Seite (von - bis)

454-461

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.