Files in this item
|(no description provided)|
|Title:||An eigenvalue-based approach to the finite time behavior of simulated annealing|
|Author(s):||Desai, Madhav P.|
|Doctoral Committee Chair(s):||Rao, Vasant B.|
|Department / Program:||Electrical and Computer Engineering|
|Degree Granting Institution:||University of Illinois at Urbana-Champaign|
|Subject(s):||Engineering, Electronics and Electrical|
|Abstract:||In this thesis, we present a framework under which the finite time behavior of the simulated annealing for combinatorial optimization can be studied. We will use linear algebraic methods for this purpose. The simulated annealing algorithm will be modeled as a finite space, discrete time Markov chain which can then be represented by a probability transition matrix whose entries are controlled by a parameter known as the temperature.
We first consider a simpler version of the algorithm in which the temperature is held to a constant value. The algorithm can then be modeled by a time homogeneous Markov chain which converges to an equilibrium distribution. In this case, the speed of convergence can be ascertained if certain eigenvalues of the transition matrix are known, and the equilibrium distribution depends on the distribution of costs. We explore different approaches to obtain bounds on these eigenvalues and apply these bounds to study the convergence of the fixed-temperature algorithm to solve the integer composition problem, which is NP-complete. We present a detailed study of the cost distribution for this problem. Consequently, we are able to study the computational complexity of the fixed-temperature algorithm to solve the integer composition problem.
We also consider the case of simulated annealing in which the temperature is reduced according to a cooling schedule. By using an absorbing chain model of the algorithm, we are able to study its finite time behavior in terms of an eigenvalue of the absorbing chain's transition matrix. We provide asymptotic bounds for this eigenvalue from which we obtain an asymptotic sufficiency result for the annealing algorithm to find an optimal state. We also obtain structural bounds for this eigenvalue, from which the finite time behavior of the algorithm may be studied.
|Rights Information:||Copyright 1992 Desai, Madhav Pandurang|
|Date Available in IDEALS:||2011-05-07|
|Identifier in Online Catalog:||AAI9215802|
This item appears in the following Collection(s)
Dissertations and Theses - Electrical and Computer Engineering
Dissertations and Theses in Electrical and Computer Engineering
Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois