Doctoral Dissertations
Abstract
"Simulated annealing is an attractive, but expensive, heuristic for approximating the solution to combinatorial optimization problems. Since simulated annealing is a general purpose method, it can be applied to the broad range of NP-complete problems such as the traveling salesman problem, graph theory, and cell placement with a careful control of the cooling schedule.
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. One way to mitigate this bottleneck is 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 dissertation places analytically derived bounds on the cost 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"--Abstract, page iii.
Advisor(s)
McMillin, Bruce M.
Committee Member(s)
Erçal, Fikret
Gillett, Billy E.
Ho, C. Y. (Chung You), 1933-1988
Patel, J.
Department(s)
Computer Science
Degree Name
Ph. D. in Computer Science
Publisher
University of Missouri--Rolla
Publication Date
Fall 1992
Pagination
xi, 134 pages
Note about bibliography
Includes bibliographical references (pages 127-133).
Rights
© 1992 Chul-Eui Hong, All rights reserved.
Document Type
Dissertation - Restricted Access
File Type
text
Language
English
Thesis Number
T 6473
Print OCLC #
28627934
Recommended Citation
Hong, Chul-Eui, "Relaxing synchronization in distributed simulated annealing" (1992). Doctoral Dissertations. 994.
https://scholarsmine.mst.edu/doctoral_dissertations/994
Share My Dissertation If you are the author of this work and would like to grant permission to make it openly accessible to all, please click the button above.
Comments
A report which is substantially this dissertation is available here for download.