Solutions to Parallel and Distributed Computing Problems: Lessons from Biological Sciences

4.4 SIMULATED ANNEALING: CONSERVATIVE PARTITIONING

Simulated annealing (SA), introduced by Kirkpatrick et al. [17], is a powerful method for optimizing functions defined over complex systems. It is based on ideas from statistical mechanics and motivated by an analogy to the behavior of physical systems in the presence of a heat bath.

While greedy algorithms and other simple iterative improvement techniques accept a new configuration of lower cost and reject more costly states, SA escapes from local minima by sometimes accepting higher cost arrangements with a probability determined by the simulated “temperature.” Simulated annealing leads to efficient heuristic algorithms with several advantages over other approaches to solving combinatorial optimization problems [30], First, it is problem independent. By substituting a few problem-specific data structures and functions, the SA algorithm can be applied to many combinatorial optimization problems. Second, SA can easily handle multiple, potentially conflicting goals of a problem. It has been successfully applied in solving combinatorial problems such as cell placements [19], floorplan design and task assignments [30].

Boukerche and Tropper [3] have shown how to apply simulated annealing to partitioning conservative simulation on multiprocessor machines. This method is derived by mapping the complex simulation system into a physical system.

In this approach, each LP is considered a particle moving in space with n distinct positions, ...