Search ETDs:
Assessing the performance of the simulated annealing algorithm using information theory
Fleischer, Mark Alan

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.

Recommended Citations

Hide/Show APA Citation

Fleischer, M. (1994). Assessing the performance of the simulated annealing algorithm using information theory. (Electronic Thesis or Dissertation). Retrieved from https://etd.ohiolink.edu/

Hide/Show MLA Citation

Fleischer, Mark. "Assessing the performance of the simulated annealing algorithm using information theory." Electronic Thesis or Dissertation. Case Western Reserve University, 1994. OhioLINK Electronic Theses and Dissertations Center. 28 Aug 2015.

Hide/Show Chicago Citation

Fleischer, Mark "Assessing the performance of the simulated annealing algorithm using information theory." Electronic Thesis or Dissertation. Case Western Reserve University, 1994. https://etd.ohiolink.edu/

Files

case1057677595.pdf (4.57 MB) View|Download