Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


case1057677595.pdf (4.57 MB)

ETD Abstract Container

Abstract Header

Assessing the performance of the simulated annealing algorithm using information theory

Fleischer, Mark Alan
http://rave.ohiolink.edu/etdc/view?acc_num=case1057677595

Abstract Details

1994, Doctor of Philosophy, Case Western Reserve University, Operations Research.
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.
Sheldon Jacobson (Advisor)
161 p.
simulated; annealing; algorithm; information theory

Recommended Citations

Citations

  • Fleischer, M. A. (1994). Assessing the performance of the simulated annealing algorithm using information theory [Doctoral dissertation, Case Western Reserve University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=case1057677595

    APA Style (7th edition)

  • Fleischer, Mark. Assessing the performance of the simulated annealing algorithm using information theory. 1994. Case Western Reserve University, Doctoral dissertation. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=case1057677595.

    MLA Style (8th edition)

  • Fleischer, Mark. "Assessing the performance of the simulated annealing algorithm using information theory." Doctoral dissertation, Case Western Reserve University, 1994. http://rave.ohiolink.edu/etdc/view?acc_num=case1057677595

    Chicago Manual of Style (17th edition)

case1057677595
1,386
© 1994, all rights reserved.
This open access ETD is published by Case Western Reserve University School of Graduate Studies and OhioLINK.