Type of Document Dissertation Author Vaughan, Diane Elizabeth URN etd-08042000-14590003 Title Simultaneous Generalized Hill Climbing Algorithms for Addressing Sets of Discrete Optimization Problems Degree PhD Department Industrial and Systems Engineering Advisory Committee
Advisor Name Title Jacobson, Sheldon H. Committee Co-Chair Koelling, Charles Patrick Committee Co-Chair Bish, Ebru K. Committee Member Nachlas, Joel A. Committee Member Rogers, Robert C. Committee Member Keywords
- Traveling Salesman Problem
- Local Search
- Markov Chains
- Simulated Annealing
- Generalized Hill Climbing Algorithms
- Manufacturing Applications
Date of Defense 2000-07-31 Availability unrestricted 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.
Filename Size Approximate Download Time (Hours:Minutes:Seconds)
28.8 Modem 56K Modem ISDN (64 Kb) ISDN (128 Kb) Higher-speed Access dianeetd.pdf 887.90 Kb 00:04:06 00:02:06 00:01:50 00:00:55 00:00:04 vita.pdf 3.30 Kb < 00:00:01 < 00:00:01 < 00:00:01 < 00:00:01 < 00:00:01
If you have questions or technical problems, please Contact DLA.