Simultaneous Generalized Hill Climbing Algorithms for Addressing Sets of Discrete Optimization Problems

Simple item page
dc.contributor.authorVaughan, Diane Elizabethen
dc.contributor.committeecochairKoelling, C. Patricken
dc.contributor.committeecochairJacobson, Sheldon H.en
dc.contributor.committeememberRogers, Robert C.en
dc.contributor.committeememberBish, Ebru K.en
dc.contributor.committeememberNachlas, Joel A.en
dc.contributor.departmentIndustrial and Systems Engineeringen
dc.date.accessioned2014-03-14T20:14:43Zen
dc.date.adate2000-08-22en
dc.date.available2014-03-14T20:14:43Zen
dc.date.issued2000-07-31en
dc.date.rdate2001-08-22en
dc.date.sdate2000-08-04en
dc.description.abstractGeneralized hill climbing (GHC) algorithms provide a framework for using local search algorithms to address intractable discrete optimization problems. Many well-known local search algorithms can be formulated as GHC algorithms, including simulated annealing, threshold accepting, Monte Carlo search, and pure local search (among others). This dissertation develops a mathematical framework for simultaneously addressing a set of related discrete optimization problems using GHC algorithms. The resulting algorithms, termed simultaneous generalized hill climbing (SGHC) algorithms, can be applied to a wide variety of sets of related discrete optimization problems. The SGHC algorithm probabilistically moves between these discrete optimization problems according to a problem generation probability function. This dissertation establishes that the problem generation probability function is a stochastic process that satisfies the Markov property. Therefore, given a SGHC algorithm, movement between these discrete optimization problems can be modeled as a Markov chain. Sufficient conditions that guarantee that this Markov chain has a uniform stationary probability distribution are presented. Moreover, sufficient conditions are obtained that guarantee that a SGHC algorithm will visit the globally optimal solution over all the problems in a set of related discrete optimization problems. Computational results are presented with SGHC algorithms for a set of traveling salesman problems. For comparison purposes, GHC algorithms are also applied individually to each traveling salesman problem. These computational results suggest that optimal/near optimal solutions can often be reached more quickly using a SGHC algorithm.en
dc.description.degreePh. D.en
dc.identifier.otheretd-08042000-14590003en
dc.identifier.sourceurlhttp://scholar.lib.vt.edu/theses/available/etd-08042000-14590003/en
dc.identifier.urihttp://hdl.handle.net/10919/28514en
dc.publisherVirginia Techen
dc.relation.haspartvita.pdfen
dc.relation.haspartdianeetd.pdfen
dc.rightsIn Copyrighten
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subjectTraveling Salesman Problemen
dc.subjectErgodicityen
dc.subjectLocal Searchen
dc.subjectMarkov Chainsen
dc.subjectSimulated Annealingen
dc.subjectGeneralized Hill Climbing Algorithmsen
dc.subjectManufacturing Applicationsen
dc.titleSimultaneous Generalized Hill Climbing Algorithms for Addressing Sets of Discrete Optimization Problemsen
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 - 2 of 2
Thumbnail Image
Name:
dianeetd.pdf
Size:
867.09 KB
Format:
Adobe Portable Document Format
Download
Thumbnail Image
Name:
vita.pdf
Size:
3.23 KB
Format:
Adobe Portable Document Format
Download

Collections

Doctoral Dissertations