Record Details
A comparison of single runs versus multistart for simulated annealing and threshold accepting
ScholarsArchive at Oregon State University
| Field | Value |
|---|---|
| Title | A comparison of single runs versus multistart for simulated annealing and threshold accepting |
| Names |
Crews, Matthew
(creator) Kim, David (advisor) |
| Date Issued | 2014-06-10 (iso8601) |
| Note | Graduation date: 2014 |
| Abstract | Simulated Annealing and Threshold Accepting are two stochastic search algorithms that have been successfully used on a variety of complex and difficult problem sets. Due to their stochastic nature they are not guaranteed to produce the same result for each run. This means that these techniques actually produce a distribution of solutions which are based on the input parameters and the problem instance. Most research in the area of Simulated Annealing and Threshold Accepting focuses on the single run performance of these algorithms and does not consider sampling multiple runs and taking the best result, known as multisampling. Previous work that has looked at multisampling did not explore a variety of settings or problem instances which has left gaps in the understanding of the multisampling performance of Simulated Annealing and Threshold Accepting. This work examines the use of single runs and multisampling on four instances of the Traveling Salesman Problem. A systematic exploration is done of the variables which affect the performance of these two heuristics. A pairwise analysis is then performed to identify if there are cases where it is advantageous to employ a multistart method instead of a single run. The conclusion is that in a majority of cases a single run outperforms the multistart method but there are cases in which the multistart method outperforms single runs. |
| Genre | Thesis/Dissertation |
| Topic | Simulated Annealing |
| Identifier | http://hdl.handle.net/1957/50660 |
