VTechWorks staff will be away for the Thanksgiving holiday beginning at noon on Wednesday, November 27, through Friday, November 29. We will resume normal operations on Monday, December 2. Thank you for your patience.
 

Assessing the Finite-Time Performance of Local Search Algorithms

Simple item page
dc.contributor.authorHenderson, Darrallen
dc.contributor.committeecochairJacobson, Sheldon H.en
dc.contributor.committeecochairKoelling, C. Patricken
dc.contributor.committeememberWakefield, Ronald R.en
dc.contributor.committeememberBish, Ebru K.en
dc.contributor.committeememberSherali, Hanif D.en
dc.contributor.departmentIndustrial and Systems Engineeringen
dc.date.accessioned2014-03-14T20:09:49Zen
dc.date.adate2001-04-18en
dc.date.available2014-03-14T20:09:49Zen
dc.date.issued2001-05-13en
dc.date.rdate2002-04-18en
dc.date.sdate2001-04-17en
dc.description.abstractIdentifying a globally optimal solution for an intractable discrete optimization problem is often cost prohibitive. Therefore, solutions that are within a predetermined threshold are often acceptable in practice. This dissertation introduces the concept of B-acceptable solutions where B is a predetermined threshold for the objective function value. It is difficult to assess a priori the effectiveness of local search algorithms, which makes the process of choosing parameters to improve their performance difficult. This dissertation introduces the B-acceptable solution probability in terms of B-acceptable solutions as a finite-time performance measure for local search algorithms. The B-acceptable solution probability reflects how effectively an algorithm has performed to date and how effectively an algorithm can be expected to perform in the future. The B-acceptable solution probability is also used to obtain necessary asymptotic convergence (with probability one) conditions. Upper and lower bounds for the B-acceptable solution probability are presented. These expressions assume particularly simple forms when applied to specific local search strategies such as Monte Carlo search and threshold accepting. Moreover, these expressions provide guidelines on how to manage the execution of local search algorithm runs. Computational experiments are reported to estimate the probability of reaching a B-acceptable solution for a fixed number of iterations. Logistic regression is applied as a tool to estimate the probability of reaching a B-acceptable solution for values of B close to the objective function value of a globally optimal solution as well as to estimate this objective function value. Computational experiments are reported with logistic regression for pure local search, simulated annealing and threshold accepting applied to instances of the TSP with known optimal solutions.en
dc.description.degreePh. D.en
dc.identifier.otheretd-04172001-135808en
dc.identifier.sourceurlhttp://scholar.lib.vt.edu/theses/available/etd-04172001-135808/en
dc.identifier.urihttp://hdl.handle.net/10919/26926en
dc.publisherVirginia Techen
dc.relation.haspartHenderson_D_Dissertation.pdfen
dc.rightsIn Copyrighten
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subjecthill climbing algorithmsen
dc.subjectheuristicsen
dc.subjectfinite-time performanceen
dc.subjectdiscrete optimizationen
dc.subjectcombinatorial optimizationen
dc.subjectsimulated annealingen
dc.subjectconvergenceen
dc.subjectlocal searchen
dc.titleAssessing the Finite-Time Performance of Local Search Algorithmsen
dc.typeDissertationen
thesis.degree.disciplineIndustrial and Systems Engineeringen
thesis.degree.grantorVirginia Polytechnic Institute and State Universityen
thesis.degree.leveldoctoralen
thesis.degree.namePh. D.en

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Henderson_D_Dissertation.pdf
Size:
648.96 KB
Format:
Adobe Portable Document Format
Download

Collections

Doctoral Dissertations