Graduate Thesis Or Dissertation

 

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

Downloadable Content

Download 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.
Resource Type
Date Available
Date Copyright
Date Issued
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Advisor
Committee Member
Academic Affiliation
Non-Academic Affiliation
Keyword
Subject
Rights Statement
Peer Reviewed
Language
Replaces
Additional Information
  • description.provenance : Made available in DSpace on 2014-07-22T19:28:17Z (GMT). No. of bitstreams: 1 CrewsMatthewC2014.pdf: 3320684 bytes, checksum: 2c2bbe62fc85e537401218f8d5d47069 (MD5) Previous issue date: 2014-06-10
  • description.provenance : Rejected by Julie Kurtz(julie.kurtz@oregonstate.edu), reason: Rejecting per students request. Upload final copy after final defense and if there are any revisions request by major professor or committee members. Best, Julie on 2014-06-10T15:48:51Z (GMT)
  • description.provenance : Submitted by Matthew Crews (crewsm@onid.orst.edu) on 2014-06-10T16:36:33Z No. of bitstreams: 1 M Crews Thesis Defense.pptx: 991750 bytes, checksum: fff5721c22561c6e973788635fd401ca (MD5)
  • description.provenance : Submitted by Matthew Crews (crewsm@onid.orst.edu) on 2014-05-27T21:54:05Z No. of bitstreams: 1 CrewsMatthewC2014.pdf: 704465 bytes, checksum: 33bbaffcdccb69c3bc3aad1d0425bf5a (MD5)
  • description.provenance : Approved for entry into archive by Julie Kurtz(julie.kurtz@oregonstate.edu) on 2014-06-17T21:14:29Z (GMT) No. of bitstreams: 1 CrewsMatthewC2014.pdf: 3320684 bytes, checksum: 2c2bbe62fc85e537401218f8d5d47069 (MD5)
  • description.provenance : Approved for entry into archive by Laura Wilson(laura.wilson@oregonstate.edu) on 2014-07-22T19:28:17Z (GMT) No. of bitstreams: 1 CrewsMatthewC2014.pdf: 3320684 bytes, checksum: 2c2bbe62fc85e537401218f8d5d47069 (MD5)
  • description.provenance : Rejected by Julie Kurtz(julie.kurtz@oregonstate.edu), reason: Rejecting per students request. ~Julie on 2014-06-10T22:19:34Z (GMT)
  • description.provenance : Submitted by Matthew Crews (crewsm@onid.orst.edu) on 2014-06-12T23:52:14Z No. of bitstreams: 1 CrewsMatthewC2014.pdf: 3320684 bytes, checksum: 2c2bbe62fc85e537401218f8d5d47069 (MD5)

Relationships

Parents:

This work has no parents.

In Collection:

Items