{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/69378"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/69378","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Optimization by Simulated Annealing: A Time-Complexity Analysis","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.","abstract_html":"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.","abstract_has_math":false,"creators":["Sasaki, Galen Hajime"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Electrical Engineering","degree_department":null,"school":null,"contributors":["Hajek, Bruce"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2014,"date_issued":"2014-12-15T19:05:27Z","date_published":"2014-12-15T19:05:27Z","updated_at":"2026-07-22T22:26:00Z","subjects":["Engineering, Electronics and Electrical"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["(UMI)AAI8803190"],"render_values":[{"text":"(UMI)AAI8803190","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/69378","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Hajek, Bruce"]},{"key":"dc:creator","label":"Author","values":["Sasaki, Galen Hajime"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2014-12-15T19:05:27Z","10000-01-01","1987"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical Engineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Engineering, Electronics and Electrical"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/69378","(UMI)AAI8803190"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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.","Made available in DSpace on 2014-12-15T19:05:27Z (GMT). No. of bitstreams: 1 8803190.pdf: 3613020 bytes, checksum: 8be2438a750df27ff7a1b4cdd561ff53 (MD5) Previous issue date: 1987","Embargo set by: Seth Robbins for item 69544 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","U of I Only","113 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1987."]},{"key":"dc:title","label":"Title","values":["Optimization by Simulated Annealing: A Time-Complexity Analysis"]}]}],"canonical_facts":{"dc:contributor":["Hajek, Bruce"],"dc:creator":["Sasaki, Galen Hajime"],"dc:date":["2014-12-15T19:05:27Z","10000-01-01","1987"],"dc:description":["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.","Made available in DSpace on 2014-12-15T19:05:27Z (GMT). No. of bitstreams: 1 8803190.pdf: 3613020 bytes, checksum: 8be2438a750df27ff7a1b4cdd561ff53 (MD5) Previous issue date: 1987","Embargo set by: Seth Robbins for item 69544 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","U of I Only","113 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1987."],"dc:identifier":["http://hdl.handle.net/2142/69378","(UMI)AAI8803190"],"dc:subject":["Engineering, Electronics and Electrical"],"dc:title":["Optimization by Simulated Annealing: A Time-Complexity Analysis"],"dc:type":["text"],"thesis:degree_discipline":["Electrical Engineering"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:26:00Z"}