Files in this item
|(no description provided)|
|Title:||Optimization by Simulated Annealing: A Time-Complexity Analysis|
|Author(s):||Sasaki, Galen Hajime|
|Doctoral Committee Chair(s):||Hajek, Bruce|
|Department / Program:||Electrical Engineering|
|Degree Granting Institution:||University of Illinois at Urbana-Champaign|
|Subject(s):||Engineering, Electronics and Electrical|
|Abstract:||In this thesis, results of a study of the heuristic random search optimization method called simulated annealing are given. Most of the results are concerned with the average amount of time simulated annealing takes to find an acceptable solution.
We analyzed the average time complexity of simulated annealing for the matching problem. Although the matching problem has worst-case polynomial time complexity, we show that there is a sequence of graphs where the average time complexity of a "natural" version of simulated annealing is at least exponential. In contrast, we show that the "natural" version of simulated annealing has a worst-case polynomial average time complexity if it is only required to find "near" maximum matchings. An exponential lower bound on the minimum average time complexity over a wide class of simulated annealing algorithms when our attention is restricted to constant temperature schedules is also given.
The typical case for simulated annealing for the matching problem is also analyzed. Since we were not able to discover a method to exactly analyze the average time complexity of simulated annealing for the matching problem for "typical" graphs, we used approximations to estimate the average time complexity and then checked the accuracy of the approximation with data from computer simulations. Our results indicate that if we only consider graphs that have at least as many edges as they have nodes then the average time complexity of simulated annealing for a typical graph with n nodes of O(n$\sp4$).
A technique for producing easy-to-analyze annealing processes, called the template method, is given. It is our hope that this method will produce interesting examples of simulated annealing that will help us to understand the heuristic. We provide two examples of using the template method to analyze the finite-time behavior of simulated annealing as a function of the temperature schedule. A generalization of simulated annealing, which we refer to as the threshold random search algorithm, is presented. We also give conditions under which no monotone decreasing temperature schedule is optimal.
Finally, we discuss the use of quadratic penalty methods in conjunction with simulated annealing to solve problems with equality constraints. An experimental evaluation is made between adaptive and static quadratic penalty methods, and it is shown that adaptive quadratic penalty methods can provide low-valued solutions over a wider range of penalty parameter values than static quadratic penalty methods.
Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1987.
|Date Available in IDEALS:||2014-12-15|
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