DSpace Repository

Acceleration techniques for simulated annealing

Show simple item record

dc.contributor.author Telfar, Grant John
dc.date.accessioned 2011-07-13T21:39:44Z
dc.date.accessioned 2022-10-27T01:34:12Z
dc.date.available 2011-07-13T21:39:44Z
dc.date.available 2022-10-27T01:34:12Z
dc.date.copyright 1996
dc.date.issued 1996
dc.identifier.uri https://ir.wgtn.ac.nz/handle/123456789/25448
dc.description.abstract Combinatorial optimisation problems involve choosing the best solution from a finite set of mutually exclusive outcomes and are often deceptively difficult to solve. Simulated annealing is an heuristic method for finding 'good' solutions to optimisation problems. The technique is based on an analogy with a method in statistical mechanics designed to simulate the physical process of annealing. Decisions made when implementing the simulated annealing algorithm can affect both the algorithm efficiency (speed) and effectiveness. Since the time requirements of the simulated annealing algorithm can often be unacceptable, it is worth investigating various modifications to the basic simulated annealing algorithm in order to accelerate (i.e. 'speed up') its convergence to a good quality solution. Several techniques are investigated to accelerate the simulated annealing paradigm. These can be partitioned into two categories: those that are simple to implement and those that are more difficult to implement. Simple techniques include the selection of an appropriate annealing schedule, its subsequent parameter fine-tuning, and careful implementation of all problem specific coding requirements such as that represented by the incremental cost update procedure. Other techniques include the investigation of departures from 'pure' simulated annealing. Among these are: recording the best solution encountered in an annealing run, approximate exponentiation, approximate random number generation, and the implementation of a local search trigger. Techniques that are more arduous to implement include parallel simulated annealing, nested simulated annealing, and two stage simulated annealing. Most of these acceleration techniques are not mutually exclusive and several can often be used in combination to produce time savings of a magnitude greater than those available through the use of individual acceleration techniques. Dramatic time savings are generally unlikely, and although the simulated annealing algorithm can be made to perform more efficiently with a little care, it still remains slow when compared to tailored algorithms. Nevertheless, it possesses the ability to regularly produce very good solutions for some difficult combinatorial optimisation problems. en_NZ
dc.format pdf en_NZ
dc.language en_NZ
dc.language.iso en_NZ
dc.publisher Te Herenga Waka—Victoria University of Wellington en_NZ
dc.subject Combinatorial optimization en_NZ
dc.subject Combinatorial optimisation en_NZ
dc.subject Simulated annealing en_NZ
dc.title Acceleration techniques for simulated annealing en_NZ
dc.type Text en_NZ
vuwschema.type.vuw Awarded Research Masters Thesis en_NZ
thesis.degree.grantor Te Herenga Waka—Victoria University of Wellington en_NZ
thesis.degree.level Masters en_NZ


Files in this item

This item appears in the following Collection(s)

Show simple item record

Search DSpace


Browse

My Account