Generalized hill climbing algorithms for discrete optimization problems

Simple item page
dc.contributor.authorJohnson, Alan W.en
dc.contributor.committeechairJacobson, Sheldon H.en
dc.contributor.committeememberAllison, Donald C. S.en
dc.contributor.committeememberBlanchard, Benjamin S. Jr.en
dc.contributor.committeememberSarin, Subhash C.en
dc.contributor.committeememberSherali, Hanif D.en
dc.contributor.departmentIndustrial and Systems Engineeringen
dc.date.accessioned2014-03-14T21:12:24Zen
dc.date.adate2008-06-06en
dc.date.available2014-03-14T21:12:24Zen
dc.date.issued1996-10-01en
dc.date.rdate2008-06-06en
dc.date.sdate2008-06-06en
dc.description.abstractGeneralized hill climbing (GHC) algorithms are introduced, as a tool to address difficult discrete optimization problems. Particular formulations of GHC algorithms include simulated annealing (SA), local search, and threshold accepting (T A), among. others. A proof of convergence of GHC algorithms is presented, that relaxes the sufficient conditions for the most general proof of convergence for stochastic search algorithms in the literature (Anily and Federgruen [1987]). Proofs of convergence for SA are based on the concept that deteriorating (hill climbing) transitions between neighboring solutions are accepted by comparing a deterministic function of both the solution change cost and a temperature parameter to a uniform (0,1) random variable. GHC algorithms represent a more general model, whereby deteriorating moves are accepted according to a general random variable. Computational results are reported that illustrate relationships that exist between the GHC algorithm's finite-time performance on three problems, and the general random variable formulations used. The dissertation concludes with suggestions for further research.en
dc.description.degreePh. D.en
dc.format.extentix, 128 leavesen
dc.format.mediumBTDen
dc.format.mimetypeapplication/pdfen
dc.identifier.otheretd-06062008-152638en
dc.identifier.sourceurlhttp://scholar.lib.vt.edu/theses/available/etd-06062008-152638/en
dc.identifier.urihttp://hdl.handle.net/10919/38064en
dc.language.isoenen
dc.publisherVirginia Techen
dc.relation.haspartLD5655.V856_1996.J646.pdfen
dc.relation.isformatofOCLC# 36210610en
dc.rightsIn Copyrighten
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subjectsimulated annealingen
dc.subjecthill climbing algorithmsen
dc.subjectdiscrete optimizationen
dc.subjectcombinatorial optimizationen
dc.subjectconvergenceen
dc.subjectheuristicsen
dc.subject.lccLD5655.V856 1996.J646en
dc.titleGeneralized hill climbing algorithms for discrete optimization problemsen
dc.typeDissertationen
dc.type.dcmitypeTexten
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:
LD5655.V856_1996.J646.pdf
Size:
5.36 MB
Format:
Adobe Portable Document Format
Description:
Download

Collections

Doctoral Dissertations