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

Generalized 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.

Name thesis:degree_name

Ph. D.

Level thesis:degree_level

doctoral

Discipline thesis:degree_discipline

Industrial and Systems Engineering

Department dc:contributor.department

Industrial and Systems Engineering

Grantor dc:publisher

Virginia Tech

Year dc:date.issued

2000

Author dc:creator

• Vaughan, Diane Elizabeth

Chairs dc:contributor.committeechair

• Koelling, C. Patrick
• Jacobson, Sheldon H.

Committee members dc:contributor.committeemember

• Rogers, Robert C.
• Bish, Ebru K.
• Nachlas, Joel A.

• Traveling Salesman Problem
• Ergodicity
• Local Search
• Markov Chains
• Simulated Annealing
• Generalized Hill Climbing Algorithms
• Manufacturing Applications

Statement dc:rights

• In Copyright

Licence dc:rights.uri

• http://rightsstatements.org/vocab/InC/1.0/

Dc Identifier Other

etd-08042000-14590003

OAI identifier oai:identifier

oai:vtechworks.lib.vt.edu:10919/28514