Parallel simulated annealing techniques

Abstract

Simulated annealing is a stochastic algorithm for solving discrete optimization problems, such as the traveling salesman problem and circuit placement. To reduce execution time, researchers have parallelized simulated annealing. Serial-like algorithms identically maintain the properties of sequential algorithms. Altered generation algorithms modify state generation to reduce communication, but retain accurate cost calculations. Asynchronous algorithms reduce communication further by calculating cost with outdated information. Experiments suggest that asynchronous simulated annealing can obtain greater speedups than other techniques. It exhibits the properties of cooperative phenomena: processors asynchronously exchange information to bring the system toward a global minimum. This paper provides a comprehensive, taxonomic survey of parallel simulated annealing techniques, highlighting their performance and applicability. © 1990.