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 Ergodicity Local Search Markov Chains Simulated Annealing Generalized Hill Climbing Algorithms Manufacturing Applications
Date of Defense	2000-07-31
Availability	unrestricted
Abstract 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.
Files	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.