Doctoral Dissertations

Chul-Eui Hong

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

Comments

A report which is substantially this dissertation is available here for download.

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

Link to Catalog Record

Electronic access to the full-text of this document is restricted to Missouri S&T users. Otherwise, request this publication directly from Missouri S&T Library or contact your local library.

http://merlin.lib.umsystem.edu/record=b2635042~S5

Download
Off-campus S&T users

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.

Share

 
COinS