Files in this item



application/pdf8803190.pdf (4MB)Restricted to U of Illinois
(no description provided)PDF


Title:Optimization by Simulated Annealing: A Time-Complexity Analysis
Author(s):Sasaki, Galen Hajime
Doctoral Committee Chair(s):Hajek, Bruce
Department / Program:Electrical Engineering
Discipline: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.
Issue Date:1987
Description:113 p.
Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1987.
Other Identifier(s):(UMI)AAI8803190
Date Available in IDEALS:2014-12-15
Date Deposited:1987

This item appears in the following Collection(s)

Item Statistics