Graduate Thesis Or Dissertation
 

A comparison of single runs versus multistart for simulated annealing and threshold accepting

Público Deposited

Contenido Descargable

Descargar PDF
https://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/1v53k044p

Descriptions

Attribute NameValues
Creator
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.
License
Resource Type
Fecha Disponible
Fecha de Emisión
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Advisor
Committee Member
Academic Affiliation
Non-Academic Affiliation
Subject
Declaración de derechos
Publisher
Peer Reviewed
Language
Replaces

Relaciones

Parents:

This work has no parents.

En Collection:

Elementos

Miniatura Título Fecha de subida Visibilidad Acciones
file details CrewsMatthewC2014.pdf 2017-08-04 Público Descargar