Display Full Text | Download Full Text
4.56 MB PDF file

Degree

Doctor of Philosophy, Case Western Reserve University, Operations Research, 1994.

Abstract

The simulated annealing (SA) algorithm has traditionally been viewed as a simulation of a thermodynamic system that can be used to solve combinatorial optimization problems. In this dissertation, SA is studied from the perspective of information theory and viewed as an inhomogeneous Markov information source. The concepts of the entropy of ergodic information sources and the Asymptotic Equipartition Property (AEP) from information theory are then utilized to explain the finite-time behavior of SA. This dissertation extends the AEP to the case of strongly ergodic inhomogeneous Markov chains and then specializes it to incorporate the concept of convergence in distribution. The theory is then applied to Markov chains of the type encountered in SA. This makes it possible to define typical sequences of states in an annealing experiment and the relationship between them and the entropy measure of an SA experiment. The theory developed shows that the finite-time behavior of SA is directly related to this entropy measure. This entropy effect can therefore be used as a guide in developing methods to improve the finite-time performance of SA. Four methodologies are employed to illustrate this entropy effect which involve modification of the neighborhood structure and polynomial transformations between NP-hard problems.

Keywords

simulated; annealing; algorithm; information theory

Advisor

Sheldon H. Jacobson

Pages

161p.

Document number: case1057677595
Permalink: http://rave.ohiolink.edu/etdc/view?acc_num=case1057677595

This ETD has been downloaded 740 times (through March 2013)