Abstract

Simulated annealing is an attractive, but expensive, heuristic for approximating the solution to combinatorial optimization problems. Attempts to parallelize simulated annealing, particularly on distributed memory multicomputers, are hampered by the algorithm's requirement of a globally consistent system state. In a multicomputer, maintaining the global state S Involves explicit message traffic and is a critical performance bottleneck. To mitigate this bottleneck, it becomes necessary to amortize the overhead of these state updates over as many parallel state changes as possible. By using this technique, errors in the actual cost C(S) of a particular state S will be introduced into the annealing process. This paper places analytically derived bounds on this error in order to assure convergence to the correct result. The resulting parallel Simulated Annealing algorithm dynamically changes the frequency of global updates as a function of the annealing control parameter, i.e. temperature. Implementation results on an Intel iPSC/2 are reported.

Department(s)

Computer Science

Comments

The first Author is a Graduate Student.

This work was supported in part by the National Science Foundation under Grant Number CDA-8820714 and in part by the University of Missouri Weldon Springs Foundation.

Report Number

CSc-92-06

Document Type

Technical Report

Document Version

Final Version

File Type

text

Language(s)

English

Rights

© 1992 University of Missouri - Rolla, All rights reserved

Publication Date

6-April, 1992

Download

Share

 
COinS