Optimization by Simulated Annealing: A Time-Complexity Analysis
Sasaki, Galen Hajime
This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.
Permalink
https://hdl.handle.net/2142/69378
Description
Title
Optimization by Simulated Annealing: A Time-Complexity Analysis
Author(s)
Sasaki, Galen Hajime
Issue Date
1987
Doctoral Committee Chair(s)
Hajek, Bruce
Department of Study
Electrical Engineering
Discipline
Electrical Engineering
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(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.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
